我的 LSM 树比 B 树还慢？直到我进行了性能剖析

背景

几周前，作者出于对底层存储引擎运作机制的好奇，决定不只是阅读文档，而是亲手构建一个。RocksDB、LevelDB、Cassandra、TiKV 和 CockroachDB 等知名数据库系统均基于同一种核心思想：日志结构合并树（Log-Structured Merge Tree, LSM Tree）。尽管几乎所有后端工程师都使用过基于 LSM 树的数据库，但由于生产级实现代码量高达数十万行，很少有人能真正读懂其内部逻辑。

为了理解这一机制，作者使用 Go 语言从零构建了一个 LSM 树存储引擎。然而，初步基准测试的结果令人尴尬：其写入性能仅为每秒 25 万次，而基于纯 Go 实现的 B 树数据库 BoltDB 的性能却更高。

这篇文章详细记录了作者如何通过性能剖析（Profiling），将写入性能从每秒 25 万次提升至接近每秒 198 万次的过程。这一过程并非依靠猜测，而是完全基于数据驱动的性能优化。每一个瓶颈的消除都揭示了下一个瓶颈，这种“追逐移动靶”的能力才是工程实践中真正的核心技能。

核心内容

1. 为什么 B 树在写入密集型负载下表现不佳？

B 树的核心特性是保持数据在磁盘上始终有序。每次插入操作都需要在树中找到正确的位置并进行写入，这意味着每次写入都是随机写入。无论是机械硬盘还是 SSD，顺序写入的速度都远快于分散的随机写入。

基准测试数据证实了这一点：

• BoltDB（B 树）：在顺序写入下，性能高达每秒 277 万次；但在随机写入下，性能暴跌至每秒 23.4 万次，降幅超过 10 倍。
• LSM 树的解决方案：LSM 树的设计初衷正是为了填补这一性能缺口。

2. LSM 树的基本原理与权衡

LSM 树的核心思想是避免随机写入：

• 写入路径：不直接在磁盘上写入，而是将数据写入内存中的有序结构（MemTable）。内存写入是即时的。
• 持久化：当 MemTable 满时，将其整体以顺序写入的方式转储到磁盘，形成不可变的文件（SSTable, Sorted String Table）。
• 合并（Compaction）：后台进程负责将旧的 SSTable 合并在一起，生成新的 SSTable。
• 读取权衡：数据分散在 MemTable 和多个 SSTable 中，读取时需要检查所有这些层级。通过布隆过滤器（Bloom Filter）、稀疏索引和分层结构来管理读取成本，是 LSM 树工程实现的主要挑战。

3. 初始瓶颈与性能剖析

第一个可用的版本性能如下：

• 顺序写入：250,000 次/秒
• 随机写入：120,000 次/秒

使用 pprof 进行剖析后，发现三个主要瓶颈占据了 80% 的 CPU 时间：

1. Write 系统调用：34%
2. 垃圾回收（GC）：约 35%
3. 排序操作：约 13%

4. 瓶颈突破与优化过程

瓶颈一：Write 系统调用（34% → 2.16%）

• 问题：每次写入预写日志（WAL）时都调用 file.Write，导致频繁进入内核态并发生数据拷贝。
• 解决方案：使用 mmap 将 WAL 文件映射到内存。启动时映射整个文件，通过普通的 copy() 操作写入映射区域，从而避免系统调用。数据直接落入页缓存，由后台 goroutine 处理实际的 fsync 到磁盘。
• 结果：这是整个项目中收益最大的优化。

瓶颈二：GC 与排序（合计 48%）

• 问题：合并（Compaction）阶段将所有待合并的 SSTable 条目加载到一个巨大的切片中，进行全局排序，然后去重。这导致大量的临时对象分配（引发 GC）和 sort.Slice 操作。
• 解决方案：采用流式多路归并（Streaming k-way merge）。由于各个 SSTable 内部已经有序，使用最小堆（container/heap）从所有输入文件中逐个提取最小的键。无需加载所有数据，无需全局排序，内存占用恒定。
• 结果：GC 开销和排序时间完全消失。

关键 Bug：布隆过滤器失效

在重写合并迭代器后，读取性能反而大幅下降，每次读取都在扫描整个 SSTable 文件。

• 原因：布隆过滤器的大小计算错误。合并迭代器将输入 SSTable 文件的数量（约 5-10 个）误传为预期条目数。导致布隆过滤器仅分配了约 100 位空间，但实际存储了 100,000 个条目。
• 后果：100 位的布隆过滤器容纳 10 万个键会瞬间饱和，所有位都被置为 1。这意味着它对所有查询都返回“可能存在”，导致过滤功能失效，每次读取都回退到全文件扫描。
• 修复：将布隆过滤器的大小基于固定常量 entriesPerChunk = 100000 进行设置，而非文件数量。读取性能恢复。
• 启示：这是一个典型的“静默失效”Bug，代码编译运行正常，只有通过基准测试才能发现其无用性。

瓶颈三：读取经过内核

• 问题：读取操作通过 ReadAt 系统调用进行，每次读取都涉及系统调用开销。
• 解决方案：在打开 SSTable 文件时使用 mmap。读取操作直接解析映射内存，实现零拷贝，无系统调用。
• 结果：读取吞吐量提升 234%。

5. 其他细微优化

在解决主要瓶颈后，作者进行了一系列增量优化：

• 增量 CRC 计算：关闭 SSTable 时不再回读整个 4MB 文件来计算校验和，而是在写入过程中累积 CRC。
• 缓冲 SSTable 写入：使用 256KB 缓冲区批量处理系统调用。
• MemTable 容量提示：Go 的 Map 在增长时会重新哈希和重新分配。预先分配容量提示避免了约 17 次重新分配，带来 6% 的性能提升。
• NoWAL 模式：跳过 WAL 以测试性能上限，发现 WAL 不再是瓶颈，持久化与非持久化之间的差距仅为 10%。

6. 最终性能与诚实对比

• 最终成绩：顺序写入达到 1.98 百万次/秒，相比初始的 25 万次，提升了约 8 倍。
• 随机写入对比：在 LSM 树擅长的随机写入负载下，达到每秒 119 万次，而 BoltDB 仅为 23.4 万次，快 5 倍。
• 局限性：
  • 作者承认 BadgerDB 比其实现快约 4 倍。原因是 BadgerDB 基于 WiscKey 论文，将值存储在单独的日志中，LSM 树中仅保留键和指针。这使得树结构更小，能完全放入内存，合并移动的数据更少。
  • 在读取方面，作者实现的 LSM 树慢于 BoltDB。B 树读取只需一次查找，而 LSM 树可能需要检查 MemTable、多个 L0 文件以及后续层级中的文件，查找路径更长。

关键要点

• 数据驱动优化：性能优化不应依赖直觉，而应依赖 pprof 等工具进行的精确剖析。每个优化步骤都应量化其收益。
• 系统调用是性能杀手：在高频写入场景下，通过 mmap 避免系统调用和内核态切换，可以带来巨大的性能提升（如本例中从 3