LevelDB 多版本和压缩

作为高性能键值存储库，LevelDB 的高效运行离不开多版本机制与压缩策略的支撑。多版本如何实现数据的并发读写与历史回溯？压缩机制怎样平衡存储效率与访问性能？当数据遭遇异常，恢复机制又如何保障可靠性？本文将围绕这三大核心维度，拆解 LevelDB 的底层设计智慧。

文件类型：

多版本

版本管理中相关的类

• Version 标识了一个版本，主要信息是这个版本包含的 SSTable 信息；

• VersionSet 是一个版本集，里面保存了 Version 的一个双链表，其中有一个 Version 是当前版本，因为只有一个实例，还保存了其它的一些全局的元数据，Dummy Version 是链表头；

• VersionEdit 保存了要对 Version 做的修改，在一个 Version 上应用一个 VersionEdit，可以生成一个新的 Version；

• Builder 是一个帮助类，帮助 Version 上应用 VersionEdit，生成新版本

VersionSet 是一个双链表结构，每个 Version 代表了一个版本

将当前的 版本 和 VersionEdit 合并之后，就得到了一个新的版本 VersionEdit 就是一次 Minor Compaction、或者是 Major Compaction 的结果

版本管理的工作流程：

• VersionSet 里保存着当前版本，以及被引用的历史版本；

• 当有 Compaction 发生时，会将更改的内容写入到一个 VersionEdit 中；

• 利用 Builder 将 VersionEdit 应用到当前版本上面生成一个新的版本；

• 将新版本链接到 VersionSet 的双链表上面；

• 将新的版本设置为当前版本；

• 将旧的当前版本 Unref，就是引用计数减 1。

版本控制中的引用计数：

• 每个 Version 包含了一个引用，当前版本的 ref 为 1

• 当有迭代器需要遍历数据库时，这个版本的 ref ++ 等于 2

• 其他线程不断写入，触发 compaction，生成新版本

• 新版本 + 1，老版本 - 1

• 因为 老版本为 1，所以不会被删除，直到迭代接受，ref = 0

• 如果 Version 的 ref 为 0，则可以删除了

实际存储的时候，是存入dbname/MANIFEST-[0-9]+ 这样的文件 CURRENT 指向最新的 manifest 文件 Version 相当于 一个 manifest 文件，VersionSet 则管理多个 manifest 文件 VersionSet 头结点指向最新的 manifest 文件

FileMetaDatasstable 的元信息

Version

位置：db/version_set.h

读取数据库时，就需要 Version 里面的信息

VersionEdit

VersionEdit 中包含了两个函数

这个就是一个 编码，一个解码将 dst 中的信息，写入到所有变量中，以及从 变量中解码信息到 Slice 中

VersionSet

VersionSet::Builder 辅助类

主要变量：

LevelFileNumIterator

主要变量

其中 new 出来的 两次迭代器，就使用到了 LevelFileNumIterator

builder 版本变迁过程

总结一下

• 整体是 VersionSet 的双链表结构，一个版本由 Version 表示

• VersionEdit 是一次变更，比如 sstable 新增，删除(通过压缩产生)，通过 应用 VersionEdit 就可以得到一个新版本

• builder 会加速变更，可以将多个 VersionEdit 一次性应用

• 每个 Version 内部关联了一个 FileMetaData，表示一个 sstable 的元数据，内部包含了 min、max key 方便定位

• MANIFEST 实际关联了一个 log 文件，还会将变更的内容当做 log 记录下来，等启动恢复的时候，就会读取这些 log 文件

压缩

压缩，包含两种

• Minor Compaction，mem-table 写满会后刷盘，写入到 level-0 中

• Major Compaction，某个层的文件太多，需要将部分文件推入更高层

Minor Compaction 过程

Minor Compaction 时序图

WriteLevel0Table 过程

• 得到一个新的 FileMetaData 编号，就是 VersionSet->next_file_number_++

• 调用 BuildTable，其生成的 TableFileName 是根据 FileMetaData 的编号得到的

• 获取 min、max key，然后确定将 ss-table 推入哪个层级，调用 PickLevelForMemTableOutput

• 将 压缩状态存入 CompactionStats[level] 中，这里的 level 固定为 PickLevelForMemTableOutput 返回的层级

BuildTable 过程：

• 从 skip-list 的第一个元素开始遍历，一直到结束，将这些 key-value 加入到 TableBuilder

• 同时记录 FileMetaData 的最大、最小、key 数量、文件 size

• 将数据写入到磁盘

PickLevelForMemTableOutput

• 如果跟 0 层的有重叠，则推入 0 层

• 检查方式是，对于 level0，需要遍历所有文件，检查每个文件跟 min、max key 是否有重叠

• 非 level 0 的，则使用 二分查找 当前层的所有文件

• 还会检查 level 0、level 1 在其祖父层级(对应的就是 level 2、level 3 中，是否重叠太多

• 默认的最大单个文件大小为 2M，如果一次重叠的数量 > 20M，PickLevelForMemTableOutput 会继续往更深层级查找

• 不过限制了最大查找层级为 2，这也是做了一个权衡

Major Compaction 的过程

Compaction 类

ManualCompaction 类

Compaction 的触发方式

• Manual Compaction

• Size Compaction

• Seek Compaction

手动压缩的触发函数：

Size compation

• 实现函数为： void VersionSet::Finalize(Version* v)
  

• 对于 leve 0，如果 > 4 就会触发

• 超过 0 的，如果超过了 10^n MB 就会触发

• 由于 ss-table 的不变性，只有版本变更的时候才会变化

• 在每次版本变更之后，调用 Finalize，计算出比例最大的 level，下次就从这里开始

• 由于一次压缩要很久，这里会记录一个 level 的 key，std::string compact_pointer_[config::kNumLevels];

• 下次再压缩这一层的时候，就从这个 key 开始继续压缩

Seek Compaction

• 为读做的优化，DB::GET、DBIter 时候，如果读取了超过一个 ss-table 则需要优化

• 对于读取 超过一个 的 ss-table，对于第一个 ss-table 做一个 减操作，如果等于 0 了，就需要做压缩

• 所以 seek 是精确到某个 ss-table 的

• 迭代的时候，是每读取 2M 数据，就模拟一个 key，做对应的 ss-table–

• 初始值，static_cast((f->file_size / 16384U))

• 一次 Seek 花费 10ms；

• 读写 1MB 的花费 10ms （100MB/s）；

• 而 Compaction 1MB 的数据花费 25MB 左右的 IO

执行过程

• 执行优先级是 Manual、Size、Seek

• 前两者是根据 start、end key 选择某一个 level 的多个文件

• 后者只有确定的一个文件

• 根据 level 层的文件，再确定 level + 1 层的文件，之后再反向 level 层扩大 level 的输入范围

• 最后调用多路合并，进行压缩

扩大输入文件集合

• 确定起始 key、结束 key

• 在 level i 层中，查找与起始输入文件有 key 重叠的文件，如图中红线所标注，最终构成 level i 层的输入文件；

• 利用 level i 层的输入文件，在 level i+1 层找寻有 key 重叠的文件，结果为绿线标注的文件，构成 level i，i+1 层的输入文件；

• 最后利用两层的输入文件，在不扩大 level i+1 输入文件的前提下，查找 level i 层的有 key 重叠的文件，结果为蓝线标准的文件，构成最终的输入文件；

归并的过程：

• 迭代按照 Internal Key 的顺序进行，多个 key 则按 seq number 降序排列

• 相同的 key 只有第一个有效，因为它的 seq 是最大的

• 碰到一个删除时，并且它的 seq_number <= 最新快照，会判断更高层是否有这个 key

• 如果有则无法丢弃这个删除操作，因为一旦丢弃，更高层又可见了，不存在可则可以删除

• 如果 ss-table 达到 2M，或者和上层文件重叠超过 10 个，这两个条件任意一个触发就会 生成一个 ss-table 写磁盘

数据删除的处理

• 如果是覆盖写入，则当做一个删除处理，即按照降序排序，前面的覆盖后面的，后面重复的 key 可以忽略

• 如果是删除标记，并且 level + 1 层没有这个 key，则可以删除

• 如果这个 key 的 seq_number <= 最老快照的序列号，则可以删除，否则不能删除(因为可能被使用中)

level 0 的压缩过程

• 选择 key 800 - 2500

• 因为 level 0 有重叠，遍历所有文件，找到 key 重叠的文件，确定 start、end key

• 选择 level 1 层，根据 start key、end key 确定 level 1 层的文件

• 将 level 0 和 level 1 的文件做多路归并

level > 0 的压缩过程

• 选择 key 800 - 2500

• 因为是完全有序的，可以根据二分搜索到确定的范围，确定出 level 层的文件

• 再确定出 level + 1 层的文件

MVCC 数据清理

• 遍历所有文件

• 小于 VersionSet 的 log_number_ 的文件

• 或者不在 遍历列表中的文件，则可以删除

恢复

LevelDB 打开需要做以下事情：

• 如果数据库目录不存在，创建目录

• 加文件锁，锁住整个数据库；

• 读取 MANIFEST 文件，恢复系统关闭时的元数据，也就是版本信息，或者新建 MAINFEST 文件；

• 如果上一次关闭时，MemTable 里有数据，或者 Immutable MemTable 写入到 SSTable 未完成，那么需要做数据恢复，从 WAL 恢复数据；

• 创建数据库相关的内存数据结构，如 Version、VersionSet 等

DBImpl::Recover 做了以下事情

• 创建数据库目录；

• 对这个数据库里面的 LOCK 文件加文件锁，单进程的

• 如果数据库不存在，那么调用 DBImpl::NewDB 创建新的数据库；

• 调用 VersionSet::Recover 来读取 MANIFEST，恢复版本信息；

• 根据版本信息，搜索数据库目录，找到关闭时没有写入到 SSTable 的日志，按日志写入顺序逐个恢复日志数据

• DBImpl::RecoverLogFile 会创建一个 MemTable，开始读取日志信息，将日志的数据插入到 MemTable

• 并根据需要调用 DBImpl::WriteLevel0Table 将 MemTable 写入到 SSTable 中

异常恢复

• 如果元数据丢了，但是数据还在，也可以恢复的

• 把所有 sstable 当做 level 0 层，然后不断做压缩

• 由于 sstable 数量会远大于 0，这样会大致大量的 compaction

• 经过很多次 compation 最后会稳定下来，形成新的 元数据

• 旧的文件则会删除

参考

• 论文《Less hashing, same performance:Building a better Bloom filter》

• github index

• Bloom Filters by Example

• 漫谈 LevelDB 数据结构（一）：跳表（Skip List）

• 漫谈 LevelDB 数据结构（二）：布隆过滤器（Bloom Filter）

• 漫谈 LevelDB 数据结构（三）：LRU 缓存（ LRUCache）

• LevelDB 源码剖析

• SF-Zhou’s Blog

• leveldb-handbook

• 庖丁解 LevelDB

• rust 使用

• LevelDB 使用介绍

• LeveLDB 维基百科

• dbdb.io 的 LevelDB 介绍

• MariaDB 的插件

• 书籍：精通 LevelDB

• leveldb 实现解析

• POSIX™ 1003.1 Frequently Asked Questions (FAQ Version 1.18)

• Spurious wakeup

• Memory barrier

• Memory Barriers: a Hardware View for Software Hackers

• Bean Li 的 LevelDB 文章汇总

• LevelDB 设计与实现 - Compaction

• LevelDB 设计与实现 - MVCC 等

• leveldb 源码剖析 系列

• HBase file format with inline blocks (version 2)

相关文章

• LevelDB 辅助工具类

• LevelDB SSTable 模块

• LevelDB MemTable 模块

• LevelDB Log 模块

• LevelDB 公开的接口