LSM-Tree

B+Tree 扛不住爆寫啦！

假設你是 LINE 的 backend engineer，每天早上要處理多少早安圖 request？假設早安圖好發年紀在 60 歲，該年紀人口平均起床時間為早上 6:30。如果 LINE 底層的資料庫用 B+Tree，每筆早安 Put request 都要先 search 到正確的 leaf node，然後 in-place update。一筆寫入可能觸發 leaf split，造成多次 random disk I/O。你還記得我們之前學 SSD 的 garbage collection 嗎？大量 random write 會讓 FTL 很難把 valid page 集中在一起，GC 就得搬更多資料。有沒有一種 index 結構針對 write-heavy workload 優化的？ LSM-Tree 出場～

LSM-Tree 的核心哲學

1996 年，Patrick O'Neil 等人提出了 Log-Structured Merge-Tree（LSM-Tree）。他們的想法是：既然 HDD 的 random write 很貴，那就不要做 random write。所有寫入都先 buffer 在 memory 裡面，等累積到一定量之後，一口氣 sequential write 到 disk。SSD 上 sequential write 的吞吐量可以到 random write 的 10 倍以上，HDD 上差距更大。

今天，許多重要的 storage engine 採用 LSM-Tree：Google 的 LevelDB（就是 Chrome 在用的那個）、Facebook 的 RocksDB、Apache Cassandra、HBase、CockroachDB ... 等等，還有乙太坊的區塊鏈資料庫 !!

寫入路徑

Memtable

所有寫入都先寫進 memory 中的 memtable。Memtable 通常用 skip list 或 red-black tree 來實作，讓資料在 memory 中保持有序。寫一筆到 memtable 的成本大約是 $O(\log n)$ 的記憶體操作，沒有任何 disk I/O。

同時，每筆寫入也會 append 到一個 write-ahead log（WAL）。WAL 是 sequential append，速度很快。萬一系統掛掉，memtable 裡還沒 flush 到 disk 的資料可以從 WAL 救回來。這跟我們上學期 OS 學的 journaling 的概念一樣，先把要做的事記在硬碟，真正出事的時候才有得救。

Flush：一口氣吐出來

當 memtable 的大小超過 threshold（通常 32-64 MB），整個 memtable 會被凍結成 immutable，然後 flush 到 disk 上，變成一個 SSTable（Sorted String Table）。SSTable 是一個按 key 排序的 immutable 檔案。 Flush 完成後，對應的 WAL 就可以丟掉了，memtable 的記憶體也釋放回來。

送幾張早安圖來瞭解 LSM-Tree 寫入流程吧!

上層 application 做的是一堆看似 random 的 Put 操作，但到了 disk 上全部變成 sequential write。讚讚！ 這就是 LSM-Tree 名字裡 "Log-Structured" 的意思。

Update 和 Delete 怎麼處理

LSM-Tree 的 SSTable 是 immutable 的，寫出去就不會再改。那要怎麼 update？

答案很直覺：直接寫一筆新的 record，讓新版本覆蓋舊版本。 讀的時候從最新的 SSTable 往舊的找，找到第一筆就是最新的版本。舊的版本先留著，反正之後 compaction 會清掉。

Delete 也一樣。你不會真的去磁碟上把那筆資料抹掉（你連它在哪個 SSTable 的哪個 offset 都不一定知道），而是寫入一個特殊標記叫 tombstone （墓碑）。讀取時碰到 tombstone 就知道這筆資料已經被刪除了。真正的物理刪除要等到 compaction 的時候才會發生。

這個 "never update in place" 的設計，跟我們學過的 SSD FTL 是不是非常像？FTL 也是 out-of-place write，把新版本寫到新的 physical page，舊的 page 標成 invalid，等 GC 來回收。LSM-Tree 在軟體層做了同樣的事情，恰好跟底層 SSD 的特性配合。

讀取

寫入這麼輕鬆，代價在哪裡？在讀取。

查一個 key，你必須：

1. 先查 memtable（最新的資料在這裡）
2. 如果沒找到，查最近 flush 的 SSTable
3. 還沒找到，查更舊的 SSTable
4. 一路查到最老的 SSTable

最壞情況：一個根本不存在的 key，你得把所有 SSTable 都翻一遍。如果系統裡有 100 個 SSTable，就是 100 次 disk I/O。這就是 LSM-Tree 的 read amplification 問題。

Bloom Filter 出場

在 Bloom Filter 單元，我們提到 Chrome 的 LevelDB。現在你終於知道 SSTable 是什麼了，也知道為什麼 LevelDB 需要 Bloom filter 了。 每次查詢一個 key 之前，先問 Bloom filter：「這個 key 有沒有可能在這個 SSTable 裡？」如果回答「不在」，保證不在，直接跳過。如果說「可能在」，才需要真的去讀那個 SSTable。

假設 FPR 是 1%，系統裡有 100 個 SSTable，平均只有 1 個會因為 false positive 讓你白跑一趟 disk read。Bloom filter 讓 point query 從「查 100 個檔案」變成「查 1-2 個檔案」。

你可以對比一下 B+Tree 的讀取路徑：從 root 走到 leaf，路徑是確定的，一次 traversal 就找到了。B+Tree 不需要 Bloom filter，因為它的讀取路徑本來就很短。LSM-Tree 犧牲了讀取的確定性（不知道 key 在哪個 SSTable），然後用 Bloom filter 這種機率型結構來補回來。兩種 index 的 trade-off 完全不同。

Compaction

隨著時間推移，SSTable 越來越多。不做任何處理的話：

• 每個 SSTable 的 Bloom filter 要佔 memory（即使一個 Bloom filter 很小，100 個就開始有感了）
• 被覆蓋的舊版本和 tombstone 一直浪費 disk 空間
• 即使有 Bloom filter，SSTable 太多還是會拖慢讀取

所以 LSM-Tree 需要 compaction：把多個 SSTable 合併成更少的 SSTable，過程中丟掉被覆蓋的舊版本和 tombstone。

Compaction 本質上就是 merge sort：把多個已排序的 SSTable 合併成一個新的已排序 SSTable。是 sequential read + sequential write，對 disk 友善。但問題是：同一筆資料可能在 compaction 過程中被讀出來又寫回去好幾次，這就是 LSM-Tree 自己的 write amplification。軟體層和硬體層的 write amplification 會疊加：compaction 產生的額外寫入，到了 SSD 內部又會因為 GC 被放大一次。

Compaction 怎麼做，決定了 LSM-Tree 的三個重要指標之間的 trade-off：write amplification（同一筆資料被反覆讀寫幾次）、read amplification（讀一筆資料要查幾個 SSTable）、space amplification（舊版本佔了多少額外空間）。 兩種主流策略：

• Leveled compaction（LevelDB、RocksDB default）：積極合併，保持每層 SSTable 的 key range 不重疊。讀取快、空間省，但同一筆資料會被反覆搬動很多次。
• Tiered compaction（Cassandra default）：懶惰合併，等同一大小的 SSTable 累積夠多才一次合在一起。寫入便宜，但讀取要查更多檔案，舊版本也佔更多空間。

leveled 像是每天整理房間，東西永遠井井有條，但你花很多時間在整理上。Tiered 像是囤一堆再一次大掃除，平時輕鬆但找東西要翻比較久。

三個放大鏡

Write amp、read amp、space amp 三者無法同時最小化。

ScyllaDB 的工程師做了一個很有意思的實驗：對同一組 1.2 GB 的資料反覆 overwrite 15 次，比較兩種策略：

Tiered 的 space amplification 膨脹到了將近 8 倍，因為舊版本散落在多個 SSTable 裡遲遲沒被清掉。Leveled 則控制在 2 倍以內。 但 write amplification 剛好反過來。寫入 8.8 GB 資料，tiered 實際寫了 50 GB（write amp ~5x），leveled 實際寫了 111 GB（write amp ~13x）。Leveled 的 write amp 是 tiered 的 2 倍以上。

	Write Amp	Space Amp	Read Amp
Tiered	低 (~5x)	高 (~8x worst)	高 (多個 SST 要查)
Leveled	高 (~13x)	低 (~1.1-2x)	低 (每層只查 1 個)

選哪種取決於你的 workload。Write-intensive 用 tiered。Read-intensive 或 space-sensitive 用 leveled。

補充資料：ScyllaDB: Leveled Compaction（重點看 space amp 和 write amp 的實測圖表），以及 mini-lsm tutorial（有完整的 tiered 和 leveled 觸發條件和程式碼）。

為什麼即使有 Compaction 的 WAF，LSM-Tree 的寫入吞吐量還是比 B+Tree 高？

有人可能會問：「compaction 不是也在做大量的 disk write 嗎？LSM-Tree 的 WAF 都到 50 倍了，寫入吞吐量怎麼還是贏 B+Tree？」

關鍵在於 sequential vs. random。

假設 LSM-Tree 的 WAF 是 10 倍，它實際寫入的資料量是 application 要求的 10 倍，但全部都是 sequential write。B+Tree 的 WAF 可能只有 2-3 倍，但那些 write 幾乎全是 random。在 SSD 上，sequential write 的吞吐量可以到 random write 的 10 倍以上。所以 LSM-Tree 即使多寫了好幾倍的資料，總吞吐量還是贏。

而且，compaction 通常在背景執行，不在 application 的 critical path 上。寫入操作通常只要完成兩件事就可以返回：寫進 memtable（一次 memory 操作）和 append 到 WAL（一次 sequential write）。B+Tree 的 Put 要真的等到 leaf node 的 in-place update 完成才行。

沒有最好的資料結構，只有最適合你 workload 的資料結構。

RocksDB（LSM-Tree）被用在 LINE、Instagram、Netflix、CockroachDB 這些 write-heavy 的場景。MySQL InnoDB 和 PostgreSQL（B+Tree）被用在 read-heavy 的 OLTP 場景。

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

1. 為什麼 LSM-Tree 要先把資料寫入 memtable 再 flush 到 disk，而不是直接 append 到 SSTable 檔案的尾端？（提示：SSTable 裡的 key 需要滿足什麼性質？）

2. 假設一個 LSM-Tree 有 5 層（L0-L4），每層容量是上一層的 10 倍，使用 leveled compaction。一筆 1 KB 的資料從寫入到最終落在 L4，最壞情況下 disk 上一共會寫入多少 bytes？請估算 write amplification。

3. 你正在設計一個 time-series database，用來存 IoT sensor data。特性是寫入量極大、幾乎不更新、查詢主要集中在最近幾小時的資料。你會選 leveled 還是 tiered compaction？為什麼？

4. LSM-Tree 的讀取路徑需要從最新的 SSTable 一路查到最舊的。如果 Bloom filter 的 false positive rate 是 2%，系統中有 50 個 SSTable，平均會有幾次「不必要的」disk read？