第二章：LSM-Tree — 寫入密集型系統的引擎
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 引擎）。 核心優勢：
- 寫入放大降低：順序批量寫入特性相比隨機寫密集的 B+Tree 負載，能有效減少對 SSD 的磨損。
- 壓縮率：由於 SSTable 是靜態有序的，RocksDB 可以應用前綴壓縮（Prefix Compression），在特定場景下相比未壓縮的 B+Tree 能大幅節省存儲空間。
- 靈活策略：透過支援 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. 參考資料
- The Log-Structured Merge-Tree (LSM-Tree) - Patrick O’Neil (原始論文)
- RocksDB Architecture Guide
- Facebook Engineering: Under the Hood of RocksDB