LevelDB：读操作

前面写了两篇文章介绍 LevelDB 的整体架构和接口使用。这篇文章，我们从代码的角度看看 LevelDB 的设计与实现，先从读操作开始。

LevelDB 的版本更新不是很频繁，整体变化不大。本文的源代码参考和索引的版本是 LevelDB v1.20。

LevelDB 的目录结构很简单，就不用介绍了，直接进入正题吧。

leveldb::DB

LevelDB 暴露给外部的操作接口都封装在 leveldb::DB 这个抽象类里，具体实现是 leveldb::DBImpl 。使用时，leveldb::DB 用于引用一个 LevelDB 实例。一个 LevelDB 实例可以简单认为是一个支持并发读写和持久化的 map。

LevelDB 暴露给外部的操作接口都很简单，具体可以根据上面提供的索引链接看看代码和注释。

读操作

leveldb::DB::Get 根据 Key 获取 Value，先看看函数的原型：

virtual Status Get(const ReadOptions& options, const Slice& key, std::string* value) = 0;

leveldb::ReadOptions 是读操作的一些参数。verify_checksums 和 fill_cache 是两个偏优化的参数，重点是 snapshot 参数，表示本次读操作要从哪个 Snapshot 读取。snapshot 默认是 NULL，此时 LevelDB 会从当前 Snapshot 读取。

讲到 Snapshot，我们顺便来看看 leveldb::Snapshot 的实现。leveldb::Snapshot是个空壳，具体实现是在 leveldb::SnapshotImpl ，也相当简单，和 Snapshot 相关的变量只有一个 number_ (SequenceNumber) —— 不难看出 LevelDB 是通过维护一个 Sequence Number 来实现快照功能。

LevelDB 单个 Key 的读取操作的具体实现是 leveldb::DBImpl::Get 。我们来看看读操作的过程：

1. 获取互斥锁。
2. 获取本次读操作的 Sequence Number：如果 ReadOptions 参数的 snaphot 不为空，则使用这个 snapshot 的 Sequence Number；否则，默认使用 LastSequence（LastSequence 会在每次写操作后更新）。
3. MemTable， Immutable Memtable 和 Current Version 增加引用计数，避免在读取过程中被后台线程进行 Compaction 时“垃圾回收”了。Version 主要用来维护 SST 文件的版本信息。
4. 释放互斥锁 ，下面 5 和 6 两步是没有持有锁的，特别是第 6 步。
5. 构造 LookupKey 。
6. 查找
   1. 从 MemTable 查找 。
   2. 从 Immutable Memtable 查找。
   3. 从 SST 文件查找。
7. 获取互斥锁
8. 更新 SST 文件的统计信息，根据统计结果决定是否调度后台 Compaction。
9. MemTable, Immutable Memtable 和 Current Version 减少引用计数。
10. 释放锁（由析构函数完成），返回结果。

MemTable

上面分析读流程的时候，可以发现第 6 步，从 Memtable、Immutable Memtable 和 Current Version 指向的 SST 文件查找内容是不需要持有锁的。这样做没有并发读写的问题吗？

简单分析一下：引用计数保证了相关文件和内存数据结构不会被回收，而 Immutable Memtable 和 SST 文件都是只读的，没有并发读写问题。所以，只要看 MemTable 是否支持并发读写。

leveldb::MemTable 底层的实现是 leveldb::SkipList 。在 leveldb::SKipList 有一段注释说明 ，简单地说就是：

1. 写写冲突需要外部同步。
2. 读写冲突不需要外部同步，只要保证 SkipList 不会被垃圾回收就好。
3. 这里的 SkipList 只插入，不修改和删除 。

因此，从这段注释可以看出，MemTable 支持一写多读同时并发操作。后面有机会聊到 LevelDB 的写操作再来介绍一下 SkipList 的 Insert 操作如何实现读写并发不需要锁。

LookupKey

LevelDB 通过 user_key 和 sequence 构造 leveldb::LookupKey ，用于 LevelDB 内部接口的查找。参考 LookupKey 的代码和注释 ，其格式为：

LookupKey.png

1. klength 的类型是 varint32，是 leveldb 内部编码的可变长度的 uint32_t，存储 userkey + tag 的长度。表示一个 varint32 最多需要 5 个字节。
2. userkey 就是一个 userkey 的 char 数组。
3. tag 是使用 LittleEndian 编码的 uint64，其组成是 7 字节的 sequence 和 1 字节的 value_type。
4. 所以，一个 LookupKey 的最大长度为: 5 + userkey size + 8 = userkey size + 13。

SST 文件的查找

LevelDB 中将 SST 文件的管理实现成 leveldb::Version ，同时实现了 leveldb::VersionSet 管理多个 Version —— 因为 LevelDB 要支持 MVCC 所以可能同时存在多个版本。

查找的时候，获取当前版本 current , 调用 leveldb::Version::Get 在 SST 上进行查找。

1. 从 level0 开始一层一层查找 —— 小 level 的数据比大 level 新，所以如果先找到了的话可以直接返回。
2. 在要查找的 level 收集需要查找的文件。level0 的 sst 文件比较特殊，是直接由 Immutable MemTable dump 得到的，因此，每个文件的 key 范围可能重叠。level0 可能需要查找多个文件，其它 level 的 文件的 key 不会重叠，至多只需要读一个文件。
3. 对步骤 2 收集到的文件进行查找。具体查找逻辑由 leveldb::TableCache::Get 实现。这里面涉及一些 Cache 相关的实现，暂时略过。
4. 查找过程会记录一些统计信息：如果不止读取一个 sst 文件，则记录最后读取的是哪个 level 的哪个文件。

读触发的 Compaction

读取结束后，如果不止读取一个 sst 文件，则更新统计信息，决定是否触发 Compaction。更新统计信息时，直接将记录的文件的 leveldb::FileMetaData 的 allowed_seeks 减一，当 allowed_seeks <= ０时，表示读取效率很低，需要执行 Compaction，减少这条路径上的文件数量。

调用 MaybeScheduleCompaction 尝试调度后台线程的 Compaction。

小结

这里只是简单介绍了 LevelDB 的读操作的大概情况。实际上，LevelDB 的读操作涉及很多东西，如：写操作相关的并发读写、Sequence Number 等；Compaction 相关的 Version、VersionSet等；读操作还有可能触发 Compaction；还有 Table Cache、Block Cache 这些相关的东西没提及。

参考文档

• LevelDB Source Code
• SSTable and Log Structured Storage: LevelDB