LSM-Tree

為什麼需要另一種結構

B+Tree 的每次更新都是原地修改一個頁面：即使只改 100 bytes，最終也要把整個 8–16 KB 的頁寫回磁碟（寫入放大 80–160 倍）， 而且這些頁散佈各處，是隨機寫入。在 HDD 時代這是尋道瓶頸，在 SSD 上則加速磨損並放大 FTL 內部的垃圾回收。 隨機寫入的另一個代價：每頁寫入前都要取 latch、處理分裂、寫 WAL。

O’Neil 等人（1996）的 改變策略：

1. 寫入先進入記憶體中的排序結構（並 append 到 WAL 保證持久）。

2. 滿了就整批循序寫出成一個不可變的排序檔案。

3. 背景把多個檔案合併（compaction）成更大的檔案，清掉被覆蓋的舊值。

所有磁碟寫入都是大塊循序寫，讀取則要查多個檔案——LSM 把成本從寫入端搬到讀取端與背景工作。 Google Bigtable（2006）、LevelDB（2011）、RocksDB（2012）讓它成為現代寫入密集系統的標準配備。

結構

• MemTable：記憶體中的排序結構，通常是 skiplist（並行插入友善；RocksDB 預設），也可用紅黑樹或 B-tree。寫滿（，64 MB）後凍結成 immutable 並換新的。

• WAL：每筆寫入先 append 到 WAL；一個 memtable flush 完成後對應的 WAL 即可刪除。復原只需重播 WAL 重建 memtable（第 11 章）。

• SSTable（Sorted String Table）：不可變、鍵排序的檔案。寫出後永不修改，只會在 compaction 中被讀取與刪除——因此不需要 latch、也沒有 torn page 問題。

• Levels：L0 由 flush 直接產生，各檔鍵範圍可重疊；L1 以下每層內的檔案鍵範圍互不重疊，整層等同一個巨大的排序陣列，查找只需二分搜尋 MANIFEST 中的鍵範圍。

• MANIFEST：描述目前版本（每層的檔案清單）的日誌；每次 flush/compaction 追加一筆版本編輯。

SSTable 檔案格式

Data block 內的鍵以前綴壓縮儲存（每 16 個鍵一個 restart point 供二分搜尋），整個 block 可用 LZ4/Zstd 壓縮並附 CRC。 讀一個鍵：footer \(\to\) index block（通常常駐快取）\(\to\) 二分搜尋找到 data block \(\to\) 讀取、解壓、在 block 內搜尋。

讀取路徑

點查詢 由新到舊依序找，第一個命中即為答案（新值蓋舊值）：

1. MemTable \(\to\) immutable memtable(s)。

2. L0 的每一個檔案（鍵範圍重疊，所以都得查；這是 L0 檔數要控制的原因）。

3. L1、L2……每層最多一個檔案（二分搜尋 MANIFEST 的鍵範圍）。

最壞情況要讀「L0 檔數 + 層數」個 SSTable——這是 讀取放大。兩個關鍵武器：

• Bloom filter：每個 SSTable（或每個 data block）一個；10 bits/key 時誤判率約 1%，讓不存在於該檔的查詢幾乎免費跳過。 對不存在鍵的查詢（例如「insert if not exists」）尤其關鍵。Bloom filter 對範圍查詢無效（除非用前綴 bloom）。

• Block cache：快取解壓後的 data block（RocksDB 預設 LRU，8 MB——務必調大），index/filter block 可固定在快取中。

範圍掃描無法用 bloom filter，必須在每一層開一個游標，用合併迭代器（merging iterator）（最小堆）同時推進並去重； 層數越多、tombstone 越多，掃描越慢。這就是 LSM 的範圍查詢通常比 B+Tree 慢的原因。

Compaction

Compaction 是 LSM 的心臟：它回收空間（丟棄被覆蓋的舊版本與已刪除的鍵）、限制讀取放大（減少要查的檔案數）、維持層級結構。 代價是消耗 I/O 與 CPU，並造成寫入放大：同一筆資料在生命週期中會被重寫多次。

Leveled compaction

RocksDB／LevelDB 預設。每層有大小上限（\(L_1 = 256\) MB、每層 \(\times 10\)）；某層超標時，挑一個檔案與下一層鍵範圍重疊的檔案合併、寫成新檔到下一層。 L0 累積 4 個檔時觸發 L0\(\to\)L1。因為每層內鍵不重疊，每層只佔約 10% 的「冗餘」空間，空間放大約 1.1； 但一筆資料每往下一層就要和下一層約 \(T = 10\) 倍大的資料一起重寫，寫入放大約 \(T \times\) 層數 \(\approx 10 \times L\)（實務 10–30）。

Tiered / Universal compaction

每層容許 \(T\) 個鍵範圍重疊的 run；累積到 \(T\) 個就把它們合併成一個 run 放到下一層。一筆資料每層只被重寫一次， 寫入放大約等於層數（低），但每層要查 \(T\) 個 run、且被覆蓋的舊值可能同時存在多個 run，讀取與空間放大高（空間最壞 \(2\times\) 以上）。 Cassandra 的 size-tiered、RocksDB 的 universal compaction、HBase 都屬此類；寫入極重、讀取可容忍較慢時使用。

Athanassoulis 等人（2016）的 RUM 猜想：Read、Update、Memory（空間）三種開銷不可能同時最小化——任何存取方法都是三角形上的一點， LSM 的各種 compaction 策略就是在這個三角形上移動。

刪除、tombstone 與其他實務問題

• 刪除是寫入： 寫入一個 tombstone。它必須存活到抵達最底層並確認沒有更舊的版本後才能丟棄； 大量刪除後讀取反而變慢（要跳過成堆的 tombstone），Cassandra 的「tombstone 警告」即源於此。範圍 tombstone 以一筆記錄刪除整個鍵區間。

• Write stall：寫入速度超過 compaction 時，L0 檔案與待合併資料堆積。RocksDB 在 L0 達 20 個檔減速、36 個檔停止寫入（）， 以及 。延遲尖峰常來自這裡；對策是限制寫入速率（rate limiter）、增加 compaction 執行緒、調大 L0 觸發值。

• 壓縮分層：上層用快速的 LZ4（頻繁重寫）、最底層用高壓縮比的 Zstd（90% 的資料、很少重寫）。

• Key-value 分離（WiscKey）：大 value 存到獨立的 value log，LSM 只存鍵與指標，compaction 不再搬動 value（RocksDB BlobDB、TiKV Titan、Badger）。代價是範圍掃描要多一次隨機讀，value log 自己需要 GC。

• MVCC 內建：RocksDB 的每筆寫入帶一個遞增的 sequence number，snapshot 就是一個 sequence number； CockroachDB、TiKV 進一步把交易時間戳編進鍵（），LSM 天然保留多版本，舊版本由 compaction 依 GC 門檻清除（第 9、16 章）。

採用 LSM 的系統

• 嵌入式 KV：LevelDB、RocksDB（Meta；MySQL 的 MyRocks、Kafka Streams、Flink 狀態後端）、Pebble（CockroachDB，Go 重寫）、Badger、Sled。

• 分散式資料庫：Cassandra／ScyllaDB、HBase、TiKV（TiDB）、CockroachDB、YugabyteDB（DocDB）、FoundationDB（可選 Redwood B+Tree）。

• 時序／搜尋：InfluxDB（TSM）、Prometheus TSDB（類 LSM 的 block）、Lucene/Elasticsearch 的 segment merge 也是同一思想。

• 對照：MongoDB WiredTiger 預設仍是 B+Tree（可選 LSM），PostgreSQL／MySQL InnoDB／SQL Server／Oracle 皆為 B+Tree。

LSM 還是 B+Tree？