LSM Tree 存储结构解析：写入密集场景下的数据组织与压缩

前言

LSM Tree，全称 Log-Structured Merge Tree，是一种面向写入密集场景设计的存储结构。它的核心思想不是在磁盘上原地更新数据，而是把随机写尽量转化为顺序追加写，再通过后台 Compaction 将数据逐步整理成有序文件。

这类设计广泛出现在 LevelDB、RocksDB、Cassandra、HBase、Bigtable、TiKV 等系统或存储引擎中。它非常适合日志、监控、时序数据、消息索引、分布式数据库等“写入量大、数据持续增长”的场景。

如果用一句话概括 LSM Tree：

LSM Tree 用顺序写提升写入吞吐，再用后台合并换取读取性能和空间效率。

LSM Tree 要解决什么问题？

传统 B+ 树适合读写比较均衡、范围查询较多的场景。它的数据组织方式是树结构，数据页在磁盘上相对稳定，查询路径清晰。但是当写入非常频繁时，B+ 树可能遇到几个问题：

1. 写入可能落在不同的数据页上，形成随机写；
2. 页分裂、页合并会带来额外维护成本；
3. 在机械磁盘或远端存储场景下，随机 I/O 成本更高；
4. 高并发写入下，局部热点页可能成为瓶颈。

LSM Tree 的思路是：

1. 新写入先进入内存；
2. 同时追加写 WAL / CommitLog 保证持久性；
3. 内存数据达到阈值后批量刷盘为有序不可变文件；
4. 后台不断合并这些文件，清理旧版本和删除标记。

也就是说，LSM Tree 并不是让写入成本消失，而是把大量小随机写转换成更容易被磁盘和 SSD 处理的顺序写、批量写和后台合并。

核心组成

一个典型 LSM Tree 存储引擎通常包含以下组件。

1. WAL / CommitLog

WAL，全称 Write-Ahead Log，也叫 CommitLog。它的作用是保证写入持久性。

当一条数据写入时，系统通常会先把操作追加到 WAL 中，然后再写入内存结构。这样即使进程崩溃，也可以通过 WAL 回放恢复尚未刷盘的数据。

需要注意：

WAL 通常是追加写日志，不是“有序表”。真正按 Key 有序组织数据的是 MemTable 和 SSTable。

2. MemTable

MemTable 是内存中的有序数据结构，常见实现可以是跳表、平衡树或其他有序结构。

它的作用是承接最新写入，并支持快速查询。因为 MemTable 在内存中，所以写入延迟低；又因为它按 Key 有序，所以后续刷盘时可以直接生成有序文件。

3. Immutable MemTable

当 MemTable 达到一定大小后，它会被冻结为 Immutable MemTable。新的写入会进入新的 MemTable，旧的 Immutable MemTable 则等待后台线程刷盘。

这个设计可以避免刷盘过程阻塞前台写入。

4. SSTable

SSTable，全称 Sorted String Table，是磁盘上的有序不可变文件。

它有几个关键特征：

• 按 Key 有序；
• 文件一旦生成就不再原地修改；
• 更新同一个 Key 时通常生成新版本；
• 删除数据时通常写入 Tombstone 删除标记；
• 后续通过 Compaction 清理旧版本和删除标记。

SSTable 通常还会配套索引块、数据块、元信息和过滤器，用于加速读取。

5. Bloom Filter

LSM Tree 的一个读取难点是：同一个 Key 可能存在于 MemTable、Immutable MemTable 和多个 SSTable 中。

为了减少无效磁盘读取，存储引擎通常会为 SSTable 构建 Bloom Filter。读取某个 Key 时，可以先通过 Bloom Filter 判断“这个 SSTable 是否可能包含该 Key”。

Bloom Filter 的判断结果有两个特点：

• 如果判断不存在，通常可以直接跳过该 SSTable；
• 如果判断可能存在，还需要继续查索引和数据块确认。

它不能完全消除读放大，但可以显著降低不必要的文件访问。

6. Compaction

Compaction 是 LSM Tree 的核心后台任务。它会把多个 SSTable 合并成新的 SSTable，并在合并过程中：

• 保留同一个 Key 的最新版本；
• 清理被覆盖的旧版本；
• 清理过期的 Tombstone；
• 减少 SSTable 数量；
• 控制层级大小和数据重叠范围。

Compaction 让 LSM Tree 获得更好的读取性能和空间效率，但它也带来了额外的磁盘写入和后台资源消耗。

写入路径

典型写入路径如下：

写请求
  ↓
追加写 WAL / CommitLog
  ↓
写入 MemTable
  ↓
返回写入成功
  ↓
MemTable 达到阈值
  ↓
转为 Immutable MemTable
  ↓
Flush 成 SSTable
  ↓
后台 Compaction 合并到更低层级

这个流程有两个关键点。

第一，前台写入路径非常短：追加 WAL + 写内存结构。追加写通常比随机写更友好，因此 LSM Tree 可以获得较高写入吞吐。

第二，很多成本被延后到了后台：排序、合并、清理旧版本、整理层级都由 Flush 和 Compaction 完成。也就是说，LSM Tree 的高写入性能不是没有代价，而是把代价转换成后台维护成本。

读取路径

典型读取路径如下：

读请求
  ↓
查询 MemTable
  ↓
查询 Immutable MemTable
  ↓
按层级查询 SSTable
  ↓
Bloom Filter 判断是否可能存在
  ↓
Index Block 定位数据块
  ↓
读取 Data Block
  ↓
根据版本号 / 时间戳 / Tombstone 判断最新结果

读取时，系统通常会优先查最新数据，因为最新数据更可能在 MemTable 或高层级 SSTable 中。

如果同一个 Key 在多个 SSTable 中出现，存储引擎需要根据 sequence number、timestamp、MVCC 版本或类似机制判断哪一个版本最新。

因此，LSM Tree 中“旧版本暂时存在”并不意味着查询结果会不准确。它真正带来的问题是：

• 查询可能需要检查更多文件；
• 空间中可能暂时保存多个版本；
• 后台需要 Compaction 来清理历史数据。

更新与删除：为什么需要 Tombstone？

在 LSM Tree 中，SSTable 是不可变文件。既然文件不能原地修改，那么更新和删除就不能像普通数据页那样直接覆盖。

更新一个 Key 时，系统通常会写入一个新版本：

put user:1 = Alice
put user:1 = Bob

读取时返回最新版本 Bob。旧版本 Alice 会在后续 Compaction 中被清理。

删除一个 Key 时，系统通常不会马上从所有 SSTable 中删除数据，而是写入一个 Tombstone：

delete user:1

读取时如果遇到最新版本是 Tombstone，就认为该 Key 已被删除。等到 Compaction 确认更老层级中的旧值都可以安全丢弃后，再真正释放空间。

这也是为什么删除很多数据后，磁盘空间不一定立即下降：删除只是先写入标记，真正回收空间依赖后续 Compaction。

Compaction：LSM Tree 的核心成本

Compaction 可以理解为 LSM Tree 的“垃圾回收 + 重新排序 + 层级整理”。它决定了写入吞吐、读取延迟和磁盘空间之间的平衡。

常见 Compaction 策略包括以下几类。

策略	特点	适用场景
Size-Tiered / Tiered Compaction	将多个大小接近的 SSTable 合并	写入吞吐优先，接受一定读放大
Leveled Compaction	控制每层大小和 Key 范围重叠	点查、空间效率和稳定读取优先
Universal Compaction	RocksDB 中常见，偏向按文件序列整体合并	降低部分场景下的写放大
FIFO Compaction	按文件时间或顺序淘汰旧文件	日志、缓存、时序等有生命周期的数据
Time-Window Compaction	按时间窗口组织和合并 SSTable	时间序列、事件日志、Cassandra 常见场景

不同策略没有绝对好坏，只有适不适合当前负载。

如果更关注写入吞吐，可以选择更偏 Tiered 的策略，让后台合并不要过于频繁。如果更关注查询稳定性和空间放大，可以选择更偏 Leveled 的策略，但这通常会带来更高写放大。

三种放大问题

理解 LSM Tree，必须理解三个 Amplification。

1. Write Amplification：写放大

一条数据写入后，可能不只写一次磁盘。

它可能经历：

1. 写 WAL；
2. Flush 成 SSTable；
3. 从 L0 合并到 L1；
4. 从 L1 合并到 L2；
5. 继续合并到更低层级。

因此，用户写入 1 GB 数据，底层实际写入磁盘的数据量可能大于 1 GB。这就是写放大。

写放大会影响：

• SSD 寿命；
• 后台 I/O；
• 写入延迟抖动；
• Compaction backlog。

2. Read Amplification：读放大

读取一个 Key 时，可能需要检查多个结构：

• MemTable；
• Immutable MemTable；
• 多个 L0 SSTable；
• 多个层级中的候选 SSTable。

虽然 Bloom Filter、Block Cache、索引块可以降低读取成本，但当 SSTable 数量过多或 Compaction 跟不上时，读放大会明显增加。

3. Space Amplification：空间放大

由于旧版本、重复 Key、Tombstone、正在合并的新旧文件会同时存在，LSM Tree 的实际磁盘占用可能大于逻辑数据量。

Compaction 可以降低空间放大，但 Compaction 本身又会带来写放大和后台 I/O。

所以 LSM Tree 的调优本质上是在三者之间做权衡：

写入吞吐
  ↔ 写放大
  ↔ 读放大
  ↔ 空间放大
  ↔ 后台 Compaction 资源

LSM Tree 与 B+ 树对比

维度	B+ 树	LSM Tree
写入方式	原地更新为主，可能随机写	追加写、批量刷盘、后台合并
读取路径	树高稳定，路径相对确定	可能查询多个层级和 SSTable
范围查询	天然适合范围扫描	依赖 SSTable 有序性和合并状态
写入吞吐	中等，受随机写影响	通常更适合高写入吞吐
后台任务	相对少	Compaction 是核心后台任务
空间回收	页级管理和碎片整理	依赖 Compaction 清理旧版本和 Tombstone
典型系统	MySQL InnoDB 等	LevelDB、RocksDB、Cassandra、HBase、TiKV 等

如果你的核心场景是高频写入、追加写、日志型数据、时序数据或分布式 KV 存储，LSM Tree 往往更合适。

如果你的核心场景是复杂事务、强一致读写、频繁范围查询、读写比较均衡，B+ 树仍然是非常成熟的选择。

关于 B+ 树和 InnoDB 索引机制，可以参考我之前整理的文章：B+树原理与 MySQL InnoDB 索引机制解析。

适用场景

LSM Tree 适合以下场景：

1. 写入密集型数据库：例如分布式 KV、宽列表数据库、日志型数据库；
2. 日志和事件存储：数据持续追加，查询多按时间或 Key 过滤；
3. 时序数据：数据天然按时间增长，适合批量写入和按窗口合并；
4. 缓存或嵌入式 KV：例如基于 RocksDB / LevelDB 的本地状态存储；
5. 分布式存储引擎：例如 HBase、Cassandra、TiKV 这类需要横向扩展的系统。

不适用场景

LSM Tree 并不是所有场景的最优解。以下场景需要谨慎：

1. 极端读多写少：如果数据写入少、查询多，B+ 树或专门的读优化结构可能更稳定；
2. 大量随机点查且缓存命中率低：如果 Bloom Filter 和 Block Cache 效果不好，读放大会明显；
3. 磁盘空间非常紧张：Compaction 前可能存在较高空间放大；
4. 后台 I/O 资源有限：Compaction 可能和前台读写争抢资源；
5. 删除非常频繁：大量 Tombstone 会拖慢查询并推迟空间回收。

常见系统实现

LevelDB

LevelDB 是 Google 开源的嵌入式 Key-Value 存储。它使用 Log、MemTable、SSTable 和分层 Compaction，是理解 LSM Tree 工程实现的经典项目。

RocksDB

RocksDB 源自 LevelDB，面向更复杂的生产环境做了大量优化，支持多种 Compaction 策略、Column Family、Block Cache、Bloom Filter、事务等能力。

Cassandra

Cassandra 使用 CommitLog、MemTable 和 SSTable 组织数据，并提供多种 Compaction 策略。它的写入路径非常典型：先写 CommitLog，再写 MemTable，随后 Flush 成 SSTable。

HBase / Bigtable

HBase 和 Bigtable 代表了面向大规模分布式存储的 LSM 类设计。它们通常通过内存写入缓存、不可变磁盘文件和后台合并来支撑大规模写入。

TiKV / Pebble 等

TiKV 使用 RocksDB 作为底层存储引擎，适合结合分布式事务、Raft 副本和 MVCC 进一步理解 LSM Tree 在分布式数据库中的位置。关于 TiDB / TiKV 的整体架构，可以参考：PCTA 学习笔记：TiDB 数据库核心原理与架构。

调优思路

LSM Tree 的调优不能只看单个参数，而要结合负载画像。

写入压力大时

重点关注：

• MemTable 大小是否合适；
• WAL 同步策略是否符合可靠性要求；
• Flush 是否频繁；
• Compaction 是否跟不上；
• 是否出现写入限速或停顿；
• SSD 写放大是否过高。

如果 Compaction 跟不上，系统可能出现：

• L0 文件数量增加；
• 读放大上升；
• 磁盘空间增长；
• 写入延迟抖动；
• 后台 I/O 长期处于高位。

读取压力大时

重点关注：

• Bloom Filter 是否开启且配置合理；
• Block Cache 命中率；
• SSTable 数量；
• L0 文件数量；
• Compaction 策略是否偏向读取优化；
• 热点 Key 是否被缓存命中。

删除或 TTL 数据多时

重点关注：

• Tombstone 数量；
• Tombstone 保留时间；
• Compaction 是否能及时清理旧版本；
• 是否适合使用 Time-Window 或 FIFO 类策略。

总结

LSM Tree 的价值在于，它把写入路径做得非常轻：追加 WAL、写入 MemTable，然后快速返回。真正复杂的排序、合并、清理旧版本和空间回收，都交给后台 Compaction 完成。

它的优势是：

• 写入吞吐高；
• 顺序写友好；
• 适合大规模写入；
• 适合分布式存储和日志型数据；
• 能通过 Compaction 持续整理数据。

它的代价是：

• 读取路径更复杂；
• 存在读放大、写放大、空间放大；
• Compaction 会消耗后台 I/O；
• 删除和更新需要依赖 Tombstone 与后续清理。

因此，LSM Tree 不是简单地“比 B+ 树更快”，而是更适合写入密集、追加写友好、可接受后台合并成本的场景。理解 WAL、MemTable、SSTable、Bloom Filter、Compaction 和三种放大问题，才算真正理解 LSM Tree 的工程价值。

参考资料

• The Log-Structured Merge-Tree 原始论文
• LevelDB Implementation Notes
• RocksDB Wiki：Compaction
• RocksDB Wiki：Leveled Compaction
• Apache Cassandra：Storage engine