# 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* 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 FileSet; // 这个是记录添加和删除的文件 struct LevelState { std::setdeleted_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 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& base_files = base_->files_[level]; std::vector::const_iterator base_iter =base_files.begin(); std::vector::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::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(config::kL0_CompactionTrigger); ``` **S2 对于level>0，根据level内的文件总大小计算** ``` const uint64_t level_bytes = TotalFileSize(v->files_[level]); score = static_cast(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_`之前。