農歷新年的最后一天，趁著假期看看代碼蒲障，順便做點筆記歹篓。時間上比較倉促瘫证，如有問題/疑問，歡迎指出庄撮。
簡介
LevelDB 的寫操作是 Append-Only 的背捌，新的數(shù)據(jù)寫入后，相應的舊數(shù)據(jù)就過期了洞斯。過期的數(shù)據(jù)需要被 Garbage Collection毡庆，不然數(shù)據(jù)文件的體積會持續(xù)膨脹，這是不可接受的烙如。
LevelDB 通過后臺線程的 compation 來對過期數(shù)據(jù)進行 Garbage Collection么抗。
分析
LevelDB 在執(zhí)行讀操作和寫操作的時候都有可能會調用 MaybeScheduleCompaction 函數(shù)，MaybeScheduleCompaction 有可能觸發(fā) compaction亚铁。
-
讀操作調用
MaybeScheduleCompaction（相關代碼）
if (have_stat_update && current->UpdateStats(stats)) {
MaybeScheduleCompaction();
}
- 當本次讀取的數(shù)據(jù)沒有在 MemTable 和 Immutable MemTable 命中蝇刀， 而是從 SST 文件查找時，
have_stat_update為true徘溢。（相關代碼 ） - 從 SST 文件查找時吞琐，如果查找的文件多于一個，則記錄下第一個查找的文件然爆，存放在
stats站粟。（相關代碼） -
UpdateStats函數(shù)根據(jù)步驟 2 記錄下的 SST 文件，allowed_seeks（一開始初始化為 2^30）減 1曾雕。當allowed_seeks <= 0且當前沒有其它文件等待 compaction 時卒蘸，記錄當前文件為待 compaction 的文件，并返回 true 翻默，否則返回 false。（相關代碼）
- 個人理解
瀏覽代碼的時候恰起，上面 2 和 3 的邏輯讓我不是很好理解修械。自己思考了一下，現(xiàn)在來嘗試回答一下（不一定完全準確）检盼。
LevelDB 的結構肯污，其實就是一個多級緩存的結構《滞鳎看看讀操作的順序就是很好理解這個多級緩存結構蹦渣。
- MemTable 是 Immutable MemTable 的緩存。
- Immutable MemTable 是 Level 0 的緩存貌亭。
- Level0 是 Level1 的緩存柬唯。
- Level1 是 Level2 的緩存。
- ...
從 SST 文件進行查找時圃庭，首先根據(jù)要查找的 Key 從文件的元數(shù)據(jù)（記錄著每一個 SST 文件 Key 范圍）找出每個 Level 對應的文件（某些 Level 可能沒有對應的文件锄奢，Level0 可能有多個對應文件）失晴。按照文件的新舊排序，就組成這個 Key 對應的一個多級緩存拘央。查找的時候也是按照這個順序涂屁，如果最新的 SST_n 文件命中目標，則直接返回結果灰伟，否則繼續(xù)查找 SST_n-1拆又、SST_n-2 ...
這種情況下，我們自然希望大部分請求都能在第一個 SST 文件命中栏账，這樣效率最高帖族。
如果有很多請求不能從第一個查找的文件命中目標，說明发笔，這個文件的 Key 并沒有緩存的價值盟萨，應該把這個文件向下一級 Level 合并掉，這樣可以減少無效的文件查找了讨。
- 寫操作調用
MaybeScheduleCompaction
寫操作會調用 MakeRoomForWrite 為即將寫入數(shù)據(jù)準備空間捻激。整個邏輯由下面幾個分支組成。（相關代碼）
-
!bg_error_.ok()：后臺任務有錯誤前计，直接返回錯誤胞谭。 -
allow_delay && versions_->NumLevelFiles(0) >= config::kL0_SlowdownWritesTrigger：正常的寫操作都allow_delay都為true。Level0 的文件數(shù)量超過了config::kL0_SlowdownWritesTrigger男杈，說明有可能寫入太多了丈屹，后臺線程來不及 Compaction，需要減慢寫操作伶棒。LevelDB 減慢寫操作的方法是旺垒，每個寫操作 sleep 1ms。 -
!force && (mem_->ApproximateMemoryUsage() <= options_.write_buffer_size)：MemTable 還有足夠的空間支持這次寫入肤无，直接返回先蒋。 -
imm != NULL： 來到這里說明 MemTable 的空間不夠了，且 Immutable MemTable 還存在（沒被 compaction 或 正在被 compaction）宛渐，需要等到compaction 完成竞漾。 -
versions_->NumLevelFiles(0) >= config::kL0_StopWritesTrigger： Level0 的文件實在太多了，停止寫入操作窥翩，等待 compaction 完成业岁。 -
來到這里說明：1. Level0 的文件數(shù)量在正常范圍內；2. Immutable MemTable 已經被 Compact寇蚊；3. MemTable 已經滿了笔时。此時會切換 MemTable，并調用
MaybeScheduleCompaction幔荒。
-
MaybeScheduleCompaction的實現(xiàn)（相關代碼 ）
MaybeScheduleCompaction函數(shù)的實現(xiàn)比較簡單：判斷幾個分支的情況糊闽，最后確定需要 Compaction 則將任務交交給后臺線程梳玫。
-
bg_compaction_scheduled_： 后臺線程已經在進行 compaction。 -
shutting_down_.Acquire_Load()：正在關閉數(shù)據(jù)庫右犹。 -
!bg_error_.ok()： 后臺任務錯誤提澎。 -
imm_ == NULL && manual_compaction_ == NULL && !versions_->NeedsCompaction()：不需要 compaction。 - 由后臺線程調用
DBImpl::BGWork進行compaction念链。DBImpl::BGWork直接調用了DBImpl::BackgroundCall盼忌。 （相關代碼）
-
DBImpl::BackgroundCall的實現(xiàn)（相關代碼）
- 調用
BackgroundCompaction執(zhí)行 compaction 。 - 調用
MaybeScheduleCompaction嘗試再觸發(fā) compaction掂墓。
-
DBImpl::BackgroundCompaction的實現(xiàn) （相關代碼）
- 持久化 Immutable MemTable：如果存在 Immutable MemTable谦纱，則調用
CompactMemTable進行 compaction。一個 Immutable MemTable 被持久化為 Level0 的一個 SST 文件君编。（相關代碼） -
非人工觸發(fā)跨嘉，調用
VersionSet::PickCompaction，獲得一個Compaction對象吃嘿。class Compaction封裝了本次要進行 compaction 的信息祠乃。(class Compaction的相關代碼 ）。人工觸發(fā)的 compaction 走另一個分支兑燥，暫不討論亮瓷。 -
VersionSet::PickCompaction選擇要進行 compaction 的文件的策略有兩種（相關代碼）：
1）size compaction，某一 Level 的數(shù)據(jù)太多了降瞳；
2）seek compaction嘱支，太多查詢沒有命中第一個 SST 文件。
另外還有一點要注意的就是 Level0 需要特殊處理挣饥，因為每個文件的 Key 范圍可能是相交的除师。 - LevelDB 的 compaction 是 Level_n-1 合并到 Level_n。一些比較特殊的情況扔枫，只需要把 Level_n-1 的文件**移到 ** Level_n 即可馍盟。
- 一般的 compaction 分下面幾步：
1）調用DoCompactionWork， 執(zhí)行 compaction缠导。
2）調用CleanupCompaction唐责，清理已經完成的 compaction 完成。
3）調用DeleteObsoleteFiles， 刪除無效文件饥脑。
小結
- Compaction 都是通過
MaybeScheduleCompaction函數(shù)觸發(fā)的。 - Compaction 是單線程異步完成的雄可。
-
seek compaction：LevelDB 在 SST 文件查找效率較低時（太多請求不在第一個 SST 文件命中购公，導致
allowed_seeks小于等于 0）會觸發(fā) compaction。 - LevelDB 切換 MemTable 會生成 Immutable MemTable泊交，需要將 Immutable MemTable 持久化乳讥，此時會觸發(fā) compaction柱查。
-
size compaction ：每次執(zhí)行 Compaction 的任務完成后，會嘗試再次調用
MaybeScheduleCompaction云石。因為有可能 level_n 的這次 compaction 導致 level_n+1 的 size 太大唉工，需要進行 compaction。 - Compaction 是單線程異步完成的汹忠，所以淋硝，LevelDB 的寫入速度在一定程度上受限于 compaction 的速度。對于寫入量比較平穩(wěn)的業(yè)務可能影響不大宽菜，但是對于經常有寫入峰值的業(yè)務谣膳，峰值時的寫入請求可能會受影響。
