wickdb SSTable 文件格式逐行精讲Block、Index Block、Footer 与 Snappy 压缩【免费下载链接】wickdbPure Rust LSM-tree based embedded storage engine项目地址: https://gitcode.com/gh_mirrors/wi/wickdbwickdb是一个纯 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 字节 Trailer1 字节压缩类型 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→duckdeckshared0存完整deckdock与前一个共享d只存ockduckrestart 点强制不共享重新存完整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 更大的分隔 keyseparator/successorvalue 是一个BlockHandleoffset size两个 varint。查找某个 key 时先在 Index Block 里二分找到对应条目就知道目标数据块在文件中的位置见 src/sstable/mod.rs。MetaIndex Block存放元信息指针目前的核心内容就是filter 名 → filter block handle让读路径能找到 Bloom Filter 块src/sstable/mod.rs。四、Footer48 字节里的文件身份证Footer 固定占2 * 10 8 28字节的编码上限空间FOOTER_ENCODED_LENGTHsrc/sstable/mod.rs内容为字段说明MetaIndex BlockHandlevarint 编码占位到 10 字节Index BlockHandlevarint 编码占位到 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 TrailerSnappy 压缩与 CRC-32 逐行拆解这是本文最字节级的部分写入路径在 write_raw_block先压缩compress_block用snap::raw::Encoder对整块数据做 Snappy 压缩src/sstable/table.rs。压缩类型默认就是SnappyCompression见 src/options.rs。拼 Trailer第一字节写压缩类型1 Snappy0 不压缩。算校验和CRC-32 覆盖的是压缩后数据 压缩类型字节再经过mask/unmask混淆src/util/crc32.rs避免只改 trailer 自己这种局部攻击绕过校验。更新 BlockHandle记录offset和压缩后size供 Index Block 引用。读取路径 read_block 严格反向按 handle 读 size5 字节 → 校验 CRC不匹配报 block checksum mismatch → 按压缩类型字节选择解压分支 → Snappy 则先 decompress_len 再解压 → 返回原始块数据注意两个细节压缩类型字节参与CRC 计算L559-L560 与 L577-L579 的注释呼应Filter Block 例外不做压缩src/sstable/mod.rs保证 Bloom Filter 位图可以直接按偏移寻址。六、完整读取流程一次 Get 的字节之旅步骤动作源码位置1读文件尾部 28 字节校验 Magic NumberFooter::decode_from2解析 Footer 拿到 Index BlockHandle读 Index Block 并解压、校验src/sstable/table.rs3用目标 key 在 Index Block 二分得到数据块 BlockHandle同上4按 handle 读块 5 字节 trailer校验 CRC 后 Snappy 解压read_block5在 restarts 数组二分 前缀补全定位 entrysrc/sstable/block.rs七、关键参数速查参数默认值作用源码block_size4 KB数据块目标大小越小读放越大src/options.rsblock_restart_interval16前缀压缩的重启频率src/options.rscompressionSnappy块级压缩算法src/options.rsMagic Number0xdb4775248b80fb57文件格式指纹src/sstable/mod.rs八、小结Blockvarint 长度 前缀压缩的 KV 条带靠 restart 点兼顾压缩率与随机定位Index Block块级二分目录value 是 BlockHandleFooter固定 28 字节编码空间 8 字节 Magic Number一切读取的起点Trailer1 字节压缩类型 4 字节 CRC-32Snappy 压缩类型字节也参与校验想动手验证跑一遍 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考