LSM Tree 索引 (LSM Tree)
為什麼需要 LSM Tree
傳統 B-Tree 在「讀多寫少」場景很好，但有瓶頸：
| 問題 | 原因 |
|---|---|
| 隨機磁碟 I/O | 每次寫入要找到對應葉節點去更新，位置隨機 |
| SSD/HDD 隨機寫慢 | 順序寫遠快於隨機寫（HDD 10~100x，SSD 也有差距） |
| 高並發寫效能差 | 頻繁更新樹節點造成鎖競爭 |
LSM Tree 的設計初衷：把隨機寫變成順序寫，換取更高的寫入吞吐。
LSM Tree 的核心結構
寫入先進記憶體，累積後批次寫到磁碟，磁碟檔案多層分級。
Client 寫入
│
▼
┌──────────────────┐
│ WAL (log) │ ← 順序寫入，掉電可恢復
└──────────────────┘
│
▼
┌──────────────────┐
│ MemTable │ ← 記憶體中排序結構（SkipList）
│ (in-memory) │
└──────────────────┘
│ 滿了 → flush
▼
┌──────────────────┐
│ Level 0 SSTable │ ← 不可變檔案
├──────────────────┤
│ Level 1 SSTable │
├──────────────────┤
│ Level 2 SSTable │
│ ... │
└──────────────────┘
↑
Compaction 合併
寫入流程（3 步驟）
1. Write-Ahead Log（WAL）
每次寫入前先把資料 順序寫入 log 檔。
- 目的：掉電 / crash 時可從 WAL 重播恢復 MemTable
- WAL 是 append-only，純順序寫 → 極快
2. MemTable（記憶體）
- 資料結構：SkipList 或 平衡樹（排序好的）
- 寫入 WAL 後同時更新 MemTable
- 支援快速查詢（O(log n)）
3. SSTable（Sorted String Table，磁碟檔案）
- 當 MemTable 寫滿 → flush 成一個 不可變 的 SSTable 檔案
- SSTable 是排序好的 key-value 集合
- 每個 SSTable 附帶：
- Index Block — 區段索引，定位 key 在檔中位置
- Bloom Filter — 概率資料結構，快速判斷 key 是否存在
- Block Cache — 熱 block 留在記憶體
Compaction（合併壓縮）
隨著時間磁碟上累積大量 SSTable，查詢時要掃很多檔案。
Compaction：後台定期把多個 SSTable 合併成更大的。
Level 0: [ss1] [ss2] [ss3] [ss4] ← flush 直接寫到 L0
↓ compaction
Level 1: [──── merged ────────]
↓ compaction
Level 2: [────────── bigger ──────────]
- 合併時：刪除舊版本、移除 delete 標記（tombstone）
- 層級越往下：檔案越大、越少、越冷
- 寫放大（Write Amplification） — 同一筆資料可能被多次重寫
查詢流程
Key 可能在記憶體或任一層 SSTable，因此查詢 從新到舊 依序查：
1. MemTable ← 記憶體查
2. Immutable MemTable ← 正在 flush 的
3. Level 0 SSTables ← 最新
4. Level 1, 2, ... ← 越往下越舊
為了避免每次都掃多層 SSTable：
- 每 SSTable 的 Bloom Filter 可 O(1) 回答「key 一定不在」
→ 快速跳過不含 key 的 SSTable - Index block 快速定位 key 在檔內位置
- Block cache 減少重複磁碟讀
優缺點
優點
| 優點 | 為什麼 |
|---|---|
| 寫入吞吐極高 | 寫入 = 記憶體 + 順序寫 WAL，隨機 I/O 全部消除 |
| 對 SSD / HDD 友好 | 順序寫比隨機寫快 10~100 倍 |
| 適合海量寫入 | 寫入擴展性好，適合大規模 ingest |
缺點
| 缺點 | 原因 |
|---|---|
| 讀取開銷高 | 可能要檢查多層 SSTable（Bloom Filter 緩解但沒消除） |
| Compaction 昂貴 | 合併時需要讀寫大量資料，佔用磁碟 I/O、CPU |
| 寫放大 | 同一筆資料可能被多次 compaction 重寫 |
| 空間放大 | 同一 key 可能在多層都有版本，compaction 前空間比實際大 |
Simplification-with-exceptions
邊界情況
- 讀取不總是慢 — 熱資料多半在 MemTable 或 L0 cache 中；Bloom Filter 誤報率
可調到很低（<1%）。 - Compaction 策略 — Leveled Compaction（RocksDB）空間放大小但寫放大大；
Size-Tiered Compaction（Cassandra）寫放大小但空間放大大。面試時說得出名字即可。 - 並非只能寫多讀少 — Cassandra / RocksDB 透過合理 tuning 也能勝任混合負載；
極端 read-heavy 才回去用 B-Tree。 - Tombstone 刪除 — LSM 的 DELETE 不會立即移除資料，而是寫入 tombstone，
由 compaction 延遲清理。若大量 DELETE 會讓讀放大變嚴重。
使用場景
| 系統類型 | 例子 |
|---|---|
| 分散式 KV-Store | Cassandra、HBase、ScyllaDB |
| 嵌入式儲存引擎 | LevelDB（Google）、RocksDB（Facebook）、BadgerDB |
| 時序資料庫 | InfluxDB（底層 TSM engine 是 LSM 變體） |
| 區塊鏈儲存層 | Bitcoin Core 的 UTXO DB |
| MySQL 寫優化引擎 | MyRocks（基於 RocksDB） |
LSM vs B-Tree
| 面向 | B-Tree | LSM Tree |
|---|---|---|
| 寫入 | 隨機 I/O，較慢 | 順序 I/O，極快 |
| 讀取 | 穩定 O(log n) | 可能要掃多層 |
| 空間 | 緊湊 | 有寫放大、空間放大 |
| 適合負載 | 讀多寫少、平衡 | 寫多、log / 時序 / 海量 ingest |
| 典型系統 | MySQL InnoDB、PostgreSQL | Cassandra、RocksDB、LevelDB |