存储算法 #04：SSTable

SSTable（Sorted String Table）是 LSM Tree 的磁盘存储格式：一个不可变的、按 key 有序排列的键值对文件。理解 SSTable 是理解 LSM Tree 读写路径、Compaction 机制的基础。LevelDB、RocksDB、Cassandra、HBase 均使用 SSTable。

相关文章：LSM Tree · Bloom Filter · B+ Tree

目录

核心特性

不可变（Immutable）：
  SSTable 写入磁盘后永远不修改
  更新 = 写一条新的 SSTable 记录（带更高的序列号）
  删除 = 写一条 tombstone（墓碑）标记

有序（Sorted）：
  文件内所有 key 按字典序排列
  支持二分查找定位 key
  多个 SSTable 合并时可用归并排序，O(N) 时间复杂度

两者结合的优势：
  不可变 → 无需加锁，多线程并发读安全
  有序 → 支持高效点查和范围扫描
         支持 O(N) 多文件合并（Compaction）

文件内部结构

SSTable 文件布局（从文件头到文件尾）：

┌─────────────────────────────────────┐
│          Data Block 0               │  ← 实际 key-value 数据，约 4KB
│          Data Block 1               │
│          Data Block 2               │
│          ...                        │
├─────────────────────────────────────┤
│          Meta Block                 │  ← 统计信息（key 数量、大小等）
├─────────────────────────────────────┤
│          Filter Block               │  ← Bloom Filter（可选）
├─────────────────────────────────────┤
│          Index Block                │  ← 每个 Data Block 的最大 key + 偏移量
├─────────────────────────────────────┤
│          Metaindex Block            │  ← Filter Block / Meta Block 的偏移量
├─────────────────────────────────────┤
│          Footer（固定 48 字节）      │  ← Metaindex 和 Index Block 的偏移量
└─────────────────────────────────────┘

Data Block（数据块）

每个 Data Block 约 4KB（一个磁盘页），存储若干有序 key-value 对

内部结构（支持前缀压缩，节省空间）：
  key="apple",   value="red"
  key="application", value="software"  ← 前缀 "appl" 共享，只存差异 "ication"
  key="banana",  value="yellow"
  ...
  trailing: 重启点列表（每 16 个 key 一个完整 key，支持二分查找）
            checksum（CRC32，用于检测数据损坏）

Index Block（索引块）

每条记录：{最大 key，Data Block 偏移量，Data Block 大小}

查找 key=X 时：
  在 Index Block 二分查找，找到第一个 ≥ X 的条目
  → 得到对应 Data Block 的偏移量
  → 直接定位读取该 Data Block

避免了全文件扫描，读取 1 个 SSTable 最多 2 次磁盘 I/O
（1次读 Index Block，1次读 Data Block）

Filter Block（过滤块）

默认存储 Bloom Filter（每 2KB 数据块一个，或全文件一个）

查找时先查 Bloom Filter：
  → 不存在：直接跳过整个 SSTable（节省磁盘 I/O）
  → 可能存在：再走 Index → Data Block 流程

作用：大幅减少"key 不存在"时的无效磁盘读
RocksDB 实测：Bloom Filter 可减少 90%+ 的不必要 SSTable 读取

写入过程

MemTable（内存红黑树/跳表，有序）→ Flush 为 SSTable：

1. 遍历 MemTable，按 key 顺序输出所有 key-value 对
2. 每积累 4KB 数据，写一个 Data Block
3. 每写完一个 Data Block，更新 Index Block（记录该块最大 key + 偏移）
4. 同时为每个 Data Block 计算 Bloom Filter
5. 所有 key-value 写完后，顺序写入：
   Data Blocks → Filter Block → Index Block → Footer
6. fsync 刷盘

整个写入过程是顺序写，I/O 效率极高

读取过程

查找 key=X 在 SSTable 中：

1. 读 Footer（文件最后 48 字节）
   → 获取 Metaindex Block 偏移量

2. 读 Metaindex Block
   → 获取 Filter Block 和 Index Block 的偏移量

3. 读 Filter Block，查 Bloom Filter
   → 不存在：直接返回（无需读数据，节省 I/O）
   → 可能存在：继续

4. 读 Index Block，二分查找目标 Data Block 的偏移量

5. 读目标 Data Block，二分查找 key=X
   → 找到则返回 value
   → 未找到则返回不存在

实际 I/O 次数：
  key 不存在（Bloom Filter 拦截）：1~2 次（Footer + Filter）
  key 存在：3~4 次（Footer + Filter + Index + Data）

Compaction 合并

多个 SSTable 合并为一个（或多个）新 SSTable：

输入：SSTable A [apple:1, cherry:3, mango:2]
      SSTable B [banana:4, cherry:5, grape:1]（cherry 有两个版本）

合并算法（多路归并排序）：
  维护最小堆，每次取最小 key
  相同 key 取版本号（序列号）更大的值（即更新的写入）
  tombstone key 直接丢弃（删除操作的最终清理）

输出：[apple:1, banana:4, cherry:5, grape:1, mango:2]
      （cherry 旧版本 3 被丢弃，空间回收）

时间复杂度：O(N log k)，N = 总 key 数，k = 参与合并的文件数

与 LSM Tree 的关系

LSM Tree 是架构，SSTable 是 LSM Tree 磁盘层的存储格式：

                  ┌─────────────┐
  写入    →        │  MemTable   │  （内存）
                  └──────┬──────┘
                   Flush │
                  ┌──────▼──────┐
  L0 层   →        │  SSTable 0  │  （磁盘，不可变）
                  │  SSTable 1  │
                  └──────┬──────┘
                Compact  │
                  ┌──────▼──────┐
  L1 层   →        │  SSTable A  │  （有序，不重叠）
                  │  SSTable B  │
                  └─────────────┘

每次 Flush/Compaction 都产生新的 SSTable 文件
旧文件在 Compaction 完成后删除

异常场景

文件损坏检测

每个 Data Block 末尾存 CRC32 checksum
读取时验证 checksum：
  不匹配 → 文件损坏，报错
  → 从副本（如 Raft 其他节点）重新获取数据

RocksDB 还支持对整个 SSTable 文件做定期校验（Verify Checksum）

Compaction 中途崩溃

SSTable 是不可变文件：
  Compaction 生成新 SSTable 文件
  全部写完 + fsync 后，原子性地更新 MANIFEST 文件（记录哪些文件有效）
  崩溃后：
    新文件写完但 MANIFEST 未更新 → 新文件当成垃圾清理，原文件仍有效 ✅
    MANIFEST 已更新 → 正常使用新文件，原文件标记删除 ✅

关键：MANIFEST 的原子更新保证了一致性

参考资料

• LevelDB SSTable 格式：https://github.com/google/leveldb/blob/main/doc/table_format.md
• RocksDB BlockBasedTable：https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format
• 《Designing Data-Intensive Applications》Ch.3 — SSTables and LSM-Trees