企业官网建设流程全解析

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

【免费下载链接】fqfq - jq for binary formats. Tool, language and decoders for working with binary formats.项目地址: https://gitcode.com/gh_mirrors/fq/fq

fq 是面向二进制格式的解析工具，内置了 LevelDB 数据目录中三类核心文件的解码支持：Table（*.ldb数据与索引文件）、Log（*.log写前日志）与 Descriptor（MANIFEST-*版本描述文件）。本文以 leveldb_table.md 为线索，结合 leveldb_table.go 的实现与 testdata 中的真实样例，系统讲解 LevelDB Table 的二进制布局、fq 的逐层解析逻辑、internal key 的四种切分复原策略，以及校验和与 Snappy 解压的验证方式。读完本文，你将能看懂fq -d leveldb_table输出的每一层结构，并能够自行定位.ldb文件中的键、值、序列号与索引信息。

背景：LevelDB 目录中的三类文件

LevelDB 的一个数据库目录内通常包含多种文件，fq 的format/leveldb包按格式分文件实现了各自的解码器：

其中 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）的逻辑如下：

1. 解析 footer，得到metaindex_handle与index_handle（偏移 + 大小）；
2. 跳转到 metaindex 块，读取其中引用的所有 meta 块句柄；
3. 跳转到 index 块，读取所有 data 块句柄；
4. 依次解析 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 = 0xdb4775248b80fb57

tableMagicNumber的来源在源码注释中写得很清楚：取echo http://code.google.com/p/leveldb/ | sha1sum哈希结果的前 64 位。解析顺序为：

• magic_number：先跳到文件末尾的 8 字节处，用d.UintAssert(tableMagicNumber)断言校验——如果魔数不匹配则立刻失败（fail fast），避免把非 LevelDB 文件误解析；
• metaindex_handle：两个 ULEB128 编码的 varint（offset、size）；
• index_handle：同样是两个 varint；
• padding：剩余位以原始数据输出。

从实际解码输出（见下文 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的枚举）：

对于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_restarts（uint32，小端）；
• 其前面是restarts数组，每个元素是 4 字节的重启点偏移；
• restartOffset由size*8 - (1+num_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 handle

index 块的 value 保存的是指向 data 块的句柄，readBlockHandle()（leveldb_table.go）将其解析为offset与size两个 ULEB128 字段。ldbTableDecode通过遍历 index 条目收集dataHandles，随后逐个定位并解析 data 块。

internal key 的四种切分复原

LevelDB 的键在内部表示为(user_key, type, sequence_number)三元组：1 字节type（0x0=deletion，0x1=value）+ 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 分别是：

1. case 1：user_key、type、sequence_number 全部位于 unshared 区（shared == 0）——直接输出user_key（UTF-8）、type（带符号映射）、sequence_number（7 字节小端）；
2. case 2：type 与 sequence_number 完整落在 unshared 区，user_key 被切分——输出user_key_suffix，并把 shared 前缀与后缀拼接为合成的user_key（标记为inferred，即推断字段）；
3. case 3：sequence_number 完整落在 unshared 区，type 被切断——从 shared 前缀末尾提取 type 字节；
4. case 4：sequence_number 本身被切断——需要从 shared 前缀尾部与 unshared 后缀拼接出完整的 7 字节 sequence_number，并通过bitio.ReverseBytes64(56, ...)把小端字节序还原成数值。

这种对"共享前缀任意切断"场景的细致处理，保证了即使 key 高度相似（前缀很长）时也能准确还原每条记录的完整 internal key。

整体解析流程串联

ldbTableDecode把上述部件按顺序组装（leveldb_table.go）：

• footer→ 获得metaIndexOffset/Size与indexOffset/Size；
• metaindex 块：用keyValueContentsReader(nil, readBlockHandle)读取条目，key 按普通字符串输出，value 解析为 meta 块句柄，收集到metaHandles；
• index 块：用keyValueContentsReader(readInternalKey, readBlockHandle)读取条目，key 按 internal key 复原，value 解析为 data 块句柄，收集到dataHandles；
• meta 块：若有句柄，逐个readTableBlock("meta_block", size, readMetaContent, ...)解析。目前readMetaContent（leveldb_table.go）只是把内容作为raw原始位输出——这正是文档 Limitations 中所说的 "no Meta Blocks (like 'filter') are decoded yet"；
• data 块：逐个readTableBlock("data_block", size, keyValueContentsReader(readInternalKey, nil), ...)解析，key 复原为 internal key，value 直接按 UTF-8 输出。

实际运行与测试样例

仓库的 testdata 目录提供了多种真实.ldb数据目录，均由 make_ldb.py 生成，覆盖不同压缩与内容形态：

• uncompressed.ldb：无压缩 Table；
• snappy.ldb：Snappy 压缩的 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)

从输出可以直观看到三个关键点：

1. 前缀共享：第二个条目shared_bytes: 6，只额外存储"ipsum"5 字节后缀，与前一 key"lorem.dolor"共享"lorem."前缀，fq 合成出user_key: "lorem.ipsum" (inferred)；
2. checksum 验证：compression: "none"与checksum: 0xb31d996f (valid)并列出现，说明校验通过；
3. index 指向 data：index 条目 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 小节，当前实现有两处尚未覆盖：

1. Meta Blocks 未解码：如filter等 meta 块内容目前只以raw原始位输出（见 leveldb_table.go），尚未按table_format.md的 Filter Meta Block 布局逐字段解析；
2. Zstandard 解压未实现：压缩类型0x2（zstd）会触发 "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.ldb（fqtest 见 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