Compaction 的作用

因為 LevelDB 的增刪改都是通過追加寫來實現(xiàn)的，所以需要通過后臺線程的 compaction 來：

1. 清理過期（舊版本或者已刪除）的數(shù)據(jù)。
2. 維護數(shù)據(jù)的有序性。

Compaction 的觸發(fā)

除了從外部調(diào)用 CompactRange，LevelDB 有幾種情況會自動觸發(fā) compaction：

1. 當(dāng) MemTable 的大小達到閾值時，進行 MemTable 切換，然后需要將 Immutable MemTable 刷到外存上 —— 一般稱之為 Minor Compaction。
2. 當(dāng) level-n 的 SSTable 超過限制，level-n 和 level-n+1 的 SSTable 會進行 compaction —— 一般稱之為 Major Compaction。
   1. level-0 是通過 SSTable 的數(shù)量來判斷是否需要 compaction。
   2. level-n(n > 0) 是通過 SSTable 的大小來判斷是否需要 compaction。

Minor Compaction

Minor Compaction 比較簡單，基本代碼路徑是：DBImpl::CompactMemTable => DBImpl::WriteLevel0Table => BuildTable。

Major Compaction

1. 每次 compaction 結(jié)束，更新 manifest 之后，都會調(diào)用 VersionSet::Finalize 計算下一次要進行 major compaction 的 level。
2. 每次 major compaction 開始時，調(diào)用 VersionSet::PickCompaction 計算需要進行 compaction 的 SSTable。
3. 如果選中的 level-n 的 SSTable 和 level-n+1 的 SSTable 的 key 范圍沒有重疊，可以直接將 level-n 的 SSTable “移動”到 level-n+1，只需要修改 Manifest。
4. 否則，調(diào)用 DBImpl::DoCompactionWork 對 level-n 和 level-n+1 的 SSTable 進行多路歸并。

Compaction 的問題

Compaction 會對 LevelDB 的性能和穩(wěn)定性帶來一定影響：

1. 消耗 CPU：對 SSTable 進行解析、解壓、壓縮。
2. 消耗 I/O：大量的 SSTable 批量讀寫，十幾倍甚至幾十倍的寫放大會消耗不少 I/O，同時縮短 SSD 的壽命（SSD 的寫入次數(shù)是有限的）。
3. 緩存失效：刪除舊 SSTable，生成新 SSTable。新 SSTable 的首次請求無法命中緩存，可能引發(fā)系統(tǒng)性能抖動。

常見的做法是，控制 compaction 的速度（比如 RocksDB 的 Rate Limiter），讓 compaction 的過程盡可能平緩，不要引起 CPU、I/O、緩存失效的毛刺。
這種做法帶來一個問題：compaction 的速度應(yīng)該控制在多少？Compaction 的速度如果太快，會影響系統(tǒng)性能；Compaction 的速度如果太慢，會阻塞寫請求。
這個速度和具體的硬件能力、工作負載高度相關(guān)，往往只能設(shè)置一個“經(jīng)驗值”，比較難通用。同時這種做法只能在一定程度上減少系統(tǒng)毛刺、抖動，Compaction 帶來的寫放大依然是那么大。

寫放大簡單分析

• +1 - WAL 的寫入。
• +1 - Immutable Memtable 寫入到 level-0 文件。
• +2 - level-0 和 level-1 的 compaction（level-0 的每個 SSTable 的 key 范圍是重疊的。一般控制 level-0 和 level-1 的數(shù)據(jù)大小是一樣的，每次拿全量 level-0 的數(shù)據(jù)和全量 level-1 的數(shù)據(jù)進行 compaction）。
• +11 - level-n 和 level-n+1 合并的寫入（n >= 1，默認情況下，level-n+1 的數(shù)據(jù)大小是 level-n 的 10 倍）。

所以，總的寫放大是 4 + 11(n-1) = 11n - 7 倍。

假設(shè)有 5 個 level，寫放大最大是 48 倍——也就是說，外部寫入 1GB 的數(shù)據(jù)，內(nèi)部觀察到的 I/O 寫流量會有 48GB。

關(guān)于 LSM-Tree 的寫放大有不少論文進行了詳細的介紹、討論和提出優(yōu)化方案，比如：

1. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging - 這篇論文將各種 compaction 方式和影響介紹得非常清楚。
2. WiscKey: Separating Keys from Values in SSD-conscious Storage - 通過將鍵值分離，大大減少了寫放大。
3. ...

小結(jié)

1. 根據(jù)實際經(jīng)驗，在大部分場景下， compaction 帶來的問題不是特別明顯。
2. 一些會有突發(fā)流量的情況，很容易造成 compaction 的速度跟不上實際寫入的速度，導(dǎo)致寫失敗。
3. Write intensive 的場景，寫放大縮短了 SSD 的壽命也是個問題。