首页 > 代码库 > leveldb version机制
leveldb version机制
该文章主要回答三个问题:
- leveldb 怎么管理因compact带来的文件变化?
- 当db关闭后重新打开时,如何恢复状态?
- 如何解决版本销毁文件变化和已经获取过的迭代器的冲突?
每次leveldb后台进行compact时, 会造成sst文件的变化。levedb利用version来管理了这些变化。
compact前为Version1, compact后为Version2. VersionSet利用链表将前后一系列的version组织起来。核心代码在db/version_set.h db/version_set.cpp
version间的变化通过VersionEdit来表示:
1 std::vector< std::pair<int, InternalKey> > compact_pointers_; //表示level上下次可以开始compact的key值 2 DeletedFileSet deleted_files_;//表示这次删除的文件 3 std::vector< std::pair<int, FileMetaData> > new_files_;//表示这次删除的文件
那么将如何从旧版本生成新版本了?看下下段VersionSet::LogAndApply的代码:
1 Version* v = new Version(this); 2 { 3 Builder builder(this, current_); 4 builder.Apply(edit); //将版本的变化即VersionEdit应用到VersionSet的compact_pointers, deleted_files及added_files。 5 builder.SaveTo(v);//根据VersionSet中的deleted_files以及added_files, 从base Version(即current_)生成新Version的数据内容 6 } 7 Finalize(v);
详细看下SaveTo的过程
1 void SaveTo(Version* v) { 2 BySmallestKey cmp; 3 cmp.internal_comparator = &vset_->icmp_; 4 for (int level = 0; level < config::kNumLevels; level++) { 5 // Merge the set of added files with the set of pre-existing files. 6 // Drop any deleted files. Store the result in *v. 7 const std::vector<FileMetaData*>& base_files = base_->files_[level];//一个根据根据file的最小key值排序的有序vector 8 std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin(); 9 std::vector<FileMetaData*>::const_iterator base_end = base_files.end(); 10 const FileSet* added = levels_[level].added_files; //FileSet是一个根据file的最小key值排序的有序set 11 v->files_[level].reserve(base_files.size() + added->size()); //如下过程类似于归并排序 //base files:{2}, {5}, {7} //add files:{1}, {6} //过程就是{1}->files, {2}, {5}->files, {6}->files, {7}->files. //当然,上步骤的过程中,还需要判断下该file是否能add到files中去,即MaybeAddFile(不在删除files里即可添加) 12 for (FileSet::const_iterator added_iter = added->begin(); 13 added_iter != added->end(); 14 ++added_iter) { 15 // Add all smaller files listed in base_ 16 for (std::vector<FileMetaData*>::const_iterator bpos 17 = std::upper_bound(base_iter, base_end, *added_iter, cmp); 18 base_iter != bpos; 19 ++base_iter) { 20 MaybeAddFile(v, level, *base_iter); 21 } 22 23 MaybeAddFile(v, level, *added_iter); 24 } 25 26 // Add remaining base files 27 for (; base_iter != base_end; ++base_iter) { 28 MaybeAddFile(v, level, *base_iter); 29 } 30 31 } 32 }
这段代码让我感兴趣的是很好的利用了std::upper_bound, 要是自己实现,估计就会自己去写归并的逻辑了。
此外,当leveldb在运行时记录了每次的版本变化,并将其持久化于manifest文件中。当leveldb重新打开时,将从manifest文件中Recover出上一次levedb运行时的每次版本变化,并通过VersionSet::Builder Apply每次版本变化到当前版本对象中(current_)。
那么,难道manifest文件一直都保存这版本的历史变化么?答案当然是no, 在DB::open时就会调用LogAndApply.
1 std::string new_manifest_file; 2 Status s; 3 if (descriptor_log_ == NULL) {
//DB::open时就会运行到这,因此会新建一个manifest_file, 此时的manifest_file_number就与当前的manifest文件不同。
//然后通过WriteSnapshot将当然的状态写到该manifest_file,因此manifest_file就只有一个版本变化了,这个版本变化融合了之前所有的历史变化。
//最后又进行了current文件指到该新manifest文件的操作,就完成了manifest_file替换。
4 // No reason to unlock *mu here since we only hit this path in the 5 // first call to LogAndApply (when opening the database). 6 assert(descriptor_file_ == NULL); 7 new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_); 8 edit->SetNextFile(next_file_number_); 9 s = env_->NewWritableFile(new_manifest_file, &descriptor_file_); 10 if (s.ok()) { 11 descriptor_log_ = new log::Writer(descriptor_file_); 12 s = WriteSnapshot(descriptor_log_); 13 } 14 }
还有一个问题,在某个版本Version1上通过DBImpl::NewIterator获取了iterator后。如果进行compact,Version1对象以及Version1中的文件会不会销毁掉?答案肯定时no, 那么它时基于什么来实现的了?看下面一段代码
1 Iterator* DBImpl::NewInternalIterator(const ReadOptions& options, 2 SequenceNumber* latest_snapshot) { 3 IterState* cleanup = new IterState; 4 mutex_.Lock(); 5 *latest_snapshot = versions_->LastSequence(); 6 7 // Collect together all needed child iterators 8 std::vector<Iterator*> list; 9 list.push_back(mem_->NewIterator()); 10 mem_->Ref();//memtable引用计数+1 11 if (imm_ != NULL) { 12 list.push_back(imm_->NewIterator()); 13 imm_->Ref();//immutable memtable引用计数+1 14 } 15 versions_->current()->AddIterators(options, &list); 16 Iterator* internal_iter = 17 NewMergingIterator(&internal_comparator_, &list[0], list.size()); 18 versions_->current()->Ref();//当前version的引用计数+1 19 20 cleanup->mu = &mutex_; 21 cleanup->mem = mem_; 22 cleanup->imm = imm_; 23 cleanup->version = versions_->current(); //注册了CleanupIteratorState,这里就是当释放iterator时,会进行memtable, immutable memtable, version的引用计数-1 24 internal_iter->RegisterCleanup(CleanupIteratorState, cleanup, NULL); 25 26 mutex_.Unlock(); 27 return internal_iter; 28 }
从上面代码可以看出,通过引用计数避免了version的销毁。从而version中相对应的文件也不会销毁,可以从void DBImpl::DeleteObsoleteFiles() 中看出,每次删除文件时,遍历所有的version,找出当前的live files, 即每个版本的file总集合。不在live files里才会被删除。