对象存储与LSM引擎:从SSTable到Compaction
对象存储与LSM引擎:从SSTable到Compaction
关系库用 B+ 树把更新做成就地改写,代价是随机写;高写入吞吐的系统走另一条路——只追加、不更新,用后台合并换取顺序写。本文从一条写入的内存路径讲到 SSTable 的磁盘布局,再看 compaction 如何在写放大、读放大、空间放大之间做取舍,最后说明为什么把 LSM 直接搬到对象存储上会失效。
为什么放弃 B+ 树
B+ 树是"就地更新":改一行数据,要找到对应页、在页内修改、整页写回,还要配 WAL 和 doublewrite 保证崩溃一致性。一次 4KB 页的修改,实际落盘可能是页本身 + WAL + 双写缓冲,写放大从头就开始累积。机械盘上这是随机 IO,云盘上是计费的 IOPS。
LSM(Log-Structured Merge Tree)的思路反过来:任何修改都追加成新记录,旧版本留给后台合并处理。前台永远是顺序写,代价被推迟到 compaction。
LSM 与 B+ 树的基本差异
B+ 树 LSM
├─ 随机读写页 ├─ 顺序追加
├─ 原地更新,一个版本 ├─ 多版本共存
├─ 读放大 = 树高 ├─ 读放大 = 层数 + L0 文件数
└─ 无后台合并 └─ compaction 消耗 CPU/IO
写入路径:从 WAL 到 L0
client write
│
▼
WAL(append + fsync 或组提交) ← 掉电恢复的唯一来源
│
▼
MemTable(跳表,内存有序结构)
│ 超过大小阈值 → 冻结
▼
Immutable MemTable ──flush──▶ L0 SSTable(key 范围互相重叠)
│ compaction
▼
L1(层内 key 范围不重叠)
│
▼
L2 …… Ln
写入不碰磁盘上的旧数据,只做三件事:写日志、插内存、后台刷盘。这也是 LSM 写吞吐远高于 B+ 树的根本原因。
三个必须调的开关
| 开关 | 调小的后果 | 调大的后果 |
|---|---|---|
| WAL 同步策略 | 每次写都 fsync,吞吐掉一个量级 | 异步写,掉电丢最近一段数据 |
| MemTable 阈值 | flush 频繁、L0 文件多、读放大上升 | 内存占用高、崩溃后 WAL 重放时间长 |
| L0 文件数阈值 | compaction 频繁、写放大高 | 查询要扫更多文件,P99 抖动 |
组提交(group commit)是这里的关键技巧:把并发到达的多个写请求合并成一次 fsync,持久性不变、吞吐提升数倍。代价是单次写延迟从"一次磁盘往返"变成"一个提交周期"。
SSTable 的内部布局
L0 以下的每个文件都是不可变的 SSTable,结构大致如下:
┌──────────────────────────────────┐
│ data block 0(key 前缀压缩) │
│ data block 1 │
│ …… │
├──────────────────────────────────┤
│ filter block(布隆过滤器) │ ← 确定不存在就不读盘
├──────────────────────────────────┤
│ index block(每块起始 key+偏移) │
├──────────────────────────────────┤
│ footer(index/filter 位置 + 魔数)│
└──────────────────────────────────┘
一次点查的顺序是:读 footer → 读 index → 二分定位 data block → 块内二分。注意 data block 与 index block 都常驻 block cache,真正昂贵的只有"确定要读的 data block"。布隆过滤器的作用是把"肯定不在这里"的查询挡在 IO 之前,它只减少无效 IO,不能替代索引。
读路径与读放大
读一个 key 要按新鲜度从新到旧查找:
MemTable → Immutable MemTable
→ L0:key 范围重叠,最坏要逐个文件查
→ L1..Ln:层内不重叠,每层最多一次 IO(布隆过滤器可短路)
因此读放大约等于 L0 文件数 + 层数。这解释了一个常见现象:写入高峰过后查询变慢——L0 堆了十几个文件,每次点查都要多探几次。写吞吐和读延迟在这里是同一笔预算的两面。
Compaction 策略:三种放大的取舍
| 策略 | 写放大 | 读放大 | 空间放大 | 典型实现 |
|---|---|---|---|---|
| size-tiered | 低,每层数据只重写一次 | 高,同层多个 run 需合并查询 | 高,多版本长期共存 | Cassandra STCS |
| leveled | 高,每条记录每层重写一次 | 低,层内不重叠 | 低,同层容量受控 | LevelDB、RocksDB |
| hybrid / tiered+leveled | 中 | 中 | 中 | RocksDB Universal、ScyllaDB |
leveled 的写放大可以粗算:
每层容量比 fanout = 10,共 6 层
一条记录从 L0 走到 L6,平均被重写 6 次以上
实际写放大通常在 10~30 之间(取决于 key 分布与压缩率)
这意味写入 1TB 数据,compaction 要重写 10~30TB
所以"LSM 写入快"是有前提的:写入量要在 compaction 预算之内。当写入持续超过后台合并能力,L0 会堆积,触发写限速(write slowdown)甚至写停顿(write stall)——表现就是写入吞吐突然断崖式下跌,而不是慢慢劣化。
墓碑:删除为什么不能马上腾空间
删除在 LSM 里只是一条带删除标记的新记录(tombstone)。只有当 compaction 把墓碑推到最底层、并确认下面没有更老的版本时,才能物理删除。推论有三条:
- 大量删除后磁盘占用不会立刻下降,这是设计行为,不是泄漏。
- 墓碑本身占空间、占读路径、加重 compaction。
- 按时间分区的数据(比如日志表)可以直接丢弃整个 SSTable,这是成本最低的删除方式——TTL 引擎都会利用这一点。
把 LSM 放到对象存储上
对象存储的语义与本地盘差别很大:只能整对象 PUT/GET、不支持原地追加、没有原子 rename、按请求数和流量计费、延迟是毫秒到几十毫秒。直接把单机 RocksDB 的数据目录放到对象存储,manifest 并发覆盖会直接损坏数据目录。要跑通必须改三件事:
① 日志外置 WAL 放本地盘或独立日志服务,对象存储不适合低延迟追加
② 元数据收拢 manifest / 版本文件用 CAS 或事务库维护,避免并发覆盖
③ 合并外置 compaction 变成独立服务,与前台读写做资源隔离
这就是 SlateDB、Iceberg、Delta Lake 这类"存算分离"表格式的共同形状:数据文件不可变、元数据用小文件提交、合并任务独立调度。LSM 的合并逻辑没变,变的是"谁在什么时候做合并"。
顺带区分一个常被混淆的设计:ClickHouse 的 MergeTree 也是"只追加 + 后台合并",但它按分区目录组织、合并以 part 为单位,没有全局有序的 L0/L1 层级,点查能力远弱于 LSM。名字像,取舍完全不同。
什么场景不该选 LSM
LSM 的优势建立在"写多读少、能容忍后台合并"之上。反过来看,下面几类场景选它会很痛苦:
| 场景 | 为什么不合适 | 更合适的选择 |
|---|---|---|
| 强事务 + 多表 join | 缺少就地更新与行级锁语义,读路径要合并多版本 | B+ 树关系库 |
| 随机点查为主、写入很少 | 层数带来的读放大是纯开销,没有写吞吐收益 | B+ 树或内存索引 |
| 大量范围扫描做分析 | 逐层归并 + 多版本解码,比列存扫描慢一个量级 | 列式存储 + 分区 |
| 数据量小于内存 | compaction 的复杂度完全没必要 | 全内存结构,定期快照即可 |
| 频繁全量删除 | 墓碑要等合并触底,空间长期不释放 | 按分区整体丢弃 |
判断只需要两个问题:写入量是否显著大于读取量?能否为后台合并预留独立的 CPU 与 IO?两个都是"是",LSM 才划算。
常见坑
- 把布隆过滤器当索引。误判率设成 1% 就以为不会读盘,实际它只能过滤"确定不存在",存在性检查仍要走索引。
- compaction 与前台读写共享 IO 配额。后台合并把磁盘带宽打满,P99 直接上秒级,应在部署上做资源隔离或限速。
- 用 size-tiered 存更新频繁的数据。空间放大到 3 倍,误判为磁盘泄漏,实际是旧版本还没合并。
- 关 WAL 换吞吐。掉电后只能恢复到上一次 flush,最近的写入全部丢失,恢复点不可控。
- 为减少 compaction 上调 L0 阈值。写放大降了,但读路径变长,查询延迟抖动更明显。
- 忽略 key 设计的顺序性。单调递增 key 让 compaction 范围固定、热点集中;随机 key 分布均匀但缓存命中差,两者要用不同策略。
- 单机引擎直接挂对象存储。没有外置 WAL 与独立 manifest,任何一次并发提交都可能让整个数据目录不可读。
总结
| 维度 | 结论 |
|---|---|
| 写入 | 只追加 + 组提交,用顺序写换吞吐 |
| 读取 | 按新鲜度分层查找,布隆过滤器挡无效 IO |
| 合并 | 写放大、读放大、空间放大三者只能优先两个 |
| 删除 | 墓碑延后回收,空间释放滞后是设计而非故障 |
| 稳定性 | 写入量必须留在 compaction 预算内,否则写停顿 |
| 对象存储 | WAL、元数据、合并三件事都必须外置与隔离 |
LSM 不是"更快的 B+ 树",而是把随机写的代价从关键路径挪到后台。它换来的是前台写入的平稳吞吐,代价是必须持续为 compaction 支付 CPU、IO 与容量预算——这笔账算不清,LSM 的优势就会变成写停顿。
- 点赞
- 收藏
- 关注作者
评论(0)