Nếu từng dùng Cassandra, RocksDB, LevelDB hay HBase, bạn đã sử dụng một cấu trúc dữ liệu gọi là LSM-Tree (Log-Structured Merge Tree). Đây là xương sống của hầu hết hệ thống lưu trữ tối ưu cho tác vụ ghi. Bài viết lần lượt giải thích hành trình của một thao tác ghi, từ lúc dữ liệu vào bộ nhớ đến khi được lưu xuống đĩa.

Bước 1: Memtable, bộ nhớ tạm siêu tốc

Khi ứng dụng gửi một thao tác ghi (write), dữ liệu đầu tiên được ghi vào Write-Ahead Log (WAL) trên đĩa để đảm bảo độ bền. Sau đó, nó được chèn vào memtable, một cấu trúc dữ liệu có thứ tự nằm hoàn toàn trong RAM, thường là Red-Black Tree hoặc Skip List. Hãy hình dung memtable như một cuốn sổ tay mà bạn ghi nhanh mọi thứ theo thứ tự ABC. Vì toàn bộ nằm trong bộ nhớ, tốc độ ghi cực kỳ nhanh.

Khi memtable đầy, thường ở ngưỡng vài MB đến vài chục MB, hệ thống sẽ chuyển nó thành immutable memtable và tạo một memtable mới để tiếp tục nhận dữ liệu ghi. Memtable đóng băng, sau đó được flush xuống đĩa dưới dạng một file SSTable.

Bước 2: SSTable, tệp dữ liệu bất biến

SSTable (Sorted String Table) là một tệp chứa các cặp key - value đã được sắp xếp theo thứ tự. Quan trọng hơn, tệp này là bất biến: một khi đã ghi xong, nó không còn bị sửa nữa. Mỗi lần flush memtable, hệ thống tạo ra một SSTable mới. Theo thời gian, số lượng SSTable tăng dần. Khi đọc một key, hệ thống có thể phải dò qua nhiều tệp để tìm phiên bản mới nhất.

Để giảm chi phí đọc, mỗi SSTable thường kèm theo hai công cụ hỗ trợ. Thứ nhất là Bloom Filter, một cấu trúc xác suất cực gọn, có thể trả lời chắc chắn "key này KHÔNG có trong file" (không có false negative), nhưng đôi khi nói "có thể có" khi thực tế không có (false positive). Nhờ vậy, hệ thống bỏ qua hầu hết các file không chứa key cần tìm mà không cần mở file ra đọc. Thứ hai là fence pointer, hay index block: mỗi SSTable lưu một bảng chỉ mục nhỏ ghi lại các mốc key của từng khối dữ liệu. Khi cần tìm key, hệ thống dùng tìm kiếm nhị phân trên fence pointer để nhảy thẳng tới đúng block thay vì quét toàn bộ tệp.

Bước 3: Compaction, dọn dẹp và hợp nhất

Compaction là quá trình hệ thống gộp nhiều SSTable nhỏ thành ít SSTable lớn hơn, đồng thời loại bỏ dữ liệu cũ (key đã bị xóa hoặc ghi đè). Đây chính là phần "Merge" trong tên LSM-Tree. Có hai chiến lược compaction phổ biến nhất.

Leveled Compaction tổ chức SSTable thành nhiều tầng (level). Level 0 chứa các SSTable vừa flush từ memtable. Khi Level 0 đầy, hệ thống chọn một SSTable và merge nó với các SSTable có phạm vi key chồng lấn ở Level 1. Quá trình tương tự lặp lại từ Level 1 xuống Level 2, và cứ thế. Mỗi level có dung lượng lớn hơn level trước khoảng 10 lần. Ưu điểm lớn nhất là đọc nhanh, vì mỗi level chỉ có tối đa một SSTable chứa bất kỳ key nào, nên một thao tác đọc chỉ cần kiểm tra O(log N) file. Nhược điểm là write amplification cao, có thể lên tới 10-30 lần, nghĩa là mỗi byte dữ liệu gốc có thể bị ghi lại hàng chục lần trong quá trình compaction.

Size-Tiered Compaction đi hướng ngược lại. Thay vì chia theo level, chiến lược này gộp các SSTable có kích thước tương đương với nhau. Khi có đủ số lượng SSTable nhỏ cùng cỡ (thường 4 file), chúng được merge thành một SSTable lớn hơn. Ưu điểm là độ khuếch đại ghi thấp hơn nhiều, phù hợp với các hệ thống ghi nhiều như log, chuỗi thời gian hoặc luồng sự kiện. Nhược điểm là đọc chậm hơn vì có thể tồn tại nhiều SSTable chứa cùng phạm vi key, và tạm thời cần nhiều dung lượng đĩa hơn trong lúc compaction diễn ra.

Chọn chiến lược nào?

Không có câu trả lời đúng cho mọi trường hợp. Leveled compaction phù hợp khi ứng dụng đọc nhiều hơn ghi, ví dụ hệ thống phục vụ truy vấn người dùng theo key. Size-tiered compaction phù hợp khi ghi áp đảo, ví dụ hệ thống thu thập log hoặc dữ liệu IoT. Nhiều hệ thống hiện đại như RocksDB cho phép kết hợp cả hai: dùng size-tiered ở các level thấp để xử lý lượng ghi lớn, và leveled ở các level cao để tối ưu tốc độ đọc.

LSM-Tree không phải cấu trúc hoàn hảo, nhưng sự đánh đổi rõ ràng giữa tốc độ ghi và chi phí đọc khiến nó vẫn là lựa chọn hàng đầu cho các hệ thống cần thông lượng ghi cao.ựa chọn phổ biến trong nhiều hệ thống lưu trữ hiện đại. đọc chấp nhận được, cộng với khả năng tinh chỉnh qua chiến lược compaction, khiến nó trở thành nền tảng của hầu hết các hệ thống lưu trữ phân tán hiện đại.