Luke a Pro

Luke Sun

Developer & Marketer

🇺🇦
EN|简|繁
© 2015–2026 Luke Sun.
All rights reserved.

第二章：LSM-Tree — 寫入密集型系統的引擎

| , 2 minutes reading.

1. 定義

LSM-Tree (Log-Structured Merge-Tree) 是一種優化了寫入吞吐量的資料結構，被廣泛應用於 NoSQL 資料庫（如 Cassandra, HBase）和鍵值存儲引擎（如 RocksDB, LevelDB）。

它的核心設計哲學是：將隨機寫入轉換為順序寫入。與 B+Tree 的就地更新（In-place Update）不同，LSM-Tree 核心採用 Log-Structured 寫入方式（數據寫入 MemTable，SSTable 一旦寫入磁碟即不可變，僅透過 Compaction 重寫），這使得它在機械硬碟（HDD）和固態硬碟（SSD）上都能獲得極高的寫入效能。

2. 技術深度：LSM-Tree 的三層結構

LSM-Tree 並非一棵單一的樹，而是由記憶體和磁碟中的多層結構組成的。

A. MemTable (記憶體表)

所有寫入操作（Insert/Update/Delete）首先被寫入 WAL (Write-Ahead Log) 以確保持久性，然後被寫入記憶體中的 MemTable。MemTable 通常是一個有序的資料結構（如 SkipList 或紅黑樹）。

  • 讀取：先查 MemTable，如果找到即回傳（速度極快）。

B. Immutable MemTable (不可變記憶體表)

當 MemTable 達到閾值（如 64MB）時，它被凍結為 Immutable MemTable，並由背景執行緒非同步刷新（Flush）到磁碟。

C. SSTable (Sorted String Table - 磁碟表)

刷盤後的數據形成 SSTable。這是一種不可變、有序的磁碟檔案。為了加速查詢，SSTable 內部通常包含 Bloom Filter 和稀疏索引。

3. 可視化：寫入路徑與 Compaction (合併)

隨著 SSTable 檔案越來越多，讀取效能會下降（因為需要檢查多個檔案）。Compaction 是 LSM-Tree 的心臟，它負責合併多個 SSTable，清理已刪除（標記為 Tombstone）的數據，並重新排序。

sequenceDiagram
    participant Client as 用戶端
    participant WAL as 預寫日誌
    participant Mem as MemTable
    participant Disk as 磁碟 (L0/L1 SSTables)

    Client->>WAL: 1. 追加日誌 (Append)
    Client->>Mem: 2. 寫入記憶體 (Put Key=A)
    Mem-->>Client: 回傳成功 (Ack)

    Note over Mem: MemTable 已滿
    Mem->>Disk: 3. 非同步 Flush -> 生成 L0 SSTable
    
    Note over Disk: 背景 Compaction 觸發
    Disk->>Disk: 4. 合併 L0 檔案 -> 生成 L1 SSTable
    Note right of Disk: 捨棄舊版本 Key=A<br/>物理刪除 Tombstone<br/>(僅當底層無舊版本時)

4. 真實案例：Facebook 的 RocksDB 遷移 (2013-2016)

背景：Facebook 的用戶收件匣（User Inbox）和訊息系統原本運行在基於 B+Tree 的存儲引擎上。 挑戰：隨著 SSD 的引入，他們觀察到 B+Tree 的寫入放大 (Write Amplification) 在特定負載下會影響 SSD 的壽命，且隨機寫入無法充分利用 SSD 的併發通道。

技術選型：Facebook 開發並開源了 RocksDB（基於 Google LevelDB 的改進版 LSM-Tree 引擎）。 核心優勢：

  1. 寫入放大降低：順序批量寫入特性相比隨機寫密集的 B+Tree 負載，能有效減少對 SSD 的磨損。
  2. 壓縮率：由於 SSTable 是靜態有序的，RocksDB 可以應用前綴壓縮（Prefix Compression），在特定場景下相比未壓縮的 B+Tree 能大幅節省存儲空間。
  3. 靈活策略：透過支援 Universal Compaction 等多種策略，RocksDB 能夠在不同的讀寫負載下進行針對性調優。

影響：RocksDB 現在已成為事實上的業界標準，不僅用於 Facebook 內部，還是 CockroachDB、TiKV 等現代分散式資料庫的底層存儲引擎。

5. 深度最佳化與縱深防禦

A. 根本修復：Compaction 策略調優

  • Leveled Compaction：優化讀取效能，適合讀多寫少。（每層大小是上一層的 10 倍）。
  • Tiered/Universal Compaction：優化寫入效能並降低寫入放大，但空間放大與讀取放大可能顯著增加。
  • 防禦：監控 pending_compaction_bytes。如果積壓過多，像 RocksDB 這樣的引擎會觸發 寫入停頓 (Write Stall) 以限制寫入速度，防止系統過載。

B. 縱深防禦：Bloom Filter

  • 在每個 SSTable 中嵌入 Bloom Filter。在讀取磁碟區塊之前，先透過布隆過濾器判斷 Key 是否可能存在。這能過濾掉絕大多數的無效磁碟 I/O。

C. 空間放大控制

  • 對於頻繁更新的業務，舊數據版本會佔用大量磁碟空間（空間放大）。定期執行 Major Compaction 可以強制回收空間，但這會消耗大量 CPU 和 I/O，需在業務低峰期進行。

6. 參考資料