LevelDB SSTable 模块

作为 LevelDB 存储引擎的核心组件，SSTable（Sorted String Table）模块承担着数据持久化与高效读写的关键职能，是保障 LevelDB 性能的重要基石。

本目录围绕 SSTable 模块展开系统解析，先从文件格式切入，明晰其底层数据组织逻辑；再深入数据块构建过程，阐述数据如何有序存储；随后剖析索引构建机制，揭示快速定位数据的原理；进而讲解读取流程，呈现数据检索的完整链路；最后附上参考资料，为深入研究提供方向，助力读者全面掌握 SSTable 模块的核心技术要点。

文件格式

sstable 按照 4K 大小，分为若干个 block，每个 block 除了数据外，还有压缩类型，CRC

footer 固定为 48 个字节，因为采用了变长编码，如果不足长度，需要填充 0

其中最后的 magic number 是固定的长度的 8 字节： 0xdb4775248b80fb57ull

BlockHandle 指向文件的某个位置和偏移量，用于自解释，一个 varint64 最多 10 个字节，所以 footer 包含了 4 个最多 40 字节，不够级补 0

各个文件块的含义

• Data Blocks: 存储一系列有序的 key-value

• Meta Block：存储 key-value 对应的 filter(默认为 bloom filter)

• metaindex block: 指向 Meta Block 的索引

• Index BLocks: 指向 Data Blocks 的索引

• Footer : 指向索引的索引

文件块的物理格式，这里采用了前缀压缩的方式先存储一个完整的 key，后面的 key 存储时，记录公有部分，只存非公有部分即可

逻辑格式

数据库的构建

构建数据块的实现在 table/block_builder.cc 中

主要函数

Add 过程

• 如果小于重启点阈值，默认为 16，则求出当前 key 和 last_key 的公共部分长度

• 如果大于重启点，则直接将整个 key 的长度记录下来，并清空 重启点 counter

• 记录非公共部分，然后记录变长 int32 的 shared、non_shared 长度，value 长度

• 追加到 std::string buffer_ 中

• 更新 last_key_ 为当前 key 的公共部分

Finish

• 将所有每个重启点都记录下来，保存为 fixed32

• 记录所有充重启点数量

• 重启点变量：std::vector<uint32_t> restarts_; // Restart points

• 重启点变量中记录的是长度，对应的就是 key-value 的偏移量

数据块的组织

key_shared、non_shared，value 的组织结构

数据的查找

查找入口

• 这里会在 重启点中，做二分查找

• 找到 key < target 的最后一个重启点

• 找到后，跳转到重启点

• 自重启点线性向下，直到遇到 key>= target 的 k/v 对

索引的构建

索引的构建实现，在 table/table_builder.cc 中

这个文件中的 主要函数为

Add 流程

• 上一个块的最后一个 key，和当前要写入的(也就是后面一个块的第一个 key)，计算这两个 key 非分割

• 假设上一个块的最后一个 key 是：“the quick brown fox”，当前的块第一个 key 是：“the who”

• 分割的 key 就是 “the r”，正好比"the qu…" 的"q" 的 ASCII + 1

• 如果上一个 key 正好是当前 key 的前缀，那么直接返回 上一个 key

• 增加到 索引块中

• 根据情况增加 filter 块

• 将 last_key 设置为 当前 key，为后面做准备

• 总数量++，写入到 data_block 中

• 如果大于阈值，则 flush

Flush 流程

• 调用 WriteBlock 写入数据

• 如果写成功，则将 pending_index_entry 设置为 true，后面再写新的块，Add 流程的时候就会用到这个变量

• 刷新到磁盘，处理 filter 块

WriteBlock，写入的格式为：

• 首先将 重启点写入到 buffer 中

• 是否要压缩，只支持 snappy 压缩类型

WriteRawBlock

• 这个就是将待写入的内容，append 到磁盘文件上

• 最后补充 5 个字节的内容，1 个字节是 压缩类型，4 个字节是 CRC

索引块的组织

读取

读取相关的实现在 table/table.cc

重要函数

读取返回的是一个 两层的迭代器

两层迭代器中的两个变量

Open 过程

• 调用系统的文件 API，随机读 Footer 部分

• 读取 index block，读取 meta block，并设置对应的变量保存

ReadMeta 过程

• 读取 meta 部分的 block，封装成一个 Block 对象

• 创建一个两层迭代器，读取 meta 中的 filter

• 读取第一个 filter block 块，封装为 BlockContents 对象

• 再在第一个 filter block 的基础上，创建 FilterBlockReader 对象

BlockReader 过程

• 这个就是调用系统的 文件 API，随机读数据部分

• 先 new 一个固定大小的 buffer，然后读进去，再 CRC 检查，并确定压缩类型，看是否要解压

• 最后封装到 BlockContents 中返回

• BlockContents 中包含了一个 Slice，数据就放在这里了

InternalGet 过程

• 先创建一个两层迭代器

• index 迭代器根据 key，返回数据块迭代器

• 在数据库迭代器上如果有 filter，则检查 这个 key 是否匹配 filter，也就是 bloom-filter 是否匹配

• 匹配的话，则读取这个数据块，跳转到对应的位置，具体处理逻辑是一个回调函数，回调函数内处理 key，value

• 检查 status，并返回

参考

• 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 MemTable 模块

• LevelDB Log 模块

• LevelDB 公开的接口

• LevelDB 基本概念