前面写了两篇文章介绍 LevelDB 的整体架构和接口使用。这篇文章,我们从代码的角度看看 LevelDB 的设计与实现,先从读操作开始。
LevelDB 的版本更新不是很频繁,整体变化不大。本文的源代码参考和索引的版本是 LevelDB v1.20。
LevelDB 的目录结构很简单,就不用介绍了,直接进入正题吧。
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 。我们来看看读操作的过程:
上面分析读流程的时候,可以发现第 6 步,从 Memtable、Immutable Memtable 和 Current Version 指向的 SST 文件查找内容是不需要持有锁的。这样做没有并发读写的问题吗?
简单分析一下:引用计数保证了相关文件和内存数据结构不会被回收,而 Immutable Memtable 和 SST 文件都是只读的,没有并发读写问题。所以,只要看 MemTable 是否支持并发读写。
leveldb::MemTable 底层的实现是 leveldb::SkipList 。在 leveldb::SKipList 有一段注释说明 ,简单地说就是:
因此,从这段注释可以看出,MemTable 支持一写多读同时并发操作。后面有机会聊到 LevelDB 的写操作再来介绍一下 SkipList 的 Insert 操作如何实现读写并发不需要锁。
LevelDB 通过 user_key 和 sequence 构造 leveldb::LookupKey ,用于 LevelDB 内部接口的查找。参考 LookupKey 的代码和注释 ,其格式为:
LookupKey.png
LevelDB 中将 SST 文件的管理实现成 leveldb::Version ,同时实现了 leveldb::VersionSet 管理多个 Version —— 因为 LevelDB 要支持 MVCC 所以可能同时存在多个版本。
查找的时候,获取当前版本 current , 调用 leveldb::Version::Get 在 SST 上进行查找。
读取结束后,如果不止读取一个 sst 文件,则更新统计信息,决定是否触发 Compaction。更新统计信息时,直接将记录的文件的 leveldb::FileMetaData 的 allowed_seeks 减一,当 allowed_seeks <= 0时,表示读取效率很低,需要执行 Compaction,减少这条路径上的文件数量。
调用 MaybeScheduleCompaction 尝试调度后台线程的 Compaction。
这里只是简单介绍了 LevelDB 的读操作的大概情况。实际上,LevelDB 的读操作涉及很多东西,如:写操作相关的并发读写、Sequence Number 等;Compaction 相关的 Version、VersionSet等;读操作还有可能触发 Compaction;还有 Table Cache、Block Cache 这些相关的东西没提及。