首页 > 代码库 > 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里才会被删除。