【RocksDB 内核机制】SST 格式与 MANIFEST：BlockBasedTable 与 VersionSet

第 5 篇 讲到 FlushJob 通过 BuildTable 把 MemTable 刷成 L0 .sst。磁盘上 SST 不是「key 顺序 dump」：RocksDB 默认 BlockBasedTable 把数据切成带 trailer 的 Block，Footer 指向 Index / Metaindex，Filter Block 支撑读路径裁剪（第 9 篇）。

同时，单个 SST 只解决 一个文件内部 的布局；哪些 SST 在哪一层、边界 key 是什么 由 MANIFEST 描述。VersionSet 把一系列 VersionEdit 追加进 MANIFEST，内存中 materialize 为不可变 Version——读路径 SuperVersion 持有的就是当前 Version + MemTable 视图（第 7 篇）。

版本锚定：RocksDB 9.x（table/block_based/*、table/format.h、db/version_edit.h、db/version_set.h）。工具：reproduce/build_rocksdb.sh 编译 sst_dump（或 Makefile make sst_dump）。

一、两类元数据：SST 内 vs DB 级

flowchart TB
  subgraph file ["单个 *.sst"]
    DATA["Data Blocks"]
    IDX["Index Block(s)"]
    FILT["Filter Block(s)"]
    META["Metaindex Block"]
    FOOT["Footer"]
    DATA --> IDX
    FILT --> META
    IDX --> META
    META --> FOOT
  end
  subgraph db ["DB 目录"]
    MANI["MANIFEST-000xxx"]
    CUR["CURRENT"]
    SST["*.sst"]
    WAL["*.log"]
  end
  MANI -->|"VersionEdit: AddFile level N"| SST
  CUR -->|"pointer"| MANI

LevelDB 起沿用 CURRENT 文件保存 最新 MANIFEST 文件名；RocksDB 扩展了 Column Family、Blob 文件、WAL 元数据 等 Tag（db/version_edit.h）。

二、BlockBasedTable 物理布局

2.1 Block 与 BlockHandle

table/format.h BlockHandle：(offset, size) 指向文件内一段连续字节。Data / Index / Filter / Metaindex 都是 Block；每个 Block 末尾有 trailer（compression type + checksum，长度由 Footer::GetBlockTrailerSize() 决定，block-based 通常为 5 字节）。

典型文件顺序（逻辑上）：

[ Data block 0 ][ trailer ]
[ Data block 1 ][ trailer ]
...
[ Filter block(s)     ]
[ Index block         ]   // 或 partitioned index 的 top / partition
[ Metaindex block     ]
[ Footer              ]   // 固定/有界长度，在文件最尾

读 SST 时 Footer::DecodeFrom 先读文件尾部，拿到 metaindex_handle；再读 metaindex 得 filter / index / properties 等命名 Block 的 handle。

2.2 Data Block

Data Block 存 排序后的 InternalKey → value 序列，块内 前缀共享（BlockBuilder）降低空间。BlockBasedTableReader::NewIterator 按 Index 定位 Data Block，再块内二分或 scan（受 format_version 与 hash index 影响）。

TableProperties（写入 properties block）记录：num_entries、raw_key_size、data_size、column_family_id 等——sst_dump --show_properties 可读。

2.3 Index Block

Index 把 key upper bound → Data Block handle 映射。table/format.h IndexValue 注释：

Index entry for block n: \(y \rightarrow h,\,[x]\)，其中 \(y\) 介于 block \(n\) 最后 key 与 block \(n{+}1\) 首 key 之间；\(h\) 为 BlockHandle；可选 \(x\) 为 block \(n\) 首 key（未缩短）。

大 SST 可开 partition_filters / index_per_partition：Index 自身分层，减少单次读 index 的 CPU（第 9 篇）。

2.4 Filter Block

默认 Full Filter 或 Ribbon Filter（table/block_based/block_based_table_builder.cc WriteFilterBlock）。Metaindex 中登记 handle，名字前缀如 rocksdb.fullfilter / partitioned 变体（block_based_table_reader.h 静态前缀常量）。

Filter 不 保证无假阴性：miss 则跳过 Data Block I/O；hit 仍需读 Block 确认（与 lsm-tree Bloom 篇 一致）。

2.5 Footer 与 magic

table/format.h Footer（节选职责）：

Footer 编码长度有 kMinEncodedLength / kMaxEncodedLength 界，读端从 文件末尾 反向解析——与 Parquet/ORC「尾部落元数据」同理。

2.6 Metaindex Block

键值 map：名字 → BlockHandle。常见键：rocksdb.index、rocksdb.filter、rocksdb.properties、rocksdb.compression_dict 等。Builder 侧 MetaIndexBuilder 与 WriteIndexBlock / WriteFilterBlock 协作（block_based_table_builder.h）。

三、Version、VersionSet 与 LSM 快照

3.1 Version 是什么

每个 Column Family 持链式 Version：VersionSet 维护 doubly linked list，新 Version 由 VersionBuilder 自旧 Version + VersionEdit 增量构建。

一个 Version 包含 每层 LevelFileNumIterator 管理的 SST 列表，以及 compaction 指针、文件重叠关系（L0 特殊：允许 key range 重叠）。

3.2 VersionEdit：MANIFEST 记录格式

db/version_edit.h 用 Tag 枚举 序列化增量（部分与 LevelDB 兼容，CF 扩展从 200 起）：

VersionEdit::EncodeTo / DecodeFrom 写入 变长 record；MANIFEST 文件是 append-only log of edits。

3.3 LogAndApply

VersionSet::LogAndApply（db/version_set.h 注释 REQUIRES: no other thread concurrently calls LogAndApply()）：

1. 对多个 CF 的 VersionEdit 批量应用；
2. 追加写入 MANIFEST（WritableFile + 可选 manifest_preallocation_size）；
3. 内存安装新 Version，递增 ref；
4. 旧 Version refcount 归零后由 obsolete file queue 删除对应 SST。

Recovery：VersionSet::Recover 从 CURRENT 指向的 MANIFEST 顺序重放 全部 Edit，重建最新 LSM 快照；若最新 MANIFEST 损坏，可尝试 次新的（RocksDB 保留历史 MANIFEST 号）。

3.4 与 Flush / Compaction 的交界

Compaction picker 读 当前 Version 选输入；Job 完成后 单次 LogAndApply 切换视图，读侧通过 SuperVersion 切换无锁看到新快照。

四、Column Family 与 MANIFEST

RocksDB MANIFEST 全局一份，每条 Edit 可带 kColumnFamily Tag 区分 CF。多 CF 共享 WAL（第 13 篇），但 各自 Version 链 独立——TiKV / Flink 多 CF 映射依赖此分裂。

VersionSet::ColumnFamilySet 维护 cfd → Version*；LogAndApply 可一次提交 多 CF 的原子 Edit 组（kInAtomicGroup），服务 atomic flush / 2PC 边界。

五、sst_dump：对照磁盘布局

build_rocksdb.sh 在 _build/（或 Makefile 在源码根）生成 sst_dump。对 exp05 产生的 SST：

cd post/db/rocksdb/reproduce
export SST_DUMP="$PWD/rocksdb/sst_dump"   # 路径随构建方式调整
$SST_DUMP --file=output/bench_dbs/exp05_flush/*.sst --command=scan
$SST_DUMP --file=<path>.sst --show_properties
$SST_DUMP --file=<path>.sst --command=verify

阅读建议（不在此粘贴未实测 dump 全文）：

1. 先看 show_properties 的 data size、index size、filter size 比例，理解读放大构成；
2. 再用 scan 对照 MemTable flush 的 key 范围；
3. L0 多文件时 key range 可重叠，勿用「单 SST 覆盖全 keyspace」假设。

与 MANIFEST 对照：对同一 DB 目录，strings MANIFEST-* | head 可见 AddFile 类 ASCII 片段（仅作定性）；精确解析应使用 ldb dump_manifest 或 debug 工具，不在此展开。MANIFEST 中每条 flush 对应一次 VersionEdit::AddFile(0, ...)，可与 sst_dump 的 file number 交叉验证。

RocksDB 官方 DUMP_FORMAT.md（仓库根目录）与 Wiki Block-based Table Format 为 B 级辅助；以 9.x 源码 table/format.h 为准。

六、与 lsm-tree / LevelDB 的分工

LevelDB doc/table_format.md 仍是理解 BlockHandle + Footer 的简洁入口；RocksDB 在 partition index/filter、format_version、checksum context 上扩展。

七、FileMetaData 与 Level 组织

MANIFEST 中每个 SST 对应 FileMetaData（version_edit.h / version_set.cc）：

level L, file_number F
  smallest_seqno .. largest_seqno
  smallest_internal_key .. largest_internal_key
  file_size, checksum, path_id (多路径 DB)

Leveled compaction 不变式（L \(\ge\) 1）：同一层内 key range 不重叠（除 TTL / UDT 等扩展）。L0 无此约束，故 Version::GetOverlappingInputs 对 L0 与 deep level 算法不同——compaction picker 读 Version 时依赖这些元数据。

CompactCursor（Tag kCompactCursor）记录各层 compaction 进度，避免 starve 某些 level。

八、CURRENT 文件与 MANIFEST 滚动

DB 目录布局（典型）：

CURRENT                 # 文本：MANIFEST-000042
MANIFEST-000042         # 追加 VersionEdit
OPTIONS-000043          # 选项快照（可选）
000056.sst              # file number 命名
LOG                     # 人类可读日志

CURRENT 仅 指针；真正状态在 MANIFEST。切换 MANIFEST 文件（大小过大时 NewManifest）会写新 MANIFEST 并从 snapshot Edit 继续——旧 MANIFEST 在 obsolete 后删除。

WAL 文件 log_number 与 MANIFEST 中 kLogNumber / kPrevLogNumber 联动，决定 recovery 从哪条 WAL 开始 replay（与第 4 篇 min_log_number_to_keep 一致）。

九、BlockBuilder 与 compression

Data Block 构建（table/block_based/block_builder.cc）：

1. 按 BlockBasedTableOptions::block_size（默认约 4 KiB）切分；
2. restart interval 控制块内索引密度；
3. 块满则 CompressBlock（Snappy/Zstd/LZ4 等）+ trailer checksum；
4. compression_dict（format 高版本）可共享字典块，metaindex 单独登记。

Index / Filter Block 同样可压缩。sst_dump --show_compression_ratio 可看各层压缩效果（若构建版本支持该 flag）。

十、读路径预告（不展开）

打开 SST 的 TableCache 缓存 TableReader 对象；Get 路径：

Footer → Metaindex → Filter（maybe）→ Index → Data Block → 合并 MemTable 更新。

Block Cache 与 Bloom 细节见 第 9 篇；Get 与 Snapshot 见 第 7 篇。

十一、小结

1. BlockBasedTable：Data + Index + Filter + Metaindex + Footer；BlockHandle 串联偏移。
2. MANIFEST：VersionEdit 追加日志；VersionSet::LogAndApply 原子安装 LSM 快照。
3. Flush / Compaction 仅通过 VersionEdit 增删 FileMeta；物理 SST 由 obsolete 机制异步删。
4. sst_dump 是核对 Flush 产物与 properties 的第一手工具。

写路径 WAL → MemTable → SST → MANIFEST 在此闭合；读路径从 SuperVersion + sequence 开始。

参考资料

1. RocksDB 9.x 源码：table/format.h（BlockHandle、Footer、IndexValue）。
2. RocksDB 9.x 源码：table/block_based/block_based_table_builder.h、block_based_table_builder.cc（WriteIndexBlock、WriteFilterBlock、WriteFooter）。
3. RocksDB 9.x 源码：table/block_based/block_based_table_reader.h（打开 SST、读 Block）。
4. RocksDB 9.x 源码：db/version_edit.h（Tag、VersionEdit 编解码）。
5. RocksDB 9.x 源码：db/version_set.h、db/version_set.cc（LogAndApply、Recover）。
6. RocksDB 仓库：DUMP_FORMAT.md（格式说明，注意与 9.x format_version 对齐）。
7. lsm-tree 第 3–4 篇（DIY SST 与 Version）。
8. 本系列 index；构建 reproduce/build_rocksdb.sh。

返回 系列目录 ｜ 上一篇：MemTable 与 Flush ｜ 下一篇：Get 与 Snapshot