LSM-Tree 存储引擎原理与工程实践：从 RocksDB 到 TiKV 的分布式优化

引言：为什么数据库选择 LSM-Tree

LSM-Tree（Log-Structured Merge-Tree）是由 O'Neil 等人在 1996 年提出的存储结构。与传统 B+ 树不同，它将随机写顺序化为追加写，天然适合写密集工作负载。如今，LSM-Tree 已经成为现代分布式数据库（TiKV、CockroachDB、ScyllaDB）和嵌入式存储引擎（RocksDB、LevelDB）的首选结构。

1. 核心数据结构

LSM-Tree 分为内存层和磁盘层：

• MemTable：内存中的有序数据结构（通常用 SkipList，支持 O(logN) 读写和范围查询）
• Immutable MemTable：写满后冻结的只读 MemTable，正在被 Flush 到磁盘
• SSTable (Sorted String Table)：磁盘上的不可变有序文件，包含数据块、索引块和 Bloom Filter

| Level |  大小限制    | SST 数量 |
|-------|-------------|---------|
| L0    | 无限制      | 4-10    |  ← 未合并，范围可能重叠
| L1    | 256 MB      | 10      |  ← 内部有序，范围不重叠
| L2    | 2.5 GB      | 100     |
| L3    | 25 GB       | 1000    |
| Ln    | 10^(n-1)×256MB | 10^(n-2)×10 |
（每级大小约为上一级的 10 倍 — 称为 size ratio）

2. Compaction 策略

Size-Tiered Compaction (RocksDB Leveled)：

• 当某一层的 SST 数量达到阈值，多个 SST 合并为一个更大的 SST 写入下一层
优点：写放大低（摊销）
• 缺点：读放大高（可能有多个重叠 SST）、空间放大高（同一 key 多个副本）

Leveled Compaction（经典层级）：

• L0→L1：L0 中每个 SST 与 L1 重叠范围合并到 L2

• Lv→Lv+1：每个 SST 只与下一层中范围重叠的部分合并
• 优点：空间放大低（只有一个副本）、读放大低

• 缺点：写放大高（每次 Compaction 可能重写大量数据）

RocksDB Tiered-Leveled：L0 用 Tiered（写友好），下层用 Leveled（读友好），实现读写折中。

3. 三大放大问题

定义：1GB 用户数据引起的实际磁盘 IO 量。

Bloom Filter 的实际效果：每个 SST 维护一个 BF，point lookup 可跳过不含该 key 的 SST。10 bits/key、7 hash functions → 约 1% 误判率，可将读放大大幅降低。

4. WAL 与崩溃恢复

每次写入操作先追加到 WAL（Write-Ahead Log），再写入 MemTable。崩溃恢复重放 WAL 重建 MemTable。

优化：parallel WAL：RocksDB 支持多个写线程各自维护 WAL，减少锁竞争。

5. RocksDB 工程优化

• Block Cache：缓存索引和数据块，减少磁盘 IO（LRU 或 Clock 算法）
• Rate Limiter：限制 Compaction 的带宽占用，避免影响前台读写
• Subcompaction：大 Compaction 拆分为多线程并行执行
• Dynamic Level Sizing：根据实际写入比例自动调整各级大小
• Remote Compaction：将 Compaction 卸载到独立服务（RocksDB-Cloud）

6. 分布式 LSM-Tree（TiKV/Titan）

TiKV 基于 RocksDB 改进的几点：

• Titan：将大 value 从 SST 分离到独立文件，当 value > 1KB 时写入Blob文件，大幅降低写放大
• Raft-based 复制：每个 Raft Group 对应一个 LSM-Tree 实例，利用 Raft 协议保证强一致
• Separate CF：KV 数据分别放在不同 Column Family，GC 策略独立配置

总结

LSM-Tree 的成功在于其工程可调性：开发者可以在写放大、读放大、空间放大三者之间根据工作负载特征做精确取舍。从 RocksDB 的单机优化到 TiKV 的分布式演进，LSM-Tree 始终在"吞吐量优先"的 OLTP 存储引擎领域占据主导地位。随着新型存储介质（Optane PMem, ZNS SSD）的成熟，LSM-Tree 也将在存储硬件变革中找到新的优化维度。