1 簡述
這一篇我們來解析leveldb的Compaction機制，要把這個講清楚赊时，需要回答下面的問題：
- 什么是Compaction?
- 什么時候會觸發(fā)Compaction?
- Compact到底怎么做? 選擇哪一個Layer和哪些Table文件做Compact? 具體怎么壓縮?
什么是Compaction?
隨著Put/Delete操作增多镊辕，sstable文件會越來越多着倾，占用的磁盤空間也越來越大慎璧。刪除無效的key(被標(biāo)記刪除的key卓嫂，被新版本覆蓋的老版本的key)瓮具，然后重新生成sstable文件槽袄，可以有效減少sstable文件的數(shù)量给僵，這個過程就是Compaction毫捣。
什么時候會觸發(fā)Compaction?
Compaction的入口函數(shù)是MaybeScheduleCompaction()，觸發(fā)的時機：
- Open()
打開數(shù)據(jù)庫時帝际，會發(fā)生Recover蔓同，重做log文件中的寫操作，這可能會引發(fā)Compaction蹲诀。 - Write()
mem寫滿時斑粱，會把mem改成imm，然后刷入sstable脯爪，這可能會觸發(fā)Compaction则北。 - Get()
leveldb對Get()進行統(tǒng)計，當(dāng)一個文件多次未命中key時痕慢，我們可以認(rèn)為這是一個冷數(shù)據(jù)文件尚揣，對這個文件進行Compact，把它推到更高的level掖举，減少它被查找的機會快骗，從而提高Get()效率。 - Iterator
與Get()類似塔次，使用Iterator訪問數(shù)據(jù)時方篮，也會進行key的命中統(tǒng)計，觸發(fā)對冷數(shù)據(jù)sstable的Compaction励负。 - Compact()
主動調(diào)用Compact(begin, Slice)藕溅，所有Layer當(dāng)中key值與[begin,end]有重疊的sstable都會進行Compact。 - BackgroundCompaction()
壓縮過程會在level+1產(chǎn)生新的sstable文件熄守，可能再次觸發(fā)Compaction
Compact到底怎么做? 選擇哪一個Layer和哪些Table文件做Compact? 具體怎么壓縮?
leveldb是在后臺線程執(zhí)行Compact蜈垮，目前只允許單線程耗跛，也就是說Compact只能串行執(zhí)行。
入口函數(shù)是DBImpl::BackgroundCompaction()攒发，流程如下：
1) if (imm != nullptr)调塌，調(diào)用CompactMemTable()，把imm生成sstable文件落盤惠猿。
2) 選擇進行Compact的layer和文件：
if (is_manual) { // 優(yōu)先考慮主動調(diào)用Compact()操作
選定所有l(wèi)ayer當(dāng)中與[begin,end]區(qū)間有重疊的sstable文件羔砾；
} else {
調(diào)用VersionSet::PickCompaction()選擇最需要壓縮的layer和文件，具體算法下面代碼有解釋偶妖；
}
3) 進行壓縮
if (IsTrivialMove()) { // 修改文件layer就可以
修改文件layer姜凄；
把version修改歷史生成record寫入MANIFEST文件；
} else { // 真正需要壓縮
生成InputIterator{inpus}趾访，遍歷key态秧，刪除無效數(shù)據(jù)(已經(jīng)被刪除的key，被新版本覆蓋的key)扼鞋，生成sstable文件申鱼；
Compact過程中，除了正常的sstable文件大小限制之外云头，還要判斷生成的level+1文件與level+2層文件的重疊情況捐友；
如果重疊的文件過多，則結(jié)束當(dāng)前文件溃槐，開啟新的文件匣砖，避免將來level+1向level+2壓縮時涉及的文件太多；
}
2 源碼解析
VersionSet::LogAndApply()觸發(fā)Compaction
leveldb通過VersionSet::PickCompaction()來選擇要壓縮的Layer和Table昏滴，怎么做到的呢猴鲫？
原來，在每個Version生成的時候谣殊，會計算哪個Layer需要進行Compaction变隔，方法是計算每個layer的compaction_score，選擇得分最高的layer蟹倾，這是由LogAndApply()函數(shù)完成的：
LogAndApply() 生成Version的最后一步是調(diào)用VersionSet::Finalize()匣缘，計算compaction_score：
1）對于level-0，因為每次read都要對所有文件進行merge鲜棠，文件太多影響讀效率肌厨，因此主要考慮文件數(shù)據(jù)量，
compaction_score = file_num/kL0_CompactionTrigger
2）對于其他level豁陆，因為文件之間key不重疊柑爸，主要考慮文件大小，
compaction_score = file_size/MaxBytesForLevel()
最后選出compaction_score最高的layer作為compaction_level盒音。
注：當(dāng)max_compaction_score>1時表鳍，需要Compaction馅而，否則不需要。
調(diào)用LogAndApply()生成Version的時機：
1) Open數(shù)據(jù)庫時譬圣，會合并歷史VersionEdit瓮恭，生成新的Version。
2) Compaction過程厘熟，會生成新的Version屯蹦。
具體是BackgroundCompaction()、CompactMemTable()绳姨、InstallCompactionResults()這幾個函數(shù)登澜。
DBImpl::Get()觸發(fā)Compaction，把冷數(shù)據(jù)推導(dǎo)更高的Level：
// Get()入口
Status DBImpl::Get(const ReadOptions& options, const Slice& key, std::string* value) {
....
// 調(diào)用VersionSet::Get()查找key
// VersionSet::Get()在查找key之余飘庄，會通過GetStat返回查找過程中第一個未命中key的文件
s = current->Get(options, lkey, value, &stats);
......
// 根據(jù)GetStat判斷是否觸發(fā)Compaction脑蠕，判斷標(biāo)準(zhǔn) f->allowed_seeks<0
if (have_stat_update && current->UpdateStats(stats)) {
MaybeScheduleCompaction();
}
// f->allowed_seeks這個值是怎么來的呢?
// 原來是在sstable文件加入到Version時，會根據(jù)文件大小跪削，設(shè)置查找次數(shù) allowed_seeks空郊，參考：
void VersionSet::Builder::Apply(VersionEdit* edit) {
......
// We arrange to automatically compact this file after
// a certain number of seeks. Let's assume:
// (1) One seek costs 10ms
// (2) Writing or reading 1MB costs 10ms (100MB/s)
// (3) A compaction of 1MB does 25MB of IO:
// 1MB read from this level
// 10-12MB read from next level (boundaries may be misaligned)
// 10-12MB written to next level
// This implies that 25 seeks cost the same as the compaction
// of 1MB of data. I.e., one seek costs approximately the
// same as the compaction of 40KB of data. We are a little
// conservative and allow approximately one seek for every 16KB
// of data before triggering a compaction.
f->allowed_seeks = static_cast<int>((f->file_size / 16384U));
if (f->allowed_seeks < 100) f->allowed_seeks = 100;
......
}
Iterator觸發(fā)Compaction，刪除過期key(被新版本覆蓋)：
// 調(diào)用DBImpl::NewIterator()生成一個Iterator切揭，而后遍歷key，每隔一段會讀取一些樣本锁摔，判斷是否過期數(shù)據(jù)：
bool DBIter::ParseKey(ParsedInternalKey* ikey) {
Slice k = iter_->key();
size_t bytes_read = k.size() + iter_->value().size();
while (bytes_until_read_sampling_ < bytes_read) {
bytes_until_read_sampling_ += RandomCompactionPeriod(); // [0,2*kReadBytesPeriod]之間的隨機數(shù)
db_->RecordReadSample(k); // 讀取數(shù)據(jù)樣本廓旬，判斷是否需要Compact
}
assert(bytes_until_read_sampling_ >= bytes_read);
bytes_until_read_sampling_ -= bytes_read;
......
}
// DBImpl::RecordReadSample() 實質(zhì)上是調(diào)用Version::RecordReadSample()調(diào)用統(tǒng)計樣本
void DBImpl::RecordReadSample(Slice key) {
MutexLock l(&mutex_);
if (versions_->current()->RecordReadSample(key)) {
MaybeScheduleCompaction();
}
}
// 真正干活的地方
bool Version::RecordReadSample(Slice internal_key) {
ParsedInternalKey ikey;
if (!ParseInternalKey(internal_key, &ikey)) {
return false;
}
struct State {
GetStats stats; // Holds first matching file
int matches;
static bool Match(void* arg, int level, FileMetaData* f) {
State* state = reinterpret_cast<State*>(arg);
state->matches++;
if (state->matches == 1) {
// 當(dāng)一個key存在多個版本時，最先讀到的也最老的版本
// Remember first match.
state->stats.seek_file = f;
state->stats.seek_file_level = level;
}
// We can stop iterating once we have a second match.
return state->matches < 2;
}
};
State state;
state.matches = 0;
ForEachOverlapping(ikey.user_key, internal_key, &state, &State::Match);
// Must have at least two matches since we want to merge across
// files. But what if we have a single file that contains many
// overwrites and deletions? Should we have another mechanism for
// finding such files?
if (state.matches >= 2) { // key存在多個版本
// 1MB cost is about 1 seek (see comment in Builder::Apply).
return UpdateStats(state.stats); // 更新Compaction統(tǒng)計谐腰，認(rèn)為key的第一個(最老)版本所在的文件未命中
}
return false;
}
選擇Layer和Table的過程頭緒比較多孕豹，具體實施Compaction的過程相對比較好理解，用下面這張圖表述Compaction的整個過程:
leveldb_compaction
