Leveldb 源码类功能解析

Leveldb 的基本介绍网上很多资料，这里不赘述，我们直接进入主题，解析 leveldb 源码中各个类（概念）的功能。

LRUCache

使用环状链表表示 LRU 数据，prev 指向最新，next 指向最旧，记录内存使用量，用来末尾淘汰。为了加快数据查找，使用了一张 hash 表，从 hash 表中查找到 LRU 的对象指针，若要删除即可直接调用 LRURemove 从环状链表中删除 LRU 对象。每次使用过的数据（即被 lookup 过的数据）会从 LRU 中 remove 再 append 进 LRU，保证最近使用的数据为最新。

TableCache

使用 LRUCache 缓存表信息，以 file number 做 key，table 指针和 file 指针组成的结构体的指针为 value。

MemTable

内部数据结构是 skiplist，保存有序的 key，以 user key 加上序列号的方式保存，user key 相同时，序列号大的排在前面，因此数据库维持了一个全局序列号，只向上递增，这样就保证了多次 user key 的操作，最新的操作放在所有老的操作前面。DB 的每次写入数据是先写 log 再把数据放入到 MemTable 中。

User Key/Internal Key/MemTable Key(SkipList Key, in SkipList Data)

放在 MemTable（由 SkipList 实现） 里的数据格式是：

table1.jpg

其中 Internal Key 是 User Key 加上 7 字节序列号和类型，MemTable Key 是 Internal Key 加上变 32 位长度。实际的 Comparator 比较的数据是 Internal Key，先用 User Key 比较，若相同，序列号大的 Key 更小。每次操作时，序列号递增，当删除已添加过的 User Key 时，序列号更大，则存放在前，同时有删除标记标识。查找某个 User Key 时，给的序列号是最大值，这样查到的 User Key 都在返回的 Iterator 之后，检查 Iterator 有效且 User Key 相同则查找到了。

Table

存储格式如下：

table2.jpg

每个 block 最末尾有 5 字节的数据，1 字节表示是否压缩，后 4 字节是 crc 校验数据，这 5 个字节不在 index block 的 value 范围内。

Data block 和 index block 里的数据以 key value 方式存放，格式如下：

table3.jpg

其中 Key 数据有压缩，每个 Key 与上一个 Key 共享前缀，减少空间使用，把不一样的后缀保存下来，最后存放value 数据。Restart array 里指向重新开始的 Key，即这个 Key 与前一个 Key 不共享前缀保存，开始一组新 Key，接下来的继续与前一个 Key 共享前缀。

最后放置了 meta index block 和 index block 分别用来索引 meta blocks 和 data blocks，其中索引 meta blocks 的 key 是 meta block 的名字，value 是下标及大小；索引 data blocks 的 key 是介于前一个 data block 的最后一个 key 和后一个 data block 的第一个 key 的中间 key，value 是下标和大小。

Table 提供 Iterator 访问元素，由于 Table 里有多个 data blocks 和 index block，因此访问元素的时候会有跨 block 的情况，而每次查找一个元素时，先在 index block 中查找到相应的 data block，再在查到的 data block 中查询。因此 Table 提供的 Iterator 是 two level 的，每个 data block 也提供 Iterator 供 Table 使用。

每个 Table 可能会使用 block cache (LRUCache) 来缓存 block 数据。

DB Iterator

DB Iterator 内部使用 Merging Iterator，Merging Iterator 把 MemTable 的 Iterator 和 current version 的所有 Iterator 归并。DB Iterator 维护删除和覆盖 Key 的逻辑查找，如果一个 Key 插入之后，又有过删除或者更新操作，那么这个 Key 的所有值会在一张表内连续存储，并且新值在旧值前，因此 DB Iterator 需要把这种 Key 跳过。

Iterator

Iterator 是整个 DB 的访问的核心接口，所有的数据集都实现了此接口。DB 同时也提供了归并 iterator，将多个 iterator 的数据归并，可用于 compact 操作。

VersionEdit

VersionEdit 是 DB 的版本描述记录信息，它 encode 后的数据构成 manifest 文件中的 record，一个版本由一个 manifest 文件描述，其中的多条 VersionEdit records 描述了整个版本的 table 文件。VersionEdit 可以是一个增量的 record，manifest 文件中的第一条记录是一条完整的 record，后面的多条record 是增量信息，所有 records 构成完整的版本描述。

Version

Version 描述了一个在内存中的数据库版本，它由 Builder 结合 VersionEdit 构建，若某个 Version 的引用技术降低为 0，此 Version 对象会从 VersionSet 中删除并析构。

VersionSet

VersionSet 描述整个 DB 打开之后历经的版本变化集合，DB 刚刚创建的时候，放入了一个空 Version 到VersionSet 中，再从 manifest 文件中读取持久化的 DB 版本信息 Version，并把它加入到 VersionSet 中，同时 current_ 指向当前 Version。当 DB 打开恢复完成，在后续操作中触发了 compact，那 compact 之后会产生新的 table 文件，此时版本也发生变化，即会创建新的 Version 来描述完成的 compact 结果，并把新的 Version 放入 VersionSet 中当作当前版本。

Compaction

Compaction 用来描述需要在后台执行的 compact 操作信息，包括需要操作的 level 等信息。Compact 操作由特定操作累计后触发，比如某个 level 文件的查询次数到了 100 次，这种 compact 是查找触发，名为 seek compact，此时 compact 的只是当前触发的文件；还有由 level 中文件的个数或者大小决定是否需要compact，名为 size compact，这是会将某个 level 中的多个文件 compact。每次 compact 时，并不是把下一个 level 的所有文件都提取出来 compact，而是把当前需要 compact 的文件与下一个 level 的文件中有重叠的文件取出来 compact。

Manifest

Manifest 文件描述了当前版本的所有文件信息。Manifest 文件以 log 的格式记录了一系列的 record 信息，每个 record 是 VersionEdit 编码之后的结果。当 DB 打开的时候会重新创建一个新的 manifest 文件，并把老的 manifest 文件中所有 records 恢复的 VersionEdit 信息写入到新的 manifest 文件中作为第一条 record，之后的所有操作都在新的 manifest 文件中进行，老的 manifest 以及不再使用的 table 文件会在文件垃圾回收的时候被删除，也就是说 DB 每次打开创建新的版本，并把老的版本删除。

Log 文件格式

把文件按 32KB 分成块，每块里面存储一组 record 片信息（每个 record 片大于等于 7 字节，小于 32KB），如果一个逻辑 record 的大小大于块大小，那么就跨越多个块存储，用 first-middle-last 标记这些 record 分片。每个 record 分片中会有 checksum 数据用于校验，这种方式的好处是，当某些块数据错误时，可以简单的跳过一些块，继续读取接下来没有数据错误的块（找到 checksum 正确的并且是 full 或者 first 的 record 片）。

Log

Log 的内容与 MemTable 保持一致，所有记录写入到 DB 时先写入到 log 中，再将数据写入 MemTable。

Level 0

Level 0 有多个文件，由 MemTable 写满之后生成，一个 MemTable 对应一个 Level 0 文件，生成的时候把MemTable 中同一个 user key 的多个记录只保留最新的记录，这样保证一个 level 0 文件中的 user key 不重复并有序排列。不过由于多个 level 0 的文件由多个 MemTable 在不同时间生成，因此，这些 level 0 文件之间的 user key 可能会重叠。

Level 1~N

Level 1 到 Level N 的每个 level 中都有多个文件。同一个 level 中的每个文件的 user key 有序排列，且这些文件不存在 user key 重叠的情况，由 compact 逻辑保证。Level 与 Level 之间的 user key 可能会有重叠（即在 level m 中存在的 key，在 level n 中也存在），因此 compact 的时候需要处理这些重叠数据，保证新生成 level 的各个文件中的 user key 无重叠。