LSM Tree（Log-Structured Merge Tree）是现代高写入吞吐存储引擎的核心数据结构，通过将随机写转换为顺序写，大幅提升写入性能。RocksDB、LevelDB、TiKV、Cassandra、HBase 均以 LSM Tree 为底层引擎。
相关文章：Bloom Filter · B+ Tree · SSTable
目录
| 章节 | 说明 |
|---|---|
| 核心思想 | 随机写 → 顺序写的转换原理 |
| 整体结构 | MemTable / SSTable / 多层 Level |
| 写入路径 | WAL → MemTable → Flush → Compaction |
| 读取路径 | 多层查找与 Bloom Filter 优化 |
| Compaction 策略 | Size-Tiered vs Leveled |
| 三种放大 | 读放大、写放大、空间放大 |
| 异常场景 | 崩溃恢复、读性能退化、Compaction 积压 |
| 与 B+ Tree 对比 | 适用场景的根本差异 |
核心思想
问题：磁盘随机写极慢（HDD ~100 IOPS，SSD ~10万 IOPS），而顺序写快 10~100 倍。
B+ Tree 的写入问题：
更新 key=X → 找到对应磁盘页 → 原地修改 → 写回
→ 随机 I/O，受限于磁头寻道时间
LSM Tree 的解法：
所有写入 → 追加到内存缓冲区（MemTable）
内存满了 → 顺序写一个不可变文件（SSTable）到磁盘
→ 全部是顺序写，磁盘友好
代价：写入变快，读取变慢（数据分散在多个文件），需要 Compaction 控制文件数量。
整体结构
内存层：
MemTable（可写） ← 当前接受写入的内存表（红黑树/跳表，有序）
Immutable MemTable ← MemTable 满后转为不可变，等待 Flush
磁盘层（多级 SSTable）：
L0：Flush 直接写入，文件间 key range 可以重叠（最新），通常 4~8 个文件
L1：约 10MB，文件间 key range 不重叠
L2：约 100MB，文件间 key range 不重叠
L3：约 1GB
...（每层大小 = 上层 × 放大因子，通常 10）
WAL（Write-Ahead Log）：
在 MemTable 写入前先追加到 WAL
崩溃恢复时用 WAL 重建 MemTable
写入路径
Client 写入 key=X, value=V：
① 追加到 WAL（顺序写磁盘，持久化保证）
② 写入 MemTable（内存红黑树/跳表，有序插入，O(log N)）
③ 返回客户端成功 ← 写入完成，极快
后台流程：
④ MemTable 达到阈值（如 64MB）
→ 转为 Immutable MemTable，创建新 MemTable
⑤ 后台线程将 Immutable MemTable Flush 到磁盘 L0（顺序写一个 SSTable 文件）
→ 删除对应的 WAL 段
⑥ L0 文件数超过阈值 → 触发 Compaction
→ 合并 L0 + L1 文件，生成新的 L1 SSTable
→ 依此类推，逐级向下 Compaction
写入性能关键：步骤①②完成即可返回，③④⑤⑥全在后台异步执行，不阻塞写入。
读取路径
Client 读取 key=X：
① 查 MemTable（内存，O(log N)）→ 找到则返回
② 查 Immutable MemTable（可能有多个）
③ 从 L0 最新文件开始逐个查找（L0 文件间可能重叠，需全查）
④ 查 L1 → 二分定位包含 key 的文件 → 读取
⑤ 查 L2 → ... → Ln
最坏情况：需要查每一层，读放大严重
优化：每个 SSTable 配备 Bloom Filter
if BloomFilter(key) == 可能存在:
实际读取 SSTable 文件
else:
直接跳过这个文件（减少 90%+ 的无效读取）
读取性能关键：Bloom Filter 让大多数"不存在的 key"查询只需内存操作，无需磁盘 I/O。
Compaction 策略
Size-Tiered（大小分层，Cassandra 默认）
思想：相同大小的 SSTable 积累到 N 个后合并成一个更大的文件
L0: [1MB][1MB][1MB][1MB] → 合并 → [4MB]
L1: [4MB][4MB][4MB][4MB] → 合并 → [16MB]
L2: [16MB][16MB]...
优点：写放大低（每次 Compaction 合并的文件少）
缺点：
空间放大高（同一 key 的多个版本分散在不同层）
读放大高（同一层的多个文件都可能包含目标 key）
适合：写多读少，时序数据
Leveled（分层压缩，LevelDB/RocksDB 默认）
思想：每层内 SSTable 的 key range 不重叠，层间大小有固定比例
L1: [a-m][n-z] （文件间无重叠）
L2: [a-d][e-h][i-l][m-p][q-t][u-z]
Compaction 时：
选 L1 的一个文件 [a-m]
找 L2 中与其 key range 重叠的所有文件
合并 → 写回 L2（保持无重叠）
优点：
读放大低（每层最多一个文件包含目标 key）
空间放大低（旧版本快速被清理）
缺点：写放大高（一个文件可能触发多层 Compaction）
适合：读写均衡，通用场景（RocksDB/TiKV 默认）
三种放大
存储引擎设计的核心三角矛盾，无法同时最小化：
| 放大类型 | 定义 | LSM Tree | B+ Tree |
|---|---|---|---|
| 写放大（WA） | 实际写磁盘量 / 用户写入量 | 中~高（Compaction 反复写） | 低（原地修改） |
| 读放大（RA） | 实际读磁盘量 / 用户读取量 | 中（多层查找） | 低（树高固定 3~4） |
| 空间放大（SA） | 磁盘占用 / 实际数据量 | 中（旧版本未及时清理） | 低（原地更新） |
RocksDB Leveled Compaction 典型数值：
写放大：10~30×（每条数据平均被重写 10~30 次）
读放大：< 10×（Bloom Filter 后接近 1×）
空间放大：1.1~1.3×
异常场景
崩溃恢复
场景：MemTable 有数据，Flush 前进程崩溃
恢复流程：
重启 → 读取 WAL → 重放 WAL 中的写操作 → 重建 MemTable
→ 继续正常服务
WAL 必须在 MemTable 写入前完成（先写 WAL 再写内存）
否则崩溃后数据无法恢复
读性能退化（L0 文件堆积）
场景：写入速度 > Compaction 速度，L0 文件越来越多
影响：
L0 文件间 key range 重叠，每次读需扫描所有 L0 文件
读放大急剧增大，延迟飙升
解决：
L0 文件数超过软限制（如 20）→ 限速写入（stall writes）
L0 文件数超过硬限制（如 36）→ 停止写入（stop writes）
→ 等 Compaction 追上后恢复
RocksDB 配置：
level0_slowdown_writes_trigger = 20
level0_stop_writes_trigger = 36
Compaction 写入风暴
场景：大量数据写入后触发多层 Compaction，磁盘 I/O 打满
影响：
Compaction 和用户读写竞争磁盘带宽
读写延迟 P99 飙升
缓解：
限制 Compaction 的 I/O 带宽（RocksDB rate_limiter）
使用独立磁盘做 Compaction I/O
调大 L1 大小，减少 Compaction 频率
与 B+ Tree 对比
| 维度 | LSM Tree | B+ Tree |
|---|---|---|
| 写入 | ✅ 极快（顺序写） | ⚠️ 慢（随机写） |
| 点查 | ⚠️ 较慢（多层查找） | ✅ 快（树高固定） |
| 范围查询 | ⚠️ 需要合并多层迭代器 | ✅ 叶节点链表，天然有序 |
| 空间 | ⚠️ 旧版本延迟清理 | ✅ 原地更新 |
| 崩溃恢复 | WAL 重放 | WAL + redo log |
| 典型系统 | RocksDB、Cassandra、TiKV | MySQL InnoDB、PostgreSQL |
选型原则：
- 写多读少、时序数据、KV 存储 → LSM Tree
- 读写均衡、强一致事务、范围扫描多 → B+ Tree
参考资料
- O'Neil, P. et al. (1996). The Log-Structured Merge-Tree
- RocksDB Wiki: https://github.com/facebook/rocksdb/wiki
- 《Designing Data-Intensive Applications》Ch.3 — Storage and Retrieval
评论 (0)
发表评论