LevelDB 表文件格式详解：从 Data Block、Filter Block 到 Footer 的 SSTable 全解析

本文基于 LevelDB 仓库中的表格式规范文档 doc/table_format.md，系统拆解 LevelDB 表文件（SSTable）的完整二进制布局：数据块的前缀压缩与 restart point 机制、meta block 中的 filter/stats 扩展、metaindex 与 index block 的索引设计，以及固定 48 字节 Footer 与魔数校验。读完后你将能够独立解析一个 LevelDB 表文件中的任意 block，并理解 table/table_builder.cc 写路径与 table/format.cc 读路径之间的完整对应关系。

一、文件总体布局

一个 LevelDB 表文件从上到下的固定结构如下（与 doc/table_format.md 中的图示一致）：

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer]        (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

关键规则：

1. 键值对按排序后的顺序被切分为若干数据块（data block），连续存放在文件头部。每个数据块按 table/block_builder.cc 定义的格式编码，然后可选压缩；
2. 数据块之后是一系列 meta block，目前支持 filter 和（预留的）stats 两种类型，未来可扩展。meta block 同样用 block_builder.cc 的格式编码并可压缩；
3. metaindex block：为其他每个 meta block 建一个条目，key 是 meta block 名称，value 是指向该 meta block 的 BlockHandle；
4. index block：每个数据块对应一条索引条目，key 是该数据块最后一个键的"最短分隔符"（大于等于本块所有键、且小于下一块首个键），value 是该数据块的 BlockHandle；
5. 文件末尾是定长 Footer，包含 metaindex block 和 index block 的 BlockHandle 以及魔数。

文件内部的指针统一用 BlockHandle 表示，格式为：

offset:   varint64
size:     varint64

varint64 是 protobuf 的可变长度整型编码，LevelDB 用 util/coding.cc 中的 PutVarint64/GetVarint64 实现。从 table/format.h 可以看到 BlockHandle::kMaxEncodedLength = 10 + 10，即每个 varint64 最长 10 字节，单个 BlockHandle 编码后最长 20 字节——这正是 Footer 中 padding 计算 40 == 2*BlockHandle::kMaxEncodedLength 的由来。

写入侧的实现入口在 table/table_builder.cc 的 TableBuilder::Finish()（L213-L268）：依次 Flush 最后一个数据块 → 写 filter block → 写 metaindex block → 写 index block → 写 Footer，与上面的布局一一对应。

二、Data Block：前缀压缩与 restart point

数据块是 LevelDB 的存储基本单元。table/block_builder.cc 文件头部注释（L4-L27）给出了完整格式说明：

一条 key-value 记录：
    shared_bytes:   varint32
    unshared_bytes: varint32
    value_length:  varint32
    key_delta:     char[unshared_bytes]
    value:         char[value_length]

块尾部：
    restarts:     uint32[num_restarts]
    num_restarts: uint32

机制要点：

• 前缀压缩：存储一个 key 时，丢弃它与前一个 key 共享的前缀，只存差异部分。这能显著减少空间占用；
• restart point：每 K 个 key 强制"重新开始"，不压缩、存完整 key。块尾部记录所有 restart point 在块内的偏移，使得查找时可以先对 restart 数组二分，再在命中区间内线性扫描；
• value 原样存放在对应 key 差异之后，不做压缩。

默认参数在 include/leveldb/options.h 中定义：

size_t block_size = 4 * 1024;      // 每个数据块的目标大小，默认 4KB
int block_restart_interval = 16;   // 每 16 个 key 设一个 restart point

在 table/block_builder.cc 的 Add()（L71-L105）中可以看到：当 counter_ < options_->block_restart_interval 时与上一个 key 计算共享前缀；到达间隔时则把当前 buffer_.size() 记为一个 restart point 并清零计数器。BlockBuilder::Finish()（L61-L69）把所有 restart 偏移与个数追加到缓冲区末尾。

读取侧对应 table/block.cc：

• 构造函数（L25-L40）从块尾读出 num_restarts，反推出 restart 数组起点 restart_offset_，并对过小的块做损坏标记；
• Iter::Seek()（L164-L227）先在 restart 数组上二分找到最后一个 key 小于 target 的 restart point，再调用 ParseNextKey() 线性前进到第一个 >= target 的 key；
• DecodeEntry()（L55-L75）还有一个性能细节：三个 varint 若各只需 1 字节（值 < 128）则走快速路径，直接按字节解码。

切分时机在 table/table_builder.cc 的 TableBuilder::Add()（L119-L122）：当 data_block.CurrentSizeEstimate() 达到 options.block_size 时调用 Flush() 落盘一个数据块。

三、块级完整性：类型字节与 CRC trailer

规范文档描述的是逻辑块布局，而实际落盘时每个块还带一个 5 字节的 trailer。table/format.h 中 kBlockTrailerSize = 5，table_builder.cc 的 WriteRawBlock()（L192-L209）揭示了具体编码：

block_data: uint8[n]
type:       uint8     // kNoCompression=0 / kSnappyCompression=1 / kZstdCompression=2
crc:        uint32    // crc32c 覆盖 block_data + type 字节，且经过 Mask 处理

注意 crc32c::Mask() 的应用：LevelDB 用 Mask 把 CRC 变换成一个与数据模式无关的值，用于抵御某些硬件的位翻转模式。读取时 ReadBlock()（table/format.cc L69-L162）做对称操作：先 Unmask 存储值，再对 data + type 字节 重算 crc32c::Value 比对，不一致返回 Status::Corruption("block checksum mismatch")。

两个与 include/leveldb/options.h 对应的开关：

• verify_checksums = false（L154，属于 ReadOptions 域）：读路径可跳过 CRC 校验；
• CompressionType compression = kSnappyCompression（L132，属于 Options）：默认使用 Snappy。

压缩策略有一个实用细节（table_builder.cc L153-L186）：Snappy/Zstd 压缩后，如果压缩收益不足 12.5%（compressed->size() < raw.size() - raw.size()/8 不成立）或压缩器不可用，就退化为 kNoCompression 直接存原始数据。Zstd 的压缩级别由 Options::zstd_compression_level（默认 1，L136）控制。

四、Meta Block 之一："filter" 块

这是 doc/table_format.md 明确规定的 meta block 类型之一：当数据库以 FilterPolicy 打开时（对应 Options::filter_policy，include/leveldb/options.h），每个表都会带一个 filter block，metaindex block 中有一条 filter.<N> 的条目，其中 <N> 是 FilterPolicy::Name() 的返回值。

实现对应关系：

• metaindex 条目的写入在 TableBuilder::Finish()（table/table_builder.cc L228-L241）：拼出 key "filter." + options.filter_policy->Name()，value 是 filter block 的 BlockHandle 编码；
• filter block 的构建在 table/filter_block.cc。

4.1 按 2KB 文件偏移分桶

规范中 filter i 覆盖"文件偏移落在 [i*base ... (i+1)*base-1] 范围内的数据块中的全部 key"，且 base 当前为 2KB。源码里这个 base 由常量硬编码（table/filter_block.cc L14-L16）：

// Generate new filter every 2KB of data
static const size_t kFilterBaseLg = 11;   // lg(base)
static const size_t kFilterBase = 1 << kFilterBaseLg;  // 2KB

也就是说 filter 的粒度不是数据块，而是 2KB 的文件偏移区间：一个 filter 可以跨越多个小数据块的 key。FilterBlockBuilder::StartBlock(block_offset)（L21-L27）用 block_offset / kFilterBase 算出 filter 下标，若跨越了空桶就逐个 GenerateFilter()；AddKey() 在 TableBuilder::Add() 中被逐 key 调用（L111-L113）。

4.2 filter block 的二进制布局

[filter 0]
[filter 1]
...
[filter N-1]

[offset of filter 0]                  : 4 bytes
...
[offset of filter N-1]                : 4 bytes

[offset of beginning of offset array] : 4 bytes
lg(base)                              : 1 byte

FilterBlockBuilder::Finish()（table/filter_block.cc L35-L49）按此顺序产出：先追加各 filter（每个由 policy_->CreateFilter() 生成），再写 offset 数组、数组起始位置的 4 字节指针，最后写 1 字节的 kFilterBaseLg。末尾的 offset 数组让"数据块文件偏移 → 对应 filter"的映射变成一次数组下标计算。

读取侧 FilterBlockReader::KeyMayMatch()（L90-L104）：用 block_offset >> base_lg_ 定位 filter，取出 [start, limit) 区间调用 policy_->KeyMayMatch(key, filter) 做布隆过滤器式的成员判断；对空 filter 返回 false，对解析错误则保守地返回 true（"Errors are treated as potential matches"）。测试可参见 table/filter_block_test.cc，表级测试见 table/table_test.cc。

五、Meta Block 之二："stats" 块

规范为 stats meta block 预留了位置：key 是统计项名称，value 是统计值，并列出 TODO 计划记录的指标（doc/table_format.md L95-L107）：

data size
index size
key size (uncompressed)
value size (uncompressed)
number of entries
number of data blocks

需要说明的是：在当前仓库源码中，TableBuilder::Finish() 内只有一行 // TODO(postrelease): Add stats and other meta blocks（table/table_builder.cc L239），即 stats block 仍是文档中声明的扩展位，尚未落地实现。metaindex 的可扩展设计（name → BlockHandle 的映射表）正是为这类未来 meta 类型准备的。

六、metaindex block

metaindex block 本身就是一个普通 block（同样按 block_builder 格式编码、可压缩），其条目结构是：

key	value
filter.<FilterPolicy::Name()>	filter block 的 BlockHandle 编码
（预留：stats 等其他 meta 名称）	对应 meta block 的 BlockHandle 编码

在 TableBuilder::Finish()（table/table_builder.cc L228-L241）中，metaindex 用一个临时的 BlockBuilder 构建后通过 WriteBlock() 落盘。由于它只是"meta block 的目录"，读取表时解析顺序是：Footer → metaindex → 按需读取 filter 等 meta block，这使得新增 meta 类型无需修改 Footer 格式。

七、index block

index block 每个数据块一条记录：

• key：一个字符串，>= 该数据块所有 key 且 < 下一个数据块的第一个 key；
• value：该数据块的 BlockHandle（两个 varint64）的编码。

源码里 index block 的构建有个值得注意的优化。TableBuilder::Rep 的注释（table/table_builder.cc L50-L61）解释了 pending_index_entry 机制：不立即写索引条目，而是等看到下一个数据块的第一个 key 时才用 comparator->FindShortestSeparator() 生成尽量短的分隔 key。注释中的例子：若某块最后 key 是 "the quick brown fox"、下一块首个 key 是 "the who"，那么 "the r" 就足以作为索引 key，节省索引块空间。最后一个数据块的索引条目则用 FindShortSuccessor()（L245-L251）生成"严格大于"其最后一个 key 的最短后继。

此外，index block 使用专门的 index_block_options（L24-L35），强制 block_restart_interval = 1——即索引块内不做前缀压缩，让每条索引记录都可独立解码，便于随机访问。

查找时，表迭代器由 table/two_level_iterator.cc 的两级迭代器驱动：外层在 index block 上迭代，用 index 条目的 value（BlockHandle）定位并读出对应数据块，再挂接块内迭代器；table/two_level_iterator.h 的注释明确了"index iterator 的 value 指向一系列 block，返回迭代器产出所有 block 的键值对拼接结果"。单块内的二分查找能力（restart 数组）就是这条读路径的底层加速。

八、Footer：固定 48 字节尾部与魔数

Footer 是打开表文件的唯一入口，格式（doc/table_format.md L49-L53）：

metaindex_handle: char[p];     // metaindex 的 BlockHandle
index_handle:     char[q];     // index 的 BlockHandle
padding:          char[40-p-q];// 零填充至固定长度（40 == 2*BlockHandle::kMaxEncodedLength）
magic:            fixed64;     // == 0xdb4775248b80fb57（小端）

对应 table/format.h：

enum { kEncodedLength = 2 * BlockHandle::kMaxEncodedLength + 8 };  // = 48
static const uint64_t kTableMagicNumber = 0xdb4775248b80fb57ull;

即 20 + 20 + 8 = 48 字节，序列化后长度恒定，永远位于 file_size - 48 处。魔数来源在源码注释中交代得很清楚：取 echo http://code.google.com/p/leveldb/ | sha1sum 的前 64 位。

写入路径 Footer::EncodeTo()（table/format.cc L32-L41）：编码两个 handle 后用 dst->resize() 补零到 40 字节，再以两个 PutFixed32 写出小端魔数；读取路径 Footer::DecodeFrom()（L43-L67）先校验 input->size() >= kEncodedLength，再比对魔数（不符报 "not an sstable (bad magic number)"），然后解码两个 handle。ReadBlock() 则完成从 handle 到可用 block 内容的最后一步：按 handle.offset 读取 size + 5 字节，校验 CRC，并按 type 字节选择解压分支（kSnappyCompression / kZstdCompression），产出的 BlockContents 带 cachable 标志供 include/leveldb/cache.h 的块缓存决定是否可缓存。

九、相关配置项速查

结合 include/leveldb/options.h 与表格式规范，下表汇总直接影响表文件布局的选项：

选项	默认值	作用（对应本文结构）
Options::block_size	4 * 1024（L101）	数据块目标大小，决定 N 个 data block 的切分粒度
Options::block_restart_interval	16（L106）	数据块内前缀压缩的 restart 间隔；index block 内部固定为 1
Options::compression	kSnappyCompression（L132）	块级压缩算法；收益不足 12.5% 时自动退化为不压缩
Options::zstd_compression_level	1（L136）	选择 kZstdCompression 时的压缩级别
Options::filter_policy	nullptr（L147）	非空时每个表生成 filter meta block，metaindex 记录 filter.<Name> 条目
ReadOptions::verify_checksums	false（L154）	读块时是否校验 type+CRC trailer

十、小结：读一张 LevelDB 表的标准路径

1. 从文件末尾读 48 字节，Footer::DecodeFrom() 校验魔数并取出 index 与 metaindex 两个 BlockHandle；
2. 需要布隆过滤时，经 metaindex 找到 filter.<Name> 条目，ReadBlock() 读 filter block，用 2KB 偏移分桶快速排除"必然不存在"的 key；
3. 在 index block 中二分定位目标 key 所在数据块的 BlockHandle；
4. ReadBlock() 按 handle 读块、验 CRC、按 type 解压，得到块数据；
5. Block 迭代器先在 restart 数组上二分，再线性扫描到具体记录。

整个格式的设计取舍非常清晰：数据块靠前缀压缩 + restart 二分平衡空间与查找速度；meta block 通过 metaindex 命名注册实现前向兼容；Footer 定长化保证 O(1) 定位入口；而每个块独立的 type + CRC32C trailer 则把损坏检测的粒度控制在块级别。