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

什么是 LSM 树？

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

Patrick O’Neil、Edward Cheng、Dieter Gawlick 和 Elizabeth O’Neil 在 1996 年发表的论文 日志结构合并树（LSM-tree）中正式提出了 LSM 树。此后约十年间，它一直是一种相对冷门的学术结构，直到 Google 的 Bigtable 以这一概念构建存储层。Bigtable 催生了 LevelDB，LevelDB 又催生了 RocksDB，而大多数为高摄取量设计的系统底层，都运行着某种形式的 LSM 树。  

这个名称让人以为它是一棵树，这其实非常容易造成误解。 

更准确地说，LSM 树是以下三个组件协同运作的结果：

• memtable（内存表）：保存最新写入的内存缓冲区
• 预写日志（WAL）：仅追加的磁盘文件，用于确保持久化这些写入
• 不断增长的 **有序字符串表文件（SST）**集合：用于保存更早数据的不可变有序文件

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

什么是 put？ 

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

从 Put(key, value) 讲起最自然，但严格来说，RocksDB 并不存在这样的操作。每次写入都是一个批次，单独一次 put 只是仅含一项的批次。由于这是 RocksDB 的原生操作，因此它天然支持原子性的多键写入。

WriteBatch 是一种结构固定的紧凑字节串。它包含一个 12 字节的头部，其中有 8 字节的序列号和 4 字节的记录数，之后是记录本身。每条记录都包含一个单字节类型标签、一个带长度前缀的键；如果是写入，还包含一个带长度前缀的值。

本系列第一篇文章中的说法——键和值都是任意字节数组——在这里体现得非常直接。批次编码既不知道也不关心这些字节代表什么，唯一强加的结构就是长度前缀。 

每个批次都会带上一个单调递增的计数器，称为序列号。它为数据库曾接受的每次写入建立全序关系。快照、一致性读取和崩溃恢复之所以能够实现，正是因为序列号。WAL 可以重放，因为其中的每条记录都知道自己所处的顺序位置。

Put、Delete、Merge

需要特别注意的是，Put 对应 kTypeValue，而 Delete 对应 kTypeDeletion。这意味着删除并不是真的移除数据，而是执行一次写入——写入一个墓碑标记来记录删除事实，真正的空间回收则推迟到压缩阶段。

Put 和 Delete 与由 Merge 操作写入的 kTypeMerge 共用 WriteBatch 格式。Merge 之所以存在，是因为“读取-修改-写入”对写入优化型存储来说极其不利。使用 Put 递增计数器，需要先读取当前值、加一，再写回结果。为了修改一个数字，数据库必须遍历两次，而读取还要承担完整读取路径的成本。 

Merge 完全跳过了读取。 

它只会追加一个操作数（即对变更的描述，例如“加一”），然后立即返回。写入时不会进行任何计算。之后，数据库会使用应用提供的合并运算符，将操作数归并为最终值：要么在下次读取该键时执行，要么在压缩遇到这条操作链时执行。

删除推迟空间回收，而合并推迟计算。 

从这三个类型标签中，就能看出 LSM 树的全部特性：每次变更，包括那些逻辑上依赖现有状态的变更，都会转化为盲追加。在 LSM 树中，一切都是追加。 

详解 LSM 树写入路径

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

第一步：预写日志

写入首先被追加到 WAL。追加操作发生在修改 memtable 之前，这一顺序构成了持久性契约。也就是说，一旦 WAL 追加完成，这次写入就已经以可在崩溃后保留的形式存在于磁盘上，即使它尚未被整理成便于读取的形式。

追加日志是成本最低的磁盘操作，这正是整个设计的核心。持久性只需付出顺序写入的成本。

RocksDB 会将并发写入合并为组提交，以进一步分摊成本。sync 选项则控制是否在调用返回前，将追加内容经由操作系统页面缓存刷入稳定存储。

第二步：memtable

持久性得到保障后，写入会被插入 memtable。默认情况下，RocksDB 的 memtable 使用跳表。之所以选择跳表，是因为 memtable 既要吸收并发写入，也要按键的排序顺序返回内容，以支持读取和后续刷写。

跳表支持无锁并发插入，同时始终保持所有内容有序。这就像文件一到便立即归档，而不是先任其堆积。

第三步：memtable 写满

memtable 会不断增长，直到达到配置的阈值（即 write_buffer_size），默认值为 64 MB。此时，它会被标记为不可变，并切换到一个全新的空 memtable，传入的写入不会中断。已写满并冻结的 memtable 则等待在后台刷写。 

写入绝不会因刷写本身而阻塞。

第四步：刷写

后台线程会将不可变 memtable 写入磁盘，生成树中第 0 层（L0）的一个 SST 文件。由于跳表已经排好序，刷写只需进行一次顺序遍历，按顺序访问并写出各个条目。

memtable 的任务至此完成，对应的 WAL 条目最终也可以丢弃。数据现在以永久且可读的形式保存在磁盘上。

SST 文件中有什么？

数据会在 SST 文件中度过余下的生命周期。它由三类数据块和一个页脚组成：

• 数据块：已排序的条目本身，每块几 KB，并分别压缩
• 索引块：将键范围映射到块偏移量，使查询可以直接跳转到正确的数据块
• 可选的布隆过滤器块：一种紧凑的概率性摘要，无需读取其他内容即可回答“这个键肯定不在此文件中”
• 页脚：用于定位上述所有内容

这种布局中的每个元素，都是为了让未来的读取尽量少接触字节，尤其是索引和布隆过滤器。

写入路径实操

以上所有内容都可以直接观察。本节将使用 RocksDB 附带的检查工具 ldb 和 sst_dump，快速跟踪一次 Put 在数据库中的完整过程。示例使用 Rust 和 rocksdb crate，不过任何绑定都可以。

前置条件

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

在 macOS 上，运行 brew install rocksdb 会同时安装 ldb 和 sst_dump。 在 Debian/Ubuntu 上，对应的软件包是 rocksdb-tools。

安装完成后，创建一个新项目：

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

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

第一步：写入并停止

使用以下代码替换 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();
// Deliberately no flush. Let the process exit.
}

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

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

CURRENT 和 MANIFEST 文件用于跟踪数据库的文件清单，OPTIONS 则记录数据库打开时采用的配置。不带数字的 LOG 是供调试使用的人类可读文本日志，不要将它与 000004.log 混淆，后者才是预写日志本身。

每次运行的具体文件编号会有所不同，但整体结构不会改变。

注意，目录中一个 .sst 文件都没有。写入已经持久化，因为它在进程退出后依然存在，但目前仅以 WAL 记录的形式存在。这正体现了持久化与整理相分离的设计。

第二步：转储 WAL

将 ldb 指向目录中包含的 .log 文件：

$ 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 字节的值。

第三步：刷写并转储 SST

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

在 put 后向 main.rs 添加一行：

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

调用 db.flush().unwrap(); 会强制将 memtable 写成 SST 文件，而不是等待它写满。

再次运行该文件，然后列出目录内容。 

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

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

请注意，在扫描结果之前，sst_dump 会输出几行与文件格式有关的前置信息；此处及下方输出均已将其省略。

这就是进入永久存储位置后的键值对，它仍然携带着序列号。 

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

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

属性输出逐项展示了前文介绍的 SST 结构：数据块数量和大小、索引块大小、是否存在过滤器、压缩算法以及条目数量。 

尽管这里只有一个键，所有结构元素仍被逐项列出，但有一个很有启发性的例外。过滤器块大小为零，过滤器策略为 N/A，因为在 RocksDB 中，布隆过滤器需要主动启用，通过 filter_policy 配置，而默认选项并未设置它。 

本系列的下一篇文章将介绍为什么生产部署几乎总会启用它。 

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

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

这就是 WAL 与 memtable 生命周期之间的完整联动。 

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

第五步：删除键并查看剩余内容

前文所说的“删除也是写入”可以直接观察到。 

修改 main.rs，删除该键并强制再次刷写：

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

运行它，然后列出目录内容。 

现在会有两个 .sst 文件。较旧的文件是不可变的，因此未被修改，里面仍然包含该键及其值。可以通过扫描验证：

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

现在扫描较新的文件：

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

它包含相同的键，但序列号更高，类型是 type:0 而非 type:1，并且不携带值。这就是墓碑标记：WriteBatch 一节中的 kTypeDeletion 记录被刷入了自己的 SST。现在，数据库同时包含该值及其删除记录，二者并列存在于不同文件中。

读取该键时，这一矛盾会以墓碑标记胜出而得到解决。 

可以通过向程序添加一次查询来验证：

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

它会输出 not found，因为读取路径会优先检查较新的数据，而序列号 2 的优先级高于序列号 1。从数据库的角度看，该值已经消失，但它实际上仍位于较旧的 SST 文件中。 

此时没有回收任何内容。删除只是被记录下来，并会持续遮蔽该值，直到压缩最终合并这两个文件，同时丢弃墓碑标记和被遮蔽的值。

第六步：删除键并查看剩余内容

同样可以观察 Merge 记录类型。为此需要配置合并运算符，因为如果没有运算符，RocksDB 无法知道操作数的含义。

再次删除数据库目录，并使用以下代码替换 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 记录。也就是说，这里执行了三次追加，而不是一次读取：

$ 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

合并运算符在读取时归并了这条操作链，结果以原始字节形式返回。程序会输出 Some([51])，因为 51 是字符 3 的 ASCII 编码。原因仍然是键和值都是任意字节数组。

还可以在查询前添加 db.flush().unwrap();，删除目录后重新运行程序。扫描 SST 会显示一条记录：

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

刷写应用了运算符，并将它们折叠为一个操作数。

为什么第 0 层很特殊？

新的 SST 文件会进入第 0 层。它们是 memtable 的直接快照，每个文件都覆盖对应 memtable 当时吸收的键范围，因此 L0 文件之间可能重叠，而且经常如此。这与所有更深层级不同：更深层级的文件互不重叠，每个文件拥有不同的键范围，因此每层最多只有一个文件可能包含指定的键。

这意味着，每个 L0 文件都是键可能藏身的独立位置，因此 L0 文件数量会直接拖累读取性能。正因如此，RocksDB 会密切监控 L0 文件数量，并在数量过高时开始限制写入，甚至暂停写入。

保持较少的 L0 文件，是压缩的主要任务之一。

为什么 LSM 树的写入性能优于 B 树？

B 树在写入时承担数据整理成本，让读取可以在数据所属的准确位置找到一切；LSM 树则将整理工作推迟到后台压缩，之后再批量支付成本。

B 树是大多数传统数据库的底层结构。它原地更新数据，这意味着每次写入都要找到负责该键的页面，读取、修改，再写回。涉及的页面散布在磁盘各处，因此逻辑上的随机写入流会变成物理上的随机 I/O 流。

LSM 树拒绝在写入时支付这笔成本。它执行追加（写入 WAL）、缓冲（写入 memtable）和批处理（刷写）。每次磁盘写入都是顺序的，而数据整理的债务则推迟到压缩阶段。工作并没有消失，而是在之后批量完成，并整合为磁盘非常擅长处理的形式。

这一点对 SSD 尤其重要，因为 SSD 根本无法原地覆盖数据。 

闪存以数百 KB 到数 MB 的大块为单位擦除，却以更小的页面为单位写入。这意味着每次小规模随机覆盖，都会迫使硬盘的闪存转换层（FTL）在后台迁移仍然有效的数据并擦除块。 

B 树的随机页面写入会让 FTL 不断执行这些操作。设备本身会产生写放大，再叠加到数据结构自身产生的写放大之上，最终同时损耗吞吐量和硬盘寿命。LSM 树的大规模顺序写入，接近闪存硬件所能获得的最佳工作负载。

最适合的理解方式，是把它看作一笔贷款。推迟的数据整理最终要通过压缩 I/O 偿还，而且读取需要检查的位置也比 B 树更多。因此，LSM 树现在买下写入吞吐量，之后再以读取放大和空间放大的形式偿还。 

如需深入了解 LSM 树与 B 树在读取放大、写入放大和空间放大方面的差异，请参阅 B 树与 LSM 树对比。 

RocksDB 崩溃后会发生什么？

memtable 位于易失性内存中，因此崩溃会将其清空。这正是 WAL 存在的原因。

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

日志追加落盘的瞬间，写入就具备了持久性。之后，刷写会整理数据，让它能够以较低成本读取。B 树将二者绑定在一起，LSM 树则将它们分离，而这种结构的大部分特性都源于这一分离。 

Solana 如何给写入路径带来压力？

本系列的第一篇文章介绍了 Agave 如何在 RocksDB 中存储 Solana 的账本。从写入路径来看，这种工作负载几乎就是专门设计的压力测试。shred（即账本数据的原始单元）持续以线速通过网络到达，而每个 shred 都必须经过 WAL 追加和 memtable 插入路径，validator 的存储层才算完成工作。

其中涉及的机制与本文追踪的过程完全相同，只是扩大到了生产规模。当 shred 到达时，Agave 中的 Blockstore 插入路径会验证整批传入的 shred，对任何缺失的 shred 尝试进行 Reed-Solomon 恢复，并将所有内容（即 shred 载荷、slot 元数据、纠删码元数据和索引更新）暂存到一个 RocksDB WriteBatch 中，最后通过一次原子写入提交。

以下代码简化自 insert_data_shred：

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

这条注释用九个词表达了 Agave 工程师与本文相同的观点：批次是原子性的单位，而 validator 在插入过程中崩溃时，绝不能让账本停留在只更新一半的状态。 

实操中追踪的单项批次，在 validator 内部则是包含数千项的批次——涵盖多个列族中的 shred 及其元数据，使用一个序列号范围、一次 WAL 追加和一次组提交。

不过，它有利的一面是 shred 以 slot 编号开头（也就是说，简化代码片段中的 (slot, index) 元组就是 ShredData 键），而 slot 几乎单调递增。因此，每个 memtable 都会吸收键空间中一段狭窄且大致连续的区域，刷写生成的 L0 文件几乎不会重叠。

我们能够直接感受到这条写入路径的影响。 

我们在 Helius 运行的归档系统会将 Solana 的完整交易历史摄取到 RocksDB——数据规模达数百 TB，工作负载以追加为主且永久增长。形成这一架构的迁移过程，记录在我们的 ClickHouse 迁移到 RocksDB 一文中。

结论

LSM 树是与硬件达成的一笔交易：以推迟数据整理为代价，将所有写入转化为顺序写入。这意味着，相比 B 树，读取路径需要在更多位置查找数据。memtable 负责吸收，WAL 提供保障，SST 则不断累积。在随机覆盖会受到双重惩罚的闪存上，这笔交易非常划算。

不过，写入只是简单的一半。这种设计的代价要在读取时支付，因为一个键的当前值可能存在于 memtable、L0 文件或下方的任意层级中。如何让这种代价保持在可控范围内，正是 LSM 工程真正有趣的地方。 

本系列的下一篇文章将深入讲解读取路径，包括 memtable、布隆过滤器、块缓存，以及放大三角如何在实践中发挥作用。

如果花一个下午跟踪一个键值对穿越四种不同的数据结构，听起来正合你意，那就加入我们，一起构建这些系统。本系列介绍的系统，正是我们在互联网资本市场规模下部署、运营和调优的系统。我们的工程团队正在招聘。访问 helius.dev/careers 查看所有空缺职位。