LSM Tree 是什么？为什么很多分布式存储使用 LSM？

简化版

LSM Tree 是一种面向写优化的存储结构，写入先进入内存 MemTable，再顺序刷盘成 SSTable，后台通过 Compaction 合并文件。它把随机写转成顺序写，适合高写入吞吐的分布式 KV 和数据库。

详细版

LSM 的基本流程：

写入先追加 WAL，保证崩溃恢复。
写入内存 MemTable。
MemTable 达到阈值后刷盘为不可变 SSTable。
查询时先查 MemTable，再查多个 SSTable。
后台 Compaction 合并 SSTable，清理旧版本和删除标记。

优点：

写入吞吐高，磁盘顺序写友好。
适合 SSD 和大规模写入场景。
文件不可变，便于复制和恢复。

缺点：

读可能要查多个层级。
Compaction 带来写放大和性能抖动。
删除通常用 Tombstone，真正清理要等 Compaction。

完整版教学

一、LSM 为什么适合写多场景

传统 B+ 树更新数据时，可能要在磁盘上随机修改页面。随机写对磁盘不友好，尤其在写入量非常大时，会成为瓶颈。

LSM 的思路是：先不急着在磁盘原地修改，而是把写入追加下来，尽量变成顺序写。

顺序写对磁盘和 SSD 都更友好，也更容易批量处理。

二、一次写入发生了什么

写入通常先进入 WAL：

append WAL -> write MemTable -> return success

WAL 是为了崩溃恢复。即使机器写入 MemTable 后宕机，重启时也能从 WAL 重放恢复。

MemTable 是内存中的有序结构，例如跳表或红黑树。它满了以后会被冻结并刷到磁盘，形成 SSTable。

三、SSTable 为什么不可变

SSTable 一旦写入磁盘就不再原地修改。新的更新会写到新的 MemTable 和新的 SSTable。

例如 keyA 原来是 1，后来更新成 2，磁盘上可能同时存在旧版本和新版本。读取时按新到旧顺序查，返回最新版本。

不可变文件的好处是写入简单、便于并发读取、便于复制和校验。坏处是旧版本会堆积，需要后台合并。

四、Compaction 做什么

Compaction 会把多个 SSTable 合并成更大的、有序的新 SSTable，同时删除过期版本和 Tombstone。

它解决两个问题：

文件太多会拖慢查询。
旧版本和删除标记占空间。

但 Compaction 会消耗磁盘 I/O 和 CPU，也会产生写放大。系统如果 Compaction 跟不上写入速度，读写延迟会明显抖动。

五、LSM 的读优化手段

因为数据可能分散在多个 SSTable，LSM 读取需要优化。

常见手段包括：

手段	作用
Bloom Filter	快速判断某个 SSTable 是否可能有 key
Block Cache	缓存热点数据块
索引块	快速定位 key 所在范围
分层 Compaction	控制每层文件数量

没有这些优化，LSM 写得快，但读会很痛苦。

六、常见误区与追问

这道题要紧扣「LSM Tree 存储结构」本身回答，不能把它混成泛泛的分布式存储套话。面试官通常会追问“写入怎么确认、失败怎么补、旧数据怎么防、成本在哪里”，所以回答要覆盖副本、分片、元数据、路由、复制协议、恢复迁移、热点和一致性模型。

回答层次	要讲清的内容	容易漏掉的边界
核心结论	LSM Tree 把随机写变成顺序写，数据先写 WAL 和 MemTable，再刷成 SSTable，并通过 Compaction 合并清理	不要停在名词解释
流程机制	写 WAL 保证恢复 -> 更新 MemTable -> 刷盘生成 SSTable -> 读时查内存和多层文件 -> Compaction 合并去重 -> 删除过期版本	要说清触发点、状态变化、确认点和失败兜底
工程取舍	写入 1000 条记录先进入内存 MemTable，达到阈值后顺序刷盘成 SSTable，后台再合并层级文件	分布式存储用复杂的复制、分片和恢复机制换容量、吞吐和可用性，但会引入一致性、扩容和运维成本

LSM Tree 存储结构 面试拆解：
1. 写 WAL 保证恢复
2. 更新 MemTable
3. 刷盘生成 SSTable
4. 读时查内存和多层文件
5. Compaction 合并去重
6. 删除过期版本

记忆钩子：先给结论，再拆流程，再讲数字例子和失败边界；回答「LSM Tree 存储结构」时要围绕题目问法收束，不要把相邻概念堆成一段没有重点的名词清单。

误区：LSM 只有写入优势没有代价。 读放大、写放大和空间放大是 LSM 的核心代价。
误区：Compaction 可有可无。 不合并会导致文件越来越多、旧版本堆积和读性能下降。
误区：删除数据会立即物理消失。 通常先写 tombstone，等 Compaction 后才真正清理。
追问：为什么适合写多读少？ 它把随机写转顺序写，提升写吞吐。
追问：Bloom Filter 有什么用？ 快速判断某个 SSTable 不包含 key，减少无效磁盘查找。
追问：LSM 常见于哪些系统？ RocksDB、LevelDB、HBase、Cassandra 等写密集存储。

七、加强记忆

LSM Tree 的核心是“写内存、顺序刷盘、后台合并”。它用 WAL 保安全，用 MemTable 接写入，用 SSTable 存磁盘，用 Compaction 清理旧数据；写吞吐高，但要付出读放大、写放大和 Compaction 抖动的代价。

简化版

详细版