假设磁盘里已经保存了这样一条数据：
user:42 = Alice现在应用执行：
Put("user:42", "Bob")最符合直觉的做法是什么？
大概是先找到 Alice 在文件里的位置，再把那一段改成 Bob。就像打开档案柜、找到原卡片、擦掉旧名字并写上新名字。
可 RocksDB 通常不会回到旧 SST 中原地修改 Alice。它会把 Bob 当成一条更新的记录继续写入，让读取规则先选择 Bob；Alice 即使还留在旧文件中，也会在后续合适的 Compaction 中被处理。
这乍看很绕：明明只是改一个值，为什么要允许新旧版本同时存在，还要在后台不断合并文件？
答案就在 RocksDB 采用的 LSM Tree 思路里。
先给结论： LSM Tree 没有让磁盘成本消失。它把“每次前台更新都定位并修改旧位置”的工作，转化为“先在内存接收新记录、批量生成有序文件，再由后台持续合并”。这条路线很适合吸收大量写入，但持续吞吐依赖 Flush 与 Compaction 能否跟上，也会带来读放大、写放大和空间放大的权衡。
本文只建立 LSM 的成本模型，不深入 RocksDB 的 Writer Queue、Sequence Number 和各种 Compaction Picker。示例默认使用单个 Column Family，并以常见的 Level Style 帮助理解；Universal、FIFO 以及定制策略会呈现不同的文件形态。
先从一个朴素问题开始：更新旧数据要付出什么？
“找到旧值并覆盖”并不是错误设计。许多成熟数据库使用 B-Tree 或类似的页式结构，正是因为它们可以沿索引定位到目标页，在合适的缓存、日志和并发控制下完成点查、更新和范围扫描。
但一次页式更新通常不只是把六个字节的 Alice 换成三个字节的 Bob。系统还可能需要处理：
- 沿索引找到目标页；
- 把不在内存中的页读入缓存；
- 在页内定位并修改记录；
- 记录恢复或事务日志；
- 处理并发、脏页和刷盘顺序；
- 空间不足时分裂、合并或重组页面。
数据库会用 Buffer Pool、WAL、Group Commit、批量刷页等机制减少这些成本。因此，不能把 B-Tree 简化成“每次更新都直接随机写一次裸磁盘”，更不能由此推导出它必然慢。
真正值得比较的是成本安排方式：
- 页式结构倾向于先定位已有组织，再维护目标页及其索引关系；
- LSM 倾向于先接收新记录，不为这次逻辑更新回头修改旧 SST，再批量重组多个有序文件。
LSM 没有消除成本，而是把每次前台定位旧位置的工作转移为批量落盘与后台合并。
假如写入很少、读取很多，而且目标页长期命中缓存，直接维护页式结构可能非常自然。假如更新源源不断到达，那么先聚合更新、再成批处理文件，就可能更容易摊薄单次写入的固定成本。
注意这里一直使用“可能”。存储结构的实际表现还会受到 Value 大小、读写比例、缓存命中、设备特性、同步要求和实现质量影响。LSM 是一条设计路线，不是一张脱离 workload 的性能保证书。
LSM 的第一步：先把写入留在内存
如果不去旧文件里修改 Alice，Bob 先放在哪里？
答案是内存中的可查询结构。在 RocksDB 里，这个角色由 MemTable 承担。
连续到达的写入可能是：
Put("user:43", "Chen")
Put("user:41", "Amy")
Put("user:42", "Bob")
Put("order:9", "PAID")到达顺序并没有按 Key 排列，但 MemTable 的组织方式会让这些记录保持可查询的内部顺序。默认 MemTable 常见实现是 Skip List，不过 RocksDB 允许选择其他实现；在本篇里，我们只关心它具备两个能力：
- 前台可以继续插入更新；
- 读取可以按照 Key 与版本顺序找到当前结果。
这一步的关键不是“内存一定比磁盘快”这么简单，而是先把许多细小更新聚到一个适合批量处理的边界内。
不过，只写内存显然不可靠。进程退出后，MemTable 会消失。因此 RocksDB 的常见写入路径还会记录写前日志（WAL），为尚未进入 SST 的更新提供恢复依据。
这里要把两个概念分开：
- MemTable 是 LSM 数据组织的一部分，服务当前读写与后续 Flush；
- WAL 是工程上的恢复机制，解决内存状态尚未落成 SST 时怎样重建。
是否等待 WAL 同步到更深的持久化层、突然断电时能承诺什么，不是 LSM 这个词本身决定的，而取决于 WriteOptions、操作系统、文件系统与硬件。精确故障模型留到工程篇讨论。
从 MemTable 到 Sorted Run
MemTable 不可能无限增长。达到切换条件后，活跃的 Mutable MemTable 会成为不再接收新写入的 Immutable MemTable；新的 Mutable MemTable 接管前台写入，旧表等待后台 Flush。
Flush 会遍历旧 MemTable 的有序内容，构造一个新的 SST 文件。我们可以先把这个文件理解成一个 Sorted Run：一段内部按 Key 排好顺序、生成后不再原地修改的数据。
内存缓冲把许多小更新聚合成一次有结构的文件生成过程。
为什么“有序的一批”有价值？
因为它让后续查询和合并都能利用顺序：
- 文件可以记录最小 Key 与最大 Key，先排除范围不可能命中的文件；
- Index 与 Filter 可以继续把候选缩小到更细的块；
- 范围扫描可以按顺序向后推进；
- 两个内部有序的 Run 可以用线性 Merge 形成新的有序 Run。
这也是 LSM 相对“每条更新都立即维护最终磁盘布局”的重要变化：前台只负责把更新送进可写的内存边界，后台一次处理一批有序内容。
“批量落盘”不等于“所有物理写都是顺序写”
讲 LSM 时经常会看到一句极度压缩的描述：把随机写变成顺序写。
这句话适合建立第一层直觉，却不适合作为严格的 I/O 结论。
RocksDB 确实避免为每一次逻辑 Update 都回到旧 SST 原地改写，并会批量生成、重写有序文件；但真实物理 I/O 还受到很多因素影响：
- WAL、Flush 与 Compaction 是不同的写入流；
- Compaction 同时读取多个输入并写出多个输出；
- 文件系统分配、Page Cache、Direct I/O 配置会改变路径；
- 存储设备内部还有映射、缓存、垃圾回收与写入合并；
- 多个 Column Family 和后台任务可能并发争用带宽。
因此，更准确的说法是：
RocksDB 通过内存聚合与不可变有序文件，避免为每次逻辑更新原地修改旧 SST，并把大量文件工作批量放到 Flush 与 Compaction 中完成。
为什么多个 Sorted Run 一定会“相遇”？
假设我们连续经历三次 Flush：
Run A（最旧）: user:42 = Alice
Run B : user:42 = Alice-v2
Run C（最新）: user:42 = Bob每个 Run 内部都已经排序，但不同 Run 之间并没有自动去重成唯一位置。同一个 User Key 仍可能出现在多个文件里。
于是，一次 Get("user:42") 不能随便命中一个文件就结束。它要把内存与文件中的相关记录放回新旧顺序和当前读视图中，选择最新可见的结果。
Run 内部有序不等于全局只有一个位置，多个 Run 会带来读取合并成本。
如果系统只 Flush、从不整理，Run 会越来越多：
- 点查可能面对更多文件候选；
- 范围扫描需要合并更多有序来源；
- 新值遮蔽的旧值仍占据空间；
- Tombstone 与被删除的旧值可能分处不同文件；
- 文件元数据、打开文件与缓存也会承担更多压力。
这说明后台 Merge 不是“数据库有空时顺便清理一下”，而是 LSM 维持长期可用状态的必要环节。
在 RocksDB 中，承担这项工作的核心机制叫 Compaction。
两路 Merge：先理解 Compaction 的算法直觉
先忽略 Level、Snapshot 和 Tombstone，只看两个已经排好序的 Run：
Run A: a, c, h, m
Run B: b, h, k, z合并时，不需要把全部元素重新乱序排序。只要比较两个输入的当前位置：
a < b，先输出 a，推进 Run A；b < c，输出 b，推进 Run B；c < h，输出 c；- 两边都遇到 h，进入重复 Key 的版本处理；
- 继续输出 k、m、z。
Compaction 的算法基础是有序 Merge，但真实实现还要处理版本、删除和文件边界。
如果两个输入共包含 N 条记录，这种合并的核心遍历可以近似看成线性工作，而不是把 N 条记录重新做一次通用排序。
不过，真实 Compaction 远比这张图谨慎。遇到相同 User Key 时，RocksDB 不能简单地“只留最后一个”：
- 旧 Snapshot 可能仍需要较老版本；
- Tombstone 下面可能有本次输入范围没有覆盖到的旧值；
- Merge Operand 有自己的计算规则；
- 输出文件需要按大小与 Key 边界切分；
- 新输出发布成功前，旧输入仍承担读取职责。
B02 只需要记住两件事：有序性让批量 Merge 可行；能否丢弃记录则受可见性与覆盖条件约束。后一个问题会在 B06 专门展开。
Compaction 交换了哪些成本？
把多个 Run 合成更可控的文件组织，可以减少未来读取的候选，也可以在安全时清理被覆盖的版本和 Tombstone。但代价是：旧文件必须被读取，仍需保留的记录要写进新文件。
一次 Compaction 通常会消耗：
- CPU： 比较 Key、处理版本、压缩与校验；
- 读取带宽： 读取输入 SST；
- 写入带宽： 生成新的输出 SST；
- 后台线程： 与 Flush 以及应用请求共享机器资源；
- 临时空间： 新输出安全发布前，新旧文件会短时共存。
因此，LSM 所谓“适合写密集型”不是说后台没有写，而是说前台可以先走一条较短的接收路径，再把大量整理工作批量化。
低前台写延迟依赖后台持续消化，短时快不等于持续吞吐无限。
短时吞吐与持续吞吐是两个问题
如果测试只运行十秒，足够大的内存缓冲可能让结果非常漂亮。此时许多写入刚进入 MemTable，真正的 Flush 与 Compaction 成本还没有完全显现。
把测试时间拉长，系统会逐渐进入更接近稳定状态的循环：
前台持续写入
→ MemTable 持续切换
→ Flush 持续生成 L0 文件
→ Compaction 持续读取并重写文件当数据产生速度长期高于后台处理能力，Immutable MemTable、L0 文件或待 Compaction 字节会积压。RocksDB 会先减慢写入，必要时暂停写入，避免内存、文件数量、读放大和空间继续失控。
这就是理解 Write Stall 最重要的前提：它不是凭空出现的随机故障，而是前台与后台长期收支不平衡时的保护边界。具体触发条件与诊断放到 B03 和工程篇。
怎样用一个小实验看见成本转移？
如果想验证这套模型，不要只记录一轮 Put 的平均耗时。可以把实验分成四段：先写入少量数据让数据库启动；再持续写到多次 MemTable 切换和 Compaction 出现；随后更新同一批 Key；最后停止前台写入，继续观察后台是否仍在工作。
每一段至少同时记录这些信号：
- 应用写入速率与 P50、P99 延迟；
- Immutable MemTable 和 L0 文件数量；
- Flush、Compaction 的读写字节与 Pending Compaction Bytes；
- 设备吞吐、利用率和尾延迟；
- 数据目录占用与当前逻辑有效数据量。
常见现象是：前段写入主要被内存吸收，延迟较平稳；进入稳定写入后，后台 I/O 开始持续出现；更新热点数据后，后续 Compaction 重写量上升；停止 Put 以后，磁盘仍可能忙一段时间，因为后台正在偿还先前积累的工作。
这不是一套性能评分公式，而是一种验证方法。只有把前台延迟、后台队列和设备 I/O 放在同一条时间线上，才能判断测试测到的是缓冲能力、稳定吞吐，还是已经触发背压后的吞吐。不同配置的结果也必须在相同数据量、Key 分布、同步选项和预热状态下比较。
三种放大：LSM 的成本记账方式
只说“Compaction 有成本”还不够。存储系统通常用三种放大来描述这种成本怎样分布。
三种放大不是三个可以同时归零的独立旋钮。
读放大：一次逻辑读取需要做多少额外工作？
应用只执行一次 Get，但 RocksDB 可能要检查内存结构、多个文件范围、Filter、Index 和 Data Block。候选来源越多、重叠越复杂，潜在读取工作通常越多。
“候选数量”适合建立直觉，却不是适用于所有场景的固定公式。Bloom Filter、Block Cache、操作系统缓存、点查与范围扫描都会改变真实 I/O。讨论读放大时，必须说明测量的是文件探测、块读取、设备读取，还是端到端延迟。
写放大：一份逻辑写入最终被物理写了多少？
应用写入 1 GB 数据，存储设备实际接收的写入可能不止 1 GB。记录会进入 WAL、L0 SST，也可能在多个 Compaction 中被重复写入新的 SST。
RocksDB Tuning Guide 常用“存储写入字节 / 数据库逻辑写入字节”表达写放大。不过统计时是否包含 WAL、文件系统与设备内部写放大，要看具体指标口径，不能只比较一个没有上下文的数字。
空间放大：物理占用为什么高于当前有效数据？
假设当前业务上只有 Bob 有效，目录里却可能同时存在 Alice、Bob、Tombstone、旧输入 SST 和正在生成的新输出 SST。物理占用自然可能高于当前有效 Value 的总量。
空间放大关注这种“物理占用 / 逻辑有效数据”的差距。Snapshot、删除模式、Compaction 策略、文件生命周期与压缩算法都会影响它。
为什么三者不能独立优化？
更积极地 Compaction，可能更快减少重叠文件与旧版本，于是读放大和空间放大下降；但读取并重写更多数据，又可能提高写放大并占用更多后台带宽。
反过来，减少 Compaction 可以少写一些数据，却可能让文件和旧版本停留更久，让读放大或空间放大上升。
所以，“把 Compaction 调小能减少写放大”或“把 Compaction 调大能提升读取”都只说了一半。完整问题应该包括：
- 主要是点查还是范围扫描？
- 写入、更新、删除各占多少？
- Value 多大，Key 是否集中在热点范围？
- 内存和磁盘空间预算是多少？
- 设备更怕随机读、持续写，还是尾延迟抖动？
- 性能目标看平均值还是 P99？
离开这些条件，就没有唯一正确的放大平衡点。
LSM 与 B-Tree 应该怎样比较？
现在可以把两条设计路线放在一起，但不要把它做成“谁更先进”的排行榜。
设计路线不同不等于胜负固定，比较必须回到读写比例、设备和具体实现。
| 观察角度 | LSM 的典型做法 | B-Tree 类结构的典型做法 |
|---|---|---|
| 更新 | 新增较新记录，不原地修改旧 SST | 定位并维护目标页中的记录 |
| 持久化组织 | 内存聚合后生成不可变有序文件 | 维护页及树结构，常与 WAL/缓存协作 |
| 后台工作 | Flush 与持续 Compaction | 脏页刷写、Checkpoint、页维护等 |
| 点查 | 合并最新内存状态与文件候选 | 沿树定位目标页 |
| 范围扫描 | 合并多个有序来源 | 沿叶子页顺序扫描 |
| 空间回收 | Compaction 重写时处理旧记录 | 在页式结构与事务规则内复用或整理 |
这张表只描述常见倾向。成熟实现可以相互借鉴很多技巧：B-Tree 可以批量日志和延迟刷页，LSM 可以用 Bloom Filter、Index 和 Cache 缩短读取。NVMe、SSD、对象存储或持久内存也会改变传统成本假设。
比较时更有用的问题不是“LSM 和 B-Tree 谁快”，而是：
- 我的读写比例和查询形态是什么？
- 能接受多少后台写入与空间波动？
- 哪一种尾延迟更重要：写入、点查还是扫描？
- 故障恢复与事务边界要求是什么？
- 团队能否观察并管理对应的后台机制？
结构选择是 workload、实现和运维能力共同作用的结果。
回到 RocksDB：抽象模型分别落在哪里？
把 LSM 的抽象词汇映射到 B01 的 RocksDB 全景图，就很容易了：
| LSM 抽象 | RocksDB 中的对应角色 |
|---|---|
| 内存写入缓冲 | Mutable MemTable |
| 等待落盘的内存状态 | Immutable MemTable |
| 批量生成有序文件 | Flush |
| 磁盘 Sorted Run | SST |
| 新产生、范围可能重叠的文件区 | 默认 Level Style 下的 L0 |
| 后台有序合并与重写 | Compaction |
| 控制候选与读取成本 | Level 组织、Bloom Filter、Index、Block Cache 等 |
RocksDB 并不只是把论文里的 LSM 原样搬进代码。它还加入 WAL、Column Family、Snapshot、不同 Table Format、多种 Compaction Style、缓存、限速、统计与恢复机制，才成为一个可嵌入应用的工程化存储引擎。
也因此，理解 LSM 不能替代理解 RocksDB Write Path。LSM 告诉我们“为什么要这样安排成本”，下一篇才会沿着一次真实 Put 回答：
- 写入怎样进入统一入口；
- WAL 与 MemTable 的先后和职责是什么；
- Sequence Number 在哪里出现；
- Mutable 怎样切换成 Immutable；
- Flush 何时让 L0 SST 对读取可见；
- 后台跟不上时为什么会出现 Stall。
五个常见误区
误区一：LSM 就是只追加，永远不改文件
已有 SST 不会被原地修改，但 Compaction 会读取旧文件并生成新的输出文件。旧输入在新版本安全发布后才被淘汰。对单个 SST 来说是不可变，对整个数据目录来说却一直在创建、替换和删除文件。
误区二：LSM 的所有磁盘 I/O 都是顺序 I/O
内存聚合和批量文件生成有利于形成较大的 I/O，但真实路径仍受 Compaction 并发、文件系统、Direct I/O、设备和 workload 影响。不要把算法直觉直接当成设备层测量结论。
误区三：前台 Put 快，持续写入就一定快
前台只是先把工作交给 WAL、MemTable 与后台队列。持续吞吐由 Flush、Compaction、存储带宽和空间共同约束。短基准测试尤其容易只测到缓冲能力。
误区四：Compaction 只是偶尔做一次磁盘清理
Compaction 是 LSM 长期运行的一部分。没有它，文件、重叠候选、旧版本与 Tombstone 会持续积累。手动 Compaction 也不是适用于所有问题的“立即清空”按钮。
误区五：写放大越低越好
写放大低可能伴随更多文件候选或更高空间滞留。真正的目标是满足业务的吞吐、读延迟、空间和恢复要求，而不是孤立地把一个比率压到最小。
把整篇文章压缩成一条成本链
最后再走一遍 user:42：
Put("user:42", "Bob")不回到旧 SST 原地改 Alice；- Bob 先进入当前写路径，由 MemTable 提供可查询状态，WAL 提供相应恢复依据；
- 一批内存数据通过 Flush 形成新的有序 SST；
- Alice 与 Bob 可能暂时位于不同 Sorted Run；
- 读取按照新旧与可见性规则选择 Bob；
- Compaction 在后台合并有序输入、生成新输出；
- 只有满足可见性与覆盖条件时，旧版本才可被丢弃；
- 整个过程用前台短路径换来了后台 CPU、I/O、临时空间以及三种放大的权衡。
如果只记一句话，可以记成：
LSM Tree 是一种成本转移模型：新增代替原地更新，批量文件代替逐条整理，后台 Merge 承担长期秩序。
下一篇 B03《图解 RocksDB Write Path：WAL、MemTable 与 Flush》，我们不再停留在抽象模型，而是按时间顺序跟踪一次 Put：它什么时候写 WAL，什么时候在 MemTable 可见，什么时候变成 Immutable，又什么时候真正进入 L0 SST。