LevelDB 完全解析（三）：SSTable

前文回顾

• LevelDB 完全解析（0）：基本原理和整体架构

• LevelDB 完全解析（1）：MemTable

• LevelDB 完全解析（2）：Log

文中“蓝色字体”部分均有跳转，大部分是引用了 Github 上的源码链接，可以点击【阅读原文】查看。

SSTable 全称 Sorted String Table，顾名思义，里面的 key-value 都是有序保存的。除了两个 MemTable，LevelDB 中的大部分数据是以 SSTable 的形式保存在外存上。

SSTable 由 compaction 生成：

• Minor Compaction：一个 MemTable 直接 dump 成 level-0 的一个 SSTable。

• Major Compaction：多个 SSTable 进行合并、重整，生成 1～多个 SSTable。

SSTable 的格式

在一个 SSTable 中，文件末尾的 Footer ^[1] 是定长的，其他数据都被划分成一个个变长的 block：index block、metaindex block、meta blocks、data blocks。

• Footer

Footer 的大小为 48 字节，内容是一个 8 字节的 magic number ^[2] 和两个 BlockHandle ^[3] —— index handle 和 meta index handle，index handle 指向 index block，meta index handle 指向 meta index block。BlockHandle 相当于一个 block 的“指针”，由这个 block 的 offset(varint64) 和 size(varint64) 组成。由于采用 varint64 进行编码，每个 varint64 最多占用 10 字节 ^[4] ，所以一个 BlockHandle 最多占用 20 字节。因为 BlockHandle 是定长，而 BlockHandle 编码的结果是变长的，所以 Footer 编码的时候需要进行 padding ^[5] 。

• Index Block

Index block 中的每条 key-value 指向一个 data block。value 比较简单直接，就是对应的 data block 的 BlockHandle。key 是一个大于等于当前 data block 中最大的 key 且小于下一个 block 中最小的 key，这一块的逻辑可以参考 FindShortestSeparator 的 调用 ^[6] 和 实现 ^[7] 。这样做是为了减小 index block 的体积，毕竟我们希望程序运行的时候，index block 被尽可能 cache 在内存中。

• Meta Index Block

Meta index block 中的每条 key-value 指向一个 meta block。目前 LevelDB 中只有一个 meta block，保存的是这个 SSTable 中的 key 组成的 bloom filter。

• Data Block

Data block 是实际的 key-value 数据。

Block

Index block ^[8] 、 meta index block ^[9] 、 data block ^[10] 都是通过 BlockBuilder ^[11] 来生成，通过 Block ^[12] 来读取的。最简单的方式，block 里面只需要将一个个 key-value 有序保存。但是为了节省空间，LevelDB 在 block 的内部实现了 前缀压缩 ^[13] 。

前缀压缩利用了 key 的有序性（前缀相同的有序 key 会聚集在一起）对 key 进行压缩，每个 key 与前一个 key 相同的前缀部分可以不用保存。读取的时候再根据规则进行解码即可。

LevelDB 将 block 的一个 key-value 称为一条 entry。每条 entry 的格式如下：

• shared_bytes：和前一个 key 相同的前缀长度。

• unshared_bytes：和前一个 key不同的后缀部分的长度。

• value_length：value 数据的长度。

• key_delta：和前一个 key不同的后缀部分。

• value：value 数据。

一个 block 的数据格式如下：

• restarts：在 LevelDB 中，默认 每 16 个 key ^[14] 就会重新计算前缀压缩，重新开始计算前缀压缩到第一个 key 称之为重启点（restart point）。restarts 数组记录了这个 block 中所有重启点的 offset。

• num_restarts：是 restarts 数组的长度。

在 block 中查找一个 key（ Block::Iter::Seek ^[15] ）：

1. 先在 restarts 数组的基础上进行 二分查找 ^[16] ，确定 restart point。

2. 从 restart point 开始 遍历查找 ^[17] 。

Filter

Meta block（bloom filter）由 FilterBlockBuilder ^[18] 来生成，通过 FilterBlockReader ^[19] 来读取。

后面会单独写一篇介绍 filter。

参考资料