LSM 树笔记：一个键从写入到压缩的生命周期

LSM 树最容易被一句“写入快”概括得过于简单。

更准确地说，LSM 树把随机原地更新改成顺序追加和后台整理。前台写入变轻了，但代价并没有消失，而是转移成读放大、写放大、空间放大、压缩债务和写入停顿。

我现在更愿意沿着一个键的生命周期理解 LSM，而不是孤立地记忆内存表、SSTable 和压缩。

写入 key=a
  -> WAL 记录写入意图
  -> 内存表保存最新版本
  -> 刷盘生成 L0 SSTable
  -> 压缩将它逐层下移
  -> 后续更新或删除产生新版本
  -> 确认安全后才移除旧版本

这条线能解释 LSM 为什么快，也能解释它为什么会突然慢。

前台写入只做能快速确认的事

一次写入通常会被拆成两步：

append WAL
  -> insert into memtable

WAL 是恢复边界，内存表是查询边界。只要 WAL 策略允许，前台不需要去磁盘上寻找旧值的位置，也不需要更新某个 B+ 树页。它只需追加日志，再把新版本放进内存结构。

这就是 LSM 的写入优势。

但这个优势建立在一个前提上：后面有人会收拾旧版本。否则系统只是把垃圾堆到了未来。

SSTable 的不可变性让后台整理变得可控

内存表满了以后会变成不可变内存表，然后刷盘生成 SSTable。SSTable 写出后不再原地修改。

不可变文件有几个工程好处：

• 读线程不需要担心文件内容被改。
• 文件可以带块索引、过滤器块和范围元数据。
• 压缩可以写新文件，再通过版本清单更新原子切换。
• 崩溃恢复时可以根据文件编号、校验和版本清单判断哪些文件有效。

代价是更新不会覆盖旧值。

seq=30 key=a value=v3  in L0
seq=20 key=a value=v2  in L1
seq=10 key=a value=v1  in L3

读取路径必须找到当前快照可见的最新版本。删除也一样，只是写入一个更新的墓碑标记，而不是立刻从所有低层文件中抹掉旧值。

L0 是 LSM 的交通事故现场

L0 和其它层不同。刷盘生成的文件直接进入 L0，不同文件的键范围可能互相重叠。

这对单键查询很不友好。低层如果范围不重叠，系统可以根据键范围快速定位少数文件；L0 重叠时，一个键可能需要查询多个 L0 文件。

L0:
  file A: key range [a, z]
  file B: key range [b, y]
  file C: key range [a, m]

lookup key=k
  -> A/B/C may all need checking

所以 L0 文件数量是很重要的健康信号。它升高时，通常说明刷盘速度超过了压缩任务的消化速度，随后可能出现：

• 单键查询变慢。
• 布隆过滤器、过滤块和索引的查询次数增加。
• 压缩被迫变得更激进。
• 开始出现写入停顿。

LSM 的很多尾延迟毛刺不在写入入口，而在 L0 积压。

压缩任务选择器决定系统先偿还哪笔债

压缩不是简单的后台合并，它要先决定偿还哪笔债。

压缩任务选择器通常会考虑：

• L0 文件数量。
• 层大小是否超过目标。
• 文件范围是否和下一层重叠。
• 墓碑标记是否有机会清理。
• 压缩评分。
• 是否有正在运行的压缩任务。
• 是否可以直接移动文件而无需重写。

被选中的文件会进入 merge iterator：

input files from level N
  + overlapping files from level N+1
  -> merge by key + sequence number
  -> keep newest visible version
  -> drop obsolete versions
  -> output new SSTables
  -> 更新并安装新的版本清单

这里最关键的是“可见”。如果仍有快照需要旧序列号，压缩就不能随意删除旧版本。

这也是为什么快照、长生命周期迭代器和事务读取会影响压缩回收。旧读取者存活得越久，旧版本和墓碑标记越难清理。

墓碑标记记录删除事实，但不立即回收空间

LSM 删除一个键时，通常会写入墓碑标记：

seq=40 key=a tombstone
seq=30 key=a value=v3
seq=20 key=a value=v2

读路径看到可见的墓碑标记后，就认为该键不存在，但磁盘空间未必立刻下降。只有压缩过程确认低层旧值都已被覆盖，并且没有快照需要旧版本时，墓碑标记和旧值才能一起清理。

大量删除的负载，危险就在这里：

• 墓碑标记本身会增加写入。
• 单键查询可能一路查到墓碑标记。
• 范围扫描要跳过大量删除标记。
• 空间回收依赖压缩是否及时。

所以遇到“删除了很多数据，磁盘占用为什么没降”，不应先怀疑错误，而应先看压缩是否已经推进到能够清理墓碑标记的层级。

三个放大是同一个账本的不同列

LSM 的代价常被分成三个放大：

写放大：
  用户写入字节数 -> 磁盘实际写入字节数

读放大：
  一次逻辑读取 -> 多个数据结构、文件或数据块

空间放大：
  逻辑有效数据量 -> 磁盘物理占用字节数

它们不是孤立指标。

更积极的分层压缩可以降低读放大和空间放大，但会提高写放大。更宽松的分层策略可以降低写放大，但会加重读取路径和空间占用。

分层压缩（leveling）：
  读放大较低
  空间放大较低
  写放大较高

分级压缩（tiering）：
  写放大较低
  读放大较高
  临时空间放大较高

所以讨论 LSM 参数时不能脱离实际负载。写多读少、读多写少、范围扫描多、TTL 或墓碑标记多，对应的最优点完全不同。

写入停顿意味着后台债务已经影响前台

LSM 的设计看起来把 compaction 放到了后台，但后台债务最终会回到前台。

常见触发包括：

• 内存表太多，刷盘追不上。
• L0 文件数超过软阈值或硬阈值。
• 待压缩字节数过高。
• 磁盘空间不足。
• 后台 I/O 被限速或抢占。

这时系统会减慢甚至暂停写入，让压缩任务追赶积压。

前台写入
  -> 生成 WAL 并更新内存表
  -> 刷盘产生 L0 文件
  -> 压缩速度跟不上
  -> L0 文件持续增加
  -> 写入停顿

所以观察线上的 LSM，不要只看 QPS 和平均延迟。至少还要看 L0 文件数、待压缩字节数、停顿时间、刷盘与压缩吞吐，以及块缓存命中率。

我会怎么读一个 LSM 实现

读 RocksDB/LevelDB 这类实现时，我会按生命周期找入口：

写入路径：
  DBImpl::Write / WriteBatch
  WAL 写入器
  插入内存表

刷盘路径：
  不可变内存表
  表文件构建器
  安装 L0 文件

读取路径：
  查询内存表
  选择版本与文件
  布隆过滤器
  块缓存
  合并迭代器

压缩路径：
  选择压缩任务
  合并迭代器
  构建输出表文件
  版本编辑与清单文件

恢复路径：
  CURRENT
  重放清单文件
  重放 WAL
  清理废弃文件

具体函数名会随实现变化，但边界不会变：谁把写入变成可恢复事实，谁把内存变成不可变文件，谁把旧文件替换成新版本，谁在崩溃后确认当前历史。

LSM 的核心不是写入快，而是债务管理

LSM 树的前台写入路径很克制：追加 WAL，更新内存表，然后尽快返回。

真正决定系统能否长期稳定的，是后台能否持续还债：L0 能不能压住，旧版本能不能清掉，墓碑标记能不能回收，压缩能不能在不拖垮前台尾延迟的情况下推进。

写入快只是第一眼。债务管理才是 LSM 的工程核心。