从leveldb中学编码技巧(4)

2019-06-13 本文已影响0人 wangjie_yy

leveldb的数据以sst文件形式存储在磁盘上，后台有一个常驻线程进行compaction操作。compaction的作用主要是降低存储放大，有效利用磁盘空间。在处理读写请求过程中，以及compaction本身处理过程中，都有可能会触发新一轮的compaction。

compaction主要有两种：

将memtable中的数据写入到磁盘sst文件中
将某个level的某个文件合并到更上一层的level中

第一种就是将内存中数据写入到文件，第二种本质上是一个merge外部文件的过程。无论哪种compaction，都会改变当前数据库中的文件，可能会删除或者新增文件。

leveldb使用了一个manifest文件来保存数据库的元信息，其中包括当前有效的文件集合。当处理读请求时，会在当前有效文件集合中查询。同时使用一个CURRENT文件来指向当前的manifest文件。

后台线程进行compaction的过程大概是这样的：

确认compaction的输入是什么，是memtable，还是一些sst文件
确认compaction的输出是什么，基本都是一些sst文件
进行具体读写操作，写入一些新文件，并删除一些不需要的文件
将新的有效文件集合记录在manifest文件中(有可能是新生成的manifest文件)
将CURRENT文件指向新的manifest文件(如果有新manifest文件的话)

这里要说的问题是：如何管理磁盘上的sst文件。

随着compaction的进行，sst文件集合在不停变化，会生成一些新的文件，同时也会删除一些旧的文件。当前最新的有效文件集合记录在manifest文件中，当处理读请求时，总是从当前最新文件中读取数据。但是当在处理快照请求，以及iterator遍历时，可能也会从旧的文件中读取数据。这是因为，快照或者iterator指向的文件可能在compaction中被合并了，生成了新的文件。

leveldb定义了一个Version类，用来表示一个有效的sst文件集合。随着compaction的进行，Version会不断变化，生成新的Version。当前的Version则总是指向当前最新的有效文件集合。相关的一些Class如下定义：

class Version {
public:
    Version();
    ~Version();
    ...
    void Ref();
    void Unref();

private:
    ...
    std::vector<FileMetaData*> files_[config::kNumLevels];
};

class VersionSet {
 public:   
    VersionSet();
    ~VersionSet();
    ...
    
 private:
     
   Version dummy_versions_;  // Head of circular doubly-linked list of versions.
   Version* current_;        // == dummy_versions_.prev_     
};

class VersionEdit {
public:
    VersionEdit();
    ~VersionEdit();
    ...

private:
    ...
    std::vector< std::pair<int, InternalKey> > compact_pointers_;
    DeletedFileSet deleted_files_;
    std::vector< std::pair<int, FileMetaData> > new_files_;    
};

struct FileMetaData {
  int refs;
  int allowed_seeks;          // Seeks allowed until compaction
  uint64_t number;
  uint64_t file_size;         // File size in bytes
  InternalKey smallest;       // Smallest internal key served by table
  InternalKey largest;        // Largest internal key served by table

  FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) { }
};

VersionSet中使用一个Version链表来记录所有的Version，而current则总是指向当前最新的Version。当数据库初始打开时，只有一个current Version以及一个dummy Version。每进行一次compaction，会生成一个新的Version作为current版本并插入到链表中。

每一次compaction都会产生一个VersionEdit实例，其中记录了此次compaction对文件集合的变更：要新加入哪些文件，删除哪些文件等。将VersionEdit作用在当前current Version上，得到最新的Version，并记录在VersionSet中。(将VersionEdit作用在当前current上的实现在VersionSet::LogAndApply()中，这个过程使用了辅助类VersionSet::Builder，代码写的很简洁。使用辅助类是leveldb非常常见的技巧，主要作用是将复杂的逻辑拆解开，让过程变得更清晰，易于阅读和理解)。

Version通过引用计数来管理生命周期，当不再需要某个Version实例时，会在这个实例上调用Unref()，如果发现已经没有对此Version实例的引用时，就会删除Version实例，从而触发Version的析构函数的执行。在析构函数中，并没有直接删除此Version对应的文件，因为同一个文件可能包括在多个Version中。文件也是通过引用计数来管理的，由FileMetaData代表一个sst文件。由在Version的析构函数中，会依次减少其中文件的引用计数，当某个文件的引用计数降为0时，就会删除内存中的FileMetaData实例。也就是，在内存中没有对这个文件的引用了。

在DBImpl::DeleteObsoleteFiles()中，会统计当前前VersionSet中的所有文件，以及磁盘上的所有文件，进行交叉比对，如果发现某个文件存在于磁盘上，而VersionSet中并没有对这个文件的引用。就从磁盘上删除此文件。每次compaction结束后，以及数据库打开时，都会调用DBImpl::DeleteObsoleteFiles()函数来清理一次老旧文件。

总结

如果不用Version，VersionEdit这些类，使用其他的写法，应该也能够实现管理文件和处理变更的功能，但是极有可能代码结构会变得混乱和复杂，难以阅读和理解。leveldb的这种实现，代码结构很很清晰，容易理解它实现的功能，因此也可以降低因为复杂而出错的概率。

从leveldb中学编码技巧(4)

总结

猜你喜欢

热点阅读