以RocksDB為存儲引擎的MyRocks是近幾年流行起來的MySQL分支，在Facebook等公司廣泛使用，網易杭研的資料庫內核團隊從2018年初開始系統研究MyRocks，目前已在內部進行小範圍推廣使用，效果比較理想。

在調研、測試和試用期間，積累了一些經驗，包括技術實現等。本系列想跟大家分享我們組內小夥伴做的LevelDB調研輸出，這是第四篇，詳細介紹LevelDB Compaction機制。

第三篇鏈接：

溫正湖：LevelDB設計與實現 - 緩存機制?

zhuanlan.zhihu.com圖標

Compaction

LevelDB Compaction分兩種：

  • minor compaction
  • major compaction

以下三個條件滿足一個即可發起Compaction：

  1. imm_ != NULL 表示需要將Memtable dump成SSTable，發起Minor Compaction。
  2. manual_compaction_ != NULL 表示手動發起Compaction。
  3. versions_->NeedsCompaction函數返回True。

先介紹minor compaction，minor compaction即immutable memtable dump成sstable文件。無論是哪一種compaction,入口點都是：

DBImpl::MaybeScheduleCompaction()

minor compaction主要做兩件事情：1、構造sstable2、新的sstable文件寫入哪一層。主要函數調用流程如下圖：

新產生出來的sstable 並不一定總是處於level 0， 儘管大多數情況下，處於level 0。新創建的出來的sstable文件應該位於那一層呢？ 由PickLevelForMemTableOutput 函數來計算。

從策略上要盡量將新compact的文件推至高level，畢竟在level 0 需要控制文件過多，compaction IO和查找都比較耗費，另一方面也不能推至過高level，一定程度上控制查找的次數，而且若某些範圍的key更新比較頻繁，後續往高層compaction IO消耗也很大。 所以PickLevelForMemTableOutput就是個權衡折中。如果新生成的sstable和Level 0的sstable有交疊，新產生的sstable就直接加入level 0，否則根據一定的策略，向上推到Level1 甚至是Level 2，但是最高推到Level2，這裡有一個控制參數：kMaxMemCompactLevel。判斷sstable文件之間key是否有重疊要用到前面介紹的數據結構FileMetaData。

除了minor compaction,另外一種compaction就是major compaction。那什麼情況下發起major compaction呢？看下面這個函數：

bool NeedsCompaction() const {
Version* v = current_;
return (v->compaction_score_ >= 1) || (v->file_to_compact_ != NULL);
}

  • 文件數目太多或者某一層級文件總大小過大，會觸發compaction

如果某一層級文件的個數太多（指的是level0）， 或者某一層級的文件總大小太大，超過門限值，則設置v->compaction_score為一個大於1的數。如果存在某個或者某幾個層級的score大於等於1，選擇score最高的那個level。

  • seek次數太多，觸發compaction

還有一種情況也可能會引起Compaction，就是某個文件seek的次數太多。除了level 0以外，任何一個level的文件內部是有序的，文件之間也是有序的。但是level（n）和level（n＋1）中的兩個文件的key可能存在交叉。正是因為這種交叉，查找某個key值的時候，level（n） 的查找無功而返，而不得不去level(n＋1)查找。

我們考慮尋找某一個key，如果查找level(n) ,但是沒找到，然後去level(n+1)查找，結果找到了，那麼對level (n)的某個文件而言，該文件就意味著有一次未命中。

我們可以很容易想到，如果查找了多次，某個文件不得不查找，卻總也找不到，總是去高一級的level，才能找到。這說明該層級的文件和上一級的文件，key的範圍重疊的很嚴重，這是不合理的，會導致效率的下降。因此，需要對該level 發起一次major compaction，減少 level 和level ＋ 1的重疊情況。

這就是所謂的 Seek Compaction。

對於seek觸發的compaction, 哪個文件無效seek的次數到了閾值，那個文件就是level n的參與compaction的文件。而size 觸發的compaction稍微複雜一點，它需要考慮上一次compaction做到了哪個key，什麼地方，然後大於該key的第一個文件即為level n的參與compaction的文件。

對於n >0的情況，初選情況下level n的參與compaction文件只會有1個，如果n＝0，因為level 0的文件之間，key可能交叉重疊，因此，根據選定的level 0的該文件，得到該文件負責的最小key和最大key，找到所有和這個key 區間有交疊的level 0文件，都加入到參戰文件。

未完待續。。。

推薦閱讀：

相關文章