RocksDB的Compaction : Leveled Compaction 和 Universal Compaction

文章目錄

• Compaction算法
• • Leveled
  • Tiered
• RocksDB的Compaction
• • Leveled Compaction
  • • • which level to compact
      • subcompaction
  • Universal Compaction
  • • Compaction Picking Algorithm
    • • 前置條件
      • 1、由Space Amplification觸發的合并
      • 2、由Individual Size Ratio觸發的合并
      • 3、由 number of sorted runs 觸發的合并
      • 4、由 age of data 觸發的合并
  • FIFO Compaction
  • • FIFO Compaction with TTL

Compaction（稱為合并，或者壓縮），在LSM中，指的是把資料從Ln層，合并到Ln+1層，把重複的舊的資料删除。

Compaction算法

主要兩個類型的LSM樹合并算法：

Leveled

• leveled 合并，這個是RocksDB的預設政策

  leveled 算法的特點是以讀放大和寫放大為代價最小化空間放大。

  LSM-tree 可以看作是包含若幹 level 的序列，每個 level 是僅包括1個 sorted run。相鄰 level 的大小之比通常被我們稱為 fanout（扇出），當不同 level 之間的 fanout 相同時，LSM-tree 的寫放大最小。compaction 選擇 L(n) 的資料，與原有 L(n+1) 的資料進行合并，得到新的 L(n+1) 資料。每次 compaction 的最大寫放大系數等同于 fanout。

Tiered

• 一種替代合并政策，有時候被叫做“size tiered”或者“tiered”

  Tiered合并通過增加讀放大和空間放大，來最小化寫放大 。

  LSM-tree 依然可以看作是包含若幹 level 的序列，每個 level 包括 N 個 sorted run。L(n) 的 sorted run 大小是 L(n-1) 的 N 倍。compaction 通常選擇 L(n) 的資料合并得到新的 sorted run 輸出到 L(n+1)，但并不與 L(n+1) 的已有資料進行合并。每次 compaction 的最大寫放大系數是 1。

兩種算法的主要差别在于，leveled合并傾向于更加頻繁的把小的排序結果合并到大的裡面，而“tiered”等待多個大小接近的排序結果，然後把它們合并到一起。

• Tiered+Leveled

  Tiered+Leveled會有比leveled更小的寫放大，以及比teired更小的空間放大。

  Tiered+Leveled實作方式是一種混合實作，在小的層使用tiered，在大的層使用leveld。具體哪一層切換tiered和leveled可以非常靈活。

  RocksDB中的Leveled合并也是Tiered+Leveled。一個memtable落盤過程類似于tiered合并——memtable的輸出在L0建構一個新的排序結果并且不需要讀/重寫L0上已經存在的排序結果。根據level0_file_num_compaction_trigger的配置，L0可以有多個sort run，是以L0是Teired的。 其它層為Leveled。

RocksDB的Compaction

Rocksdb常用的Compaction模式有兩種：Leveled、Universal（tiered算法）。

Leveled Compaction

所有非0層都有 target sizes。合并的目的是限制這些層的資料大小。target sizes通常指數增加。

當L0的檔案數量到達level0_file_num_compaction_trigger，合并(compaction)就會被觸發，L0的檔案會被合并進L1。通常我們需要把所有L0的檔案都選上，因為他們通常會有交集：

合并過後，可能會使得L1的大小超過目标大小：

這個時候，我們會選擇至少一個檔案，然後把它跟L2有交集的部分進行合并。生成的檔案會放在L2：

如果結果仍舊超出下一層的目标大小，我們重複之前的操作 —— 選一個檔案然後把它合并到下一層:

然後

如果有必要，多個合并會并發進行：

最大同時進行的合并數由max_background_compactions控制。

which level to compact

當多個層觸發合并條件，RocksDB需要選擇哪個層先進行合并。對每個層通過下面方式生成一個分數：

• 對于非0層，分數是目前層的總大小除以目标大小。如果已經有檔案被選擇進行合并到下一層，這些檔案的大小不會算入總大小，因為他們馬上就要消失了。
• 對于level0，分數是檔案的總數量，除以level0_file_num_compaction_trigger，或者總大小除以max_bytes_for_level_base，這個數字可能更大一些。（如果檔案的大小小于level0_file_num_compaction_trigger，level 0 不會觸發合并，不管這個分數有多大）

我們比較每一層的分數，分數高的合并優先級更高。

subcompaction

level 0 由memtable flush而來， 每個檔案的key range會有重疊，不同于其他level，無法并行compaction。是以提出 subcompaction（次合并）來實作另一種并行。

通過一系列操作，将level 0到level 1的一次compaction按照合理的key range劃分成為互不覆寫，互不影響的多個subcompaction，并交給多個子線程并行去做，不同的子線程compaction結果輸出到不同的檔案中，等所有子線程完成自己的compaction後，主compaction線程進行結果整理合并，最終完成本次compaction。

https://blog.51cto.com/u_15057819/2647639

Universal Compaction

Universal合并方式是一種合并方式，面向那些需要用讀放大和空間放大，來換取更低的寫放大的場景。

通常認為 tiere 算法提供更好的寫放大表現，但是讀放大會變糟糕。憑直覺來看：在tiered存儲，每當一個更新被合并，他傾向于從小的sorted run移動到一個大很多的sorted run。每次合并都可能會指數級接近最後那個最大的sorted run。然而在leveled合并，一次更新更加可能通過一個小的排序結果，被合并進一個更大的排序結果，而不是直接作為一個較小的排序結果的一部分儲存起來。

最壞的情況下，sorted run數量會比leveled多很多。這會導緻讀資料的時候有更高的IO和更高的CPU消耗。

盡管如此，RocksDB仍舊提供了“tiered”家族的算分，Universal合并。使用者可以再leveled合并無法處理想要的寫速率的時候，可以嘗試這種合并方式。

使用 Universal Compaction 的 RocksDB 執行個體，可以看作是在時間上将資料劃分到不同的 sorted run，每個 sorted run 在時間上互不交疊。compaction 僅僅針對在時間上相鄰的 sorted run 進行，其輸出的時間範圍是原輸入的時間範圍的組合。

Compaction Picking Algorithm

假設我們有 sorted run

R1, R2, R3, ..., Rn
           

R1有DB最新的更新，而Rn有最老的DB更新。 sorted run 按照資料時間順序排序。由于 compaction 輸出與輸入的時間範圍相同，compaction 操作不會改變 sorted run 的排序。

前置條件

Compaction 觸發前置條件：n >= options.level0_file_num_compaction_trigger，即 sorted run 的數量達到門檻值options.level0_file_num_compaction_trigger。 （參數中的file并不準确，應該為sorted run）

如果前置條件滿足了，還有四個條件。滿足其中任意一個都可以觸發一個合并：

1、由Space Amplification觸發的合并

如果預計的空間放大比例（size amplification ratio）大于options.compaction_options_universal.max_size_amplification_percent / 100，所有的檔案會被合并為一個sorted run。

計算公式如下：

size amplification ratio = (size(R1) + size(R2) + ... size(Rn-1)) / size(Rn)
           

以 options.compaction_options_universal.max_size_amplification_percent = 25，options.level0_file_num_compaction_trigger = 1 的配置參數為例：

1
1 1  =>  2
1 2  =>  3
1 3  =>  4
1 4
1 1 4  =>  6
1 6
1 1 6  =>  8
1 8
1 1 8
1 1 1 8  =>  11
1 11
1 1 11
1 1 1 11  =>  14
1 14
1 1 14
1 1 1 14
1 1 1 1 14  =>  18
           

2、由Individual Size Ratio觸發的合并

size_ratio_trigger = (100 + options.compaction_options_universal.size_ratio) / 100
           

我們從R1開始，如果size(R2) / size(R1) <= size_ratio_trigger, 那麼（R1，R2）被合并到一起。我們以此繼續決定R3是不是可以加進來。如果size(R3) / size(R1+r2) <= size_ratio_trigger，R3應該被包含，得到(R1,R2,R3)。然後我們對R4做同樣的事情。我們一直用所有已有的大小總和，跟下一個排序結果比較，直到size_ratio_trigger條件不滿足。

以 options.compaction_options_universal.size_ratio = 0，options.level0_file_num_compaction_trigger = 5 參數配置為例：

1 1 1 1 1  =>  5
1 5  (no compaction triggered)
1 1 5  (no compaction triggered)
1 1 1 5  (no compaction triggered)
1 1 1 1 5  => 4 5
1 4 5  (no compaction triggered)
1 1 4 5  (no compaction triggered)
1 1 1 4 5 => 3 4 5
1 3 4 5  (no compaction triggered)
1 1 3 4 5 => 2 3 4 5
           

3、由 number of sorted runs 觸發的合并

如果sorted runs的數量達到了options.level0_file_num_compaction_trigger，但是沒有觸發前面提到的size amplification 或者space amplification trigger。那麼RocksDB将嘗試進行 sorted run 數量不超過options.compaction_options_universal.max_merge_width 的 compaction，以使得 sorted run 數量少于 options.level0_file_num_compaction_trigger。

4、由 age of data 觸發的合并

對于Universal Compaction,基于時間的compaction政策是最高優先級的，如果我們嘗試compaction，一定會先檢查時間條件，如果有檔案存在的時長大于options.periodic_compaction_seconds，RocksDB将會從舊到新來挑選sorted runs 來compaction，直到某個更新的sorted runs 正在被compaction，這些檔案将會被合并到最底層。

FIFO Compaction

FIFO Style Compaction 是最簡單的合并政策。很适合用于儲存低開銷的事件日志資料（例如查詢日志）。當檔案總大小超過配置值 CompactionOptionsFIFO::max_table_files_size （預設值為 1GB) 時，最早的 SST 檔案将會被删除。

使用FIFO時，所有的檔案都位于 L0，是以SST檔案過多，導緻查詢性能急劇下降。

開啟 CompactionOptionsFIFO.allow_compaction 參數，可以觸發 L0 IntraCompaction，每次至少選取 level0_file_num_compaction_trigger 個 SST 檔案進行合并，進而減少檔案數量。

FIFO Compaction with TTL

FIFO Compaction with TTL 在 FIFO compaction 的基礎之上，提供 SST 檔案級别的過期删除功能。當 SST 的最新的 key 存在時間超過 mutable_cf_options.ttl，則該 SST 檔案将會在 TTL compaction 中被删除。

參考：

https://github.com/facebook/rocksdb/wiki/Compaction

https://www.jianshu.com/p/333ec61051f0

https://zhuanlan.zhihu.com/p/165137544

https://github.com/johnzeng/rocksdb-doc-cn/blob/master/doc/Compaction.md