leveldb 源码分析 17¶
本系列《leveldb 源码分析》共有 22 篇文章，这是第十七篇
10 Version 分析之 2
10.5 Version::UpdateStats()¶
当 Get 操作直接搜寻 memtable 没有命中时，就需要调用 Version::Get() 函数从磁盘 load 数据文件并查找。如果此次 Get 不止 seek 了一个文件，就记录第一个文件到 stat 并返回。其后 leveldb 就会调用 UpdateStats(stat)。
Stat 表明在指定 key range 查找 key 时，都要先 seek 此文件，才能在后续的 sstable 文件中找到 key。
该函数是将 stat 记录的 sstable 文件的 allowed_seeks 减 1，减到 0 就执行 compaction。也就是说如果文件被 seek 的次数超过了限制，表明读取效率已经很低，需要执行 compaction 了。所以说 allowed_seeks 是对 compaction 流程的有一个优化。
函数声明：boolVersion::UpdateStats(const GetStats& stats)
函数逻辑很简单：
FileMetaData* f =stats.seek_file;
if (f != NULL) {
f->allowed_seeks--;
if (f->allowed_seeks <=0 && file_to_compact_ == NULL) {
file_to_compact_ = f;
file_to_compact_level_ =stats.seek_file_level;
return true;
}
}
return false;
变量 allowed_seeks 的值在 sstable 文件加入到 version 时确定，也就是后面将遇到的 VersionSet::Builder::Apply() 函数。
10.6 Version::GetOverlappingInputs()¶
它在指定 level 中找出和[begin, end]有重合的 sstable 文件，函数声明为：
void Version::GetOverlappingInputs(int level,
const InternalKey* begin, constInternalKey* end, std::vector<FileMetaData*>* inputs);
要注意的是，对于 level0，由于文件可能有重合，其处理具有特殊性。当在 level 0 中找到有 sstable 文件和[begin, end]重合时，会相应的将 begin/end 扩展到文件的 min key/max key，然后重新开始搜索。
了解了功能，下面分析函数实现代码，逻辑还是很直观的。
S1 首先根据参数初始化查找变量。
inputs->clear();
Slice user_begin, user_end;
if (begin != NULL) user_begin =begin->user_key();
if (end != NULL) user_end = end->user_key();
const Comparator* user_cmp =vset_->icmp_.user_comparator();
S2 遍历该层的 sstable 文件，比较 sstable 的{minkey,max key}和传入的[begin, end]，如果有重合就记录文件到 @inputs 中，需要对 level 0 做特殊处理。
for (size_t i = 0; i <files_[level].size(); ) {
FileMetaData* f =files_[level][i++];
const Slice file_start =f->smallest.user_key();
const Slice file_limit =f->largest.user_key();
if (begin != NULL &&user_cmp->Compare(file_limit, user_begin) < 0) {
//"f" 中的k/v全部在指定范围之前; 跳过
} else if (end != NULL&& user_cmp->Compare(file_start, user_end) > 0) {
//"f" 中的k/v全部在指定范围之后; 跳过
} else {
inputs->push_back(f); // 有重合，记录
if (level == 0) {
// 对于level 0，sstable文件可能相互有重叠，所以要检查新加的文件
// 是否范围更大，如果是则扩展范围重新开始搜索
if (begin != NULL&& user_cmp->Compare(file_start, user_begin) < 0) {
user_begin = file_start;
inputs->clear();
i = 0;
} else if (end != NULL&& user_cmp->Compare(file_limit, user_end) > 0) {
user_end = file_limit;
inputs->clear();
i = 0;
}
}
}
}
10.7 Version::OverlapInLevel()¶
检查是否和指定 level 的文件有重合，该函数直接调用了 SomeFileOverlapsRange()，这两个函数的声明为：
bool Version::OverlapInLevel(int level,const Slice*smallest_user_key,
const Slice* largest_user_key){
return SomeFileOverlapsRange(vset_->icmp_,(level > 0), files_[level],
smallest_user_key, largest_user_key);
}
bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
bool disjoint_sorted_files,
const std::vector<FileMetaData*>& files,const
Slice*smallest_user_key,
const Slice* largest_user_key);
所以下面直接分析 SomeFileOverlapsRange() 函数的逻辑，代码很直观。
disjoint_sorted_files=true，表明文件集合是互不相交、有序的，对于乱序的、可能有交集的文件集合，需要逐个查找，找到有重合的就返回 true；对于有序、互不相交的文件集合，直接执行二分查找。
// S1 乱序、可能相交的文件集合，依次查找
for (size_t i = 0; i <files.size(); i++) {
const FileMetaData* f =files[i];
if(AfterFile(ucmp,smallest_user_key, f) ||
BeforeFile(ucmp, largest_user_key, f)){
} else
return true; // 有重合
}
// S2 有序&互不相交，直接二分查找
uint32_t index = 0;
if (smallest_user_key != NULL) {
// Findthe earliest possible internal key smallest_user_key
InternalKeysmall(*smallest_user_key, kMaxSequenceNumber,kValueTypeForSeek);
index = FindFile(icmp, files,small.Encode());
}
if (index >= files.size())
// 不存在比smallest_user_key小的key
return false;
//保证在largest_user_key之后
return !BeforeFile(ucmp,largest_user_key, files[index]);
上面的逻辑使用到了 AfterFile() 和 BeforeFile() 两个辅助函数，都很简单。
static bool AfterFile(const Comparator* ucmp,
const Slice* user_key, constFileMetaData* f) {
return (user_key!=NULL&& ucmp->Compare(*user_key, f->largest.user_key())>0);
}
static bool BeforeFile(const Comparator* ucmp,
constSlice* user_key, const FileMetaData* f) {
return (user_key!=NULL&& ucmp->Compare(*user_key, f->smallest.user_key())<0);
}
10.8 Version::PickLevelForMemTableOutput()¶
函数返回我们应该在哪个 level 上放置新的 memtable compaction，这个 compaction 覆盖了范围[smallest_user_key,largest_user_key]。
该函数的调用链为：
DBImpl::RecoverLogFile/DBImpl::CompactMemTable -> DBImpl:: WriteLevel0Table->Version::PickLevelForMemTableOutput;
函数声明如下：
int Version::PickLevelForMemTableOutput(const Slice& smallest_user_key, constSlice& largest_user_key);
如果 level 0 没有找到重合就向下一层找，最大查找层次为 kMaxMemCompactLevel = 2。如果在 level 0or1 找到了重合，就返回 level 0。否则查找 level 2，如果 level 2 有重合就返回 level 1，否则返回 level 2。
函数实现：
int level = 0;
//level 0无重合
if (!OverlapInLevel(0,&smallest_user_key, &largest_user_key)) {
// 如果下一层没有重叠，就压到下一层，
// andthe #bytes overlapping in the level after that are limited.
InternalKeystart(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
InternalKeylimit(largest_user_key, 0, static_cast<ValueType>(0));
std::vector<FileMetaData*> overlaps;
while (level <config::kMaxMemCompactLevel) {
if (OverlapInLevel(level +1, &smallest_user_key, &largest_user_key))
break; // 检查level + 1层，有重叠就跳出循环
GetOverlappingInputs(level +2, &start, &limit, &overlaps); // 没理解这个调用
const int64_t sum =TotalFileSize(overlaps);
if (sum >kMaxGrandParentOverlapBytes) break;
level++;
}
}
return level;
这个函数在整个 compaction 逻辑中的作用在分析 DBImpl 时再来结合整个流程分析，现在只需要了解它找到一个 level 存放新的 compaction 就行了。
如果返回 level = 0，表明在 level 0 或者 1 和指定的 range 有重叠；如果返回 1，表明在 level2 和指定的 range 有重叠；否则就返回 2（kMaxMemCompactLevel）。
也就是说在 compactmemtable 的时候，写入的 sstable 文件不一定总是在 level 0，如果比较顺利，没有重合的，它可能会写到 level1 或者 level2 中。
10.9 小结¶
Version 是管理某个版本的所有 sstable 的类，就其导出接口而言，无非是遍历 sstable，查找 k/v。以及为 compaction 做些事情，给定 range，检查重叠情况。
而它不会修改它管理的 sstable 这些文件，对这些文件而言它是只读操作接口。