手写 LSM 存储引擎（三）：SSTable——磁盘上的数据长什么样
(手写 LSM 存储引擎, Part 3)
前言
上一篇讲了 Memtable。Memtable 满了以后要 flush 到磁盘，落地的文件就是 SSTable（Sorted String Table）——LSM 引擎最核心的磁盘结构。后续的 compaction、读取、range scan 都绕不开它。
这一篇聊 SSTable 的物理布局。讲完这些你会明白：为什么查一个 key 只需要两次二分查找，为什么 SSTable 的读取放大没有想象中那么糟，以及 Bloom filter 是怎么把"一定不存在"这件事做到 17 纳秒的。
设计目标
SSTable 不是一个普通的"序列化的有序表"，它要同时满足好几个要求：
- 只读不改——一旦写入就不再修改，这是 LSM 的基本假设
- 快速点查——给一个 key，要能在 O(log n) 的磁盘 I/O 内判断是否存在、以及取出 value
- 快速范围扫描——给一个范围
[lower, upper)，能顺序读取所有 key - 压缩友好——相邻 key 通常有共同前缀，应该省掉
- 可校验——磁盘会坏，要能检测出数据损坏
所有这些需求共同塑造了 SSTable 的结构。
整体布局
一个 SSTable 文件看起来是这样的：
┌──────────────────────────┐
│ Data Block 0 │
├──────────────────────────┤
│ Data Block 1 │
├──────────────────────────┤
│ ... │
├──────────────────────────┤
│ Data Block N │
├──────────────────────────┤
│ Meta Entries │ ← 每个 block 的偏移量 + 首末 key
├──────────────────────────┤
│ meta_off (u32) │ ← Meta Entries 的起始偏移
├──────────────────────────┤
│ [bloom filter] │ ← 可选
├──────────────────────────┤
│ [CRC32] │ ← 可选，文件级校验
└──────────────────────────┘
三层结构，从小到大：entry → block → table。entry 是一个 KV 对，block 是批量 I/O 的单位，table 是整个文件。
Block：I/O 的基本单位
操作系统的磁盘 I/O 是按页做的（一般 4KB）。从磁盘读数据，读 10 字节和读 4KB 是一样的代价。所以 SSTable 不按 KV 对做最小读取单位，而是攒够一定字节（典型 4KB）打包成一个 block。
Block 内部是一段紧凑的编码，外加一个偏移表方便二分查找：
┌─────────────────────────────────────┐
│ entry 0 | entry 1 | ... | entry M │ ← 紧凑排列的 KV 对
├─────────────────────────────────────┤
│ offset_0(u16) | offset_1(u16) | … │ ← 每个 entry 在 data 里的起始位置
├─────────────────────────────────────┤
│ num_entries (u16) │
└─────────────────────────────────────┘
读入 block 时先看末尾的 num_entries，再从偏移表算出每个 entry 的位置。查某个 key 时对偏移表做二分——O(log M) 次比较（M 通常几十到几百）。
前缀压缩
如果相邻的 key 是 "user:001:name"、"user:001:age"、"user:001:city"——它们共享一个很长的前缀。一个 block 里通常都是这种情形，因为 key 有序排列。
每个 entry 的编码是：
┌────────────────┬───────────────┬──────────┬──────────┬────────┐
│ overlap_len │ rest_key_len │ rest_key │ val_len │ value │
│ (u16) │ (u16) │ │ (u16) │ │
└────────────────┴───────────────┴──────────┴──────────┴────────┘
- 第一个 entry 的
overlap_len = 0，它完整存储自己的 key - 后续 entry 的
overlap_len记录"和当前 block 第一个 key 的公共前缀长度"，只存差异部分rest_key
重建完整 key 时：full_key = block.firstKey[:overlap_len] + rest_key。
这种压缩对 LSM 非常友好。实际 benchmark 里，前缀压缩 + block 编码后的 SST 体积大约是原始数据的 60-70%，代价是每次 block 第一次使用时多一次前缀拼接。
有人会问：为什么不和每一个前驱 key 比，只和 block 第一个 key 比？因为这样会导致 block 内部无法二分——如果 overlap_len 依赖前驱，那跳到中间的 entry 时就不知道它的完整 key 是什么。和固定的 firstKey 比，每个 entry 都能独立解码。
Index：快速找到 block
每个 block 在 SST 里对应一条 meta entry：
type BlockMeta struct {
Offset uint32 // block 在文件中的起始位置
FirstKey []byte // block 的第一个 key
LastKey []byte // block 的最后一个 key
}
所有 meta entry 连起来就是一个小型索引——通常几十 KB，完全可以常驻内存。
查找一个 key 的流程：
1. 在 meta 数组上二分搜索，找到 FirstKey ≤ key ≤ LastKey 的那个 block
2. 读入该 block（从磁盘/缓存）
3. 在 block 内部二分搜索，找到精确位置
两次二分查找，一次磁盘 I/O（如果缓存命中是 0 次）。对于几 MB 到几百 MB 的单个 SST，这个性能是非常好的。
Benchmark 印证了这一点——在 5000 keys 的 SST 上做随机点查，平均 1.1 µs，扫描全表要 164 µs，差 150 倍。
meta_off：入口点
文件的最后 4 字节是 meta_off——meta entries 的起始偏移。打开 SST 时第一步就是读这 4 字节，顺藤摸瓜把索引加载进内存：
func (sst *SsTable) readBlock(idx int) *Block {
start := int(sst.meta[idx].Offset)
var end int
if idx+1 < len(sst.meta) {
end = int(sst.meta[idx+1].Offset)
} else {
// 最后一个 block 的结尾 = meta_off
metaOff := int(binary.LittleEndian.Uint32(sst.data[len(sst.data)-4:]))
end = metaOff
}
return DecodeBlock(sst.data[start:end])
}
把 meta 放在文件末尾而不是开头，是一个很朴素的选择——写入时不知道 meta 会有多大，如果放开头，要么预留空间要么二次写文件头。放末尾就没这问题：一路顺序写 block，最后把 meta 和 meta_off 追加上去。
Bloom Filter：一定不存在
问题：如果一个 key 压根不在这个 SST 里，我们还是要做"读 meta → 二分 → 读 block → 二分"的全流程才能确认不存在。对 LSM 这种"一个 key 可能分散在多个 SST"的结构，很多次查询是无果的——这部分开销非常浪费。
Bloom filter 专门解决这个问题：它是一个小小的位图（典型 10 bits/key），能以很低的空间成本快速排除"这个 key 一定不在这个集合里"。
工作原理：
插入 key:
h1 = hash1(key) → 置位 bit[h1 % numBits]
h2 = hash2(key) → 置位 bit[h2 % numBits]
... (k 个哈希函数)
查询 key:
if 所有 bit[hi(key) % numBits] 都为 1:
return "可能存在" // 但也可能是假阳性
else:
return "一定不存在" // 确定无疑
Bloom filter 有假阳性（false positive）但没有假阴性（false negative）——说"不存在"的时候一定对，说"可能存在"的时候有一定概率误判。误判概率取决于位图大小和哈希函数数量，10 bits/key + 7 个 hash 能做到约 1% 的假阳性率。
为了省掉"算 k 次哈希"的开销，实际实现用double hashing：算一次 32-bit hash，派生出两个 16-bit 值作为 hash 和 delta，后续哈希用 hash += delta 递推。单次 MayContain 用时 17 纳秒，零内存分配——这是整个引擎里最快的操作。
func (bf *BloomFilter) MayContain(key []byte) bool {
h := hash32(key)
delta := (h >> 17) | (h << 15)
numBits := uint32(len(bf.bits) * 8)
for i := 0; i < bf.k; i++ {
bitPos := h % numBits
if bf.bits[bitPos/8]&(1<<(bitPos%8)) == 0 {
return false
}
h += delta
}
return true
}
一个坑：编码解码要一致
这是实现过程中踩过的坑——构建 Bloom filter 时 numBits 算出来是 100（10 keys × 10 bits/key），但实际分配的字节数是 ceil(100/8) = 13，对应 104 个 bit。构建时用 100 取模，查询时用 104 取模，hash 位置对不上，大量假阴性。
修复方案是把 numBits 对齐到字节边界，编解码两端都用这个对齐后的值。这属于"编码/解码不一致"这类经典 bug——位数、字节序、padding，任何一方搞错都是灾难。
写入 SSTable
SST 的构建是增量的。SsTableBuilder 吃一个有序的 KV 流，不断攒到当前 block 里；block 满了就封存到 blockData，开一个新的：
func (sb *SsTableBuilder) Add(key, value []byte) {
if !sb.builder.Add(key, value) {
sb.finishBlock()
sb.firstKey = append(sb.firstKey[:0], key...) // 新 block 的 firstKey
sb.builder.Add(key, value)
}
sb.allKeys = append(sb.allKeys, cloneBytes(key))
sb.lastKey = append(sb.lastKey[:0], key...)
}
注意 allKeys 要收集所有 key（不只是 block 边界的 firstKey/lastKey），因为 Bloom filter 要覆盖全集。这也是踩过的一个坑——早期只收集边界 key，导致中间 key 全部假阴性。
Build() 的时候做两件事：
- 把所有 block data 拼起来，追加 meta entries 和 meta_off
- 用
allKeys构建 Bloom filter（Bloom 本身也要编码进 SST）
校验和
可靠性要求 SST 能检测出损坏。我们在两个层级加了 CRC32：
- Block 级：每个 block 前面加 4 字节 CRC（可选，用
EncodeWithChecksum） - 文件级：整个 SST 末尾加 4 字节 CRC（可选，用
BuildWithChecksum）
文件级的代价是——现在 meta_off 不再是最后 4 字节，而是倒数第 8 字节（前面那 4 字节是 CRC）。这给 readBlock 里那个计算"最后一个 block 结尾"的逻辑带来麻烦，需要一个 hasChecksum 标记区分两种情形：
suffixOffset := 4
if sst.hasChecksum {
suffixOffset = 8 // 跳过 CRC(4) + meta_off(4)
}
metaOff := binary.LittleEndian.Uint32(sst.data[len(sst.data)-suffixOffset:])
这种"版本兼容"的细节是存储系统里最让人头大的地方——改一个字段，读取路径就可能要改好几处。生产级实现通常在 SST 头部或尾部放一个版本号，解析时根据版本分派到不同的路径。
性能数据
把上面这些设计落到代码上，SST 各层的性能数字：
| 操作 | 延迟 | 备注 |
|---|---|---|
| Bloom MayContain（命中） | 17 ns | 零分配 |
| Bloom MayContain（未命中） | 97 ns | key 生成时的分配 |
| Block 内二分查找 | 125 ns | SeekToKey |
| SST 点查（5K keys） | 1.1 µs | meta 二分 + block 二分 + 值重建 |
| SST 全扫描（5K keys） | 164 µs | 33 ns/entry，和裸 block 迭代同量级 |
点查比全扫描快 150 倍——这就是 meta index + Bloom filter 存在的意义。Bloom filter 在一个 SST 里可能只占几 KB，但它挡掉了大量无意义的 block 读取。
小结
SSTable 看似朴素，实际上每一层都在围绕磁盘特性做优化：
- Block 是 I/O 单位——按页组织，省掉小 I/O 的系统开销
- 前缀压缩——利用有序性，typical 节省 30% 空间
- 两层二分索引——meta 索引定位 block，block 内偏移表定位 entry
- Bloom filter——17 ns 就能排除"一定不存在"，读路径的第一道关卡
- CRC32——block 级和文件级校验，兼顾精度与开销
下一篇回到引擎层面——写路径全流程，WAL 怎么设计，崩溃后怎么恢复。