put完整流程经过前面 LevelDB 源码第一、二阶段的学习我们首先从其对外接口入手了解了 LevelDB 作为一个 KV 存储系统的整体框架结构。通过阅读db.h、options.h、slice.h、status.h等接口文件我们发现 LevelDB 虽然对外暴露的是简洁的Put、Get、Delete等操作但其内部涉及日志、内存表、跳表、编码格式和版本控制等多个模块。我们在调用db-Put(key, value)的时候并不会立刻将其写入到磁盘里面去而是经过了类似mysqlredis这些一样的操作先对其进行记录然后再统一写入。首先是将该写操作封装到writebatch中并且按照一定的格式进行编码然后DBImpl::Write会将编码后的东西追加到wal日志中以保证系统奔溃后仍然可以恢复。其实他在追加wal的时候并不是来一个写一个而是源码维护了一个writers_写请求队列然后每一个写操作都会被封装成writer并将其加入到队列。只要当某个writer位于队头的时候他才会真正获得写入执行权而队列中其他成员仍然是等待状态。队头writer在执行时还会将后续的多个写请求合并成一个更大的writerbatch从而减少了日志写入与锁竞争的开销。这种机制可以看成一种简单的group commit思想。当wal写入成功后leveldb才会将这些写操作进一步插入到memtable中。具体来说他会先解析writebatch中的每条记录并调用add。在add中leveldb会从arena内存池中申请一块连续空间将user key、sequence number、value type和value编码成一个完整的 entry。最后memtable会将该entry的指针插入到底层skiplist中然后根据internalkey的顺序维护有序结构。当memtable写满之后LevelDB 不会直接在原地继续写入而是会将当前 MemTable 转换为 Immutable MemTable即不可变内存表同时创建新的 MemTable 继续接收后续写请求。随后后台线程会将 Immutable MemTable 刷写到磁盘生成 Level-0 SSTable 文件。至此原本写入内存的 key-value 数据才真正以有序文件的形式落到磁盘数据层中。下面会去思考一下关键的细节Immutable MemTable 是怎么刷成 SSTable 的通过一个迭代器来实现他会按照顺序遍历其中的数据并调用TableBuilder将这些有序的entry写成磁盘上的 Level-0 SSTable 文件。SSTable 文件内部结构是什么------------------| Data Block 1 |------------------| Data Block 2 |------------------| Data Block 3 |------------------| ... |------------------| Filter Block | 可选Bloom Filter------------------| MetaIndex Block |------------------| Index Block |------------------| Footer |------------------Data Block是真正保存 key-value 的地方。但是它不是每个 key 都完整存一遍而是用了前缀压缩。也就是说当前 key 上一个 key 的前 shared 部分 当前 key 的 non_shared 部分这样可以减少磁盘空间。Index BlockIndex Block 是 Data Block 的索引。它里面保存的是某个 Data Block 的最大 key 或分隔 key - 这个 Data Block 在文件中的位置查询时不用扫描整个 SSTable而是先查 Index Block定位到可能包含目标 key 的 Data Block。这个意思就是相当于目录假如Data Block 1:applebananacatData Block 2:dogeggfishData Block 3:goathorse那么Index block里面存的是cat - Data Block 1 的位置fish - Data Block 2 的位置horse - Data Block 3 的位置也就是说Index Block 分隔 key Data Block 的文件位置Filter Block如果开启 Bloom FilterSSTable 里面还会有 Filter Block。它的作用是快速判断这个 SSTable 里大概率没有这个 key如果 Bloom Filter 判断不存在就不用读 Data Block 了。LevelDB 的 Filter Block 通常由 Bloom Filter 实现。当用户配置filter_policy后TableBuilder 在生成 SSTable 时会为数据块构建过滤信息。查询时LevelDB 会先利用 Filter Block 判断目标 key 是否可能存在于对应的数据块中。如果 Bloom Filter 判断不存在则可以直接跳过该 Data Block从而减少不必要的磁盘读取如果判断可能存在则继续读取 Data Block 进行精确查找。Bloom Filter 不会产生漏报但可能产生误报。FooterFooter 在文件最后保存MetaIndex Block 的位置 Index Block 的位置 Magic Number读取 SSTable 时LevelDB 会先读 Footer再通过 Footer 找到 Index Block 和 MetaIndex Block。所以 SSTable 可以总结成Data Block 存真正的 key-value Index Block 定位 Data Block Filter Block 快速判断 key 是否可能存在 Footer 记录关键索引位置Compaction 是怎么合并文件的LevelDB 发现某一层文件太多↓PickCompaction() 选择需要合并的文件↓读取当前层文件和下一层重叠文件↓创建合并迭代器↓按 InternalKey 顺序归并↓丢弃旧版本数据和无效删除标记↓生成新的 SSTable 文件↓更新 Version 元数据Compaction 的主要作用是1. 减少文件数量 2. 减少读放大 3. 清理旧版本 key 4. 清理删除标记 5. 维护 Level 之间的有序结构Get 查询流程当用户调用db-Get(key)时LevelDB 会先根据当前快照序列号构造一个LookupKey。这个LookupKey并不只是普通的 user key而是包含 user key、sequence number 和 value type 的内部查找 key用于和 MemTable、Immutable MemTable 以及 SSTable 中的 InternalKey 进行比较。LevelDB 查询时会按照从新到旧的顺序进行查找。首先查当前正在写入的 MemTable如果没有找到再查 Immutable MemTable。如果这两层内存结构中都没有目标 key才会继续到磁盘上的 SSTable 文件中查找。整体流程如下db-Get(key) ↓ 构造 LookupKey ↓ 查找当前 MemTable ↓ 查找 Immutable MemTable ↓ 查找 Level-0 SSTable ↓ 查找 Level-1、Level-2 等更高层 SSTable ↓ 返回 value 或 NotFound在 MemTable 和 Immutable MemTable 中LevelDB 会通过 SkipList 的Seek操作定位第一个大于等于LookupKey的 entry然后解析该 entry 的 InternalKey判断 user key 是否匹配。如果匹配并且 type 是kTypeValue则返回对应 value如果 type 是kTypeDeletion则说明该 key 已经被删除返回 NotFound。如果内存中没有找到LevelDB 会进入当前 Version 管理的 SSTable 文件中查找。对于 Level-0由于多个 SSTable 文件之间的 key 范围可能重叠因此可能需要按文件新旧顺序查找多个文件而 Level-1 及更高层级的 SSTable 文件之间 key 范围通常不重叠因此可以通过 key 范围快速定位到某一个可能包含目标 key 的文件。在查找某个 SSTable 时LevelDB 会先通过 Footer 找到 Index Block再由 Index Block 定位可能包含目标 key 的 Data Block。如果配置了 Bloom Filter还会先通过 Filter Block 判断该 key 是否可能存在于对应数据块中。如果 Bloom Filter 判断不存在则直接跳过该 Data Block如果判断可能存在则读取 Data Block 并进行精确查找。视图管理对于sstable的管理而言version里面存储了当前数据库所有 SSTable 文件的一个视图记录了每一层有哪些文件。而VersionSet是存储的是全部version版本而Version只是某一时刻的 SSTable 文件视图------------------------------------------------------------------------------------------------------------------MANIFEST则是SSTable发生了什么样的变化例如新增了哪个 SSTable 删除了哪个 SSTable 某个文件属于哪一层VersionEdit就是一次元数据修改。例如一次 Compaction 之后这次修改就会被编码成一个VersionEdit写入 MANIFEST。CURRENT它里面通常只写着当前 MANIFEST 文件名所以 LevelDB 打开数据库时先读 CURRENT↓知道当前 MANIFEST 是哪个↓读取 MANIFEST↓恢复 VersionSet所以奔溃恢复依靠的是WAL MANIFESTDB::Open↓Recover↓读取 CURRENT↓读取 MANIFEST↓恢复 VersionSet↓找到还没刷成 SSTable 的 log 文件↓重放 WAL↓重新构建 MemTable↓必要时把恢复出来的 MemTable 刷成 SSTableIterator跨多个结构的统一遍历LevelDB 里面大量使用 Iterator。因为数据可能在很多地方MemTable Immutable MemTable Level-0 多个 SSTable Level-1 SSTable Level-2 SSTable ...但是对上层来说希望看到的是一个统一有序视图。于是 LevelDB 会创建很多底层 Iterator然后再合并。相关源码vim table/iterator.cc vim table/two_level_iterator.cc vim db/db_iter.cc vim db/merger.ccTwoLevelIterator你前面问过 Index Block。SSTable 查询里面有一个 TwoLevelIterator第一层Index Block Iterator 第二层Data Block Iterator它的工作方式像翻书先看目录定位章节 再翻到具体章节看内容对应 SSTableIndex Block 定位 Data Block Data Block Iterator 遍历真正 key-valueMergingIterator如果要遍历整个数据库就要合并多个来源mem_ iterator imm_ iterator Level-0 file iterator Level-1 file iterator Level-2 file iterator ...这些 iterator 各自内部有序。MergingIterator的作用就是把它们归并成一个整体有序的迭代器。类似归并排序iter1: a c e iter2: b d f ↓ merged: a b c d e fLevelDB 的 Compaction 也大量依赖这种归并迭代器。DBIter底层 InternalKey 里面可能有多个版本name, seq105 → Tom name, seq101 → Bob name, seq100 → Alice但用户 Iterator 不应该看到三个name。用户只应该看到当前快照下可见的那个版本。所以DBIter做了一层过滤跳过被覆盖的旧版本 跳过删除标记 只返回 user key 和 value也就是说Internal Iterator 看到的是 InternalKey DBIter 对用户暴露的是 user keyTableCache / BlockCache减少磁盘 IOGet 查询 SSTable 时如果每次都打开文件、读 block会很慢。所以 LevelDB 有缓存。相关源码vim db/table_cache.cc vim util/cache.cc vim include/leveldb/cache.hTableCacheTableCache缓存的是SSTable 文件句柄 Table 对象也就是说如果某个.ldb文件之前打开过下次可以复用不用重新打开文件和解析 Footer。可以理解为TableCache 缓存打开过的 SSTableBlockCacheBlockCache缓存的是Data Block 内容比如某个 Data Block 被读取过一次下次再查附近的 key就可能直接从 BlockCache 拿不用再读磁盘。可以理解为BlockCache 缓存 SSTable 里面的数据块Get 磁盘查询时的底层流程、当 LevelDB 收到Get(key)请求时会先在内存结构中查找也就是先查当前MemTable再查Immutable MemTable。如果这两个地方都没有找到才会进入磁盘 SSTable 查询流程。进入磁盘查询前DBImpl::Get会先通过versions_-current()获取当前有效的Version。这个Version记录了当前数据库中所有有效 SSTable 文件的元数据包括文件编号、所在层级、文件大小、最小 key 和最大 key 等信息。随后LevelDB 会调用Version::Get。Version::Get会根据目标 key 和每个 SSTable 文件记录的 key 范围判断哪些 SSTable 文件可能包含该 key。对于 Level-0由于不同 SSTable 文件之间的 key 范围可能重叠所以可能需要按文件新旧顺序查找多个文件而对于 Level-1 及以上层级由于同一层内的 SSTable 文件通常不重叠因此可以通过 key 范围快速定位到某一个可能包含目标 key 的文件。当确定某个 SSTable 文件可能包含目标 key 后LevelDB 会调用TableCache::Get。TableCache的作用是缓存已经打开过的 SSTable 文件对象。如果该 SSTable 之前已经被访问过就可以直接从缓存中取出对应的Table对象如果没有命中缓存则需要打开对应的.ldb/.sst文件并通过文件末尾的Footer找到Index Block和MetaIndex Block的位置。拿到Table对象后LevelDB 会先通过Index Block定位目标 key 可能所在的Data Block。如果该 SSTable 配置了 Bloom FilterLevelDB 会进一步检查Filter Block。如果 Bloom Filter 判断该 key 一定不存在就可以直接跳过这个 Data Block避免一次不必要的磁盘读取如果 Bloom Filter 判断该 key 可能存在则继续读取对应的 Data Block。读取 Data Block 时LevelDB 还会先检查BlockCache。如果该 Data Block 已经在缓存中就直接从缓存读取如果没有命中缓存才会真正从磁盘读取 Data Block。最后LevelDB 会在 Data Block 内部查找目标 key并根据找到的 InternalKey 类型返回 value 或 NotFound。大概是Version::Get ↓ 找到可能包含 key 的 SSTable 文件 ↓ TableCache::Get ↓ 检查 TableCache 是否已有 Table ↓ 读取 Footer ↓ 找到 Index Block ↓ 用 Index Block 定位 Data Block ↓ 检查 Filter Block ↓ 如果 Bloom Filter 判断不存在直接跳过 ↓ 检查 BlockCache ↓ 如果缓存没有读磁盘 Data Block ↓ 在 Data Block 中查 keyLevelDB 底层不是简单的 key-value map而是一套基于 sequence number 的多版本有序存储系统。WAL 保证崩溃恢复MemTable 负责内存写入SSTable 负责磁盘有序存储VersionSet/MANIFEST 管理文件元数据Snapshot 和 InternalKey 保证读取视图一致Compaction 负责整理文件并清理旧版本。