LSM-tree & SSTable — cơ chế bên trong engine ghi-nhiều

TL;DR: LSM-tree biến ghi ngẫu nhiên thành ghi tuần tự qua bốn tầng: mọi ghi nối vào memtable (sorted, trong RAM) cộng một dòng WAL để bền vững; memtable đầy thì flush thành SSTable — file bất biến chứa data block + sparse index + bloom filter; compaction nền gộp các SSTable, loại bản cũ và tombstone. Đọc phải gộp memtable với nhiều SSTable (newest-wins). Trái tim của đánh đổi là chiến lược compaction: size-tiered ghi ít hơn nhưng tốn chỗ và đọc chậm hơn; leveled ghi nhiều hơn nhưng gọn và đọc nhanh hơn. Ba loại amplification (write/read/space) không tối ưu đồng thời — chọn chiến lược là chọn nghiêng về loại nào.

Bài 02 đã giới thiệu hai họ storage engine và khái niệm ba tầng của LSM (memtable → SSTable → compaction) cùng ba loại amplification. Nhưng nó cố tình dừng ở mức tổng quan: memtable bền vững nhờ đâu? bên trong một SSTable có gì để tra được một khoá? và compaction — nghe tên rồi nhưng nó chạy theo kiểu nào, và vì sao chọn kiểu compaction lại quyết định cân bằng amplification?

Bài này mở từng hộp đen đó. Cốt lõi để bạn không chỉ biết "LSM ghi nhanh" mà giải thích được vì sao nhanh, giá phải trả nằm ở đâu, và một engine LSM có thể chỉnh cân bằng đó thế nào.

1. Analogy — dọn kho giấy tờ theo hai phong cách

Bài 02 ví LSM như cuốn nhật ký chỉ nối thêm. Giờ phóng to đúng cảnh dọn dẹp cuốn nhật ký đó — vì đây mới là chỗ cơ chế thật sự phân nhánh.

Bạn có một kho chứa các tập hồ sơ, mỗi tập đã sắp xếp bên trong nhưng các tập chồng lấn nhau về nội dung (cùng một khách hàng xuất hiện ở nhiều tập). Muốn kho gọn để tra nhanh, bạn phải định kỳ gộp. Có hai phong cách:

• Gộp theo đống cùng cỡ (size-tiered): cứ khi nào có đủ vài tập cùng kích cỡ, bạn dồn chúng thành một tập lớn hơn. Ít công dọn, nhưng kho luôn có vài tập lớn chồng lấn nhau — tra một khách phải lật nhiều tập, và bản cũ còn nằm đó choán chỗ tới lượt dọn sau.
• Xếp theo tầng không chồng lấn (leveled): mỗi tầng là một dãy tập không tập nào trùng khoảng khách với tập khác trong cùng tầng (trừ tầng trên cùng nơi hồ sơ vừa đổ vào còn lẫn lộn). Để giữ tính chất đó, mỗi lần thêm tập mới bạn phải hoà nó vào tầng dưới — dọn nhiều hơn, nhưng tra một khách chỉ chạm tối đa một tập mỗi tầng, và ít bản dư thừa.

2. Memtable & WAL — đường ghi bền vững

Một ghi đến (INSERT/UPDATE/DELETE) đi qua hai nơi gần như cùng lúc, và thứ tự giữa chúng quyết định độ bền:

1. WAL (write-ahead log) — engine nối bản ghi vào cuối một file log trên đĩa và (tuỳ cấu hình bền) chờ đĩa xác nhận đã ghi. Đây là ghi tuần tự, rất nhanh so với random I/O.
2. Memtable — cấu trúc sorted trong RAM (thường là skip list, giữ khoá theo thứ tự mà chèn vẫn nhanh). Bản ghi vào đây để phục vụ đọc tức thì.

Ghi den:
  1. append vao WAL (dia, tuan tu) -- de KHOI PHUC neu crash
  2. insert vao memtable (RAM, sorted) -- de DOC ngay
  3. bao "OK" cho client

Neu crash sau buoc 3 nhung truoc khi flush:
  memtable (RAM) mat -> nhung WAL con tren dia
  -> khoi dong lai: replay WAL dung lai memtable. Khong mat du lieu.

Vì sao cần cả hai? Memtable ở RAM nên mất khi crash; nếu chỉ có nó, mọi ghi chưa flush sẽ bay. WAL nằm trên đĩa và chỉ ghi nối tiếp (rẻ), nên nó gánh vai trò durability mà không kéo chậm đường ghi. Đây chính là lý do LSM đạt throughput ghi cao: mỗi ghi bền vững chỉ tốn một lần nối tuần tự vào WAL, thay vì tìm-và-sửa một trang rải rác như B-tree.

Khi memtable đạt ngưỡng kích thước, engine đóng băng nó (chuyển thành immutable memtable), mở một memtable mới để nhận ghi tiếp, rồi flush memtable đóng băng xuống đĩa ở nền — ghi không bị chặn trong lúc flush.

3. SSTable — bên trong một file bất biến

Flush biến memtable đóng băng thành một SSTable (sorted string table). Vì memtable đã sorted, flush chỉ là ghi một mạch tuần tự. Nhưng một file phẳng thì tra khoá vẫn phải quét — nên SSTable gói kèm mấy thành phần để tra được bằng đúng một lần đọc block:

Mot SSTable (bat bien tren dia):

  +----------------------------+
  | Data block 1 (sorted kv)   |  <- key-value that, chia block ~4-64KB
  | Data block 2               |
  | ...                        |
  +----------------------------+
  | Bloom filter block         |  <- "key co the co trong file nay khong?"
  +----------------------------+
  | Sparse index               |  <- moi block 1 entry: (first-key -> offset)
  +----------------------------+
  | Footer (metadata, offsets) |
  +----------------------------+

Tra một khoá trong một SSTable:

1. Hỏi bloom filter trước: nếu nó nói "chắc chắn không có", bỏ qua file này — không chạm data block. (Cơ chế bloom filter đã học ở bài Bloom filter — cấu trúc xác suất không bao giờ báo âm tính giả.)
2. Nếu "có thể có": binary search trên sparse index (nhỏ, thường cache được trong RAM) để tìm data block chứa khoảng khoá.
3. Nạp đúng một data block đó rồi quét trong block.

Sparse index là "index thưa": chỉ lưu khoá đầu mỗi block chứ không mọi khoá, nên đủ nhỏ để giữ trong RAM. Nhờ vậy, một lần đọc điểm trong một SSTable tốn nhiều nhất một lần đọc đĩa (một data block) — không phải quét cả file.

4. Đường đọc — gộp tầng và tombstone

Vì SSTable bất biến, một UPDATE không sửa file cũ mà ghi bản mới ở tầng trên. Nên một khoá có thể tồn tại ở nhiều nơi: memtable, các immutable memtable, và nhiều SSTable qua các tầng. Đọc phải gộp theo luật newest-wins — dừng ngay ở bản mới nhất tìm thấy:

function get(key):
    if key in memtable: return ban ghi          -- moi nhat, uu tien
    for each immutable memtable (moi -> cu):
        if key found: return ban ghi
    for each tang L0 -> Ln (moi -> cu):
        for each SSTable ung vien trong tang:
            if bloom filter noi "chac chan khong": skip
            if key in SSTable: return ban ghi    -- dung ngay
    return NOT_FOUND
// Dung o ban dau tien gap duoc, ke ca khi do la tombstone (xem duoi).

Xoá xử lý thế nào khi file bất biến, không sửa được? Engine ghi một tombstone — một dấu "khoá này đã xoá" như một bản ghi bình thường. Khi đọc gặp tombstone trước bản dữ liệu cũ hơn, nó trả về "không tồn tại". Tombstone chỉ thật sự biến mất khi compaction gộp qua và bỏ luôn cả tombstone lẫn các bản cũ hơn nó.

Đây là gốc của read amplification: một đọc logic có thể phải sờ memtable cộng nhiều SSTable ở nhiều tầng. Bloom filter cắt phần lớn lần chạm đĩa vô ích, nhưng càng nhiều tầng/nhiều file chồng lấn thì đọc càng phải kiểm nhiều nơi.

5. Size-tiered vs leveled — chọn kiểu compaction nào?

Compaction là tiến trình nền gộp nhiều SSTable thành ít hơn, loại bản cũ và tombstone. Cơ chế gộp chính là merge sort nhiều dãy đã sắp xếp (đúng thuật toán ở bài Merge sort) — vì mọi SSTable đều sorted, gộp chúng chỉ là trộn k dãy sorted, giữ bản mới nhất mỗi khoá. Điểm phân nhánh là chọn file nào để gộp, gộp về đâu — và đây là nơi hai chiến lược rẽ hướng:

flowchart TB
  MT["Memtable (RAM)"] -->|flush| L0["L0: cac SSTable co the chong lap key"]
  L0 -->|"leveled: hoa vao tang duoi"| L1["L1: cac SSTable KHONG chong lap"]
  L1 -->|compaction| L2["L2: tong ~10x L1, khong chong lap"]
  L2 --> L3["L3: moi tang lon dan ~10x"]

Size-tiered (STCS): gom các SSTable cùng cỡ; khi đủ số lượng, merge chúng thành một file lớn hơn ở "tier" trên. Ít lần ghi lại dữ liệu (mỗi bản ghi chỉ bị gộp lại khi đủ đống cùng cỡ), nên write amplification thấp. Nhưng nhiều tier lớn cùng tồn tại và chồng lấn khoá, nên đọc phải kiểm nhiều file (read amplification cao hơn), và các bản cũ nằm chờ tới lượt gộp lớn nên tốn chỗ tạm thời nhiều (space amplification cao).

Leveled (LCS): tổ chức thành các tầng L1, L2, ... mỗi tầng lớn hơn tầng trên khoảng một hằng số (thường ~10 lần). Ràng buộc cốt lõi: từ L1 trở đi, trong cùng một tầng không SSTable nào chồng lấn khoảng khoá với SSTable khác. (L0 là ngoại lệ: nó nhận flush trực tiếp từ memtable nên các SSTable ở L0 vẫn có thể chồng lấn — đúng như sơ đồ trên.) Để giữ ràng buộc đó, thêm dữ liệu xuống một tầng buộc phải merge-rewrite phần trùng ở tầng dưới — ghi lại nhiều lần hơn (write amplification cao). Đổi lại: một khoá xuất hiện tối đa một lần mỗi tầng, nên đọc chỉ chạm ít file (read amplification thấp), và ít bản dư nên gọn (space amplification thấp).

Nhiều engine cho chọn chiến lược theo từng bảng: bảng ingest-nặng đọc-thưa (log, telemetry) nghiêng STCS; bảng đọc nhiều cần đọc ổn định nghiêng LCS.

6. Ba amplification không tối ưu đồng thời

LSM-tree không tối ưu đồng thời cả ba loại amplification — đây là ý phải mang theo:

                 write amp     read amp     space amp
STCS (size-tiered)  THAP         cao          cao
LCS  (leveled)      cao          THAP         THAP

=> Khong co chien luoc "thang ca ba". Giam write amp (STCS)
   thi tra bang read + space amp cao hon, va nguoc lai.

Đây là dạng cụ thể của một định luật chung trong storage: write, read, và space amplification tạo thành tam giác đánh đổi — kéo giảm một góc thường đẩy góc khác lên. Một engine LSM không "nhanh mọi mặt"; nó cho bạn cần gạt (chọn chiến lược + tham số compaction) để đặt cân bằng đúng workload. Hiểu tam giác này là hiểu vì sao câu hỏi đúng không phải "LSM có nhanh không" mà "workload của tôi cần nghiêng về giảm amplification nào".

So với B-tree (bài 02): B-tree dồn chi phí vào lúc ghi tại chỗ để đọc rẻ và ổn định; LSM dời chi phí sang compaction nền, rồi để bạn chọn compaction nghiêng về đâu. Cùng một dữ liệu, hai triết lý đặt "cái giá" ở hai chỗ khác nhau.

7. Pitfall — compaction không theo kịp

Ingest rat nhanh + compaction cham
  -> L0 tich hang chuc SSTable chong lap
  -> moi doc phai kiem qua tat ca -> read amp tang vot (duoi p99)
  -> ban cu chua don -> space amp tang, dia phinh

8. 📚 Deep Dive

9. Liên hệ các bài khác

• Bài 02 — B-tree vs LSM-tree: giới thiệu hai họ engine và ba loại amplification ở mức khái niệm — đọc trước; bài 04 này mổ sâu cơ chế của riêng LSM mà bài 02 để dành.
• Bài 01 — Tại sao cần index: nền heap vs index sorted — LSM và B-tree là hai cách hiện thực "cấu trúc sorted" đó.
• Bloom filter (Thuật toán cốt lõi): cấu trúc xác suất mà mỗi SSTable dùng để cắt lần đọc đĩa vô ích — đọc để hiểu vì sao bỏ qua một SSTable là an toàn.
• Merge sort (Thuật toán cốt lõi): thuật toán gộp nhiều dãy sorted — chính là lõi của compaction.
• Module 10 — OLTP vs OLAP: row-store/column-store là trục lưu trữ khác (theo dòng vs cột) song song với trục B-tree/LSM — nhiều chiều đánh đổi lưu trữ.

10. Tóm tắt

• LSM đạt throughput ghi cao vì mỗi ghi bền vững chỉ tốn một lần nối tuần tự vào WAL + chèn vào memtable (RAM), không random I/O.
• WAL (đĩa, tuần tự) mới là thứ đảm bảo durability; memtable (RAM) phục vụ đọc và sẽ được replay từ WAL nếu crash trước flush.
• SSTable bất biến gói data block + sparse index + bloom filter, đủ để tra một khoá bằng nhiều nhất một lần đọc block.
• Đọc gộp memtable + nhiều SSTable theo newest-wins; xoá dùng tombstone, chỉ biến mất khi compaction gộp qua — đây là gốc read amplification.
• Compaction = merge sort các SSTable. Size-tiered ghi ít (write amp thấp) nhưng tốn chỗ + đọc chậm hơn; leveled ghi nhiều (write amp cao) nhưng gọn + đọc nhanh.
• Write/read/space amplification là tam giác đánh đổi: chọn chiến lược compaction là chọn nghiêng về giảm loại nào theo workload.

11. Tự kiểm tra

Bài tiếp theo: ACID — bốn đảm bảo của một giao dịch