Compaction 是 LSM 的命脈：背景把零散的 SSTable 合併、丟掉過期與被刪的 key。策略選擇本質是在寫放大、讀放大、空間放大這個三角裡選一個你能接受的角。
🧠 Intuition
TIP
三種放大不可能同時最小化，這是 RUM 猜想（Read-Update-Memory）的日常版：你只能挑兩個來優化，第三個就得讓步。Size-tiered 省寫、leveled 省讀與空間——先問這個負載痛在哪一角。
- 寫放大 (write amplification)：一筆資料一生被 compaction 重寫幾次。重寫越多，SSD 壽命與寫頻寬越吃緊。
- 讀放大 (read amplification)：讀一筆最壞要查幾個 SSTable。檔案越多層、越重疊，單次讀要碰的檔案越多。
- 空間放大 (space amplification)：實際佔用磁碟 / 有效資料量。過期版本與墓碑沒回收乾淨，空間就膨脹。
⚖️ Tradeoffs
Size-tiered compaction (STCS) — 省寫
- 累積到「幾個大小相近的 SSTable」就把它們合併成一個更大的 → 檔案大小呈指數級分層。
- 優點：每筆資料被重寫的次數少 → 寫放大低，寫吞吐高。
- 代價：同一 key 的版本可能散在多個大檔裡 → 讀放大高；合併大檔時新舊並存 → 空間放大高（最壞瞬時佔用接近 2x）。
- 用於 Cassandra 預設、RocksDB universal compaction；適合寫重、讀多靠 Bloom filter 擋的負載。
Leveled compaction (LCS) — 省讀與空間
- 資料分成 L0、L1…多層，除 L0 外每層內 SSTable 的 key 範圍互不重疊，且每層容量呈倍數成長（如 10x）。
- 優點：每層至多一個 SSTable 含某 key → 讀放大低、可預測；過期版本被穩定下沉回收 → 空間放大低（通常 ~10% 浮動）。
- 代價：一筆資料要逐層下沉、每次都重寫 → 寫放大高（可達 STCS 數倍）。
- 用於 LevelDB、RocksDB 預設、Cassandra LCS；適合讀重或對空間敏感的負載。
Compaction 跟不上的風險
- Compaction 是背景工作，與前台寫入搶 I/O 與 CPU；若寫入速率長期 > compaction 速率，SSTable 會持續堆積。
- 後果：L0 檔案數暴增 → 讀放大飆升、p99 惡化；磁碟被舊版本佔滿 → 寫入被反壓（write stall）甚至停寫。
- 監控重點：pending compaction bytes、L0 檔案數、write stall 次數——這是 LSM 維運的頭號訊號。
Tombstone 與墓碑回收 (Garbage Collection)
- LSM 的刪除不是真刪，而是寫一個 tombstone（墓碑）標記覆蓋舊值；讀到墓碑就當作不存在。
- 墓碑必須留到「比它舊的所有版本都被 compaction 一起重寫掉」才能安全移除，否則舊值會復活（zombie / resurrection）。
- 代價：大量刪除（如 TTL 過期、佇列負載）會累積海量墓碑，拖慢 range scan（要掃過一堆墓碑），且延後空間回收——這是 Cassandra 著名的 tombstone 地雷。
🔑 Takeaways
- Compaction 的選擇 = 在寫放大 / 讀放大 / 空間放大三角裡取捨，三者不可兼得。
- Size-tiered：省寫、犧牲讀與空間，寫重負載首選。
- Leveled：層內不重疊，省讀與空間、犧牲寫，讀重或省空間負載首選。
- Compaction 跟不上是 LSM 頭號維運風險：盯 L0 檔案數與 write stall。
- Tombstone 不能即時刪，回收延遲會拖慢 scan 並推高空間放大——大量刪除時要特別小心。
2026-07-01
- Q: 既然 leveled 讀與空間都比較好，為什麼不一律用 leveled、把 size-tiered 淘汰掉？
- A: 因為寫放大是真金白銀。Leveled 的逐層下沉可能讓寫放大到 STCS 的數倍，對寫重負載（時序、事件流）會直接吃掉 SSD 頻寬與壽命，甚至讓 compaction 跟不上。實務上是看負載挑角：寫爆量選 size-tiered，讀重或省空間選 leveled，RocksDB 也允許 L0 用 tiered、深層用 leveled 的混合策略。沒有免費的午餐，只有挑哪一角讓步。