LSM-Tree 与 WAL：写放大与崩溃恢复

LSM-Tree（Log-Structured Merge-Tree）是写密集场景的事实标准：RocksDB、LevelDB、HBase、Cassandra 都在用它。它的核心思想只有一句话：把随机写变成顺序写。

写入路径：内存先行

写请求
  → 1. 追加到 WAL（顺序写磁盘，持久化）
  → 2. 写入 MemTable（内存跳表，可查询）
  → 3. MemTable 满 → 冻结为 Immutable MemTable
  → 4. 后台刷盘 → 生成 SSTable（不可变文件）
  → 5. 后台 Compaction 合并 SSTable

用户写请求只碰两个东西：WAL 的顺序追加和内存表。这就是 LSM 写快的全部原因。

为什么需要 WAL

MemTable 在内存里，崩溃就没了。WAL 是写给自己的「后悔药」：每次写先追加日志，崩溃后重放日志即可重建内存状态。顺序追加的性能开销很小，换来的是：

持久性：已确认（ACK）的写入不会丢
批量：一组写入可以合并刷一次 WAL

⚠️ 注意： 关掉 WAL（如 RocksDB 的 disableWAL）能再快一截，但换来的是「机器断电 = 丢最近写入」。线上绝不建议。

读路径：层层查找

LSM 没有「就地更新」，同一个键可能散落在多个层级：

读 key
  → 查 MemTable → Immutable → L0 SSTable → L1 → L2 → ...
  （每一层都可能命中，都要查）

为了加速，每层内部维护布隆过滤器（Bloom Filter）：大概率知道「这个键不在」，把无效的磁盘查找直接挡掉。

Compaction：LSM 的宿命

数据不断累积，层与层之间重叠越来越多，读放大越来越严重。后台线程周期性做 Compaction——合并重叠的 SSTable，生成新的、更有序的文件，删掉旧版本：

Compaction 前:  L1: [a,b] [c,d]   L2: [b,c] [d,e]
Compaction 后:  L2: [a,b,c,d,e]（旧文件删除）

代价是写放大：一条写下去的数据，可能在多次 Compaction 中被反复读改写。写放大系数（实际写盘量 / 逻辑写入量）是 LSM 调优的核心指标。

放大类型	含义	影响
写放大	实际写盘 / 逻辑写	磁盘寿命与吞吐
读放大	实际读盘 / 逻辑读	点查延迟
空间放大	占用空间 / 数据大小	磁盘成本

三者互相拉扯：Compaction 越勤，读放大越小、空间放大越小，但写放大越大。

与 B+ 树的取舍

维度	B+ 树	LSM-Tree
写路径	随机页写（读改写）	顺序追加
写吞吐	中	高
点查延迟	低（1~2 次 I/O）	中（多层+布隆过滤）
范围查询	优	中
最坏情况	稳定	依赖 Compaction 策略

一句话：写密集选 LSM，读密集选 B+ 树。混合负载则用分区（如 TiDB 的分区级选择）或双引擎（MySQL + Redis 缓存）。

小结

LSM-Tree 的设计哲学是「把昂贵的随机写延迟到后台批量解决」：前台只做顺序追加，后台慢慢整理。它用写放大换来了写吞吐，用布隆过滤器修补读路径，用 WAL 守住持久性底线——三个组件的配合，值得每个系统设计者反复琢磨。