Leveldb 解读之二：Read

1 简述

这一篇我们来分析 Leveldb 的 read，我们从几个方面入手：

• 读流程

• Snapshot

• 读操作相关实现组件和机制

读流程

leveldb 有 Get()和 Iterator 两种读访问接口，可以读取单个 key，也可以按顺序(正向/反向)遍历 key。

Get()

Get()查找 key 的顺序是: mem -> imm -> sstable files，读不到从下一个介质读取。

{  mutex_.Unlock();  // First look in the memtable, then in the immutable memtable (if any).  // 构建LookupKey(指定snapshot)  LookupKey lkey(key, snapshot);  // 先查找mem  if (mem->Get(lkey, value, &s)) {    // Done  // 再查找imm  } else if (imm != nullptr && imm->Get(lkey, value, &s)) {    // Done  // 最后查找sstable files，按顺序依次查找level-0、level-1......  } else {    s = current->Get(options, lkey, value, &stats);    have_stat_update = true;  }  mutex_.Lock();}

Iterator 顺序遍历

我们通过 db->NewIterator()创建一个 Iterator(实质上是一个MergerIterator)，实现对 mem、imm 和 sstable files 的多路归并排序，实现按顺序遍历 key。

相关实现在:

db_impl.h、db_impl.ccdb_iter.h、db_iter.ccmerger.h、merger.cc

通过分析 Get()和 Iterator 顺序遍历的代码，可以发现:

1. Iterator 的读成本相对 Get()更高一些，毕竟 Get()是找到第一个 key 就结束，而 Iterator 要做多路归并(多次比较)。但是考虑到 BufferCache 缓存局部性，在大量数据读的情况下，顺序遍历性能还是会好很多。

2. Iterator 反向遍历相对正向遍历性能要稍差一些:

3. memtable 底层是 skiplist，它是一个单向链表，没有 prev 指针，每个 Prev()都需要 FindLessThan(node_->key)；

4. sstable 也类似，next()操作只需要继续向前读 ParseNextKey()， Prev()需要定位到最近的重启点 GetRestartPoint()，再顺序查找；

Snapshot

leveldb 有个 snapshot 的概念，与数据库事务当中的快照读类似，提供一致读视图。生成一个 snapshot，后续 key 的新建、更新、删除等所有操作，就跟这个快照没有关系了。但是，snapshot 是有成本的，在快照释放前，它所关联的 keys 不能被压缩。

snaphsot 的实现方式很简单，对于我们写入的每个 user_key，leveldb 会构造出 internal_key: {user_key,sequence}，sequence 是单调递增的 64 位数字。snapshot 就是 sequence，通过对比 key 中的 sequence 和 snapshot(sequence)，就知道这个 key 对快照是否可见。

DBImpl 中维护了一个环形链表，用来保存当前活动的 snapshot: SnapshotList snapshots_ GUARDED_BY(mutex_);，执行 Compaction 时，会确保当前 live 快照的读一致视图不受影响。

Status DBImpl::DoCompactionWork(CompactionState* compact) {  ......  // 确定最小sequence，保证当前live的snapshot不受影响  if (snapshots_.empty()) {    compact->smallest_snapshot = versions_->LastSequence();  } else {    compact->smallest_snapshot = snapshots_.oldest()->sequence_number();  }  ......  // sequence < smallest_snapshot的值，才可以被drop  if (last_sequence_for_key <= compact->smallest_snapshot) {    // Hidden by an newer entry for same user key    drop = true;  }  ......}

读操作相关实现组件和机制

结合下面这张图，我们来捋一下读流程涉及的组件：

首先是在内存查找，先 mem，然后是 imm。

mem和imm是一个东西，都是写过程的产物，当mem写满以后，改了个名字叫imm(只读)。经过compaction过程，imm会变成sstable文件保存到硬盘上。memtable的需求是频繁的写入、读取，在数据结构的选择上leveldb使用了skiplist。因为skiplist结构简单，在频繁读写时效率稳定，不像红黑树需要频繁做树的平衡。

当内存里找不到 key 值时，就要到 sstable 里面去找。从 level-0 向上，按照文件序号(生成顺序)倒序，遍历所有可能包含 key 值的 sstable，直到找到为止。其中 level-0 的 sstable 因为 key 值范围重叠，可能有多个文件需要遍历，而其他 layer，则每层最多只有一个文件需要查询。

首先，使用文件 number 到 TableCache 里查找 Table*，如果 sstable 还没有打开，TableCache 负责打开文件并创建 Table 对象。

然后，调用 Table::InternalGet()查找 key。由于创建 Table 对象时，已经读入了 index block，通过 BloomFilter，判断 key 是否存在还是很快的。

如果判断 key 可能存在某一个 data block 当中，到 BlockCache 当中查找 Block*，有则直接使用，没有则从文件读取并构造 Block*后添加到缓存中。

最后使用 Block*，确认 key 是否真正存在，并读取数据。

TableCache和BlockCache都是LRU结构的缓存对象，TableCache缓冲Table*对象，BlockCache缓存Block*对象。