LevelDB 源代码阅读（二）：读流程

在 LevelDB 源代码阅读（一）：写流程 中我们介绍了 LevelDB 的 LSM 树结构以及数据写入 LevelDB 的流程。本文我们将介绍从 LevelDB 中读取数据的流程。

快照（Snapshot）

在介绍 LevelDB 的读流程之前，首先介绍一下快照（Snapshot）的概念。所谓快照，其实就是代表了数据库在某一个时刻的状态，LevelDB 中数据读取就是通过 Snapshot 机制来实现的。

LevelDB 的快照通过一个名为 sequence number 的整型数来实现。当数据被写入后，此次操作对应数据就不可再更改。假如我们在 LevelDB 中对一个键 testkey 赋一个值 testvalue1，那么这次操作对应的数据就会被存放在内存或磁盘上。假如我们又对 testkey 赋了一个新的值 testvalue2，那么前面操作的值无法修改，那么系统应该怎么去更新这个键所对应的值呢？答案是通过 sequence number 。LevelDB 维护了一个全局的 sequence number ，每次有写操作发生时这个 sequence number 就会加一。在写操作发生时，LevelDB 会为这个写操作分配一个 sequence number，其值就是当前系统中 sequence number 的值。在操作记录被持久化时，sequence number 也会通过一定的编码方式被持久化到数据中（详情看写流程的文章）。这样，新操作的 sequence number 永远会比旧操作的 sequence number 大。在读取数据时，我们就可以通过不同 sequence number 的值对应数据库历史上不同的状态。假如同时存在 sequence number 为 99、100、101 的三个操作记录，那么就会以 101 所对应的数据为当前数据库中所记录的数据。在进行文件合并（Compaction）时，对同一数据的不同操作记录会被消除，只保留 sequence number 最大的一条操作记录所对应的数据（假如此记录将数据从数据库中删除了，那么就无需保留任何数据）。

快照在代码中对应的类是 SnapshotImpl ，其内部保存了两个 SnapshotImpl 指针 prev 和 next，这和 SnapshotList 有关；另外还保存了一个 uint_64 类型的 sequence number。当用户创建一个快照时，LevelDB 会将系统中最新的 sequence number 值赋予这个 Snapshot ，这样用户通过这个 Snapshot 读取的数据就是系统中当前状态下的数据。在读数据时，所有读取到的数据会根据 Snapshot 的 sequence number 进行筛选，所有 seqnum 大于该 Snapshot 的 seqnum 的数据都会被剔除，剩下的记录中 seqnum 最大的那一个就是需要读取的数据。

读操作

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
50
51
52
53
// db_impl.cc
Status DBImpl::Get(const ReadOptions& options, const Slice& key,
                   std::string* value) {
  Status s;
  MutexLock l(&mutex_);
  // get the snapshot for read
  SequenceNumber snapshot;
  if (options.snapshot != nullptr) {
    snapshot =
        static_cast<const SnapshotImpl*>(options.snapshot)->sequence_number();
  } else {
    snapshot = versions_->LastSequence();
  }

  // increase the reference count for MemTable, ImmutableMemTable and Version
  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  mem->Ref();
  if (imm != nullptr) imm->Ref();
  current->Ref();

  bool have_stat_update = false;
  Version::GetStats stats;

  // Unlock while reading from files and memtables
  {
    mutex_.Unlock();
    // First look in the memtable, then in the immutable memtable (if any).
    // the search order is : MemTable -> Immutable MemTable -> SSTable
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // Done
    } else if (imm != nullptr && imm->Get(lkey, value, &s)) {
      // Done
    } else {
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
    }
    mutex_.Lock();
  }

  // update the statistic info for SSTable, may run compaction in background
  if (have_stat_update && current->UpdateStats(stats)) {
    MaybeScheduleCompaction();
  }

  // decrease the ref count
  mem->Unref();
  if (imm != nullptr) imm->Unref();
  current->Unref();
  return s;
}

代码的执行流程如下：

  • 获取此次 Get 操作对应的 Snapshot 。
  • 获取系统内存中的 MemTable、ImmutableMemtable 和 Version，前两者在 LSM 树中都有对应，Version 主要是维护 SSTable 的版本信息。获取之后增加其引用计数，这三个数据结构在引用计数为 0 时会其对应的内存会被释放。
  • 依次从 MemTable、Immutable Memtable 和 SSTable 中查找对应的数据。
  • 更新 SSTable 的统计信息，可能会在后台进行数据文件合并（Compaction）。
  • 减少 MemTable、ImmutableMemTable 以及 Version 的引用计数。

在查找时，对 MemTable 和 Immutable MemTable 都通过 SkipList 实现，这将在介绍 MemTable 的文章中解读。我们首先关注对 SSTable 的查找。对 SSTable 的查找最终会进入到 ForEachOverlapping 函数中

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
// version_set.cc
void Version::ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
                                 bool (*func)(void*, int, FileMetaData*)) {
  const Comparator* ucmp = vset_->icmp_.user_comparator();

  // Search level-0 in order from newest to oldest.
  std::vector<FileMetaData*> tmp;
  tmp.reserve(files_[0].size());
  for (uint32_t i = 0; i < files_[0].size(); i++) {
    FileMetaData* f = files_[0][i];
    // search for SSTable, which may contains the key for current read
    if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
        ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
      tmp.push_back(f);
    }
  }
  if (!tmp.empty()) {
  	// sort the selected files from new to old
    std::sort(tmp.begin(), tmp.end(), NewestFirst);
    for (uint32_t i = 0; i < tmp.size(); i++) {
    	// if key are found in current file, return
    	// else continue to search in next file
      if (!(*func)(arg, 0, tmp[i])) {
        return;
      }
    }
  }

  // Search other levels.
  for (int level = 1; level < config::kNumLevels; level++) {
    size_t num_files = files_[level].size();
    if (num_files == 0) continue;

    // Binary search to find earliest index whose largest key >= internal_key.
    uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
    if (index < num_files) {
      FileMetaData* f = files_[level][index];
      if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) {
        // All of "f" is past any data for user_key
      } else {
        if (!(*func)(arg, level, f)) {
          return;
        }
      }
    }
  }
}

我们可以看到，针对 SSTable 的查找分为了两个部分：对 Level-0 文件的查找以及对 Level 大于 0 的文件查找。

在对 Level-0 层的文件进行查找时，系统会将每一个有可能包含这个 key 的文件都加入到待搜查列表中，随后将选中的文件从新到旧进行排序（新文件中存储的数据才是有效的数据），再对按序对每个文件进行查找。

在对 Level-N（N>0）层的文件进行查找时，系统在每一层中通过二分查找找到了一个候选文件。如果这个文件不包含当前的 key，那么这一层的查找就结束了。

之所以对 Level-0 层的查找需要选取许多候选文件进行多次搜索，而对 Level-N（N > 0）层的文件查找只需一次，是因为 Level-0 层的文件都是从数据库中直接 dump 出来的，有可能存在前文所描述的数据重复的情况。而从 Level-1 层开始，数据文件都是从上一层文件中合并得到的。在合并的过程中，对同一条数据的操作只会保留一条，并且所有的文件会按照 key 的顺序排列，整个 Level-1 层及以上的文件是有序的。

到这里，LevelDB 的读流程就介绍完毕了。LevelDB 的读流程值得品味的点没有写流程的多，对 SSTable 的管理和查找处理的比较细节，当然这里也和 Compaction 模块有关，在后续的文章中会继续介绍。

参考资料

LevelDB Handbook

LevelDb 源码阅读–读操作

数据库 > 源代码阅读 > LevelDB
LevelDB 源代码阅读（二）：读流程
https://thumarklau.github.io/2021/07/10/Leveldb-source-code-reading-2/
作者
MarkLau
发布于
2021年7月10日
许可协议