leveldb 源码分析 18¶

本系列《leveldb 源码分析》共有 22 篇文章，这是第十八篇

11 VersionSet 分析之 1 Version 之后就是 VersionSet，它并不是 Version 的简单集合，还肩负了不少的处理逻辑。这里的分析不涉及到 compaction 相关的部分，这部分会单独分析。包括 log 等各种编号计数器，compaction 点的管理等等。

11.1 VersionSet 接口¶

1 首先是构造函数，VersionSet 会使用到 TableCache，这个是调用者传入的。TableCache 用于 Get k/v 操作。

VersionSet(const std::string& dbname, const Options* options,
           TableCache*table_cache, const InternalKeyComparator*);

VersionSet 的构造函数很简单，除了根据参数初始化，还有两个地方值得注意： N1 next_file_number_ 从 2 开始； N2 创建新的 Version 并加入到 Version 链表中，并设置 CURRENT=新创建 version；其它的数字初始化为 0，指针初始化为 NULL。 2 恢复函数，从磁盘恢复最后保存的元信息

Status Recover();

3 标记指定的文件编号已经被使用了

void MarkFileNumberUsed(uint64_t number);

逻辑很简单，就是根据编号更新文件编号计数器：

if (next_file_number_ <= number) 
     next_file_number_ = number + 1;

4 在 current version 上应用指定的 VersionEdit，生成新的 MANIFEST 信息，保存到磁盘上，并用作 current version。 要求：没有其它线程并发调用；要用于 mu；

Status LogAndApply(VersionEdit* edit, port::Mutex* mu)EXCLUSIVE_LOCKS_REQUIRED(mu);

5 对于@v 中的@key，返回 db 中的大概位置

uint64_t ApproximateOffsetOf(Version* v, const InternalKey& key);

6 其它一些简单接口，信息获取或者设置，如下：

//返回current version
Version* current() const {
     return current_; 
}   

// 当前的MANIFEST文件号  
uint64_t ManifestFileNumber() const {
     return manifest_file_number_;
} 

// 分配并返回新的文件编号  
uint64_t NewFileNumber() {
     return next_file_number_++; 
} 

// 返回当前log文件编号  
uint64_t LogNumber() const { 
     return log_number_; 
}

// 返回正在compact的log文件编号，如果没有返回0  
uint64_t PrevLogNumber() const {
     return prev_log_number_; 
}

// 获取、设置last sequence，set时不能后退  
uint64_t LastSequence() const {
     return last_sequence_; 
}

void SetLastSequence(uint64_t s) {  
    assert(s >=last_sequence_);  
    last_sequence_ = s;  
}  

// 返回指定level中所有sstable文件大小的和  
int64_t NumLevelBytes(int level) const;  

// 返回指定level的文件个数  
int NumLevelFiles(int level) const;  

// 重用@file_number，限制很严格：@file_number必须是最后分配的那个  
// 要求: @file_number是NewFileNumber()返回的.  

void ReuseFileNumber(uint64_t file_number) {  
    if (next_file_number_ ==file_number + 1) next_file_number_ = file_number;  
}  

// 对于所有level>0，遍历文件，找到和下一层文件的重叠数据的最大值(in bytes)  
// 这个就是Version:: GetOverlappingInputs()函数的简单应用  
int64_t MaxNextLevelOverlappingBytes(); 

// 获取函数，把所有version的所有level的文件加入到@live中  
void AddLiveFiles(std::set<uint64_t>* live);  

// 返回一个可读的单行信息——每个level的文件数，保存在*scratch中  
struct LevelSummaryStorage {char buffer[100]; };  
const char* LevelSummary(LevelSummaryStorage* scratch) const;

下面就来分析这两个接口 Recover、LogAndApply 以及 ApproximateOffsetOf。

11.2 VersionSet::Builder 类¶

Builder 是一个 内部辅助类，其主要作用是： 1 把一个 MANIFEST 记录的元信息应用到版本管理器 VersionSet 中； 2 把当前的版本状态设置到一个 Version 对象中。

11.2.1 成员与构造

Builder 的 vset_ 与 base_ 都是调用者传入的，此外它还为 FileMetaData 定义了一个比较类 BySmallestKey，首先依照文件的 min key，小的在前；如果 min key 相等则 file number 小的在前。

typedefstd::set<FileMetaData*, BySmallestKey> FileSet;  
// 这个是记录添加和删除的文件  
struct LevelState { 
  std::set<uint64_t>deleted_files;  
  // 保证添加文件的顺序是有效定义的
  FileSet* added_files;   
};  
VersionSet* vset_;  
Version* base_;  
LevelStatelevels_[config::kNumLevels];  

// 其接口有3个：  
void Apply(VersionEdit* edit);  
void SaveTo(Version* v);  
void MaybeAddFile(Version* v, int level, FileMetaData* f);

构造函数执行简单的初始化操作，在析构时，遍历检查 LevelState::added_files，如果文件引用计数为 0，则删除文件。

11.2.2 Apply()

函数声明：voidApply(VersionEdit* edit)，该函数将 edit 中的修改应用到当前状态中。注意除了 compaction 点直接修改了 vset_，其它删除和新加文件的变动只是先存储在 Builder 自己的成员变量中，在调用 SaveTo(v) 函数时才施加到 v 上。

S1 把 edit 记录的 compaction 点应用到当前状态

edit->compact_pointers_ => vset_->compact_pointer_

S2 把 edit 记录的已删除文件应用到当前状态

edit->deleted_files_ => levels_[level].deleted_files

S3 把 edit 记录的新加文件应用到当前状态，这里会初始化文件的 allowed_seeks 值，以在文件被无谓 seek 指定次数后自动执行 compaction，这里作者阐述了其设置规则。

for (size_t i = 0; i <edit->new_files_.size(); i++) {  
    const int level =edit->new_files_[i].first;  
    FileMetaData* f = newFileMetaData(edit->new_files_[i].second);  
    f->refs = 1;  
    f->allowed_seeks = (f->file_size /16384); // 16KB-见下面  
    if (f->allowed_seeks <100) f->allowed_seeks = 100;  
    levels_[level].deleted_files.erase(f->number); // 以防万一  
    levels_[level].added_files->insert(f);  
}

值 allowed_seeks 事关 compaction 的优化，其计算依据如下，首先假设：

1 一次 seek 时间为 10ms 2 写入 10MB 数据的时间为 10ms（100MB/s） 3 compact 1MB 的数据需要执行 25MB 的 IO ->从本层读取 1MB ->从下一层读取 10-12MB（文件的 key range 边界可能是非对齐的） ->向下一层写入 10-12MB

这意味这 25 次 seek 的代价等同于 compact 1MB 的数据，也就是一次 seek 花费的时间大约相当于 compact 40KB 的数据。基于保守的角度考虑，对于每 16KB 的数据，我们允许它在触发 compaction 之前能做一次 seek。

11.2.3 MaybeAddFile()

函数声明：

voidMaybeAddFile(Version* v, int level, FileMetaData* f);

该函数尝试将 f 加入到 levels_[level] 文件 set 中。要满足两个条件：

1 文件不能被删除，也就是不能在 levels_[level].deleted_files 集合中； 2 保证文件之间的 key 是连续的，即基于比较器 vset_->icmp_，f 的 min key 要大于 levels_[level] 集合中最后一个文件的 max key；

11.2.4 SaveTo()

把当前的状态存储到 v 中返回，函数声明：

void SaveTo(Version* v);

函数逻辑：For 循环遍历所有的 level[0, config::kNumLevels-1]，把新加的文件和已存在的文件 merge 在一起，丢弃已删除的文件，结果保存在 v 中。对于 level> 0，还要确保集合中的文件没有重合。 S1 merge 流程

// 原文件集合
conststd::vector<FileMetaData*>& base_files = base_->files_[level];   
std::vector<FileMetaData*>::const_iterator base_iter =base_files.begin();  
std::vector<FileMetaData*>::const_iterator base_end =base_files.end();  
const FileSet* added =levels_[level].added_files;  
v->files_[level].reserve(base_files.size()+ added->size());  
for (FileSet::const_iteratoradded_iter = added->begin();
    added_iter !=added->end(); ++added_iter) {  
    //加入base_中小于added_iter的那些文件  

      for(std::vector<FileMetaData*>::const_iterator bpos = std::upper_bound(base_iter,base_end,*added_iter, cmp);  
        base_iter != bpos;++base_iter) { 
        // base_iter逐次向后移到  
        MaybeAddFile(v, level,*base_iter);  
    }  
    // 加入added_iter  
    MaybeAddFile(v, level,*added_iter); 
 }  

   // 添加base_剩余的那些文件  
   for (; base_iter != base_end;++base_iter) 
      MaybeAddFile(v, level, *base_iter);

对象 cmp 就是前面定义的比较仿函数 BySmallestKey 对象。 S2 检查流程，保证 level>0 的文件集合无重叠，基于 vset_->icmp_，确保文件 i-1 的 max key < 文件 i 的 min key。

11.3 Recover()¶

对于 VersionSet 而言，Recover 就是根据 CURRENT 指定的 MANIFEST，读取 db 元信息。这是 9.3 介绍的 Recovery 流程的开始部分。

11.3.1 函数流程

下面就来分析其具体逻辑。

S1 读取 CURRENT 文件，获得最新的 MANIFEST 文件名，根据文件名打开 MANIFEST 文件。CURRENT 文件以\n 结尾，读取后需要 trim 下。

std::string current; // MANIFEST文件名  
ReadFileToString(env_, CurrentFileName(dbname_), ¤t);  
std::string dscname = dbname_ + "/" + current;  
SequentialFile* file;  
env_->NewSequentialFile(dscname, &file);

S2 读取 MANIFEST 内容，MANIFEST 是以 log 的方式写入的，因此这里调用的是 log::Reader 来读取。然后调用 VersionEdit::DecodeFrom，从内容解析出 VersionEdit 对象，并将 VersionEdit 记录的改动应用到 versionset 中。读取 MANIFEST 中的 log number, prev log number, nextfile number, last sequence。

Builder builder(this, current_);  
while (reader.ReadRecord(&record, &scratch) && s.ok()) {  
      VersionEdit edit;  
      s = edit.DecodeFrom(record);  
      if (s.ok())builder.Apply(&edit);  
      // log number, file number, …逐个判断  
      if (edit.has_log_number_) { 
          log_number =edit.log_number_;  
          have_log_number = true;  
      }  
      … …  
}

S3 将读取到的 log number, prev log number 标记为已使用。

MarkFileNumberUsed(prev_log_number);
MarkFileNumberUsed(log_number);

S4 最后，如果一切顺利就创建新的 Version，并应用读取的几个 number。

if (s.ok()) {  
    Version* v = newVersion(this);  
    builder.SaveTo(v);  
    // 安装恢复的version  
    Finalize(v);  
    AppendVersion(v);  
    manifest_file_number_ =next_file;  
    next_file_number_ = next_file+ 1;  
    last_sequence_ = last_sequence;  
    log_number_ = log_number;  
    prev_log_number_ =prev_log_number;  
}

Finalize(v) 和 AppendVersion(v) 用来安装并使用 version v，在 AppendVersion 函数中会将 current version 设置为 v。下面就来分别分析这两个函数。

11.3.2 Finalize()

函数声明：

void Finalize(Version*v);

该函数依照规则为下次的 compaction 计算出最适用的 level，对于 level 0 和>0 需要分别对待，逻辑如下。

S1 对于 level 0 以文件个数计算，kL0_CompactionTrigger 默认配置为 4。

score =v->files_[level].size()/static_cast<double>(config::kL0_CompactionTrigger);

S2 对于 level>0，根据 level 内的文件总大小计算

const uint64_t level_bytes = TotalFileSize(v->files_[level]);
score = static_cast<double>(level_bytes) /MaxBytesForLevel(level);

S3 最后把计算结果保存到 v 的两个成员 compaction_level_ 和 compaction_score_ 中。

其中函数 MaxBytesForLevel 根据 level 返回其本层文件总大小的预定最大值。计算规则为：1048576.0* level^10。这里就有一个问题，为何 level0 和其它 level 计算方法不同，原因如下，这也是 leveldb 为 compaction 所做的另一个优化。

1 对于较大的写缓存（write-buffer），做太多的 level 0 compaction 并不好 2 每次 read 操作都要 merge level 0 的所有文件，因此我们不希望 level 0 有太多的小文件存在（比如写缓存太小，或者压缩比较高，或者覆盖/删除较多导致小文件太多）。看起来这里的写缓存应该就是配置的操作 log 大小。

11.3.3 AppendVersion()

函数声明：

void AppendVersion(Version*v);

把 v 加入到 versionset 中，并设置为 current version。并对老的 current version 执行 Uref()。在双向循环链表中的位置在 dummy_versions_ 之前。