Log-Structured Storage là một mô hình cơ sở dữ liệu dựa trên nguyên tắc "chỉ ghi thêm" (Append-only Log). Dữ liệu được ghi dưới dạng nhật ký và chỉ được thêm vào cuối tệp, không ghi đè lên các bản ghi cũ. Dù mới trở nên phổ biến gần đây, nhờ sự đơn giản và hiệu quả, mô hình này xứng đáng là chương đầu tiên trong mọi giáo trình về cơ sở dữ liệu.
Cách thức hoạt động#
Để minh họa, hãy xem xét một cơ sở dữ liệu dạng Key-Value đơn giản, được xây dựng chỉ với hai hàm bash:
#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
Cách sử dụng:
Để lưu giá trị, ta gọi
db_set key value.Để truy xuất giá trị mới nhất của một key, ta dùng
db_get key.
Ví dụ:
$ 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 một tệp văn bản có định dạng gần giống CSV (bỏ qua các yếu tố phức tạp như ký tự escape). Mỗi dòng chứa một cặp key,value được phân tách bằng dấu phẩy.
Mỗi lần gọi db_set, hệ thống sẽ thêm một dòng mới vào cuối tệp. Do đó, nếu bạn cập nhật giá trị của một key, phiên bản cũ vẫn được giữ nguyên. Khi lấy dữ liệu, db_get sẽ tìm bản ghi cuối cùng (sử dụng tail -n 1) tương ứng với key đó.
Ví dụ:
$ 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"]}
Hiệu suất của Log Structured Storage#
Mặc dù đơn giản, hàm db_set của chúng ta lại có hiệu suất ghi rất tốt, bởi việc ghi thêm vào cuối tệp là một thao tác rất hiệu quả. Nhiều cơ sở dữ liệu thực tế cũng sử dụng log – một dạng tệp chỉ cho phép ghi thêm – làm nền tảng.
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.
Tuy nhiên, hàm db_get lại có hiệu suất rất kém khi số lượng bản ghi lớn. Mỗi lần tìm kiếm một key, nó phải quét toàn bộ tệp từ đầu đến cuối. Độ phức tạp cho thao tác tìm kiếm là O(n), một mức chi phí không thể chấp nhận được trong thực tế.
Giải pháp: Sử dụng Index#
Để tối ưu hóa việc tìm kiếm, chúng ta cần một cấu trúc dữ liệu phụ trợ: index. Index đóng vai trò như một "bản đồ" giúp định vị nhanh dữ liệu mà không cần quét toàn bộ tệp.
Tuy nhiên, mọi sự đánh đổi đều có cái giá của nó. Việc sử dụng index giúp cải thiện đáng kể tốc độ đọc, nhưng lại làm chậm thao tàn ghi, vì mỗi lần dữ liệu được thêm vào, index cũng cần được cập nhật. Do đó, một số hệ thống không tạo index mặc định mà để người dùng tự lựa chọn dựa trên nhu cầu cụ thể của ứng dụng.
Trong các phần tiếp theo, chúng ta sẽ khám phá một số loại index phổ biến được sử dụng trong kiến trúc Log Structured Storage.