VersionEdit

VersionEdit 对应一次修改，修改指的是 LSM 结构发生变化，比如将内存数据写入 SSTable、compaction 删除和写入新文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
class VersionEdit {
  typedef std::set<std::pair<int, uint64_t>> DeletedFileSet;

  std::string comparator_;
  uint64_t log_number_;                 // 当前 log 文件的文件序号
  uint64_t prev_log_number_
  uint64_t next_file_number_;          // 下一个 log 文件的文件序号，可以用于创建新的文件
  SequenceNumber last_sequence_;       // 保存过得最大的时间戳序号
  // ......
  std::vector<std::pair<int, InternalKey>> compact_pointers_;
  DeletedFileSet deleted_files_;
  std::vector<std::pair<int, FileMetaData>> new_files_;
}
  • new_files_ 表示需要新增的文件。生成的新 SSTable 都会加入到 new_files_
  • deleted_files_ 表示需要删除的文件。需要删除的 SSTable 都会加入到 deleted_files_。在 compaction 的时候会将不同 level 的 SSTable 合并，生成新的 SSTable。这时新的 SSTable 会加入 new_files_，而参与合并的 SSTable 会加入 deleted_files_

Version

Version 表示 LSM 的一个版本，存储着某个版本磁盘的结构信息。每次 LSM 结构发生改变都会生成一个新的 Version，新旧 Version 之间通过双向循环链表的形式连接(其中还包含一个虚拟头结点)，而这个双向链表 VersionSet 成员的一部分。

flowchart LR Version1 -- VersionEdit --> Version2 --VersionEdit --> ...... --VersionEdit --> Versionn-1 --> Versionn Versionn --> Version1 current_ --> Versionn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Version {
 private:
  VersionSet* vset_;  // VersionSet to which this Version belongs
  Version* next_;     // Next version in linked list
  Version* prev_;     // Previous version in linked list
  int refs_;          // Number of live refs to this version

  // List of files per level
  std::vector<FileMetaData*> files_[config::kNumLevels];
  // Next file to compact based on seek stats.
  FileMetaData* file_to_compact_;
  int file_to_compact_level_;

  // Level that should be compacted next and its compaction score.
  // Score < 1 means compaction is not strictly needed.  These fields
  // are initialized by Finalize().
  double compaction_score_;
  int compaction_level_;
};

Version 通过引用计数的方法进行管理，当引用数为 0 时，会从双向链表中删除该节点，并销毁该 Version。每当需要使用 Version 时都会将引用计数加一，使用完毕会引用计数会减一。当压缩生成新的 Version 引用计数也会加一，并将旧 Version 的引用计数减一。之所以需要将不同版本的 Version 都保存下来是因为在多线程访问时，各个线程访问的是不同版本的结构，只有当某个版本没有被访问时才能将其删除。

files_ 是一个数组，表示每一层的 SSTable 文件信息，即哪一层包含哪些文件，以及每个文件包含哪些元信息，可以通过下标访问对应的 level。元信息 FileMetaData 的结构如下所示

classDiagram class FileMetaData { + int refs + int allowed_seeks + uint64_t number + uint64_t file_size + InternalKey smallest + InternalKey largest + FileMetaData() }
  • number 表示这个 SSTable 的文件编号，在 LevelDB 中以文件编号作为 SSTable 的文件名
  • smallest, largest 表示这个 SSTable 中的最大最小 key，需要注意的是 SSTable 中存储的是 InternalKey，所以这里的最大最小 key 也是 InternalKey。
  • allowed_seeks 表示允许查找 miss 的次数。如果查询时查找到这个 SSTable，但是没有找到目标 key，allowed_seeks 就会减一。当 allowed_seeks 减为 0 时会触发 compaction。Version 中 file_to_compact_ 和 file_to_compact_level_ 两个成员就是为这个场景而设计的

compaction_score_ 表示压缩得分，只有当 compaction_score_ 超过某个值或者设置了 file_to_compact_ 时才会触发压缩(Mirror compaction 和手工压缩除外)。compaction_level_ 表示要压缩哪一层。这两个值都是在生成新 Version 时计算的。计算的方法在 Finalize(Version* v) 中

Version 还提供了一些工具方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Status Get(const ReadOptions&, const LookupKey& key, std::string* val,
            GetStats* stats);

// compaction may need to be triggered, false otherwise.
bool UpdateStats(const GetStats& stats);

// Record a sample of bytes read at the specified internal key.
// Samples are taken approximately once every config::kReadBytesPeriod
// bytes.  Returns true if a new compaction may need to be triggered.
// REQUIRES: lock is held
bool RecordReadSample(Slice key);

// Reference count management (so Versions do not disappear out from under live iterators)
void Ref();
void Unref();

void GetOverlappingInputs(
    int level,
    const InternalKey* begin,  // nullptr means before all keys
    const InternalKey* end,    // nullptr means after all keys
    std::vector<FileMetaData*>* inputs);

bool OverlapInLevel(int level, const Slice* smallest_user_key,
                    const Slice* largest_user_key);

// Return the level at which we should place a new memtable compaction
// result that covers the range [smallest_user_key,largest_user_key].
int PickLevelForMemTableOutput(const Slice& smallest_user_key,
                                const Slice& largest_user_key);

int NumFiles(int level) const { return files_[level].size(); }

其中最重要的是 Get 方法。每次从 LSM 中查找时，会先查找内存中的结构，如果没有找到才会查找磁盘中的结构。从磁盘中查找时会调用 Get 方法来搜索，如果查找 miss 了还会在 UpdateStats 中更新第一个 seek miss 文件的 allowed_seeks。

GetOverlappingInputs、OverlapInLevel 都是判断 SSTable 重叠区间的工具方法。PickLevelForMemTableOutput 则是 Mirror compaction 时用来选取 Push 到哪一层的。

VersionSet

VersionSet 除了管理 Version 的集合外，还管理者一些其他的信息，比如全局的序列号 last_sequence_、下一个生成文件的文件编号 next_file_number_、table 缓存 table_cache_ 等信息

classDiagram direction LR VersionSet o-- Version VersionSet ..> VersionEdit VersionSet *-- TableCache class VersionSet { - TableCache* const table_cache_ - const InternalKeyComparator icmp_ - uint64_t next_file_number_ - uint64_t manifest_file_number_ - uint64_t last_sequence_ - uint64_t log_number_ - uint64_t prev_log_number_ - WritableFile* descriptor_file_ - log::Writer* descriptor_log_ - Version dummy_versions_ - Version* current_ - string compact_pointer_[kNumLevels]; ...... + LogAndApply(VersionEdit* edit, port::Mutex* mu) Status + Recovery(bool* save_manifest) Status + Compaction* PickCompaction(); - Finalize(Version* v) void ......() }

从上面的结构可以看出来，Version 与 VersionEdit 没有直接的关系，他们之间是通过 VersionSet 来管理的。VersionEdit 记录结构的修改，通过 LogAndApply() 方法，记录到 Manifest 文件中，然后将修改应用到新生成的 Version 中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
  // 为 edit 设置一些信息，比如 log_number_, next_file_number_, last_sequence_ 等
  // ......

  // 在原有 Version 的基础上构建新 VersionEdit
  Version* v = new Version(this);
  {
    Builder builder(this, current_);
    builder.Apply(edit);
    builder.SaveTo(v);
  }
  Finalize(v); // 计算压缩得分和压缩层

  // Initialize new descriptor log file if necessary by creating
  // a temporary file that contains a snapshot of the current version.
  std::string new_manifest_file;
  Status s;
  if (descriptor_log_ == nullptr) {
    // No reason to unlock *mu here since we only hit this path in the
    // first call to LogAndApply (when opening the database).
    new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
    s = env_->NewWritableFile(new_manifest_file, &descriptor_file_);
    descriptor_log_ = new log::Writer(descriptor_file_);
    s = WriteSnapshot(descriptor_log_);
  }

  {
    mu->Unlock();
    // 写 manifest 文件
    std::string record;
    edit->EncodeTo(&record);
    s = descriptor_log_->AddRecord(record); 
    s = descriptor_file_->Sync();

    // If we just created a new descriptor file, install it by writing a
    // new CURRENT file that points to it.
    if (s.ok() && !new_manifest_file.empty()) {
      s = SetCurrentFile(env_, dbname_, manifest_file_number_);
    }
    mu->Lock();
  }

  // Install the new version
  AppendVersion(v); // 将新 Version 添加到 VersionSet 中
  log_number_ = edit->log_number_;
  prev_log_number_ = edit->prev_log_number_;

  return s;
}

Manifest

Version 是内存中的结构，为了让系统在关闭后能够恢复，还需要讲内存中的结构持久化到磁盘中，这就引入了 Manifest 文件。每当 Version 应用 VersionEdit 时，需要将 VersionEdit 中的内容写入到 Manifest 文件中，为此 VersionEdit 提供了EncodeTo(string) 方法对其自身编码。写入 Manifest 的数据包含如下信息

1
2
3
4
5
6
7
8
9
10
11
enum Tag {
  kComparator = 1, // InternalKey comparator
  kLogNumber = 2, // 当前 log 文件编号
  kNextFileNumber = 3, // 下一个文件编号
  kLastSequence = 4, // 当前版本最后一个 SequenceNumber
  kCompactPointer = 5, // 
  kDeletedFile = 6, // 该版本需要删除的文件元数据
  kNewFile = 7, // 该版本需要添加的文件元数据
  // 8 was used for large value refs
  kPrevLogNumber = 9 // 前一个 Version Log 文件编号
};

为了能够在恢复时识别数据信息，需要将 tag 连同数据一起写进 Manifest 文件，每个 tag 时一个 varint32 的值，只占用 1 个字节。需要注意的是，需要新增的文件和需要删除的文件可能有多个，所以对于每一个新增或删除的文件，都需要写入 kDeletedFile 或 kNewFile tag。对于 kDeletedFile，需要写入 文件的 level 和 file number 信息；对于 kNewFile 不仅需要写入文件的 level 和 file number，还需要写入文件的 size、smallest key 和 largest key，这是为了恢复时能够将文件元信息恢复位 FileMetaData 结构。

在 DB 恢复后第一次修改系统结构时，会调用 WriteSnapshot 对当前状态进行一次快照，并写入新的 Manifest 文件中