做 RocksDB 源码阅读的人，十有八九是把 Compaction 放在第一站的。但 Compaction 源码的门槛，其实不在那几张 LSM 层级图里，而在 SST 文件格式的源码里。因为一次 Compaction 做的事情，本质上就是打开一批旧的 SST 文件，按 key 顺序合并、重新排列，再写出一个或多个新的 SST 文件；你要是连 SST 文件里的 Footer、Index Block、Data Block、Meta Block 各承担什么职责都没搞清，后面的CompactionJob、CompactionIterator基本只能靠猜。这篇内容是 Compaction 源码解析的开篇，先把 SST 文件格式这部分彻底讲清楚。

文章适合两类人看：一类是想真正从源码层面读懂 Compaction、却总在table/目录里迷路的人；另一类是需要在线上排查压缩相关性能问题、或者自己写小工具分析 SST 文件的工程师。我不会把源码整段贴出来，因为那样反而干扰主脉络，而是带着你直接进到BlockBasedTableBuilder、BlockBuilder、Footer::DecodeFrom这几个关键源码函数的内部，讲清楚每个字节为什么这么放。

1. Compaction 链路里的 SST：不把格式吃透根本读不下去

1.1 Flush 和 Compaction 都复用同一套 SST 写入逻辑

很多刚接触 RocksDB 的人会有一个误解：认为 Flush（内存表落盘）和 Compaction（LSM 层间合并）是两套完全独立的代码路径。实际上，在较新的源码里，Flush 和 Compaction 都会走到同一个 SST 文件构建入口——db/builder.cc里的BuildTable()，并最终通过TableBuilder接口驱动一个BlockBasedTableBuilder写出 SST。

也就是说，无论是内存表刷盘，还是 L0 到 L1 的压缩任务，最终产物都是同一套 SST 文件格式。只是 Flush 的输入是 MemTable，Compaction 的输入是多个 SST 文件及可能的合并结果。正因如此，你在db/compaction/compaction_job.cc里看到CompactionJob::ProcessKeyValueCompaction时，它内部对输出文件的处理，和你第一反应想的“纯数据库合并算法”很不一样——它更像是“不断往输出 SST 里Add(key, value)，直到块写满再刷出去”。

所以在读 Compaction 源码之前，先读BlockBasedTableBuilder是性价比最高的选择。你搞清楚了一个 SST 文件怎么从无到有，就同时搞懂了 Flush 和 Compaction 输出侧的底层逻辑。

1.2 本次要盯住的核心源码文件清单

我把这次要重点阅读的文件列了出来，后面所有章节都会围绕它们展开：

阅读顺序建议是先看format.cc，再看block_builder.cc，然后看block_based_table_builder.cc。因为format.cc里定义了所有块之间互相引用的“指针”结构（BlockHandle和Footer），这是理解整个格式的钥匙。

1.3 一个容易忽视的结论：Compaction 的“读”比“写”更依赖格式

写入侧虽然复杂，但至少是顺序追加，看着Add()一路刷块就行。读取侧才是真正考验格式理解的场景：Compaction 要读旧文件，最先做的事不是读数据块，而是先定位 Footer，从 Footer 拿到 Index Block 的位置，再从 Index Block 拿到每个 Data Block 的位置。这一连串操作全建立在 SST 文件的物理布局之上。如果你对“Footer 在文件尾部”这种布局没概念，看到SeekToLast或IndexEntry相关代码时会非常晕。

所以下一篇再进 Compaction 调度代码之前，这篇先把 SST 格式本身彻底拿下来。

2. 从文件尾部读起：Footer 与 Magic Number 的编码玄机

2.1 为什么 Footer 一定要放在文件最后

SST 文件是一个不可变文件，写入时是顺序追加的：先写数据块，再写各种 Meta Block，再写 Meta Index Block、Index Block，最后写 Footer。Footer 代表整张表的“收尾”，它的作用类似书的版权页：告诉你后面这些内容的目录在哪里。

从源码角度看，BlockBasedTableBuilder::Finish()里在写完所有块之后，才会调用FooterBuilder编码 Footer，再写到文件尾。为什么不在写第一个数据块之前就确定 Footer？因为 Index Block 要包含所有 Data Block 的BlockHandle，而这些句柄只有在数据块写完才知道。所以最自然的做法就是让 Footer 出现在文件尾。

读取时也很有意思。BlockBasedTable 的打开流程不是从头开始扫，而是先 seek 到文件末尾附近，解出 Footer，得到两个关键句柄：

• metaindex_handle：指向 Meta Index Block
• index_handle：指向 Index Block

这两个句柄本质上就是BlockHandle，里面保存了某个块在文件里的offset和size。

2.2 Footer 里到底放了什么

看table/format.cc里的Footer::DecodeFrom实现，你会发现整个解析过程的核心逻辑是：

1. 从输入的尾部数据中读取最后的 magic number；
2. 根据 magic number 判断当前文件是 BlockBasedTable 还是 PlainTable；
3. 解析出前面紧邻的两个BlockHandle。

Footer 的后 8 个字节固定用来放 magic number。不同表格式的 magic 不一样，正是这个数字告诉 RocksDB 用什么方式解释前面那一串字节。如果你在文件最后没有找到预期的魔法值，RocksDB 会直接报“Corruption: Bad table magic number”。

这里要特别强调一点：不要被网上有些旧博客误导。老版 RocksDB 的 Footer 格式比较简洁，新版又加了校验和类型、格式版本等字段。所以解析的时候永远不要硬编码“从文件结尾往前数 40 字节就是句柄起点”，而应该先取出最后 8 字节的 magic，再按 magic 对应的版本宽度去解析。源码里的Footer::DecodeFrom用的也正是这种方式：它先确认 magic number 合法，再决定如何读取前面的句柄数据。

2.3 Magic Number 背后的格式版本

在table/format.h里能看到kLegacyBlockBasedTableMagicNumber和后来调整过的 magic number 值。格式版本的差异主要体现在索引块、过滤块的组织方式上，比如：

• 老版本索引块直接二分搜索；
• 新版本可支持format_version更高的索引布局，比如带first_key信息的二级索引。

但无论格式版本怎么变，Footer 里保存“MetaIndex 句柄 + Index 句柄 + magic number”这个基本盘始终没有变过。这其实是对兼容性的巨大让步——读代码时你会看到很多if (format_version >= 2)之类的分支，理解了 magic number 才理解这些分支为什么存在。

3. Block 的通用外衣：BlockHandle、压缩与校验和

3.1 BlockHandle 为什么这么朴素

class BlockHandle { uint64_t offset_; uint64_t size_; };

BlockHandle 就这么两个字段。但整个 SST 文件的导航系统全部建立在它上面：Footer 通过它指向 Index Block 和 MetaIndex Block；Index Block 通过它指向每个 Data Block；MetaIndex Block 通过它指向 Properties Block、Filter Block、RangeDeletion Block。

它编码成 varint：offset一个 varint，size一个 varint。正因为是 varint，所以它占用的长度不固定，普通小块可能只有三五个字节，大块会稍微长一点。这也是前面说的“Footer 不固定长度”的原因之一。

读format.cc里的BlockHandle::DecodeFrom，你会看到它靠GetVarint64一个一个读出来，并用Slice的剩余长度作为边界检查。这在源码里属于那种一眼看懂、但极其容易被忽视的函数。我建议你把它当作第一个精读的小函数，因为它会反复出现在所有索引条目和 MetaIndex 条目中。

3.2 每个 Block 写完后的 Trailer：压缩类型与校验和

在物理文件里，一个 Block 不只是“数据内容”本身。在BlockBasedTableBuilder::WriteBlock的流程中，写完块数据后会追加一个BlockTrailer：

[Block Data] [1 byte: 压缩类型] [4 bytes: CRC32C 校验和]

需要注意，这 1 个字节记录的不是“数据块 / 索引块”这种语义类型，而是压缩方式。常见取值有kNoCompression、kSnappyCompression、kZlibCompression、kZSTD、kLZ4等。也就是说，同一个 SST 文件里，不同 Block 可能有的压缩了、有的没压缩，完全由写入时“这个块压缩后是否更小”的动态判断决定。

CRC 校验也很关键。RocksDB 用的是crc32c，不是 zlib 里常见的crc32。写解析工具时用错 CRC 算法的例子我见过很多次——对着同一个文件算出来的值总是对不上，最后查源码才发现校验和实现是util/crc32c.cc里的crc32c::Value。这个差异在性能调优和自研工具时特别容易踩。

3.3 读取侧的 RetrieveBlock 流程

读取侧对应的是BlockBasedTableReader里的RetrieveBlock。它的动作顺序是：

1. 根据BlockHandle从文件/缓存里拿到完整的块字节；
2. 读取最后 5 个字节的 Trailer；
3. 根据压缩类型做解压；
4. 用 CRC32C 校验解压前或解压后的数据是否完整；
5. 将解压后的数据交给对应类型的解析器。

这里的“从文件/缓存”几个字背后还藏着繁琐的BlockCache逻辑。Compaction 读旧文件时，往往有大量数据块要遍历，缓存命中率直接决定了压缩任务的 IO 表现。这也是为什么block_cache的大小会显著影响压缩速度——你在线上看到压缩任务慢，很多时候不是 CPU 不够，而是数据块反复从盘上读。

4. Data Block 的真实骨架：restart 点如何支撑前缀压缩与查找

4.1 为什么不用“全量 key + 顺序存储”的朴素方案

Data Block 是真正存放用户数据的块。最朴素的想法是把每个key和value完整地拼在一起，但这在 LSM 树的场景下太浪费了：同一份数据在邻近 key 上有着极强的前缀重复，比如user:10001、user:10002、user:10003。如果每次写 key 都全量存一遍，SST 文件体积会明显变大。

RocksDB 的 Data Block 编码方式是：

• 每隔固定条目数设置一个restart point（重启点）；
• 重启点之后的第一条 key 必须完整存储；
• 重启点和重启点之间的 key，只保存与前一个 key 共享前缀的长度、剩余后缀和 value。

这个思路和字符串压缩很像，但它不是把所有 block 一次压缩到底，而是在“节省空间”和“随机定位”之间做了折中。默认restart_interval是 16，也就是每 16 条记录开一个新的重启点。如果你把重启间隔调得太大，空间节省更多，但查找时需要顺序扫描的条目也更多；调小了则随机读取性能更好，文件体积相应变大。

4.2 BlockBuilder::Add 的核心动作

看table/block_based/block_builder.cc里的BlockBuilder::Add，你会看到它的逻辑可以浓缩成下面这段等价伪代码：

// 计算与上一条 key 的公共前缀长度 size_t shared = 0; while (shared < std::min(last_key_.size(), key.size()) && last_key_[shared] == key[shared]) { shared++; } size_t non_shared = key.size() - shared; // 如果达到重启间隔，先把当前 buffer 偏移记入 restart array if (counter_ >= restart_interval_) { restarts_.push_back(buffer_.size()); counter_ = 0; } // 编码当前条目 EncodeVarint32(shared); EncodeVarint32(non_shared); EncodeVarint32(value.size()); buffer_.append(key.data() + shared, non_shared); buffer_.append(value.data(), value.size()); last_key_ = key; counter_++;

第一次看这段代码你可能会疑惑：明明把共享前缀算出来了，为什么不直接把shared对应的那部分last_key也编码进去？因为对读取端来说，它天然已经知道上一条 key 的完整内容，所以看到shared之后，只要从上一个 key 里拷贝shared字节，再拼上当前 key 的后缀，就能重建完整 key。这与“增量编码”是一回事。

比如连续写入三条 key：

key1: hello key2: hello,world key3: hello,rock

如果三者落在同一个重启间隔内，那么 key2 实际写入的是shared=5, non_shared=6, value...；key3 写入的是shared=5, non_shared=4, value...。读取端基于上一条 key 组合，完全能还原出hello,rock。

4.3 restart 数组与二分查找的结合

Data Block 的尾部除了数据本身，还有一个restart array：它把所有重启点在 block buffer 里的偏移量依次用 varint 记录下来，最后再补一个restart count。BlockBuilder::Finish()做的就是这件事。

组合出来的块布局大致如下：

[各 key-value 条目的增量编码数据] [重启点偏移1] [重启点偏移2] [重启点偏移3] ... [重启点数量]

查找某个 key 时，RocksDB 不会真的顺序扫全量数据。它会先对 restart array 做二分查找，确定目标 key 大概率落在哪个重启区间里，然后只在这个区间内做线性扫描。这就是为什么 DB 的压缩/读取能够维持不错的性能——顺序扫描是发生在一个小片段内，而不是整个 block 上。

4.4 读取端构造内部 key 时的常见遗漏

Data Block 里的 key 是InternalKey，里面包含了user_key + seq + type。源码内部比较时通过InternalKeyComparator把用户 key 和序列号合在一起比较。千万不能直接把 Data Block 里的 key 当成普通字符串读出来就完事；解析工具很容易在这里翻车，因为同一个用户 key 因为有不同序列号，可能在 block 里出现多次。Compaction 的CompactionIterator之所以能丢弃旧版本 key，依赖的正是对内部 key 结构的解构——所以你顺着源码看下去，会发现它总是在ExtractUserKey和ParseInternalKey之间反复横跳。

5. Index Block 与 Meta Block：导航层和元数据层的源码细节

5.1 Index Block：每个条目的 key 是“数据块最后一条 key”

Index Block 在物理上可以看作一个特殊的 Data Block，但它里面每个条目的意义完全不同。条目 key 是这个数据块的最后一条内部 key，value 则是一个编码后的BlockHandle，指向该数据块在文件中的位置。

为什么用“最后一条 key”作为索引 key？因为在 LSM 有序语义下，我要找某个用户 key 时，先在 Index Block 里二分查找到“最后一个小于等于目标 key 的索引条目”，这个条目的 value 就是包含目标 key 的 Data Block 的句柄。之所以必须用最后一条 key 而不是第一条，是因为二分查找的语义最容易落在这个边界上。

在BlockBasedTableBuilder里，每刷一个 Data Block，就会往index_builder塞一个条目：(last_key_in_data_block, block_handle)。源码里这一步通常叫AddIndexEntry()。

更现代的实现还支持分区索引：当 Index Block 本身很大时，索引块会被拆成一棵小型的“索引的索引”结构。这种优化在线上一张大表上非常有用，但如果你直接按“单索引块”解析 SST，遇到分区索引文件就会错位。这也是很多个人写的 SST 查看工具在碰到新版 RocksDB 时崩溃的主要原因之一。

5.2 MetaIndex Block：指向各个 Meta Block 的入口

MetaIndex Block 也是一块“键值数据”，它的 key 通常是这样的名字：

• rocksdb.properties
• rocksdb.range_deletion
• filter.rocksdb.BuiltinBloomFilter
• rocksdb.compression_dict

value 是对应 Meta Block 的BlockHandle。所以定位顺序是：

Footer -> metaindex_handle metaindex_handle -> MetaIndex Block MetaIndex Block 内找到 key -> 得到 meta block handle meta block handle -> 具体 Meta Block

源码里这一段的实现分散在BlockBasedTableBuilder::Finish()和BlockBasedTable::Open中。写入侧先收集所有 Meta Block 的句柄，再统一作为条目塞进 MetaIndex Block；读取侧则把 MetaIndex Block 当成普通 block 打开，然后逐个 key 做 seek。

5.3 Properties Block / Filter Block / RangeDeletion Block

这些 Meta Block 里，最值得先了解的是Properties Block。它保存了整张 SST 的统计信息，是性能分析和正确性校验的重要依据。我建议重点关注下面这些属性：

走在源码里你会看到TablePropertiesCollector扮演关键角色：用户在构建表时可以注册自定义 collector，以收集自己关心的属性。在 Flush/Compaction 完成后，这些属性会被写进 Properties Block；线上排查问题时，用sst_dump或自定义工具读出的那堆数据，基本就是从这里来的。

Filter Block是为了减少不必要的数据块读取。它内部保存的是布隆过滤器，常见形式是按 block 分片。Compaction 过程中读取旧 SST 时，如果某个键在过滤器里被判定为不存在，就可以跳过整个数据块，这对大范围压缩的性能影响很直接。

RangeDeletion Block则是专门存范围删除信息的。它看起来像一个特殊的有序集合，记录[start_key, end_key)的删除范围。Compaction 处理删除墓碑时，一定要结合这个块来做判断；如果你跳过它，会对“被删除的 key 为什么还出现在压缩输出里”完全摸不着头脑。

6. 写 SST 的完整路径：BlockBasedTableBuilder 的 Add/Flush/Finish

6.1 Compaction 输出侧如何接到 TableBuilder

在 Compaction 源码里，CompactionJob并不是直接 new 一个BlockBasedTableBuilder出来写文件，而是通过BuildTable()这个通用入口。BuildTable()里会根据TableFactory创建出TableBuilder，并接着调用TableBuilder::Add()把(key, value)一条一条喂进去。

所以读者读 Compaction 输出代码时，真正需要盯住的接口实际上很小：

table_builder->Add(key, value); ... table_builder->Finish();

这种设计让 Flush 和 Compaction 复用同一个格式维护逻辑。你在源码里看到fopen/new WritableFile和TableBuilder解耦，本质原因就在这里——文件 IO 可以换，格式逻辑不动。

6.2 Add 到 Flush 的分界点

BlockBasedTableBuilder::Add()的主要动作是判断当前 Data Block 是否已经写满。如果没满，就调用block_builder->Add(key, value)把新 kv 追加到内存 buffer 里；如果满了，就触发一次Flush()。

这个“满”的标准来自BlockBasedTableOptions::block_size，默认通常为 4KB 或更大。但源码里不是简单地比较block_builder的 buffer 大小大于block_size就刷出，它还会参考block_size_deviation，允许块略大或略小，避免因为边界问题导致大量小块出现。

Flush()做三件事：

1. 调用block_builder->Finish()，把当前 block 的增量编码数据和 restart 数组收拢成一个完整 block；
2. 对 block 做压缩判断；
3. 把压缩后的内容连同 BlockTrailer 写入文件，并得到这个块在文件里的BlockHandle。

拿到BlockHandle后，当前 Data Block 的索引条目会被暂存到index_builder里。注意，这里不会立刻把索引块落盘，因为后面可能还有更多 Data Block 要写。

6.3 Finish 阶段：Meta Block、MetaIndex、Index、Footer 的顺序

所有Add完成后，调用Finish()。这一步的顺序基本决定了 SST 文件布局：

1. 写必要的 Meta Block，包括 Properties Block、Filter Block、RangeDeletion Block 等；
2. 收集这些 Meta Block 的句柄，写入 MetaIndex Block；
3. 把index_builder里暂存的所有索引条目收拢，写出 Index Block；
4. 把 MetaIndex Block 句柄和 Index Block 句柄编码进 Footer；
5. 写出 Footer。

写完这些，一个完整的 SST 文件才真正成立。物理布局从文件头到文件尾就是：

[Data Block 0] [Data Block 1] ... [Data Block N-1] [Filter Block] / [Properties Block] / [RangeDeletion Block] [MetaIndex Block] [Index Block] [Footer]

这个顺序决定了 Compaction 在做大范围顺序读取时表现出很好的 IO 局部性：新生成的文件数据块集中在前半段，导航和元数据集中在后半段。使用时如果需要读很多 Meta Block，后半段往往能命中同一批缓冲页。

6.4 压缩与压缩级别：写在块级而非整个文件级

值得单独说一句：SST 文件不是“整个文件统一压缩”，而是每个 Block 各自压缩。BlockBasedTableBuilder::CompressAndVerifyBlock会先尝试压缩，如果压缩后的大小比原始数据小到一定程度，才使用压缩；否则就存原始数据。所以一个文件里不同 block 的压缩方式可能不同，BlockTrailer 里的 1 字节压缩类型就是干这个用的。

Compaction 写新文件的时候，这个逻辑会造成一个容易被误解的现象：即使输出文件整体CompressionType设置成了kSnappyCompression，也仍会有个别 block 以kNoCompression落盘。所以做 SST 解析器时不能假定“全文件压缩方式一致”。

7. 从尾到头手写 SST 解析：踩坑与读码心得

7.1 一个反向解析的实操顺序

如果你看完源码还是觉得抽象，最好的办法是拿一个真实的 SST 文件，自己写个小解析器。不要追求一次做到很完善，只要能把 Footer、Index Block、第一个 Data Block 读出来就算成功。

我建议的解析步骤是：

1. 打开文件，先 seek 到文件尾；
2. 读最后几十字节，解析 magic number，确认是 BlockBasedTable 格式；
3. 解析出metaindex_handle和index_handle；
4. 按index_handle读取整个 Index Block，拆出每个数据块条目的BlockHandle；
5. 按第一个数据块的句柄去读数据块；
6. 读数据块尾部，解析 restart array；
7. 从 restart point 开始逐条重建内部 key，打印前几行。

跑通这个顺序后，你对整张表的“导航关系”会比光读源码清晰得多。我第一次做这个实验时，光看着 hexdump 里最后一个 magic number 就想通了很多之前死记硬背的东西。

7.2 三个特别容易踩的坑

第一个坑是用错校验和算法。RocksDB 的 block trailer 校验使用的是 CRC32C，不是常见的 zlib CRC32。用crc32去校一个crc32c数据，永远对不上。

第二个坑是忽略块尾部压缩类型字节。当你拿到一个压缩过的块，如果直接按原始字节解析，得到的 restart array 全是乱码。正确做法是先读 Trailer 的压缩类型，确认是kNoCompression才直接解析数据部分，否则必须先解压。

第三个坑是把 Format Version 当成全局统一固定行为。不同format_version下，索引块可能采用不同的数据结构，比如带二级分区索引，或者过滤块采用不同的组织方式。解析源码时要多看format_version的分支，不能拿一个版本的布局套所有文件。

7.3 推荐的精读顺序

从我自己的经验看，读 SST 格式源码不要按文件顺序从头到尾。更高效率的顺序是：

1. 先读table/format.cc里的BlockHandle、Footer相关代码；
2. 再看table/block_based/block_builder.cc，理解 Data Block 内部格式；
3. 然后读block_based_table_builder.cc里的Finish()，从输出端把握布局；
4. 最后读block_based_table_reader.cc，理解读取时如何反向往回走。

这样读完后，再去看 Compaction 源码时，你会发现自己对CompactionJob里很多“为什么要先建TableBuilder，再不断 Add，最后 Finish”的流程已经毫无障碍。如果后面文章进入 LSM 层级调度和CompactionIterator的内部实现，每次提到BlockHandle和 SST 布局，都不需要再停下来翻格式代码了。

最后分享一个我自己的阅读习惯：遇到 SST 格式底层的源码，我会在代码里随手标注“这里写出去的东西，会在后续哪个位置被读回来”。这条标注链从 Footer 出发，串联到 MetaIndex、Index、Data Block，全串起来时，RocksDB 这套文件格式设计的思路基本就刻进脑子了。下一篇文章我们就能安心从这里出发，正式拆解 Compaction 的调度与执行过程。