[levelDB] Version Manager

一、作用

LevelDB如何能够知道每一层有哪些SST文件;如何快速的定位某条数据所在的SST文件;重启后又是如何恢复到之前的状态的,等等这些关键的问题都需要依赖元信息管理模块。对其维护的信息及所起的作用简要概括如下:

  • 记录Compaction相关信息,使得Compaction过程能在需要的时候被触发;
  • 维护SST文件索引信息及层次信息,为整个LevelDB的读、写、Compaction提供数据结构支持;
  • 负责元信息数据的持久化,使得整个库可以从进程重启或机器宕机中恢复到正确的状态;
  • 记录LogNumber,Sequence,下一个SST文件编号等状态信息;
  • 以版本的方式维护元信息,使得Leveldb内部或外部用户可以以快照的方式使用文件和数据。

二、相关数据结构

1. FileMetaData

leveldb中有很多SSTable,其中保存着Key值有序的数据,不同的SSTable文件之间的Key值区间没有重叠(level 0除外)。FileMetaData用于描述每一个.sst文件的信息,它记录了一个SSTable中的最小和最大的Key值,即Key值的变化区间,极大的提高了查找操作的效率。其数据结构如下:

1 struct FileMetaData {
2   int refs;//引用次数
3   int allowed_seeks;  //允许的最大查找次数
4   uint64_t number;    //.sst文件编号
5   uint64_t file_size;         // File size in bytes
6   InternalKey smallest;       // Smallest internal key served by table
7   InternalKey largest;        // Largest internal key served by table
8 };

2. Version

leveldb通过Version来记录一个版本,Version其实是一系列SSTable的集合,SSTable文件是按照不同的level来存储的,不同的level可能有多个SSTable文件。Version中保存了所有level的所有FileMetaData文件,并通过next和prev指针形成双向循环链表,链表尾部元素即为最新的Version,一般也就是所谓的Current版本。Version的数据结构为:

 1 class Version {
 2  private:
 3   VersionSet* vset_; // VersionSet to which this Version belongs
 4   Version* next_;    // next_、prev形成双向链表
 5   Version* prev_;               
 6   int refs_;                    
 7  
 8   std::vector<FileMetaData*> files_[config::kNumLevels];//二维数组,记录所有level的全部FileMetaData文件
 9  
10   // 基于Seek的结果stats得到的下一个等待Compact的文件(当FileMetaData文件查找到一定次数时,就需要执行合并操作)
11   FileMetaData* file_to_compact_;
12   int file_to_compact_level_;//需要进行合并的文件所属的level
13  
14   double compaction_score_;//当score>=1时,也需要进行合并
15   int compaction_level_;//需要进行合并的level
16 }

vset_指向Version所属的VersionSet,next_和prev_形成一个双向循环链表,file_to_compact_指向查找次数已经到达上限的等待执行合并操作的文件,files_是一个二维数组,files_[level][i]表示第level层的第i个SSTable文件。

一个Version中保存的是当前版本中各个level中的SSTable文件,以及等待合并的文件和level,并提供函数判断是否有文件需要进行合并,以及相关的level信息。
3. VersionEdit

VersionEdit用于表示Version的变化,通过原始Version加上一系列的VersionEdit可以得到最新的Version。

 

 1 class VersionEdit {
 2  public:
 3   void AddFile(int level, uint64_t file,uint64_t file_size,const InternalKey& smallestconst InternalKey& largest);
 4   void DeleteFile(int level, uint64_t file) ;
 5  private:
 6   friend class VersionSet;
 7   //通过set来记录要删除的文件,利用set可以保证变量不重复,即不会导致重复删除某个文件的错误
 8   typedef std::set< std::pair<int, uint64_t> > DeletedFileSet;
 9  
10   std::string comparator_;
11   uint64_t log_number_;
12   uint64_t prev_log_number_;
13   uint64_t next_file_number_;
14   SequenceNumber last_sequence_;
15   bool has_comparator_;
16   bool has_log_number_;
17   bool has_prev_log_number_;
18   bool has_next_file_number_;
19   bool has_last_sequence_;
20  
21   std::vector< std::pair<int, InternalKey> > compact_pointers_;
22   DeletedFileSet deleted_files_;
23   std::vector< std::pair<int, FileMetaData> > new_files_;
24 }

由上可知,VersionEdit通过两个数组new_files_和deleted_files_来保存针对当前Version要增加和删除的文件,通过AddFile()和DeleteFile()两个操作来实现。

然后通过VersionSet::LogAndApply(VersionEdit* edit)来实现将VersionEdit应用到某个Version,来生成一个新的Version。
4. VersionSet

 

三、实现

LeveDB用Version表示一个版本的元信息,Version中主要包括一个FileMetaData指针的二维数组,分层记录了所有的SST文件信息。FileMetaData数据结构用来维护一个文件的元信息,包括文件大小,文件编号,最大最小值,引用计数等,其中引用计数记录了被不同的Version引用的个数,保证被引用中的文件不会被删除。除此之外,Version中还记录了触发Compaction相关的状态信息,这些信息会在读写请求或Compaction过程中被更新。通过庖丁解LevelDB之概览中对Compaction过程的描述可以知道在CompactMemTable和BackgroundCompaction过程中会导致新文件的产生和旧文件的删除。每当这个时候都会有一个新的对应的Version生成,并插入VersionSet链表头部。

VersionSet是一个Version构成的双向链表,这些Version按时间顺序先后产生,记录了当时的元信息,链表头指向当前最新的Version,同时维护了每个Version的引用计数,被引用中的Version不会被删除,其对应的SST文件也因此得以保留,通过这种方式,使得LevelDB可以在一个稳定的快照视图*问文件。VersionSet中除了Version的双向链表外还会记录一些如LogNumber,Sequence,下一个SST文件编号的状态信息。

  [levelDB] Version Manager VersionSet Version 示意图

通过上面的描述可以看出,相邻Version之间的不同仅仅是一些文件被删除另一些文件被删除。也就是说将文件变动应用在旧的Version上可以得到新的Version,这也就是Version产生的方式。LevelDB用VersionEdit来表示这种相邻Version的差值。

  [levelDB] Version Manager VersionEidt

为了避免进程崩溃或机器宕机导致的数据丢失,LevelDB需要将元信息数据持久化到磁盘,承担这个任务的就是Manifest文件。可以看出每当有新的Version产生都需要更新Manifest,很自然的发现这个新增数据正好对应于VersionEdit内容,也就是说Manifest文件记录的是一组VersionEdit值,在Manifest中的一次增量内容称作一个Block,其内容如下:

Manifest Block := N * Item
Item := [kComparator] comparator
        or [kLogNumber] 64位log_number
        or [kPrevLogNumber] 64位pre_log_number
        or [kNextFileNumber] 64位next_file_number_
        or [kLastSequence] 64位last_sequence_
        or [kCompactPointer] 32位level + 变长的key
        or [kDeletedFile] 32位level + 64位文件号
        or [kNewFile] 32位level + 64位 文件号 + 64位文件长度 + smallest key + largest key

可以看出恢复元信息的过程也变成了依次应用VersionEdit的过程,这个过程中有大量的中间Version产生,但这些并不是我们所需要的。LevelDB引入VersionSet::Builder来避免这种中间变量,方法是先将所有的VersoinEdit内容整理到VersionBuilder中,然后一次应用产生最终的Version,这种实现上的优化如下图所示:

  [levelDB] Version Manager VersionSet::Builder

在这一节中,我们依次看到了LevelDB版本控制中比较重要的几个角色:Version、FileMetaData、VersionSet、VersionEdit、Manifest和Version::Builder。同时了解了他们各自的作用


功能点

版本控制中维护的各种元信息,为LevelDB的各个工作流程中提供了必不可少的支持:

1,Get

我们已经知道,LevelDB尝试获取某个Key的值时会依次尝试从Memtable,Immutable,SST文件中读取。一旦需要从SST文件中读取,就需要解决从大量文件中快速定位文件的问题。正是由于Version中记录了当前每个文件的最大最小值,使得这个问题变成比较Key值与文件的Key Range的过程。

我们已经知道,LevelDB的写操作会直接写入Memtable并通过异步的Compaction过程写入到不同层次的SST文件中,因此,上层文件拥有较新的数据,利用这个特征,LevelDB的Get接口会由上至下的依次从每一层中尝试查找,一旦查找成功,便可以忽略下层的相同Key的记录。

Level0层比较特殊,文件之间相互重叠无序,需要由新到旧的尝试从每个文件中查找。其他Level,由于SST文件本身有序排列,因此可以利用二分查找快速定位Key所在文件。找到Key值所在文件后,再用庖丁解LevelDB之数据存储中介绍的格式读取文件中内容。

2,Compaction触发时机

我们已经知道,LevelDB中会有后台线程来执行Compaction的操作,将上层文件与下层文件归并生成新的下层文件。Version中记录的各层的文件信息来帮助决定进行Compaction的时机:

  • 容量触发Compaction:每个Version在其生成的时候会初始化两个值compaction_level_、compaction_score_,记录了当前Version最需要进行Compaction的Level,以及其需要进行Compaction的紧迫程度,score大于1被认为是需要马上执行的。我们知道每次文件信息的改变都会生成新的Version,所以每个Version对应的这两个值初始化后不会再改变。level0层compaction_score_与文件数相关,其他level的则与当前层的文件总大小相关。这种区分的必要性也是显而易见的:每次Get操作都需要从level0层的每个文件中尝试查找,因此控制level0的文件数是很有必要的。同时Version中会记录每层上次Compaction结束后的最大Key值compact_pointer_,下一次触发自动Compaction会从这个Key开始。容量触发的优先级高于下面将要提到的Seek触发。
  • Seek触发Compaction:Version中会记录file_to_compact_和file_to_compact_level_,这两个值会在Get操作每次尝试从文件中查找时更新。LevelDB认为每次查找同样会消耗IO,这个消耗在达到一定数量可以抵消一次Compaction操作消耗的IO,所以对Seek较多的文件应该主动触发一次Compaction。但在引入布隆过滤器后,这种查找消耗的IO就会变得微不足道了,因此由Seek触发的Compaction其实也就变得没有必要了。
  • 手动Compaction:LevelDB提供了外部接口CompactRange,用户可以指定触发某个Key Range的Compaction,LevelDB默认手动Compaction的优先级高于两种自动触发。

3,构造Compaction:

达到触发条件进行Compaction操作时,会首先通过Version来构造所有本次Compaction所需要的信息,记录在Compaction对象中,包括发生Compaction的level,所有参与的level和level+1层的文件信息,level+2层的文件信息等。 下面针对自动触发Compaction的情况介绍,手动Compaction的过程大体类似,这个过程叫做PickCompaction。

  • 获得要Compaction的一个文件加入input_[0],容量触发时这个文件由compaction_level_加compact_pointer_确定,否则由file_to_compact_level_和file_to_compact_确定。对于level0,由于其文件相互重合,需要将所有与当前Compaction文件重合的文件全部加入input_[0]。
  • 获得所有与level[0]有Key Range重合的level+1层文件加入input_[1],可以看出所有input_[1]文件的Key Range可能大于level[0],为了减少LevelDB整体Compaction次数,LevelDB会在不增加input_[1]文件数的前提下尝试增加level[0]文件数来扩大level层文件的Key Range。
  • 获得所有与当前Key Range重合的level+2层文件加入input_[2],这里记录level+2层的文件信息是为了Compaction生成新的level+1层文件时,保证新文件不会与level+2中太多的文件有Key Range的重合,从而导致以后该文件的Compaction有太大的Merge开销,这个信息会在生成新文件的过程中不断检查。
  • 生成归并Iterator,接下来就是用上面收集的信息生成归并Iterator,之后遍历这个Iterator生成新的文件,Iterator相关的内容会在之后一篇博客详细介绍。

4,Version持久化:

Compaction过程会造成文件的增加和删除,这就需要生成新的Version,上面提到的Compaction对象包含本次Compaction所对应的VersionEdit,Compaction结束后这个VersionEdit会被用来构造新的VersionSet中的Version。同时为了数据安全,这个VersionEdit会被Append写入到Manifest中。在库重启时,会首先尝试从Manifest中恢复出当前的元信息状态,过程如下:

  • 依次读取Manifest文件中的每一个Block, 将从文件中读出的Record反序列化为VersionEdit;
  • 将每一个的VersionEdit Apply到VersionSet::Builder中,之后从VersionSet::Builder的信息中生成Version;
  • 计算compaction_level_、compaction_score_;
  • 将新生成的Version挂到VersionSet中,并初始化VersionSet的manifest_file_number_, next_file_number_,last_sequence_,log_number_,prev_log_number_ 信息;

 



上一篇:R01 - 010、简述 HBASE 中 compact 用途是什么,什么时候触发,分为哪两种,有什么区别,有哪些相关配置参数?


下一篇:HBase学习-HBase原理