Log Structured Storage là trường phái Database dựa trên Append-only Log, tức là dữ liệu được ghi lưu lại dưới dạng log, chỉ có ghi xuống cuối file chứ không thể ghi đè. Chỉ mới được phổ biến gần đây, tuy nhiên xét về sự đơn giản (mà vẫn hiệu quả) thì nó xứng đáng được nằm trong chương đầu của bất kỳ giáo án sách nào viết về Database 🙂

Để minh họa cho trường phái Log Structured Storage, ta sẽ bắt đầu với 1 Database Key-Value Store đơn giản nhất trên đời này, được tạo bởi 2 hàm bash rất ngắn sau:

#!/bin/bash
db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

Để lưu thì ta gọi hàm db_set key value và dùng hàm db_get key để lấy lại giá trị gần nhất mà mình đã insert vào key tương ứng:

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}' 

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

Dữ liệu được lưu trong 1 file text với định dạng khá giống với format csv, bỏ qua các yếu tố lặt vặt khác như escape ký tự,… Mỗi dòng gồm key và value, được cách nhau bởi dấu phẩy. Mọi lần gọi hàm db_set sẽ append thêm dòng mới vào cuối file, do đó nếu ta update giá trị của 1 bản ghi, thì phiên bản cũ của nó sẽ không bị ghi đè lên -> Khi lấy ra, cần lọc bỏ và giữ lại giá trị cuối cùng (tail -n 1).

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}' 

$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]} 
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]} 
42,{"name":"San Francisco","attractions":["Exploratorium"]}

Dù trông đơn giản, hàm db_set của chúng ta lại đạt hiệu suất khá là tốt, bởi vì việc append vào cuối file thực sự rất hiệu quả. Tương tự với cách thức của hàm db_set, rất nhiều database đang sử dụng log (1 loại file text chỉ có thể append vào cuối).

Database trong thực tế còn phải quan tâm tới rất nhiều thứ khác (quản lý bất đồng bộ, thu hồi bộ nhớ, xử lý lỗi), nhưng nguyên tắc cơ bản thì giống nhau.

Nhưng ngược lại, hàm db_get lại có hiệu suất rất là tệ nếu như mình có 1 lượng record cực lớn. Mỗi lần tìm kiếm 1 key nào đó, db_get cần phải scan toàn bộ file database từ đầu tới cuối. Chi phí của việc tìm kiếm đó là O(n)… Quá tệ!

Để tìm kiếm hiệu quả hơn, chúng ta cần 1 cấu trúc dữ liệu khác tốt hơn: index. Index là 1 cấu trúc bổ sung cho dữ liệu chính. Nhiều database hiện nay còn cho phép tạo và xóa index dễ dàng, mà không ảnh hưởng tới nội dung bên trong của database.

Sử dụng Index giúp cải thiện hiệu suất cho câu truy vấn, tuy nhiên càng nhiều Index sẽ càng làm chậm việc ghi dữ liệu (Write). Mỗi lần data được ghi vào, thì index cũng cần phải được cập nhật lại. Chính vì lý do này, một số database thường không sử dụng index ngay mặc định, mà chúng ta phải tự tạo chúng bằng tay (dựa theo nhu cầu của ứng dụng).

Ở những phần tiếp, ta sẽ điểm qua 1 số loại Index hay được dùng cho kiến trúc Log Structured Storage.

Phần 2: Database 102: Hash Indexes