Leveldb源码分析18

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

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

VersionSet(const std::string& dbname, const Options* options,

TableCache*table_cache, const InternalKeyComparator*)

VersionSet的构造函数很简单&＃xff0c;除了根据参数初始化&＃xff0c;还有两个地方值得注意&＃xff1a;

N1 next_file_number_从2开始&＃xff1b;

N2 创建新的Version并加入到Version链表中&＃xff0c;并设置CURRENT&＃61;新创建version&＃xff1b;

其它的数字初始化为0&＃xff0c;指针初始化为NULL。

2 恢复函数&＃xff0c;从磁盘恢复最后保存的元信息

Status Recover();

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

void MarkFileNumberUsed(uint64_t number)

逻辑很简单&＃xff0c;就是根据编号更新文件编号计数器&＃xff1a;

if (next_file_number_ <&＃61; number) next_file_number_ &＃61; number &＃43; 1;

4 在current version上应用指定的VersionEdit&＃xff0c;生成新的MANIFEST信息&＃xff0c;保存到磁盘上&＃xff0c;并用作current version。

要求&＃xff1a;没有其它线程并发调用&＃xff1b;要用于mu&＃xff1b;

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

5 对于&＃64;v中的&＃64;key&＃xff0c;返回db中的大概位置

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

6 其它一些简单接口&＃xff0c;信息获取或者设置&＃xff0c;如下&＃xff1a;

Version* current() const { return current_; } //返回current version
// 当前的MANIFEST文件号
uint64_t ManifestFileNumber() const { return manifest_file_number_; }
uint64_t NewFileNumber() { return next_file_number_&＃43;&＃43;; } // 分配并返回新的文件编号
uint64_t LogNumber() const { return log_number_; } // 返回当前log文件编号
// 返回正在compact的log文件编号&＃xff0c;如果没有返回0
uint64_t PrevLogNumber() const { return prev_log_number_; }
// 获取、设置last sequence&＃xff0c;set时不能后退
uint64_t LastSequence() const { return last_sequence_; }
void SetLastSequence(uint64_t s) {assert(s >&＃61;last_sequence_);last_sequence_ &＃61; s;
}
// 返回指定level中所有sstable文件大小的和
int64_t NumLevelBytes(int level) const;
// 返回指定level的文件个数
int NumLevelFiles(int level) const;
// 重用&＃64;file_number&＃xff0c;限制很严格&＃xff1a;&＃64;file_number必须是最后分配的那个
// 要求: &＃64;file_number是NewFileNumber()返回的.
void ReuseFileNumber(uint64_t file_number) {if (next_file_number_ &＃61;&＃61;file_number &＃43; 1) next_file_number_ &＃61; file_number;
}
// 对于所有level>0&＃xff0c;遍历文件&＃xff0c;找到和下一层文件的重叠数据的最大值(in bytes)
// 这个就是Version:: GetOverlappingInputs()函数的简单应用
int64_t MaxNextLevelOverlappingBytes();
// 获取函数&＃xff0c;把所有version的所有level的文件加入到&＃64;live中
void AddLiveFiles(std::set* live)
// 返回一个可读的单行信息——每个level的文件数&＃xff0c;保存在*scratch中
struct LevelSummaryStorage {char buffer[100]; };
const char* LevelSummary(LevelSummaryStorage* scratch) const;

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

Builder是一个内部辅助类&＃xff0c;其主要作用是&＃xff1a;

1 把一个MANIFEST记录的元信息应用到版本管理器VersionSet中&＃xff1b;

2 把当前的版本状态设置到一个Version对象中。

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

typedefstd::set FileSet;struct LevelState { // 这个是记录添加和删除的文件std::setdeleted_files;FileSet* added_files; // 保证添加文件的顺序是有效定义的};VersionSet* vset_;Version* base_;LevelStatelevels_[config::kNumLevels];
// 其接口有3个&＃xff1a;void Apply(VersionEdit* edit)void SaveTo(Version* v)void MaybeAddFile(Version* v, int level, FileMetaData* f)构造函数执行简单的初始化操作&＃xff0c;在析构时&＃xff0c;遍历检查LevelState::added_files&＃xff0c;如果文件引用计数为0&＃xff0c;则删除文件。

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

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

edit->compact_pointers_ &＃61;> vset_->compact_pointer_

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

edit->deleted_files_ &＃61;> levels_[level].deleted_files

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

for (size_t i &＃61; 0; i new_files_.size(); i&＃43;&＃43;) {const int level &＃61;edit->new_files_[i].first;FileMetaData* f &＃61; newFileMetaData(edit->new_files_[i].second);f->refs &＃61; 1;f->allowed_seeks &＃61; (f->file_size /16384); // 16KB-见下面if (f->allowed_seeks <100) f->allowed_seeks &＃61; 100;levels_[level].deleted_files.erase(f->number); // 以防万一levels_[level].added_files->insert(f);
}值allowed_seeks事关compaction的优化&＃xff0c;其计算依据如下&＃xff0c;首先假设&＃xff1a;

>1 一次seek时间为10ms

>2 写入10MB数据的时间为10ms&＃xff08;100MB/s&＃xff09;

>3 compact 1MB的数据需要执行25MB的IO

->从本层读取1MB

->从下一层读取10-12MB&＃xff08;文件的key range边界可能是非对齐的&＃xff09;

->向下一层写入10-12MB

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

函数声明&＃xff1a;voidMaybeAddFile(Version* v, int level, FileMetaData* f)

该函数尝试将f加入到levels_[level]文件set中。

要满足两个条件&＃xff1a;

>1 文件不能被删除&＃xff0c;也就是不能在levels_[level].deleted_files集合中&＃xff1b;

>2 保证文件之间的key是连续的&＃xff0c;即基于比较器vset_->icmp_&＃xff0c;f的min key要大于levels_[level]集合中最后一个文件的max key&＃xff1b;


把当前的状态存储到v中返回&＃xff0c;函数声明&＃xff1a;void SaveTo(Version* v)

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

S1 merge流程

conststd::vector& base_files &＃61; base_->files_[level]; // 原文件集合std::vector::const_iterator base_iter &＃61;base_files.begin();std::vector::const_iterator base_end &＃61;base_files.end();const FileSet* added &＃61;levels_[level].added_files;v->files_[level].reserve(base_files.size()&＃43; added->size());for (FileSet::const_iteratoradded_iter &＃61; added->begin(); added_iter !&＃61;added->end(); &＃43;&＃43;added_iter) {//加入base_中小于added_iter的那些文件for(std::vector::const_iterator bpos &＃61; std::upper_bound(base_iter,base_end, *added_iter, cmp);base_iter !&＃61; bpos;&＃43;&＃43;base_iter) { // base_iter逐次向后移到MaybeAddFile(v, level,*base_iter);}MaybeAddFile(v, level,*added_iter); // 加入added_iter}// 添加base_剩余的那些文件for (; base_iter !&＃61; base_end;&＃43;&＃43;base_iter) MaybeAddFile(v, level, *base_iter);对象cmp就是前面定义的比较仿函数BySmallestKey对象。

S2 检查流程&＃xff0c;保证level>0的文件集合无重叠&＃xff0c;基于vset_->icmp_&＃xff0c;确保文件i-1的max key <文件i的min key。

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

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

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

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

S2 读取MANIFEST内容&＃xff0c;MANIFEST是以log的方式写入的&＃xff0c;因此这里调用的是log::Reader来读取。然后调用VersionEdit::DecodeFrom&＃xff0c;从内容解析出VersionEdit对象&＃xff0c;并将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 &＃61; edit.DecodeFrom(record);if (s.ok())builder.Apply(&edit);if (edit.has_log_number_) { // log number, file number, …逐个判断log_number &＃61;edit.log_number_;have_log_number &＃61; true;}… …
}S3 将读取到的log number, prev log number标记为已使用。

MarkFileNumberUsed(prev_log_number);

MarkFileNumberUsed(log_number);

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

if (s.ok()) {Version* v &＃61; newVersion(this);builder.SaveTo(v);// 安装恢复的versionFinalize(v);AppendVersion(v);manifest_file_number_ &＃61;next_file;next_file_number_ &＃61; next_file&＃43; 1;last_sequence_ &＃61; last_sequence;log_number_ &＃61; log_number;prev_log_number_ &＃61;prev_log_number;}Finalize(v)和AppendVersion(v)用来安装并使用version v&＃xff0c;在AppendVersion函数中会将current version设置为v。下面就来分别分析这两个函数。

函数声明&＃xff1a;void Finalize(Version*v)&＃xff1b;

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

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

score &＃61;v->files_[level].size()/static_cast(config::kL0_CompactionTrigger);

S2 对于level>0&＃xff0c;根据level内的文件总大小计算

const uint64_t level_bytes &＃61; TotalFileSize(v->files_[level]);

score &＃61; static_cast(level_bytes) /MaxBytesForLevel(level);

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

其中函数MaxBytesForLevel根据level返回其本层文件总大小的预定最大值。

计算规则为&＃xff1a;1048576.0* level^10。

这里就有一个问题&＃xff0c;为何level0和其它level计算方法不同&＃xff0c;原因如下&＃xff0c;这也是leveldb为compaction所做的另一个优化。

>1 对于较大的写缓存&＃xff08;write-buffer&＃xff09;&＃xff0c;做太多的level 0 compaction并不好

>2 每次read操作都要merge level 0的所有文件&＃xff0c;因此我们不希望level 0有太多的小文件存在&＃xff08;比如写缓存太小&＃xff0c;或者压缩比较高&＃xff0c;或者覆盖/删除较多导致小文件太多&＃xff09;。

看起来这里的写缓存应该就是配置的操作log大小。

11.3.3 AppendVersion()

函数声明&＃xff1a;void AppendVersion(Version*v)

把v加入到versionset中&＃xff0c;并设置为current version。并对老的current version执行Uref()。

在双向循环链表中的位置在dummy_versions_之前。