第5章：LSM-Tree 深度
元数据卡
维度 值 难度 （进阶） 前置 第4章 B+树与存储引擎 关键词 LSM-Tree、MemTable、SSTable、Compaction、写放大、读放大、Bloom Filter、RocksDB 代码语言 SQL / 伪代码 / C++
你的进度
老陈带你穿过地下室，推开另一扇门——里面叮叮当当，几个工人在流水线上不断把散落的纸片装订成册、合并成厚卷。'这叫 LSM 工坊。不追求每次写入都整整齐齐排进架子，而是先堆在台面上，等空闲了再合并整理。写入快，但读的时候得多翻几本。'
破局 · 溯源
写入的瓶颈——B+树的随机写问题
B+树每插入一行数据，都要定位到正确的叶节点页。如果 Buffer Pool 没命中，就要从磁盘读这个页，修改后再写回去。
这看起来没什么——一次 I/O 而已。但问题在于：
- 插入顺序和物理位置无关。按时间戳插入的数据，可能分散在各个索引页。
- 页分裂更糟糕。一个满的页分裂成两个半满的页，两个新页的写入位置也是随机的。
- 二级索引的灾难。每写一行数据，所有索引都要更新。
对于每秒 10 万次写入的负载，B+树存储引擎的随机 I/O 就变成了瓶颈。
LSM-Tree 的核心理念——把随机写转顺序写
你站在工坊门口，看着工人们把散落在工作台上的纸片随手夹进文件夹就丢到一边，而不是像地下室的 B+树档案员那样一页一页往柜子里插。
'看出来区别了？'老陈问。'B+树每次写入都要找到正确的抽屉位置插进去——随机 I/O。我们这里先把所有东西扔到桌上（MemTable），等桌子堆满了，一起打包搬进仓库。'
LSM-Tree 的思路：不把数据立即写入有结构的 B+树。先把所有写操作追加到一个内存中的有序结构（MemTable），当 MemTable 满了，就一次性刷成磁盘上的不可变文件（SSTable）。
写入请求
满了
MemTable Immutable MemTable
(内存中的跳表/B树) (只读，准备落盘)
插入 O(log n)
查询 O(log n)
SSTable 文件 (Level 0)
(排序的、不可变的
键值对文件)三个关键特性：
- 所有写入都是顺序追加——先写 WAL（预写日志），再写 MemTable，最后定期刷新成 SSTable。没有随机 I/O。
- SSTable 一旦生成就不变了——没有页分裂、没有原地更新。这简化了并发控制和崩溃恢复。
- 读取需要合并多个文件——因为数据可能分散在 MemTable、Immutable MemTable 和多个 SSTable 中。这是 LSM-Tree 的主要代价。
MemTable → Immutable MemTable → SSTable 的写入管道
来看一个具体的写入过程：
// LSM-Tree 写入流程
function lsm_write(key value):
// 1. 先写 WAL（崩溃恢复用）
append_to_wal(key value)
// 2. 写入内存中的 MemTable
memtable.insert(key value)
// 3. 如果 MemTable 满了
if memtable.size() >= memtable_size_limit:
// 3a. MemTable 变为不可变，新建一个空的 MemTable
immutable = memtable
memtable = new MemTable()
// 3b. WAL 也切换
flush_wal()
// 3c. 后台线程将 Immutable MemTable 刷成 SSTable
schedule_flush(immutable)这个管道的设计保证了：
- 写入从不阻塞（除非 MemTable 刷盘跟不上写入速度）
- WAL 是纯顺序写入——追加写，没有寻道时间
- MemTable 是内存操作——纳秒级
当 MemTable 被刷成 SSTable 后，它进入 Level 0。然后通过后台的 Compaction（合并压缩）过程逐渐下沉到更深的层级。
SSTable 格式——翻开打包好的记录册
老陈从流水线上拿起一本刚装订好的册子，封面写着 'SST_0042'。'这就是 SSTable，'他翻开给你看，'打包好的数据册子，一旦合上就不再改动了。'
一个 SSTable 文件内部的组织方式：
Data Block 0 (key range: a-f)
[key value] × N
Data Block 1 (key range: g-m)
[key value] × M
...
Filter Block (Bloom Filter) ← 快速判断 key 是否存在
Index Block ← 每个 Data Block 的最小 key + 偏移
[a → offset_0 g → offset_1 ...]
Footer ← 指向 Index Block 和 Filter Block读取一个 key 时：
- 从 Footer 读取 Index Block 的位置
- 在 Index Block 中找到目标 key 属于哪个 Data Block
- （如有 Bloom Filter）检查 key 是否可能存在于这个 SSTable
- 读取对应的 Data Block，二分查找 key
注意：一个 key 可能在多个 SSTable 中存在（同一个 key 被更新过）。读取时取最新的版本。
Compaction——桌满了，该整理书架了
'有个问题，'你看着流水线，'这些 SSTable 越堆越多，要找东西不是越来越麻烦？'
老陈点头。随着时间推移，Level 0 的 SSTable 越来越多。你要找的 SSTable 也越来越多。读性能会持续下降。
Compaction 就是工人们的整理工作：在后台把多个小的 SSTable 合并成一个大的 SSTable，丢弃已被覆盖或删除的旧版本数据。
Level 0: [SST_1] [SST_2] [SST_3] [SST_4] ← 多个小文件
Compaction
Level 1: [ SST_large ] ← 一个大文件'就像把桌上散落的纸条定期装订成一本大册子，扔掉的旧版纸条就当废纸处理了。'老陈拍了拍那本新装订的大册子。
Compaction 的实现方式决定了 LSM-Tree 的读写放大特性。主要有两种策略。
深入冒险
Leveled Compaction——分层书架
'第一种方法，'老陈把你带到一面墙前，整面墙从下到上分成了几层书架。'叫 Leveled Compaction，RocksDB 的默认选择。'
多级结构，每一级的大小是上一级的固定倍数（默认 10 倍）：
L0: [S1][S2]... → 单个文件大小约 64MB
L1: [ ≈512MB ] → 单个文件 可以是多个文件的总和
L2: [ ≈5GB ] → ...
L3: [ ≈50GB ]规则：
- L0 比较特殊——SSTable 之间有 key 范围重叠（因为刷盘是无序的）
- 从 L1 开始，每个层级内的 SSTable 之间 key 范围不重叠
- Compaction 时，从 Ln 选一个 SSTable，与 Ln+1 中 key 范围重叠的所有 SSTable 合并
Leveled Compaction 的特点：
- 写放大较大：一个键写入后可能被多次 Compaction 搬移到更深的层级
- 空间放大较小：陈旧数据被高效清理，大部分层级只有 1-2 倍的数据冗余
- 读放大较小：因为每个 key 在每个层级最多只出现在一个 SSTable 中
Tiered Compaction——散装堆叠
'另一种方法，'老陈走到另一边——几摞文件堆在桌子上，每摞厚度差不多。'叫 Tiered Compaction。不急着整理，先堆着，等堆得太高了再合并。'
不将数据下沉到单文件，而是允许多个文件共存于一个层级，直到文件数达到阈值才合并：
Tier 0: [S1]
Tier 1: [S2][S3] ← 达到数量阈值时触发合并
Tier 2: [S4][S5][S6][S7]规则：
- 每个层级允许最多 N 个 SSTable（比如 4 个）
- 当层级内的 SSTable 数量超过阈值，将它们合并成一个大的 SSTable 并放到下一层级
Tiered Compaction 的特点：
- 写放大较小：数据被合并的次数少
- 空间放大较大：旧数据滞留时间长，多个 SSTable 可能包含相同的 key
- 读放大较大：每个 key 可能出现在多个 SSTable 中
三种放大的代价——每一次整理都有成本
'每次合并都有代价，'老陈擦了擦手，拿出一张纸画了三个圈。'写放大、读放大、空间放大——三角不可能全占。'
写放大（Write Amplification）：物理写入量 / 逻辑写入量。
-- 在 RocksDB 中查看写放大
-- 通过 DB::GetProperty("rocksdb.estimate-pending-compaction-bytes")
-- 或通过内嵌的统计信息
-- 假设你写入了 1MB 数据
-- 但经过多次 Compaction 后，实际写入磁盘了 10MB
-- 写放大 = 10x读放大（Read Amplification）：一次逻辑读取需要物理读取的次数。
-- B+树读放大 = 树高度 ≈ 3-4
-- LSM-Tree 读放大 = MemTable(1) + 各层级 SSTable 数量
-- Leveled Compaction 下 ≈ 层级数 + 每层文件数
-- 如果 L0 有 4 个 SSTable，L1-L3 各 1 个
-- 读放大 = 1(MemTable) + 4(L0) + 1(L1) + 1(L2) + 1(L3) = 8
-- 这就是为什么 LSM-Tree 的点查比 B+树慢
-- 也是为什么需要 Bloom Filter空间放大（Space Amplification）：磁盘上实际占用的空间 / 有效数据大小。
| 特性 | Leveled Compaction | Tiered Compaction |
|---|---|---|
| 写放大 | 高（10-40x） | 低（4-10x） |
| 读放大 | 低（~层级数） | 高（~槽位数 × 层级数） |
| 空间放大 | 低（1.1-2x） | 高（可达 10x+） |
| 适用场景 | 读多写少、SSD | 写多读少、HDD |
SSD 的寿命与写放大：SSD 有写入寿命（TBW），写放大直接缩短 SSD 寿命。一次逻辑上的 1MB 写入如果物理上写了 40MB，意味着 SSD 的磨损是 40 倍。这也是为什么 RocksDB 在 SSD 上会做大量优化来降低写放大。
RocksDB——工业级 LSM-Tree 的工程实践
'理论说完了，看看真家伙。'老陈打开一个标着 'RocksDB' 的工具箱。'Facebook 基于 Google LevelDB 改进的 LSM-Tree 实现——写放大和读放大都做了大量优化。'
1. Bloom Filter——过滤掉不存在的查问
'还记得读放大那个8次IO的问题吗？RocksDB 用了一个小把戏大幅降低它。'
Bloom Filter 是一个概率性数据结构：判断"key 肯定不存在"或"key 可能存在"。
// RocksDB 中配置 Bloom Filter
Options options;
options.table_factory.reset(NewBlockBasedTableFactory());
BlockBasedTableOptions table_options;
table_options.filter_policy.reset(NewBloomFilterPolicy(10 false));
options.table_factory.reset(
NewBlockBasedTableFactory(table_options));
// 效果：对一个 key 的查询，
// Bloom Filter 可以快速排除 99% 不包含该 key 的 SSTable
// 每次 Bloom Filter 检查是 O(k) 哈希，比磁盘 I/O 快几个数量级查询 key = 42
检查 MemTable → 没找到
↓
检查 Bloom Filter(SST_1) → "不在" → 跳过
检查 Bloom Filter(SST_2) → "可能在" → 读盘搜索 → 找到
↓
检查 Bloom Filter(SST_3) → "不在" → 跳过
这次查询只读了 1 个 SSTable，而不是 10 个。Bloom Filter 的假阳性：它会说"key 可能存在"但其实不存在。但不会出现假阴性（说"不存在"但实际存在）。假阳性率取决于位数组大小和哈希函数数量。配置中的
10表示每个 key 占用 10 bits，假阳性率约 1%。
2. 前缀压缩——省掉重复的部分
'看看这些记录，'老陈指着一个 SSTable 里的 key 列表：
"abcdef123"
"abcdef456" ← 前缀 "abcdef" 重复了
"abcdef789" ← 前缀 "abcdef" 又重复了'每个都存一遍完整字符串太浪费了。'老陈指着纸上的记录。'所以只存第一个完整的 key，后面的只存不同的部分。这叫前缀压缩，或者 key 增量编码。'
第一个 key: "abcdef123"（完整）
第二个 key: 增量 "456"（只存跟上一个不同的部分）
第三个 key: 增量 "789"这能把 Data Block 的大小压缩 30-60%，减少磁盘 I/O。代价是读取 Block 时需要对增量进行重建。
3. 列族（Column Families）——给不同类型分柜子
'有时候你的数据需要分门别类存放，'老陈打开同一个工具箱里的几个隔层，'metadata 放一层，logs 放另一层。它们各自独立 SSTable，但共享同一个 WAL。'
RocksDB 支持多个列族（Column Family），每个列族有自己的 MemTable 和 SSTable 集合，但共享同一个 WAL。这在需要隔离不同数据的保持写入顺序时非常有用。
// RocksDB 多列族
DB* db;
std::vector<ColumnFamilyHandle*> handles;
Options options;
// 创建
DB::Open(options "/tmp/testdb" &db);
// 创建列族
ColumnFamilyHandle* cf_handle;
db->CreateColumnFamily(ColumnFamilyOptions() "cf_metadata" &cf_handle);
// 写入列族
db->Put(WriteOptions() cf_handle "key1" "value1");
// 不同列族可以有完全不同的 Compaction 策略
// 比如 metadata 列族用 Leveled（读优化）
// logs 列族用 Tiered（写优化）4. Rate Limiter 和 Delayed Write——别让工坊被订单压垮
'最后一个，'老陈指了指工具箱底层的部件，'有时候任务请求太多，流水线处理不过来。你不能拒绝请求，但可以让请求慢一点进来。'
当写入速度超过 Compaction 的消化能力时，RocksDB 会主动限速——不是拒绝写入，而是让写入稍微等待，给 Compaction 留出时间。这叫 Write Stall。
// RocksDB 的写入节流
Options options;
options.rate_limiter.reset(NewGenericRateLimiter(
100 * 1024 * 1024 // 100 MB/s 写入限速
));
// 当 L0 文件数超过 soft_limit（默认 4） → 延迟写入
// 当 L0 文件数超过 hard_limit（默认 20）→ 停止写入
options.level0_slowdown_writes_trigger = 4;
options.level0_stop_writes_trigger = 20;Write Stall 是 LSM-Tree 的固有特征：写入速度不能长期超过 Compaction 的处理速度，否则层级会无限膨胀。
B+树 vs LSM-Tree：你的场景选哪个
'所以到底用哪个？'你问。
老陈把两个文件夹并排摊在桌上，一页一页对比给你看。
| 维度 | B+树 | LSM-Tree |
|---|---|---|
| 写性能 | 随机 I/O，有限的写入吞吐 | 顺序 I/O，极高的写入吞吐 |
| 读性能（点查） | O(log n)，3-4 次 I/O | O(k log n)，k=需检查的文件数 |
| 读性能（范围查询） | 叶节点链表，顺序扫描 | 需要合并多个文件 |
| 写放大 | 较低（1-3x） | 较高（10-40x leveled 4-10x tiered） |
| 空间放大 | 较低（1-2x） | Leveled 低，Tiered 高 |
| 崩溃恢复 | WAL REDO，较复杂 | WAL REDO + SSTable 原子替换 |
| 并发控制 | 页级锁，复杂 | SSTable 不可变，无需锁 |
| 内置压缩 | 页级压缩，容易 | SSTable 级压缩，更高效 |
| 代表系统 | PostgreSQL MySQL InnoDB SQLite | RocksDB LevelDB Apache Cassandra HBase ScyllaDB |
选型决策树：
你的工作负载以什么为主？
读取密集型（Web 应用、用户中心）
B+树（PostgreSQL/MySQL）
写入密集型（日志、时序数据、消息队列）
LSM-Tree（RocksDB/Cassandra）
读写均衡
要求强事务 → B+树
要求高吞吐 → LSM-Tree
大范围分析查询
在 OLTP 上 → B+树 + 覆盖索引
纯 OLAP → 列存（第6章）真实世界混合使用：TiDB 和 YugabyteDB 使用两种结构——RocksDB（LSM-Tree）做底层存储，B+树风格的元数据索引。Google Spanner 使用类 B+树的存储，但融入了 LSM-Tree 的理念。
常见陷阱
1. LSM-Tree 不适合小数据量
如果你的数据只有几万条，LSM-Tree 的层级结构反而增加开销。B+树在数据量小时 Buffer Pool 能缓存所有热页，性能完全够用。LSM-Tree 的 Compaction 在这些场景下是多余的计算。
2. Write Stall 是 LSM-Tree 的阿克琉斯之踵
当你写入速度超过 Compaction 速度（比如突发写入 100GB 数据到空数据库），L0 文件数急速膨胀。一旦超过 level0_stop_writes_trigger，写入就会完全停止。这会导致应用超时和连接池爆炸。
解决方法：
- 预分配资源、提前触发 Compaction
- 使用 Rate Limiter 让写入更平滑
- 监控
rocksdb.is-write-stopped()
3. 读放大的代价比你想的更大
LSM-Tree 的点查延迟方差很大。如果 Bloom Filter 说"可能在"但实际不在（假阳性），就要读一次磁盘。如果多个 SSTable 都有该 key 的旧版本，就要读多次。
// RocksDB 的 P99 延迟优化
ReadOptions read_options;
read_options.read_tier = kBlockCacheTier; // 只从缓存读，不到磁盘
read_options.tailing = true; // 用于大范围扫描的优化4. 不要对 LSM-Tree 的 SSTable 数量掉以轻心
每个 SSTable 有文件句柄开销。如果每个 SSTable 是 64MB，1TB 数据就是 16384 个 SSTable。操作系统有 ulimit -n 限制，需要合理配置。
通关挑战
** 热身（5 分钟，必做）**
- 安装 RocksDB 的 Python 绑定并体验基本操作：
pip install python-rocksdbimport rocksdb
db = rocksdb.DB("test_lsm.db" rocksdb.Options(create_if_missing=True))
db.put(b"key1" b"value1")
db.put(b"key2" b"value2")
print(db.get(b"key1")) # b'value1'
# 批量写入（原子操作）
batch = rocksdb.WriteBatch()
batch.put(b"key3" b"value3")
batch.put(b"key4" b"value4")
batch.delete(b"key1")
db.write(batch)
print(db.get(b"key1")) # None- 查看 SSTable 文件及其大小：
ls -lh test_lsm.db/
# 你会看到 .log (WAL) .sst (SSTable) MANIFEST OPTIONS 等文件- 写 100 万个 key 后查看层级结构：
for i in range(1000000):
db.put(f"key_{i:08d}".encode() f"value_{i}".encode())
# 查看统计
print(db.get_property(b"rocksdb.num-files-at-level0"))
print(db.get_property(b"rocksdb.num-files-at-level1"))
print(db.get_property(b"rocksdb.num-files-at-level2"))
print(db.get_property(b"rocksdb.cur-size-all-mem-tables"))** 挑战（30 分钟，选做）**
实现一个最小 LSM-Tree：
# min_lsm.py
# 实现：
# 1. MemTable（用内置的 sorted list 或 SortedDict）
# 2. MemTable 满后刷成 SSTable（直接写排序后的 JSON 或自定义二进制）
# 3. 简单的 Leveled Compaction（L0 超过 4 个文件就合并到 L1）
# 4. 读取时需要合并 MemTable + 所有 SSTable
# 5. 实现一个简单的 WAL（文件追加写入）
class SimpleLSMTree:
def __init__(self dir_path memtable_size=4):
self.dir_path = dir_path
self.memtable = {} # 当前活跃 MemTable
self.memtable_size = memtable_size
self.l0_ssts = [] # Level 0 的 SSTable 文件列表
self.l1_sst = None # Level 1 的 SSTable 文件
# TODO: 其他层级…
def put(self key value):
# 你的实现在这里
pass
def get(self key):
# 你的实现在这里
pass
def flush_memtable(self):
# 你的实现在这里
pass
def compact(self):
# 你的实现在这里
pass
def range_query(self low high):
# 你的实现在这里
pass** 观察**：用 iostat 观察写入模式：
# 在 RocksDB 写入时监控磁盘写入模式
iostat -x 1
# 对比 MySQL 的随机写和 RocksDB 的顺序写模式
# 看 await 和 %util 的差异验收标准
读完本章后，你应该能：
- [x] 描述 LSM-Tree 的三层写入管道：MemTable → Immutable → SSTable
- [x] 解释为什么 LSM-Tree 的写入是顺序 I/O 而 B+树是随机 I/O
- [x] 对比 Leveled Compaction 和 Tiered Compaction 的写放大/读放大/空间放大特性
- [x] 解释 Bloom Filter 如何在 LSM-Tree 中降低读放大
- [x] 理解 Write Stall 出现的原因及其应对方法
- [x] 根据工作负载类型判断 B+树和 LSM-Tree 哪个更合适
- [x] 说出 RocksDB 相比 LevelDB 的三项关键优化
常见卡点
| 卡点 | 原因 | 解决 |
|---|---|---|
| "LSM-Tree 为什么叫 Tree 但不是树？" | LSM-Tree 是一种数据结构思想，实际实现中用跳表/红黑树做 MemTable，用 SSTable 做磁盘文件 | 名字中的 Tree 指的是 MemTable 中的有序结构和 SSTable 的有序性 |
| "为什么 Compaction 不把数据直接写到最终层级？" | 数据可能又很快被删除或更新。逐级下沉是"给数据时间沉淀" | 写热数据的旧版本在短期内可能被覆盖，提前合并到深层是浪费 |
| "Bloom Filter 的假阳性导致读盘没用——这是不是浪费？" | 是的，但 Bloom Filter 的假阳性率可以控制在 1% 以下 | 检查 → 读盘失败 → 继续下一个 SSTable，每次读盘是全 I/O 的成本 |
| "RocksDB 的写放大 40x 不是灾难吗？" | 对于普通写操作是的，但 RocksDB 使用 O_DIRECT 跳过 Page Cache、在 Write Ahead 级别做一些跳过 | 写放大在写入 512B 小数据时尤其严重，通过键值合并可以减轻 |
现在不需要理解
- WiscKey：USENIX ATC 2016 的论文，对大值场景的 LSM-Tree 优化
- Pebble：CockroachDB 用的 Go 语言 LSM-Tree 实现
- LSM-Tree 的三层 Bloom Filter 优化：RocksDB 的 Full Filter 和 Block-based Filter 区别
- 透明压缩在 LSM-Tree 上的实现细节：ZSTD、Snappy 压缩策略和 SSTable 的关系
旅人笔记
LSM-Tree 用"先攒着再落盘"的策略把随机写变成顺序写，换来了极高的写入吞吐。代价是读操作需要在多个文件间合并，以及后台 Compaction 带来的写放大。B+树和 LSM-Tree 没有谁一定更好——读多写少用 B+树，写多读少用 LSM-Tree。真正的工程是做取舍。