wickdb SSTable 文件格式逐行精讲：Block、Index Block、Footer 与 Snappy 压缩

wickdb SSTable 文件格式逐行精讲：Block、Index Block、Footer 与 Snappy 压缩

【免费下载链接】wickdbPure Rust LSM-tree based embedded storage engine项目地址: https://gitcode.com/gh_mirrors/wi/wickdb

wickdb是一个纯 Rust 实现的 LSM-tree 嵌入式存储引擎，其静态数据的"砖块"就是 SSTable 文件。本文带你逐层拆解 wickdb 的 SSTable 磁盘格式：从最细粒度的数据 Block（前缀压缩 + restart 点）、索引 Index Block，到文件尾部的 Footer，再讲清每个 Block 如何被 Snappy 压缩并用 CRC-32 校验，帮你快速建立"字节级"阅读 SSTable 文件的能力。

一、SSTable 整体布局：一条数据带

一个 SSTable 文件从头到尾就是一串 Block，顺序是：数据 Block → 可选的 Filter Block → MetaIndex Block → Index Block → Footer。

+--------------+--------------+--------------+------+-------+-----------------+-------------+--------+ | data block 1 | ... | data block n | filter block | metaindex block | index block | footer | +--------------+--------------+--------------+--------------+-----------------+-------------+--------+ 每个 Block 后面都跟着一个 5 字节的 Trailer（压缩类型 + 校验和）

这张图来自 src/sstable/mod.rs 的模块文档注释，是整个格式的"地图"。

记住两个关键点：

• 数据是"条带"式的：没有全局目录，靠 Index Block 提供"块级目录"；
• 每个 Block 自带 5 字节 Trailer：1 字节压缩类型 + 4 字节 CRC-32 校验，定义见 src/sstable/mod.rs 的BLOCK_TRAILER_SIZE = 5。

二、数据 Block：前缀压缩 + restart 点

2.1 一条 KV 在磁盘上的样子

Block 内部由一条条 entry 拼接而成，每条 entry 的结构是：

+-------+---------+-----------+---------+----------------+ | shared | not_shared | value_len | key(变长) | value(变长) | +-------+---------+-----------+---------+----------------+ （三个长度都是 varint 变长编码）

shared表示 key 有多少字节与前一个 key 的公共前缀，磁盘上只存"不共享"的部分。例如 key 依次为deck→dock→duck：

• deck：shared=0，存完整deck
• dock：与前一个共享d，只存ock
• duck：restart 点强制不共享，重新存完整duck

这套编码的构建逻辑在 BlockBuilder::add，前缀比较从 L421-L426 开始。

2.2 restart 点：压缩率与随机访问的平衡

前缀压缩有一个副作用：想定位第 100 条 key，你得从第 1 条"逐条补全前缀"才能算出来。wickdb 的解法是restart 点：每隔block_restart_interval条（默认 16，见 src/options.rs）就强制完整写一次 key，并在 Block 末尾的restarts trailer里记录这些条目的字节偏移：

+-----------------+-----------------+-----------------+------------------------------+ | restart point 1 | .... | restart point n | restart points len (4-bytes) | +-----------------+-----------------+-----------------+------------------------------+

读取时：先在 restarts 数组里二分定位，再向后逐条解码到目标 entry——平均只需解码十几个条目，详见 src/sstable/block.rs 的注释与 L128-L200 的 entry 解析。

三、Index Block 与 MetaIndex Block：两级目录

• Index Block：本质也是一个 Block，每条记录的 key 是"比数据块最后一个 key 更大的分隔 key"（separator/successor），value 是一个BlockHandle（offset + size两个 varint）。查找某个 key 时，先在 Index Block 里二分找到对应条目，就知道目标数据块在文件中的位置，见 src/sstable/mod.rs。
• MetaIndex Block：存放"元信息指针"，目前的核心内容就是filter 名 → filter block handle，让读路径能找到 Bloom Filter 块（src/sstable/mod.rs）。

四、Footer：48 字节里的"文件身份证"

Footer 固定占2 * 10 + 8 = 28字节的编码上限空间（FOOTER_ENCODED_LENGTH，src/sstable/mod.rs），内容为：

字段	说明
MetaIndex BlockHandle	varint 编码，占位到 10 字节
Index BlockHandle	varint 编码，占位到 10 字节
Magic Number	固定 8 字节，值0xdb4775248b80fb57

+------------------- 40-bytes -------------------+ +------------------------+--------------------+------+-----------------+ | metaindex block handle / index block handle / ---- | magic (8-bytes) | +------------------------+--------------------+------+-----------------+

打开文件的第一件事就是读文件尾部校验 Magic Number，不匹配立即报not an sstable (bad magic number)——这是 Footer::decode_from 的第一道关卡（L308-L313），单元测试 test_footer_corruption 恰好演示了"改坏一个字节即被判损坏"。

五、5 字节 Block Trailer：Snappy 压缩与 CRC-32 逐行拆解

这是本文最"字节级"的部分，写入路径在 write_raw_block：

1. 先压缩：compress_block用snap::raw::Encoder对整块数据做 Snappy 压缩（src/sstable/table.rs）。压缩类型默认就是SnappyCompression，见 src/options.rs。
2. 拼 Trailer：第一字节写压缩类型（1 = Snappy，0 = 不压缩）。
3. 算校验和：CRC-32 覆盖的是"压缩后数据 + 压缩类型字节"，再经过mask/unmask混淆（src/util/crc32.rs），避免"只改 trailer 自己"这种局部攻击绕过校验。
4. 更新 BlockHandle：记录offset和压缩后size，供 Index Block 引用。

读取路径 read_block 严格反向：

按 handle 读 size+5 字节 → 校验 CRC（不匹配报 "block checksum mismatch"） → 按压缩类型字节选择解压分支 → Snappy 则先 decompress_len 再解压 → 返回原始块数据

注意两个细节：压缩类型字节参与CRC 计算（L559-L560 与 L577-L579 的注释呼应）；Filter Block 例外，不做压缩（src/sstable/mod.rs），保证 Bloom Filter 位图可以直接按偏移寻址。

六、完整读取流程：一次 Get 的字节之旅

步骤	动作	源码位置
1	读文件尾部 28 字节，校验 Magic Number	Footer::decode_from
2	解析 Footer 拿到 Index BlockHandle，读 Index Block 并解压、校验	src/sstable/table.rs
3	用目标 key 在 Index Block 二分，得到数据块 BlockHandle	同上
4	按 handle 读块 + 5 字节 trailer，校验 CRC 后 Snappy 解压	read_block
5	在 restarts 数组二分 + 前缀补全，定位 entry	src/sstable/block.rs

七、关键参数速查

参数	默认值	作用	源码
block_size	4 KB	数据块目标大小，越小读放越大	src/options.rs
block_restart_interval	16	前缀压缩的重启频率	src/options.rs
compression	Snappy	块级压缩算法	src/options.rs
Magic Number	0xdb4775248b80fb57	文件格式"指纹"	src/sstable/mod.rs

八、小结

• Block：varint 长度 + 前缀压缩的 KV 条带，靠 restart 点兼顾压缩率与随机定位；
• Index Block：块级二分目录，value 是 BlockHandle；
• Footer：固定 28 字节编码空间 + 8 字节 Magic Number，一切读取的起点；
• Trailer：1 字节压缩类型 + 4 字节 CRC-32，Snappy 压缩类型字节也参与校验；
• 想动手验证？跑一遍 examples/simple_read_write.rs，再用hexdump观察生成的.sst文件尾部，你会看到 Footer 与 Magic Number 的真身。

掌握这套格式后，你就能理解 wickdb 的 compaction 逻辑 和 table_cache.rs 如何基于 BlockHandle 做表的缓存与复用——这正是 LSM-tree 存储引擎的地基。

【免费下载链接】wickdbPure Rust LSM-tree based embedded storage engine项目地址: https://gitcode.com/gh_mirrors/wi/wickdb