第二章：LSM-Tree — 写入密集型系统的引擎
1. 定义
LSM-Tree (Log-Structured Merge-Tree) 是一种优化了写入吞吐量的数据结构，被广泛应用于 NoSQL 数据库（如 Cassandra, HBase） and 键值存储引擎（如 RocksDB, LevelDB）。
它的核心设计哲学是：将随机写入转换为顺序写入。与 B+Tree 的就地更新（In-place Update）不同，LSM-Tree 核心采用 Log-Structured 写入方式（数据写入 MemTable，SSTable 一旦写入磁盘即不可变，仅通过 Compaction 重写），这使得它在机械硬盘（HDD）和固态硬盘（SSD）上都能获得极高的写入性能。
2. 技术深度：LSM-Tree 的三层结构
LSM-Tree 并非一棵单一的树，而是由内存和磁盘中的多层结构组成的。
A. MemTable (内存表)
所有写入操作（Insert/Update/Delete）首先被写入 WAL (Write-Ahead Log) 以确保持久性，然后被写入内存中的 MemTable。MemTable 通常是一个有序的数据结构（如 SkipList 或红黑树）。
- 读取：先查 MemTable，如果找到即返回（速度极快）。
B. Immutable MemTable (不可变内存表)
当 MemTable 达到阈值（如 64MB）时，它被冻结为 Immutable MemTable，并由后台线程异步刷新（Flush）到磁盘。
C. SSTable (Sorted String Table - 磁盘表)
刷盘后的数据形成 SSTable。这是一种不可变、有序的磁盘文件。为了加速查询，SSTable 内部通常包含 Bloom Filter 和稀疏索引。
3. 可视化：写入路径与 Compaction (合并)
随着 SSTable 文件越来越多，读取性能会下降（因为需要检查多个文件）。Compaction 是 LSM-Tree 的心脏，它负责合并多个 SSTable，清理已删除（标记为 Tombstone）的数据，并重新排序。
sequenceDiagram
participant Client as 客户端
participant WAL as 预写日志
participant Mem as MemTable
participant Disk as 磁盘 (L0/L1 SSTables)
Client->>WAL: 1. 追加日志 (Append)
Client->>Mem: 2. 写入内存 (Put Key=A)
Mem-->>Client: 返回成功 (Ack)
Note over Mem: MemTable 已满
Mem->>Disk: 3. 异步 Flush -> 生成 L0 SSTable
Note over Disk: 后台 Compaction 触发
Disk->>Disk: 4. 合并 L0 文件 -> 生成 L1 SSTable
Note right of Disk: 丢弃旧版本 Key=A<br/>物理删除 Tombstone<br/>(仅当底层无旧版本时)4. 真实案例：Facebook 的 RocksDB 迁移 (2013-2016)
背景：Facebook 的用户收件箱（User Inbox）和消息系统原本运行在基于 B+Tree 的存储引擎上。 挑战：随着 SSD 的引入，他们观察到 B+Tree 的写放大 (Write Amplification) 在特定负载下会影响 SSD 的寿命，且随机写入无法充分利用 SSD 的并发通道。
技术选型：Facebook 开发并开源了 RocksDB（基于 Google LevelDB 的改进版 LSM-Tree 引擎）。 核心优势：
- 写放大降低：顺序批量写入特性相比随机写密集的 B+Tree 负载，能有效减少对 SSD 的磨损。
- 压缩率：由于 SSTable 是静态有序的，RocksDB 可以应用前缀压缩（Prefix Compression），在特定场景下相比未压缩的 B+Tree 能大幅节省存储空间。
- 灵活策略：通过支持 Universal Compaction 等多种策略，RocksDB 能够在不同的读写负载下进行针对性调优。
影响：RocksDB 现在已成为事实上的行业标准，不仅用于 Facebook 内部，还是 CockroachDB、TiKV 等现代分布式数据库的底层存储引擎。
5. 深度优化与纵深防御
A. 根本修复：Compaction 策略调优
- Leveled Compaction：优化读取性能，适合读多写少。（每层大小是上一层的 10 倍）。
- Tiered/Universal Compaction：优化写入性能并降低写放大，但空间放大与读放大可能显著增加。
- 防御：监控
pending_compaction_bytes。如果积压过多，像 RocksDB 这样的引擎会触发 写停顿 (Write Stall) 以限制写入速度，防止系统过载。
B. 纵深防御：Bloom Filter
- 在每个 SSTable 中嵌入 Bloom Filter。在读取磁盘块之前，先通过布隆过滤器判断 Key 是否可能存在。这能过滤掉绝大多数的无效磁盘 I/O。
C. 空间放大控制
- 对于频繁更新的业务，旧数据版本会占用大量磁盘空间（空间放大）。定期执行 Major Compaction 可以强制回收空间，但这会消耗大量 CPU 和 I/O，需在业务低峰期进行。
6. 参考资料
- The Log-Structured Merge-Tree (LSM-Tree) - Patrick O’Neil (原始论文)
- RocksDB Architecture Guide
- Facebook Engineering: Under the Hood of RocksDB