跳转至

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 这些文件,对这些文件而言它是只读操作接口。