Cây LSM (Log-Structured Merge-Tree)

1. Tổng quan

Định nghĩa: Cây LSM (Log-Structured Merge-Tree) là cấu trúc lưu trữ tối ưu cho ghi (write-optimized), trước tiên gom các thao tác ghi ngẫu nhiên vào một cấu trúc có sắp xếp trong bộ nhớ, sau đó ghi hàng loạt một cách tuần tự (append-only) xuống đĩa, và hợp nhất·dọn dẹp (Compaction) nhiều tệp đã sắp xếp bất biến (immutable) ở chế độ nền để khôi phục hiệu quả đọc.

Chỉ mục của cơ sở dữ liệu quan hệ truyền thống phần lớn dựa trên cây B/cây B+, cung cấp hiệu năng thời gian logarit cân bằng cho cả đọc và ghi. Tuy nhiên, cây B+ cập nhật tại chỗ (in-place update) một trang cụ thể trên đĩa mỗi khi có cập nhật, nên nếu các trang cần cập nhật nằm rải rác thì số lần ghi ngẫu nhiên (random write) xuống đĩa sẽ bùng nổ. Xét đến độ trễ tìm kiếm (seek) của HDD hay việc ghi theo trang và thu gom rác của SSD, ghi ngẫu nhiên chậm hơn ghi tuần tự hàng chục lần trở lên và còn bào mòn tuổi thọ thiết bị lưu trữ. Trong các khối lượng công việc có lượng ghi lớn liên tục đổ vào như thu thập log, chuỗi thời gian, nhắn tin, news feed mạng xã hội, chi phí ghi ngẫu nhiên này trở thành nút thắt của toàn hệ thống.

Cây LSM ra đời nhắm thẳng vào điểm này. Ý tưởng cốt lõi là "đừng cập nhật tại chỗ, hãy liên tục nối thêm giá trị mới". Thay vì ghi đè giá trị, ta thêm phiên bản mới một cách tuần tự, còn giá trị cũ sẽ được dọn dẹp sau trong quá trình hợp nhất. Như vậy việc ghi đĩa luôn là tuần tự, thông lượng được tối đa hóa và cách truy cập thân thiện với thiết bị lưu trữ. Cấu trúc do Patrick O'Neil và cộng sự đề xuất năm 1996 này sau đó trở thành storage engine cốt lõi của Bigtable của Google cùng bản triển khai mã nguồn mở Apache HBase, Cassandra và các engine key-value nhúng như LevelDB, RocksDB. Ngày nay phần lớn các hệ thống NoSQL, chuỗi thời gian, tìm kiếm quy mô lớn đều chạy trên các engine họ LSM.

Trên thực tế, sức mạnh của LSM đến từ sự bất đối xứng trong đặc tính thiết bị lưu trữ. Trên một SSD NVMe tiêu biểu, băng thông ghi tuần tự đạt vài GB mỗi giây, nhưng ghi ngẫu nhiên 4KB chỉ bằng vài phần trong số đó, và thu gom rác nội bộ còn làm dao động độ trễ đuôi (tail latency) lớn hơn. Trong khi cây B+ "gõ" ngẫu nhiên vào các trang rải rác mỗi lần cập nhật, LSM gom cùng lượng ghi đó vào bộ nhớ rồi biến thành một luồng tuần tự dung lượng lớn duy nhất. Ý tưởng "chuyển ngẫu nhiên thành tuần tự" này là điểm xuất phát của mọi lợi ích của LSM, và là lý do căn bản khiến nó vẫn giữ nguyên giá trị dù thiết bị lưu trữ tiến hóa từ HDD sang SSD, rồi sang ZNS và object storage.

Từ góc nhìn Kỹ sư chuyên nghiệp (Professional Engineer), cây LSM quan trọng vì nó không chỉ là một cấu trúc dữ liệu mà là hình mẫu điển hình của triết lý thiết kế storage engine: "hy sinh đặc tính truy cập nào để đạt được đặc tính nào". Nếu cây B+ chấp nhận khuếch đại ghi để đổi lấy hiệu quả đọc và không gian, thì cây LSM chấp nhận khuếch đại đọc và khuếch đại không gian để đổi lấy thông lượng ghi. Hiểu sự đánh đổi giữa ba loại khuếch đại này (giả thuyết RUM: Read·Update·Memory) là bản chất của việc học LSM, và phần sau sẽ trình bày điều này một cách định lượng.

• Định hướng ghi tuần tự: Chuyển mọi thao tác ghi đĩa thành append-only để loại bỏ I/O ngẫu nhiên.
• Tệp bất biến: Tệp đã sắp xếp (SSTable) một khi đã ghi thì không bị sửa, xóa và cập nhật cũng được biểu diễn bằng việc thêm bản ghi mới.
• Hợp nhất đa cấp: Compaction chạy nền dọn dẹp các bản ghi trùng lặp·đã xóa để khôi phục hiệu năng đọc và hiệu quả không gian.

2. Cấu trúc tổng thể

Cây LSM gồm cấu trúc hai tầng: tầng bộ nhớ và tầng đĩa. Các thao tác ghi mới nhất được phản ánh vào cấu trúc có sắp xếp trong bộ nhớ (MemTable), và khi đạt kích thước nhất định thì toàn bộ được flush xuống đĩa thành tệp đã sắp xếp (SSTable). Các SSTable trên đĩa được phân tầng thành nhiều cấp (Level), càng xuống cấp dưới càng chứa dữ liệu lớn và cũ hơn. Sơ đồ dưới đây thể hiện khung tổng thể của một thao tác ghi đi vào, qua bộ nhớ rồi xuống tầng đĩa.

graph TD
    W["Yêu cầu ghi (Put/Delete)"] --> WAL["WAL (Write-Ahead Log, ghi tuần tự)"]
    W --> MEM["MemTable (cấu trúc sắp xếp trong bộ nhớ: skip list/cây cân bằng)"]
    MEM -->|"Chuyển sang bất biến khi đạt ngưỡng"| IMM["Immutable MemTable"]
    IMM -->|"Flush (ghi tuần tự)"| L0["Các SSTable Level 0 (cho phép chồng lấn)"]
    L0 -->|"Compaction"| L1["SSTable Level 1 (phân chia theo khoảng khóa)"]
    L1 -->|"Compaction"| L2["Level 2 (dung lượng khoảng 10 lần)"]
    L2 -->|"Compaction"| LN["... Level N (lớn nhất·cũ nhất)"]
    R["Yêu cầu đọc (Get)"] -.->|"Tìm tuần tự từ trên xuống dưới"| MEM
    R -.-> L0
    R -.-> L1

Trong cấu trúc này, mỗi thành phần có vai trò rõ ràng. WAL (Write-Ahead Log) đảm nhận tính bền vững (Durability). MemTable nằm trong bộ nhớ khả biến nên sẽ mất khi có sự cố; bằng cách append tuần tự cùng nội dung vào WAL ngay trước khi phản ánh vào MemTable, khi khởi động lại sau sự cố có thể phát lại (replay) WAL để khôi phục mà không mất dữ liệu. WAL cũng là ghi tuần tự nên không làm tổn hại hiệu năng ghi của LSM.

MemTable là cấu trúc sắp xếp trong bộ nhớ lưu dữ liệu mới nhất theo thứ tự khóa, thường được hiện thực bằng skip list hoặc cây nhị phân cân bằng. Skip list thường được dùng vì giảm tranh chấp khóa (lock) trong khi vẫn hỗ trợ chèn·truy vấn đồng thời, và chèn/truy vấn đạt trung bình O(log n) khá tốt. Khi MemTable đạt kích thước thiết lập (ví dụ 64MB), nó được chuyển thành MemTable bất biến (Immutable) và không còn bị sửa đổi, còn các thao tác ghi mới do MemTable mới tiếp nhận. Nhờ sự tách biệt này, việc ghi không bị dừng ngay cả khi đang flush.

SSTable (Sorted String Table) là tệp đã sắp xếp bất biến lưu trên đĩa. Các cặp khóa-giá trị được lưu theo thứ tự khóa, và bên trong tệp có chỉ mục thưa (sparse index) để tìm nhanh một khóa cụ thể cùng các phân đoạn theo khối. Vì đã sắp xếp nên thuận lợi cho quét theo khoảng, vì bất biến nên không cần khóa cho đọc đồng thời, và việc cache·nhân bản·sao lưu trở nên đơn giản. Nhiều SSTable được tổ chức theo cấp, và tùy chiến lược compaction sẽ trình bày sau mà việc cho phép chồng lấn giữa các cấp và cách hợp nhất sẽ khác nhau. Các thành phần vật lý của một SSTable như sau.

• Khối dữ liệu (Data Block): Đơn vị lưu trữ thực tế chứa các cặp khóa-giá trị đã sắp xếp (thường nén theo đơn vị 4~64KB).
• Khối chỉ mục (Index Block): Chứa khóa đầu tiên và offset của từng khối dữ liệu để tìm khối đích bằng tìm kiếm nhị phân.
• Khối Bloom filter: Nhanh chóng xác định một khóa cụ thể không có trong tệp này để chặn truy cập đĩa không cần thiết.
• Meta/Footer: Siêu dữ liệu cần để diễn giải tệp như phiên bản tệp, thống kê, vị trí chỉ mục.

Việc định dạng tệp này bất biến mang lại lợi thế vận hành lớn. Tệp đã ghi không thay đổi nên không cần vô hiệu hóa page cache·block cache, việc nhân bản từ xa·snapshot·kiểm tra checksum trở nên đơn giản theo đơn vị tệp, và có thể đưa nguyên lên các thiết bị thân thiện với dữ liệu bất biến như object storage (S3, v.v.), nên cũng rất phù hợp với kiến trúc tách biệt lưu trữ-tính toán.

3. Hoạt động cốt lõi: Đường ghi·đọc·xóa

A. Đường ghi (Write Path)

Việc ghi trong LSM đơn giản và nhanh đến bất ngờ, vì hoàn toàn không cần tìm vị trí trên đĩa để ghi đè giá trị. Khi có yêu cầu ghi, ① append tuần tự vào WAL để bảo đảm bền vững, ② chèn khóa-giá trị vào MemTable. Cả hai thao tác đều không có tìm kiếm ngẫu nhiên trên đĩa nên độ trễ ghi rất ngắn và thông lượng cao. Ngay cả cập nhật (update) cũng không tìm và sửa giá trị cũ mà chỉ thêm phiên bản mới, còn giá trị nào là mới nhất được xác định bằng số thứ tự (sequence number) hoặc timestamp.

Khi MemTable đầy, nó được chuyển sang bất biến và luồng nền ghi tuần tự thành một SSTable rồi hủy đoạn WAL tương ứng. Việc flush này ghi tuần tự toàn bộ dữ liệu đã được sắp xếp sẵn trong bộ nhớ nên tận dụng tối đa băng thông đĩa. Ví dụ, trong bộ thu thập chuỗi thời gian nhận hàng trăm nghìn lượt ghi mỗi giây, chỉ mục cây B+ chậm đi nhanh chóng do tách trang và cập nhật ngẫu nhiên, còn LSM hấp thụ chúng bằng cách tích lũy trong bộ nhớ rồi flush tuần tự dung lượng lớn, duy trì thông lượng ổn định.

B. Đường đọc (Read Path)

Việc đọc phải trả giá cho sự đơn giản của việc ghi. Giá trị mới nhất của một khóa có thể nằm ở MemTable hoặc ở đâu đó trong nhiều SSTable, nên phải tìm lần lượt từ tầng mới nhất đến tầng cũ nhất. Tức là đi xuống theo thứ tự MemTable → Immutable MemTable → Level 0 → Level 1 → …, và trả về giá trị ngay khi gặp khóa cần tìm lần đầu tiên (phiên bản mới nhất). Trong trường hợp xấu nhất phải mở nhiều tệp, hiện tượng này được gọi là khuếch đại đọc (read amplification).

Để giảm chi phí này, hai cấu trúc phụ trợ được huy động như điều bắt buộc. Thứ nhất là Bloom filter, với mỗi SSTable, nó đánh giá xác suất "khóa này có thể có ở đây không" và bỏ qua những tệp chắc chắn không có mà không cần truy cập đĩa. Thông thường, dùng khoảng 10 bit cho mỗi khóa có thể hạ tỷ lệ dương tính giả xuống khoảng 1%, giảm mạnh I/O đĩa khi truy vấn khóa không tồn tại (ví dụ xác nhận cache miss). Thứ hai là chỉ mục thưa và block cache của mỗi SSTable, giúp tìm nhanh khối đích trong tệp đã qua được filter và giữ các khối được đọc thường xuyên trong bộ nhớ.

C. Xóa và cập nhật: Tombstone

Trong cấu trúc tệp bất biến, không thể xóa vật lý dữ liệu ngay lập tức. Thay vào đó, việc xóa được thực hiện bằng cách thêm một bản ghi đánh dấu xóa gọi là tombstone. Khi đọc, nếu bản ghi mới nhất của một khóa là tombstone thì khóa đó được coi là đã bị xóa, còn việc loại bỏ vật lý thực tế xảy ra về sau khi compaction hủy cùng lúc mọi phiên bản trước của khóa đó cùng tombstone. Do đặc tính xóa trễ này, ngay sau khi xóa hàng loạt dữ liệu lại tăng lên, và khi tombstone tích tụ, quét theo khoảng phải duyệt qua cả các đoạn đã xóa khiến truy vấn chậm đi. Các vấn đề "dữ liệu zombie" hay bùng nổ tombstone thường gặp khi vận hành Cassandra bắt nguồn từ đây.

Đặc biệt, trong môi trường phân tán, xóa tombstone vội vàng là nguy hiểm. Nếu tombstone biến mất trong khi một nút đã phản ánh việc xóa còn nút khác bỏ lỡ do sự cố, thì trong quá trình đồng bộ bản sao, giá trị đã "chết" sẽ sống lại, gọi là "hồi sinh dữ liệu (resurrection)". Đây là lý do Cassandra chỉ xóa vật lý tombstone sau khi qua thời gian ân hạn gc_grace_seconds (mặc định 10 ngày). Tức là dấu xóa không chỉ là cơ chế tối ưu mà còn là cơ chế bảo đảm tính đúng đắn để giữ nhất quán cuối cùng (eventual consistency), và nếu hạ giá trị này sai cách thì hiệu năng tốt lên nhưng tính nhất quán dữ liệu có thể bị phá vỡ.

D. Kiểm soát đồng thời và đọc snapshot

Cấu trúc LSM cũng có lợi cho kiểm soát đồng thời. Vì SSTable bất biến và cập nhật được biểu diễn bằng thêm phiên bản mới, nếu gán số thứ tự cho mỗi bản ghi thì tự nhiên có được snapshot nhất quán tại một thời điểm. Giao dịch đọc chỉ cần thấy "phiên bản mới nhất có số thứ tự nhỏ hơn hoặc bằng thời điểm mình bắt đầu", điều này tương đồng với MVCC (kiểm soát đồng thời đa phiên bản). Vì ghi và đọc không chặn nhau (readers never block writers), đạt được mức đồng thời cao mà không cần khóa đọc. Tính năng snapshot của RocksDB hay mức cô lập snapshot của SQL phân tán được xây dựng trên đặc tính này. Tuy nhiên, nếu giữ snapshot cũ quá lâu thì compaction không thể thu hồi các SSTable tham chiếu phiên bản đó, khiến khuếch đại không gian tăng lên, nên quản lý snapshot chạy dài trở thành điểm cần lưu ý khi vận hành.

4. Chiến lược Compaction và sự đánh đổi giữa các loại khuếch đại

Compaction là trái tim của cây LSM. Theo thời gian, SSTable tích tụ, nhiều phiên bản của cùng một khóa và tombstone nằm rải rác, số tệp mà việc đọc phải kiểm tra tăng lên (khuếch đại đọc), và dữ liệu trùng lặp lãng phí không gian (khuếch đại không gian). Compaction đọc nhiều SSTable, hợp nhất có sắp xếp, đồng thời loại bỏ các phiên bản cũ và khóa đã xóa rồi tạo SSTable mới để khắc phục vấn đề này. Sơ đồ dưới đây thể hiện quá trình compaction dọn dẹp trùng lặp·xóa và di chuyển dữ liệu xuống cấp dưới.

flowchart LR
    subgraph BEFORE["Trước compaction"]
      A1["SSTable A: k1=v1, k2=v2"]
      A2["SSTable B: k1=v1', k3 (tombstone)"]
      A3["SSTable C: k2=v2', k4=v4"]
    end
    A1 --> MERGE["Hợp nhất có sắp xếp + chọn bản mới nhất + dọn xóa"]
    A2 --> MERGE
    A3 --> MERGE
    MERGE --> RESULT["SSTable mới: k1=v1', k2=v2', k4=v4"]

Các phương thức compaction chia thành hai họ chính, và lựa chọn này quyết định đặc tính hiệu năng theo từng khối lượng công việc. Thứ nhất, compaction phân cấp (Leveled Compaction) là mặc định của RocksDB·LevelDB, bên trong mỗi cấp (từ L1 trở lên) duy trì các khoảng khóa của SSTable không chồng lấn nhau, và khi cấp trên đầy thì hợp nhất với các tệp chồng lấn ở cấp dưới. Mỗi cấp có kích thước khoảng 10 lần cấp trước. Phương thức này chỉ có một tệp mỗi cấp có thể chứa một khóa cụ thể nên khuếch đại đọc và khuếch đại không gian nhỏ, nhưng hợp nhất thường xuyên nên khuếch đại ghi lớn. Phù hợp với khối lượng công việc đọc nhiều và không gian eo hẹp.

Thứ hai, compaction phân tầng theo kích thước (Size-Tiered Compaction) là chiến lược mặc định của Cassandra, khi một số lượng nhất định SSTable có kích thước tương tự tích tụ thì hợp nhất thành một tệp lớn hơn. Tần suất hợp nhất thấp nên khuếch đại ghi nhỏ, nhưng cùng một khóa có thể tồn tại trùng lặp ở nhiều tệp lớn nên khuếch đại đọc và khuếch đại không gian lớn (ngay trước khi hợp nhất, bản gốc và kết quả cùng tồn tại nên tạm thời cần tối đa gấp 2 lần không gian). Phù hợp với việc nạp log·chuỗi thời gian có lượng ghi dồn dập. Ngoài ra còn có các chiến lược chuyên biệt như TWCS (Time-Window Compaction) dành cho chuỗi thời gian, gom theo cửa sổ thời gian để hủy toàn bộ dữ liệu hết hạn một lần.

Khác biệt giữa hai họ này rốt cuộc được tóm gọn trong đánh đổi RUM. Không thể tối thiểu hóa đồng thời cả ba loại khuếch đại, muốn được cái gì thì phải nhường cái gì.

Tiêu chí	Khuếch đại đọc (RA)	Khuếch đại ghi (WA)	Khuếch đại không gian (SA)	Hệ thống tiêu biểu/Khối lượng công việc phù hợp
Compaction phân cấp	Thấp	Cao	Thấp	RocksDB·LevelDB / OLTP·chỉ mục đọc nhiều
Compaction phân tầng theo kích thước	Cao	Thấp	Cao	Cassandra / Ghi dồn dập·nạp log
Cây B+ (nhóm so sánh)	Thấp	Trung bình (ngẫu nhiên)	Thấp	RDBMS / Khối lượng công việc cân bằng

Ở đây cần chỉ ra hàm ý thực tiễn của từng loại khuếch đại. Khuếch đại ghi lớn nghĩa là khi người dùng ghi 1 thì compaction ghi lại cùng dữ liệu đó nhiều lần, ở phương thức phân cấp thường lên tới 10~30 lần. Điều này dẫn trực tiếp đến hao mòn SSD và tiêu tốn băng thông nền, nên việc tính toán độ bền ghi (TBW) của SSD NVMe và lập lịch compaction là then chốt trong vận hành. Ngược lại, khuếch đại không gian của phương thức phân tầng theo kích thước làm tăng chi phí lưu trữ và tạo ra ràng buộc vận hành là luôn phải dự phòng gấp 2 lần không gian tại thời điểm compaction.

Khi nào compaction được kích hoạt cũng quan trọng trong vận hành. Các trigger tiêu biểu như sau, và điều phối chúng chính là quản lý ngân sách khuếch đại.

• Vượt dung lượng cấp: Khi tổng kích thước của một cấp vượt mục tiêu thì bắt đầu hợp nhất cấp trên·dưới (phân cấp).
• Ngưỡng số lượng SSTable: Khi số tệp có kích thước tương tự đạt số chỉ định (ví dụ 4 tệp) thì hợp nhất (phân tầng theo kích thước).
• Tỷ lệ tombstone/hết hạn: Khi dấu xóa hoặc dữ liệu hết hạn TTL vượt một tỷ lệ nhất định thì cưỡng bức hợp nhất để thu hồi không gian.
• Compaction thủ công/toàn phần (major compaction): Người vận hành hợp nhất mọi tệp thành một để loại bỏ hoàn toàn trùng lặp, nhưng vì gây I/O lớn nên thực hiện vào khung giờ tải thấp.

5. So sánh: Cây LSM và cây B+

Cây LSM và cây B+ là hai trục chính của thiết kế storage engine, vấn đề không phải hơn kém mà là mức phù hợp với khối lượng công việc. Nguyên nhân gốc rễ của khác biệt nằm ở cách cập nhật. Cây B+ cập nhật tại chỗ nên dữ liệu luôn được sắp gọn ở một nơi, việc đọc có thể dự đoán và nhanh, nhưng để duy trì sự gọn gàng đó phải chấp nhận ghi ngẫu nhiên và tách trang. LSM dồn thao tác ghi theo kiểu append-only để tối đa hóa thông lượng tuần tự, nhưng phải chấp nhận chi phí đọc và chi phí nền vì dữ liệu rải rác phải được hợp nhất·truy vấn về sau.

Lấy ví dụ cụ thể là một pipeline chuỗi thời gian nạp dữ liệu cảm biến IoT 500.000 bản ghi mỗi giây. Chỉ mục dựa trên cây B+ theo thời gian bị cập nhật ở khắp nơi trong cây, I/O ngẫu nhiên chiếm ưu thế và thông lượng giảm mạnh. Ngược lại, engine dựa trên LSM (ví dụ RocksDB, Cassandra) hấp thụ bằng tích lũy trong bộ nhớ rồi flush tuần tự, duy trì thông lượng ghi cao gấp vài lần đến vài chục lần. Tuy nhiên, nếu là khối lượng công việc mà point lookup truy vấn ngẫu nhiên "một bản ghi giá trị mới nhất của một cảm biến cụ thể" chiếm áp đảo, thì dù Bloom filter hoạt động tốt, do phải tìm trên nhiều SSTable và gánh nặng compaction, cây B+ có thể cho độ trễ thấp ổn định hơn.

Xét định lượng thì sự đánh đổi còn rõ hơn. Khi có L cấp và hệ số kích thước mỗi cấp là T (ví dụ 10), khuếch đại ghi của compaction phân cấp tỷ lệ xấp xỉ với T × L, thường lên tới 10~30 lần, trong khi số tệp cần kiểm tra khi đọc được giữ ở mức tối đa 1 tệp mỗi cấp. Ngược lại, phương thức phân tầng theo kích thước có khuếch đại ghi thấp cỡ L nhưng một khóa rải rác trên nhiều tệp nên khi đọc, trường hợp xấu nhất cần tìm kiếm O(số tệp). Bloom filter thực chất hạ thấp khuếch đại đọc này, nhưng khi tìm khóa tồn tại (true positive) thì filter không lọc được nên khác biệt căn bản vẫn còn. Như vậy, cùng một dữ liệu nhưng tùy dùng compaction nào mà mức hao mòn SSD và độ trễ truy vấn có thể chênh lệch vài lần, nên tinh chỉnh storage engine chính là việc khớp các hệ số này với khối lượng công việc.

Một hàm ý thực tiễn khác là quét theo khoảng và sắp xếp. Cả hai cấu trúc đều lưu dữ liệu có sắp xếp nên hỗ trợ truy vấn khoảng, nhưng trong LSM, việc quét phải duyệt hợp nhất đồng thời (merge iterator) nhiều SSTable và MemTable và có thể phải đi qua cả các đoạn tombstone, nên ở các bảng xóa thường xuyên, độ trễ quét trở nên khó dự đoán. Vì lý do này, xu hướng chung là RDBMS OLTP truyền thống coi trọng nhất quán giao dịch mạnh và độ trễ dự đoán được vẫn chọn cây B+, còn các kho lưu trữ phân tán quy mô lớn ưu tiên thông lượng ghi và mở rộng ngang thì chọn LSM.

6. Chuyên sâu: Xu hướng mới nhất và ứng dụng thực tiễn

Cây LSM vẫn là lĩnh vực tiến hóa sôi động. Thứ nhất, các thiết kế mới nhằm giảm nhẹ khuếch đại ghi liên tục được đề xuất. Kỹ thuật tách khóa-giá trị (Key-Value Separation) tiêu biểu là WiscKey lưu các giá trị (value) lớn vào một log riêng và chỉ để khóa và con trỏ trong LSM, nhờ đó khi compaction không phải ghi lại lặp đi lặp lại các giá trị lớn, giảm đáng kể khuếch đại ghi. BlobDB của RocksDB, TerarkDB và các sản phẩm khác đã thương mại hóa dòng này, và hiệu quả lớn với khối lượng công việc có giá trị lớn.

Thứ hai, thiết kế đồng thời với thiết bị lưu trữ là chủ đề then chốt. LSM ban đầu nhắm tới việc tránh ghi ngẫu nhiên trên HDD, nhưng ngày nay được thiết kế lại với tiền đề là SSD NVMe và SSD ZNS (Zoned Namespace), xa hơn nữa là mở rộng bộ nhớ dựa trên CXL. Đặc biệt, GC nội bộ của SSD và compaction của LSM đều thực hiện "dọn rác", nên LSM dựa trên ZNS phối hợp chúng không trùng lặp sẽ đồng thời hạ khuếch đại ghi và hao mòn. Đây là tối ưu thực chất quyết định TCO (tổng chi phí sở hữu) của các trung tâm dữ liệu quy mô lớn.

Một ví dụ ngành cụ thể tiêu biểu là kho lưu trữ inbox·timeline của các dịch vụ mạng xã hội quy mô lớn. Mỗi người dùng có hàng chục nghìn đến hàng trăm nghìn sự kiện được append mỗi giây và việc đọc chủ yếu tập trung vào đoạn gần nhất; với khối lượng công việc nặng về ghi như vậy, Cassandra dùng compaction phân tầng theo kích thước đã được áp dụng rộng rãi. Ngược lại, Facebook đã công bố trường hợp thay InnoDB (cây B+) của MySQL bằng MyRocks dựa trên LSM, giảm dung lượng lưu trữ của cùng tập dữ liệu xuống khoảng một nửa và hạ đáng kể tải ghi. Điều này cho thấy LSM có thể có lợi thế ở một trục khác là "tỷ lệ nén và hiệu quả không gian" — SSTable bất biến dễ nén mạnh theo khối và không cần để lại khoảng trống trang (lề fill factor) cần cho cập nhật tại chỗ.

Thứ ba, từ góc độ ứng dụng thực tiễn, RocksDB trên thực tế đã trở thành chuẩn storage engine cục bộ của các hệ thống phân tán. Kho trạng thái của Kafka Streams·Flink, tầng lưu trữ của SQL phân tán như TiKV·CockroachDB, engine MyRocks của MySQL, thậm chí cả DB trạng thái của nút blockchain đều dùng RocksDB (LSM). Tức là LSM không phải một sản phẩm độc lập mà thấm vào toàn bộ hệ sinh thái như một linh kiện storage engine (embedded engine) được nhúng vào hệ thống cấp trên. Vì vậy, từ góc nhìn Kỹ sư chuyên nghiệp, thay vì một sản phẩm cụ thể, cần giải thích được "tại sao hệ thống này chọn LSM" và ảnh hưởng của các tham số vận hành như tinh chỉnh compaction, số bit Bloom filter, kích thước MemTable đến hiệu năng.

7. Lưu ý và hàm ý

• Lựa chọn dựa trên hồ sơ khối lượng công việc: Cần đo định lượng tỷ lệ ghi:đọc, tỷ trọng point lookup so với quét khoảng, tần suất xóa rồi mới quyết định storage engine và chiến lược compaction. Không phải "ghi nhiều thì nhất định dùng LSM", mà phải xem xét cả khả năng cây B+ có lợi hơn nếu đọc điểm chiếm ưu thế.
• Quản lý ngân sách khuếch đại (RUM): Khuếch đại đọc·ghi·không gian không thể tối thiểu hóa đồng thời, nên cần lấy SLA (độ trễ·thông lượng), ngân sách lưu trữ và độ bền SSD (TBW) làm mục tiêu định lượng để quyết định rõ ràng ưu tiên cái nào trong ba, và điều phối bằng chiến lược compaction, số bit Bloom filter, hệ số cấp.
• Rủi ro vận hành compaction: Compaction tiêu tốn I/O·CPU nền, tranh giành tài nguyên với lưu lượng tiền cảnh, nên cần kiểm soát các đột biến độ trễ bằng lập lịch, giới hạn tốc độ (rate limiting), tách khung giờ bảo trì, và với phương thức phân tầng theo kích thước phải luôn bảo đảm không gian dư (tối đa 2 lần) tại thời điểm hợp nhất.
• Chiến lược dữ liệu xóa·hết hạn: Tombstone tích tụ gây độ trễ truy vấn và dữ liệu zombie, nên cần thiết kế nhất quán chính sách hết hạn như TTL, compaction theo cửa sổ thời gian (TWCS), gc_grace_seconds với chu kỳ compaction, và sau khi xóa hàng loạt phải giám sát thời điểm dọn tombstone.
• Công nghệ liên kết và mở rộng: LSM kết hợp với đồng thuận phân tán (Raft), nhân bản·sharding, tầng cache để cấu thành lưu trữ quy mô lớn, nên cần xem xét đặc tính của engine cục bộ khớp thế nào với thiết kế nhất quán, khôi phục, xử lý điểm nóng (hotspot) của hệ thống phân tán cấp trên.
• Bảo đảm khả năng quan sát: Cần liên tục đo các chỉ số cốt lõi như khuếch đại ghi/đọc/không gian, hàng đợi compaction, tỷ lệ dương tính giả của Bloom filter, độ trễ flush MemTable để làm căn cứ tinh chỉnh, và đây chính là thước đo mức trưởng thành vận hành của hệ thống dựa trên LSM.

Tài liệu tham khảo

• Patrick O'Neil et al., "The Log-Structured Merge-Tree (LSM-Tree)", 1996: https://www.cs.umb.edu/~poneil/lsmtree.pdf
• RocksDB Wiki, "Leveled Compaction": https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
• Apache Cassandra Docs, "How is data maintained (Compaction)": https://cassandra.apache.org/doc/latest/cassandra/managing/operating/compaction/index.html
• WiscKey: Separating Keys from Values in SSD-conscious Storage (FAST '16): https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf

---

Tóm tắt một câu: Cây LSM là cấu trúc lưu trữ tối đa hóa thông lượng ghi bằng cách chuyển ghi ngẫu nhiên thành tích lũy trong bộ nhớ rồi flush tuần tự và compaction nền, trong đó cốt lõi của thiết kế·vận hành là điều phối sự đánh đổi giữa khuếch đại đọc·ghi·không gian (RUM) cho phù hợp với khối lượng công việc.