深入解析 fq 的 LevelDB Table（*.ldb）格式解码器

深入解析 fq 的 LevelDB Table*.ldb格式解码器【免费下载链接】fqfq - jq for binary formats. Tool, language and decoders for working with binary formats.项目地址: https://gitcode.com/gh_mirrors/fq/fqfq 是面向二进制格式的解析工具内置了 LevelDB 数据目录中三类核心文件的解码支持Table*.ldb数据与索引文件、Log*.log写前日志与 DescriptorMANIFEST-*版本描述文件。本文以 leveldb_table.md 为线索结合 leveldb_table.go 的实现与 testdata 中的真实样例系统讲解 LevelDB Table 的二进制布局、fq 的逐层解析逻辑、internal key 的四种切分复原策略以及校验和与 Snappy 解压的验证方式。读完本文你将能看懂fq -d leveldb_table输出的每一层结构并能够自行定位.ldb文件中的键、值、序列号与索引信息。背景LevelDB 目录中的三类文件LevelDB 的一个数据库目录内通常包含多种文件fq 的format/leveldb包按格式分文件实现了各自的解码器文件类型格式实现文件说明*.ldbTableleveldb_table.go有序的键值数据块 索引块*.logLogleveldb_log.go写前日志Write-Ahead Log记录 WriteBatchMANIFEST-*Descriptorleveldb_descriptor.go版本编辑记录描述各 level 的文件集合与键范围其中 Table 格式是数据文件的核心。leveldb_table.go的头部注释直接引用了 LevelDB 官方的table_format.md、impl.md与index.md三份设计文档并在init()中通过interp.RegisterFormat(format.LevelDB_LDB, ...)注册为名为leveldb_table的格式描述为 LevelDB Table同时用//go:embed leveldb_table.md把本文所依据的说明文档嵌入可执行文件。文件整体布局从 footer 反向定位与大多数从头读到尾的二进制格式不同Table 文件的解析入口在文件末尾的 footer。ldbTableDecode()leveldb_table.go的逻辑如下解析 footer得到metaindex_handle与index_handle偏移 大小跳转到 metaindex 块读取其中引用的所有 meta 块句柄跳转到 index 块读取所有 data 块句柄依次解析 meta 块与 data 块。fq 解码时先将d.Endian设为小端d.Endian decode.LittleEndian因为 LevelDB 的数值编码是小端序。footer 结构footer 是固定长度区域leveldb_table.go中定义了三个关键常量footerEncodedLength (4*10 8) * 8 // 4 个 varint 各最多 10 字节 8 字节 magic共 48 字节 magicNumberLength 8 * 8 // 8 字节 tableMagicNumber 0xdb4775248b80fb57tableMagicNumber的来源在源码注释中写得很清楚取echo http://code.google.com/p/leveldb/ | sha1sum哈希结果的前 64 位。解析顺序为magic_number先跳到文件末尾的 8 字节处用d.UintAssert(tableMagicNumber)断言校验——如果魔数不匹配则立刻失败fail fast避免把非 LevelDB 文件误解析metaindex_handle两个 ULEB128 编码的 varintoffset、sizeindex_handle同样是两个 varintpadding剩余位以原始数据输出。从实际解码输出见下文 fqtest 样例可以看到 footer 共占 48 字节其中metaindex_handle与index_handle各只占 3 字节padding 为 34 位最后 8 字节是 magic number。块Block的统一读取与校验metaindex、index 与 data 在文件层面都是同构的 block统一由readTableBlock()leveldb_table.go处理。每个 block 的布局为------------------------------------------------------------------ | block contents | 1 字节 | 4 字节 | | | (size 字节) | 压缩类型 | 校验和 | | ------------------------------------------------------------------readTableBlock的读取顺序很有讲究先读取块内容字节再读压缩类型d.FieldU8(compression, compressionTypes)然后用块内容 压缩类型字节一起计算校验和与文件中的 checksum 字段比对d.UintAssert校验失败会报错。checksum 是 block 内容与压缩类型字节的 CRC32C而非单纯块内容。压缩类型的取值对应 LevelDBinclude/leveldb/options.h的枚举值符号说明0x0none不压缩直接解析0x1snappy使用 Snappy 解压后再解析0x2zstdZstandard当前实现尚未支持对于none直接以原始size解析块内容对于snappy调用github.com/golang/snappy解码器解压然后对解压后的字节流重新建一个 BitReader 解析同时保留compressed原始位字段供查看。对于其他压缩类型含 zstd会通过d.Errorf报出 Unsupported compression type。校验和算法computeChecksum()leveldb_table.go实现了 LevelDB 的 CRC32C 加掩码方案crc32C : crc32.New(crc32.MakeTable(crc32.Castagnoli)) crc32C.Write(bytes) return mask(crc32C.Sum32()) // mask: 右旋 15 位并加常量对应 util/crc32c.h const kMaskDelta 0xa282ead8 return ((crc 15) | (crc 17)) kMaskDelta即先按 RFC 3720 附录 B.4 用 Castagnoli 多项式计算 CRC32再做一次右旋 15 位并加0xa282ead8的掩码变换。fq 解码时把计算结果写入 checksum 字段的验证状态若一致显示为(valid)。键值条目与重启点Restarts块内容是条目 trailer的结构由readKeyValueContents()leveldb_table.go解析对应 LevelDBtable/block_builder.cc的编码方式trailer块内容末尾 4 字节是num_restartsuint32小端其前面是restarts数组每个元素是 4 字节的重启点偏移restartOffset由size*8 - (1num_restarts)*32位计算得到作为条目区结束、trailer 开始的分界。条目每个 entry 采用前缀共享压缩编码shared_bytes : ULEB128 varint —— 与上一个 key 共享的前缀字节数 unshared_bytes : ULEB128 varint —— 本条目新增的 key 字节数 value_length : ULEB128 varint —— value 字节数 key : unshared_bytes 个字节与 lastKey 的前 shared 字节拼接成完整 key value : value_length 个字节fq 在解码时维护lastKey每读入一个 key 后执行lastKey append(keyPrefix, keySuffix...)用于下一个条目。如果shared大于当前lastKey长度会调用d.Fatalf判定文件损坏。当keyCallbackFn nil shared 0时 key 直接按 UTF-8 字符串输出否则交给回调函数见下文 internal key 处理。value 默认按 UTF-8 输出若提供valueCallbackFn如 index 块中读取 block handle则走回调。block handleindex 块的 value 保存的是指向 data 块的句柄readBlockHandle()leveldb_table.go将其解析为offset与size两个 ULEB128 字段。ldbTableDecode通过遍历 index 条目收集dataHandles随后逐个定位并解析 data 块。internal key 的四种切分复原LevelDB 的键在内部表示为(user_key, type, sequence_number)三元组1 字节type0x0deletion0x1value 7 字节sequence_number小端序。由于重启点前缀压缩可以切断在任意字节边界——包括 user_key 内部、type 与 sequence_number 之间甚至 sequence_number 中间——readInternalKey()leveldb_table.go必须处理四种切分情形。源码注释用 ASCII 图展示了 key 的字节排布key ----------------------------------------------- user_key --------------------------------- ⁞ user_key_suffix type sequence_number [AAAAAAAAAAAA]⁞[BBBBBBBBBBBBBBBBBB] [T] [SSSSSSS] ⁞ 1 7 bytes ------------⁞-------------------------------- shared ⁞ unshared ⁞ cutoff四种 case 分别是case 1user_key、type、sequence_number 全部位于 unshared 区shared 0——直接输出user_keyUTF-8、type带符号映射、sequence_number7 字节小端case 2type 与 sequence_number 完整落在 unshared 区user_key 被切分——输出user_key_suffix并把 shared 前缀与后缀拼接为合成的user_key标记为inferred即推断字段case 3sequence_number 完整落在 unshared 区type 被切断——从 shared 前缀末尾提取 type 字节case 4sequence_number 本身被切断——需要从 shared 前缀尾部与 unshared 后缀拼接出完整的 7 字节 sequence_number并通过bitio.ReverseBytes64(56, ...)把小端字节序还原成数值。这种对共享前缀任意切断场景的细致处理保证了即使 key 高度相似前缀很长时也能准确还原每条记录的完整 internal key。整体解析流程串联ldbTableDecode把上述部件按顺序组装leveldb_table.gofooter→ 获得metaIndexOffset/Size与indexOffset/Sizemetaindex 块用keyValueContentsReader(nil, readBlockHandle)读取条目key 按普通字符串输出value 解析为 meta 块句柄收集到metaHandlesindex 块用keyValueContentsReader(readInternalKey, readBlockHandle)读取条目key 按 internal key 复原value 解析为 data 块句柄收集到dataHandlesmeta 块若有句柄逐个readTableBlock(meta_block, size, readMetaContent, ...)解析。目前readMetaContentleveldb_table.go只是把内容作为raw原始位输出——这正是文档 Limitations 中所说的 no Meta Blocks (like filter) are decoded yetdata 块逐个readTableBlock(data_block, size, keyValueContentsReader(readInternalKey, nil), ...)解析key 复原为 internal keyvalue 直接按 UTF-8 输出。实际运行与测试样例仓库的 testdata 目录提供了多种真实.ldb数据目录均由 make_ldb.py 生成覆盖不同压缩与内容形态uncompressed.ldb无压缩 Tablesnappy.ldbSnappy 压缩的 data 块repeats.ldb大量共享前缀的重复键用于验证前缀压缩与 internal key 切分复原log_only.ldb仅含日志与 MANIFEST 的最小目录。对应的 fqtest 测试文件如 leveldb_table_uncompressed.fqtest、leveldb_table_snappy.fqtest、leveldb_table_repeats.fqtest展示了标准用法。以无压缩样例为例fq -d leveldb_table dv uncompressed.ldb/000005.ldb输出顶层结构依次为data、metaindex、index、footer.{}: uncompressed.ldb/000005.ldb (leveldb_table) 0x0-0x65a (1626) data[0:1] [0]{}: data_block 0x0-0x601 (1537) uncompressed{} entries[0:4] [0]{}: entry 0x0-0x1d4 (468) shared_bytes: 0 unshared_bytes: 19 value_length: 445 key{}: user_key: lorem.dolor / type: value (0x1) / sequence_number: 3 value: Lorem ipsum dolor sit amet, ... [1]{}: entry 0x1d4-0x3a2 (462) shared_bytes: 6 unshared_bytes: 13 key{}: user_key_suffix: ipsum / user_key: lorem.ipsum (inferred) ... trailer{}: restarts[0:1] / num_restarts: 1 compression: none (0x0) checksum: 0xb31d996f (valid) metaindex{} index{} entries[0:1] [0]{}: entry key{}: user_key: s / sequence_number: 72057594037927935 value{}: offset: 0 / size: 1532 footer{} metaindex_handle{}: offset: 1537 / size: 8 index_handle{}: offset: 1550 / size: 23 padding: raw bits magic_number: 0xdb4775248b80fb57 (valid)从输出可以直观看到三个关键点前缀共享第二个条目shared_bytes: 6只额外存储ipsum5 字节后缀与前一 keylorem.dolor共享lorem.前缀fq 合成出user_key: lorem.ipsum (inferred)checksum 验证compression: none与checksum: 0xb31d996f (valid)并列出现说明校验通过index 指向 dataindex 条目 value 中的offset: 0 / size: 1532恰好是 data_block 的字节范围。在 leveldb_table_snappy.fqtest 中data 块则呈现为compressed: raw bits 0x0-0x266 (614) compression: snappy (0x1) checksum: 0xd289db6 (valid)压缩块内容保留为compressed原始位同时解压后的uncompressed子树被完整解析且校验和依旧(valid)——验证了用未压缩前的字节与压缩类型字节一起算 CRC的实现细节。Snappy 压缩后 1532 字节的内容仅占 614 字节压缩比在测试数据上相当可观。已知限制依据 leveldb_table.md 的 Limitations 小节当前实现有两处尚未覆盖Meta Blocks 未解码如filter等 meta 块内容目前只以raw原始位输出见 leveldb_table.go尚未按table_format.md的 Filter Meta Block 布局逐字段解析Zstandard 解压未实现压缩类型0x2zstd会触发 Unsupported compression type 错误目前仅支持none与snappy。相关文件索引解码器实现leveldb_table.go、leveldb_log.go、leveldb_descriptor.go日志/描述符共用的块序列读取leveldb_log_blocks.go描述符的 jq 美化辅助leveldb_descriptor.jq测试样例uncompressed.ldb、snappy.ldb、repeats.ldbfqtest 见 leveldb_table_uncompressed.fqtest 等测试数据生成脚本make_ldb.py格式说明文档leveldb_table.md、leveldb_log.md、leveldb_descriptor.md该解码器由 mikez 编写格式语义参考了 LevelDB 官方的table_format.md、impl.md与index.md设计文档。若需深入可以对照 leveldb_table.go 中各函数头部注释所标注的 LevelDB 源码位置如table/format.cc、table/block.cc、db/dbformat.h逐一核对字节布局。【免费下载链接】fqfq - jq for binary formats. Tool, language and decoders for working with binary formats.项目地址: https://gitcode.com/gh_mirrors/fq/fq创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考