什么是 LSM 树？详解日志结构合并树

每个数据库最终都会面临同一个问题：应用程序坚持随机写入，而磁盘——即使是市面上最快的磁盘——更喜欢顺序写入。

日志结构合并树（LSM）是针对这一问题的两大答案之一，也是 RocksDB 所选择的答案。

本系列的第一篇文章介绍了 LSM 树，而本文将对它进行全面剖析：这个结构是什么、一次写入在函数调用与磁盘文件之间究竟发生了什么，以及为什么这种设计在现代硬件上胜出。

什么是 LSM 树？

日志结构合并树（LSM）是一种数据结构，它将传入的写入缓冲在内存中，并以有序、不可变的批次合并到磁盘上。它从不原地修改数据。相反，它累积变更并推迟整理工作，用读取侧的简单性换取写入吞吐量。

LSM 树由 Patrick O'Neil、Edward Cheng、Dieter Gawlick 和 Elizabeth O'Neil 在 1996 年的论文 The log-structured merge-tree (LSM-tree) 中被正式提出。在此后的约十年里，它一直是一个相对冷门的学术结构，直到 Google 的 Bigtable 基于这一概念构建了其存储层。Bigtable 的设计催生了 LevelDB，LevelDB 又催生了 RocksDB，如今大多数为高吞吐摄入而构建的系统底层都是某种形式的 LSM 树。

这个名字暗示这是一棵单一的树，这非常具有误导性。

更准确的理解方式是，LSM 树是三个组件的协同编排：

• 一个 memtable：保存最近写入的内存缓冲区
• 一个 write-ahead log (WAL)：磁盘上的只追加文件，使这些写入持久化
• 一组不断增长的 sorted string table 文件（SSTs）：不可变、有序的文件，存放更早的数据

关于 LSM 行为的几乎所有有趣之处，都源于数据如何在这三个组件之间移动。所有这些移动都始于一个看似简单的函数调用，通常称为 put。

什么是 put？

Put 是一个便捷封装，它在内部构造一个恰好包含一条记录的 WriteBatch，并将其交给负责处理变更操作的 Write()。

最自然的起点是 Put(key, value)，但严格来说，RocksDB 并没有这样的操作。每次写入都是一个批次，单独一个 put 只不过是包含一条记录的批次。原子性多键写入在 RocksDB 中是免费获得的，因为这是原生操作。

WriteBatch 是一种具有固定形状的紧凑字节串。也就是说，一个 12 字节的头部包含 8 字节的序列号和 4 字节的记录数，后面跟着记录本身。每条记录是一个单字节的类型标签、一个带长度前缀的键，对于写入而言，还有一个带长度前缀的值。

本系列第一篇文章中的论断——键和值是任意字节数组——在这里变成了字面事实。批次编码既不知道也不关心这些字节是什么含义。唯一施加的结构就是长度前缀。

每个批次都会被打上一个单调递增计数器的印记，即 sequence number（序列号）。它为数据库曾经接受的每一次写入建立了一个全序。正是序列号使快照、一致性读和崩溃恢复成为可能。WAL 是可重放的，因为其中的每条记录都知道自己在队列中的位置。

Put、Delete、Merge

需要注意的重要一点是：Put 对应 kTypeValue，而 Delete 对应 kTypeDeletion，这意味着删除并不是移除。相反，它是一次写入——一个墓碑（tombstone）——记录删除这一事实，实际的回收工作则推迟到 compaction 阶段。

Put 和 Delete 与由 Merge 操作写入的 kTypeMerge 共享 WriteBatch 格式。Merge 存在的原因在于，读-改-写对写入优化的存储来说是毒药。使用 Put 来递增计数器需要先读取当前值、加一、再把结果写回。这意味着为了改变一个数字要对数据库进行两次遍历，而且读取还要支付完整的读路径成本。

Merge 完全跳过读取。

相反，它只是追加一个操作数（operand，即对变更的描述，例如“加一”）然后返回。写入时不做任何计算。数据库稍后使用应用提供的 merge 操作符将操作数折叠成最终值，时机要么是下次读取该键时，要么是 compaction 遇到这条操作链时。

Delete 推迟的是回收，而 Merge 推迟的是计算。

LSM 树的全部性格都体现在这三个类型标签中：每一次变更，包括那些在逻辑上依赖现有状态的变更，都变成了一次盲目的追加。在 LSM 树中，一切都是追加。

LSM 树写路径详解

理解 LSM 树最清晰的方式，就是跟踪一次 Put(key, value) 从函数调用到磁盘的全过程。

第一步：Write-Ahead Log

写入首先被追加到 WAL 中。这次追加发生在触碰 memtable 之前，而这个顺序构成了持久性契约。也就是说，一旦 WAL 追加完成，这条写入就以能在崩溃后幸存的形式存在于磁盘上，尽管它尚未被组织成可读的形式。

向日志追加是最廉价的磁盘操作，这正是全部要点所在。持久性是以顺序写入的价格买来的。

RocksDB 将并发写入批量打包成 group commit 以进一步摊薄成本，而 sync 选项控制它是否在调用返回之前把追加内容从 OS page cache 冲刷到稳定存储。

第二步：Memtable

持久性得到保障后，这条写入被插入 memtable。默认情况下，RocksDB 的 memtable 是一个跳表。之所以使用跳表，是因为 memtable 既需要吸收并发写入，又需要以按键排序的顺序交出其内容——无论是为了读取还是为了之后的 flush。

跳表支持无锁的并发插入，同时始终保持一切有序。它相当于数据结构层面的“文件随到随归档”，而不是任其堆积。

第三步：Memtable 填满

memtable 会不断增长，直到达到配置的阈值（即 write_buffer_size），该值默认为 64 MB。此时，它被标记为 immutable（不可变），一个新的空 memtable 被换入，新来的写入继续不中断地进行。装满并被冻结的 memtable 则等待轮到自己在后台被 flush。

写入永远不会因 flush 本身而被阻塞。

第四步：Flush

一个后台线程将不可变的 memtable 作为 SST 文件写到树的 level 0（L0）。由于跳表已经有序，flush 就是一次顺序遍历：按序走过所有条目并将它们写出。

memtable 的使命完成了，对应的 WAL 条目最终可以被丢弃。数据现在以永久的、可读的形式保存在磁盘上。

SST 文件里面有什么？

SST 文件是数据度过余生的地方。它由三个块和一个 footer 组成：

• Data blocks（数据块）：有序条目本身，每个几 KB，各自独立压缩
• Index blocks（索引块）：将键范围映射到块偏移量，使查找可以直接跳到正确的块
• 可选的 bloom filter 块：一个紧凑的概率摘要，无需读取其他任何内容就能回答“这个键肯定不在这个文件中”
• footer：用于定位上述所有部分

这种布局的每一个元素的存在，都是为了让未来的读取尽可能少地触及字节，尤其是索引和 bloom filter。

写路径实操演练

上面解释的一切都可以直接观察到。本节接下来将使用 RocksDB 自带的检查工具 ldb 和 sst_dump，快速跟踪一次 Put 在数据库中的完整过程。示例使用 Rust 和 rocksdb crate，不过任何语言的绑定都可以。

前置条件

要跟着操作，请安装 RocksDB 命令行工具和 Rust 工具链。

在 macOS 上，brew install rocksdb 会同时提供 ldb 和 sst_dump。在 Debian/Ubuntu 上，软件包是 rocksdb-tools。

安装好之后，创建一个新项目：

Terminal

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

rocksdb crate 在首次构建时会从源码编译 RocksDB C++ 库，所以第一次 cargo run 可能需要几分钟时间。

第一步：写入然后停止

用以下代码替换 src/main.rs 的内容：

src/main.rs

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// 故意不做 flush。让进程直接退出。
}

用 cargo run 运行一次，然后列出它创建的数据库目录：

Terminal

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

CURRENT 和 MANIFEST 文件跟踪数据库的文件清单，而 OPTIONS 记录打开数据库时所用的配置。不带任何数字的 LOG 是用于调试的人类可读文本日志，不要把它和 000004.log 混淆，后者才是 write-ahead log 本身。

具体的文件编号每次运行都会不同，但整体形态不会变。

注意，目录中没有一个 .sst 文件。这条写入是持久的，因为它在进程退出后依然存在，但它只以 WAL 记录的形式存在。这就是持久性/组织性分离的实际体现。

第二步：转储 WAL

让 ldb 指向目录中的那个 .log 文件：

Terminal

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

我们有一个批次：序列号为 1，包含 1 条记录（29 字节），是一条 PUT，其键是 slot:0001 的十六进制编码。

这个大小与前面的编码描述完全吻合：12 字节头部加上 17 字节记录，其中包括一个类型标签、两个长度前缀、一个 9 字节的键和一个 5 字节的值。

第三步：Flush 并转储 SST

首先，删除数据库目录（即 rm -rf /tmp/lsm-trace），让这次运行从干净状态开始。

在 put 之后给 main.rs 加一行：

src/main.rs

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

调用 db.flush().unwrap(); 会强制把 memtable 写出为一个 SST 文件，而不是等它填满。

再次运行程序，然后列出目录。

现在可以看到输出中出现了一个新的 .sst 文件。我们可以用 sst_dump 的两种实用模式来检查它，替换为实际文件名即可：

Terminal

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

注意，sst_dump 会在扫描输出之前打印几行关于文件格式的前导信息；这里以及下面的输出中都将其省略了。

这就是这个键值对在新永久居所中的样子，仍然带着它的序列号。

接着可以用以下命令查看它的属性：

Terminal

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

属性输出就是本文前面所述 SST 解剖结构的逐项罗列：data block 的数量和大小、index block 大小、filter 是否存在、压缩算法以及条目数量。

尽管我们只有一个键，所有结构元素都被逐项列出，只有一个颇具启发性的例外。filter block 大小为零，filter policy 显示 N/A，因为 bloom filter 在 RocksDB 中是需要主动开启的，通过 filter_policy 配置，而默认选项没有设置任何一个。

本系列的下一篇文章将讲解为什么生产环境部署几乎总是会开启它们。

第四步：重新打开并检查日志

注释掉 put 和 flush 两行，只保留 DB::open 这一行，然后再运行一次。现在列出目录会看到旧的 000004.log 已经消失，取而代之的是一个编号更大、几乎为空的新日志。它的内容已在第三步被 flush 到 SST，因此这些记录已过时，RocksDB 在重新打开时丢弃了这个文件。

这就是 WAL 与 memtable 生命周期耦合的全部体现。

要再深入一层，我们可以在 Linux 上用 strace -e trace=write,fdatasync 运行第一步的二进制程序，在系统调用边界观察持久性契约。也就是说，顺序的 write 调用向 .log 文件追加内容，而 fdatasync 只有在设置了 WriteOptions.sync 时才会出现。

第五步：删除键并查看残留内容

前面所说的“删除是一次写入”可以直接观察到。

修改 main.rs，删除该键并强制再执行一次 flush：

src/main.rs

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

运行它，然后列出目录。

现在会有两个 .sst 文件。较旧的那个原封不动，因为它是不可变的，也就是说它仍然包含这个键及其值。我们可以用扫描来验证：

Terminal

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

现在扫描较新的那个文件：

Terminal

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

还是同一个键，但序列号更高，类型是 type:0 而不是 type:1，并且不带任何值。这是一个墓碑（tombstone）：来自 WriteBatch 一节的 kTypeDeletion 记录被 flush 进了它自己的 SST。数据库现在同时包含这个值和它的删除记录，并排存在于不同的文件中。

读取这个键会解决这一矛盾，且结果偏向墓碑一方。

我们可以通过在程序中加入一次查询来验证：

src/main.rs

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

它会打印 not found，因为读路径会先检查更新的数据，而序列号 2 的优先级高于序列号 1。从数据库的角度看，这个值已经不存在了，但它其实还躺在较旧的 SST 文件里的磁盘上。

什么都没有被回收，也就是说删除只是被记录了下来，它会继续遮蔽这个值，直到 compaction 最终合并这两个文件，同时丢弃墓碑和被遮蔽的值。

第六步：删除键并查看残留内容

Merge 记录类型同样可以观察到。它需要配置一个 merge 操作符，因为没有操作符的话，RocksDB 根本不知道操作数意味着什么。

再次删除数据库目录，并用以下代码替换 main.rs：

src/main.rs

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

转储 WAL 可以看到三条独立的 MERGE 记录。也就是说，三次追加取代了一次读取：

Terminal

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

merge 操作符在读取时折叠了这条链，结果是原始字节。程序打印 Some([51])，因为 51 是字符 3 的 ASCII 码。再次强调，这是因为键和值是任意字节数组。

我们也可以在查询之前加上 db.flush().unwrap();，删除目录，然后再次运行程序。扫描 SST 会显示一条记录：

Terminal

'counter' seq:3, type:2 => 3

这次 flush 应用了操作符，把它们折叠成了单个操作数。

为什么 level 0 很特殊？

新的 SST 文件落在 level 0。它们是 memtable 的直接快照，每个文件覆盖对应 memtable 恰好吸收到的键范围，因此 L0 文件可以彼此重叠，而且经常如此。这与更深的每一层不同，那些层的文件互不重叠；每个文件拥有一个独立的键范围，所以每一层中最多只有一个文件可能包含某个给定的键。

其后果是，每个 L0 文件都是一个键可能藏身的独立位置，这使得 L0 文件数量成为对读取性能的直接征税。这就是为什么 RocksDB 密切关注 L0 文件的数量，并在数量攀升过高时开始限流甚至暂停写入。

保持 L0 小巧是 compaction 的主要任务之一。

为什么 LSM 树在写入上胜过 B-tree？

B-tree 在写入时就支付组织的成本，这样读取时总能在数据应在的位置找到它们；而 LSM 树把组织工作推迟到后台 compaction，之后再一次性批量偿还。

B-tree 是大多数传统数据库所依赖的结构。它原地更新数据，也就是说每次写入都要找到拥有该键的页，读取它、修改它、再写回去。涉及的页散布在磁盘各处，因此逻辑上的随机写入流就变成了物理上的随机 I/O 流。

LSM 树拒绝在写入时付费。它追加（到 WAL）、缓冲（memtable）、批量化（flush）。每一次磁盘写入都是顺序的，组织债务被推迟到 compaction。这些工作并没有消失，而是稍后批量偿还，被整合成磁盘非常擅长处理的形式。

这在 SSD 上关系重大，因为 SSD 根本无法原地覆写数据。

闪存按大块擦除，块大小从几百 KB 到几 MB 不等，而写入则按较小的页进行。这意味着每一次小的随机覆写都会迫使硬盘的 flash translation layer（FTL）在幕后迁移有效数据并擦除块。

B-tree 的随机页写入会让 FTL 不断地做这件事。写放大由设备强加，叠加在数据结构本身产生的开销之上，并且同时以吞吐量和硬盘寿命为代价。而 LSM 树的大块顺序写入接近闪存硬件所能获得的最理想情况。

思考这件事最好的方式是把它看作一笔贷款。被推迟的组织工作到期偿付，表现为 compaction I/O，以及读取必须比 B-tree 检查更多的地方。因此，LSM 树现在买入写入吞吐量，之后以读放大和空间放大的形式偿还。

想深入了解 LSM 树与 B-tree 在读放大、写放大和空间放大方面的对比，请参阅 B-Tree vs LSM-Tree。

RocksDB 崩溃后会发生什么？

memtable 是易失性内存，崩溃会将它抹去。这正是 WAL 存在的理由。

重启时，RocksDB 会重放每一条已被确认但尚未 flush 到 SST 的写入。它把这些写入插入到一个全新的 memtable 中，以重建崩溃前的状态。恢复成本与未 flush 的数据量成正比，这也是 WAL 与 memtable 生命周期相互关联的原因。一旦某个 memtable 的内容被安全地 flush 到 SST，对应的日志条目就过时了，WAL 也就可以被截断。

写入在日志追加落地的那一刻就是持久的。等到 flush 把它组织好之后，它才变得可以廉价地读取。B-tree 把这两件事耦合在一起，而 LSM 树把它们拆开，这种结构的绝大部分特性都源于这一拆分。

Solana 是如何给写路径施压的？

本系列的第一篇文章介绍了 Agave 如何将 Solana 的 ledger 存储在 RocksDB 中。从写路径的角度看，这种负载几乎就是一个量身定制的压力测试。也就是说，shred（即 ledger 数据的原始单元）以线速持续不断地通过网络到达，其中每一个都必须走完 WAL 追加加 memtable 插入这条路径，validator 的存储层才算完成工作。

所涉及的机制与本文跟踪的一模一样，只是运行在生产规模上。当 shred 到达时，Agave 中 Blockstore 的插入路径会校验整批传入的 shred，对缺失的部分尝试 Reed-Solomon 恢复，然后把所有东西（即 shred payload、slot 元数据、纠删元数据、索引更新）暂存进单个 RocksDB WriteBatch，最后在一次原子写入中提交。

简化自 insert_data_shred：

agave/ledger/src/blockstore.rs

// 我们不希望这些变更只有一部分生效。
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...元数据更新 */);
data_index.set_present(index, true);

那条注释是 Agave 的工程师用九个单词道出了本文的观点：批次是原子性的单位，validator 在插入中途崩溃时绝不能让 ledger 处于半更新状态。

实操演练中跟踪的单条批次，在 validator 内部则是包含数千条的批次——跨多个 column family 的 shred 及其元数据、一段连续的序列号范围、一次 WAL 追加、一次 group commit。

不过，令人欣慰的是，shred 以 slot 号开头（即简化代码片段中的 (slot, index) 元组就是 ShredData 键），而 slot 几乎单调递增。因此，每个 memtable 吸收的都是键空间中一条狭窄且基本连续的区段，flush 产生的 L0 文件几乎没有重叠。

我们切身感受着这条写路径。

我们在 Helius 运行的归档系统将 Solana 的完整交易历史摄入 RocksDB——在一个以追加为主、永久增长的负载下达到数百 TB——促成这一架构的迁移过程记录在我们的 ClickHouse to RocksDB 文章中。

结论

LSM 树是与硬件达成的一笔交易。所有写入都变成顺序的，作为交换，保持数据井然有序的工作被推迟。这意味着读路径需要在比 B-tree 更多的地方寻找数据。memtable 负责吸收，WAL 负责保证，SST 负责积累。在闪存存储上——随机覆写在那里要付出双重代价——这是一笔极好的交易。

然而，写入只是容易的那一半。这种设计的代价要在读取时支付，因为一个键的当前值可能存在于 memtable、某个 L0 文件或下面任何一层中。把这一代价控制在有限范围内的机制，正是 LSM 工程变得相当有趣的地方。

本系列的下一篇文章将走读写路径，涵盖 memtable、bloom filter、block cache，以及放大三角形的实际运作。

如果跟随一个键值对穿越四种不同的数据结构听起来像是一个美好的下午，欢迎加入我们一起构建。本系列所描述的系统正是我们在互联网资本市场规模上部署、运维和调优的系统。我们的工程团队正在招聘。请在 helius.dev/careers 查看我们所有的开放职位。

• 原文链接： helius.dev/blog/lsm-tree...
• 鸿途知科网 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～