深入理解LSM树

今天我们聊聊 LSM 树。可能这是你第一次听说 LSM 树，但 LSM 树其实已经是我们的老朋友了，大多数 NoSQL 如 HBase、LevelDB、Cassandra、RocksDB 等底层都有 LSM 树的身影。今天我们聊聊 LSM 树的理论、落地实践以及它的缺陷。

LSM 树的起源

LSM 树的概念源自一篇论文《The Log-Structured Merge Tree》，其名称直接反映了其核心特性：日志结构化和合并操作。日志结构化意味着数据以追加的方式写入，类似于应用程序的日志输出，这种方式的优势在于其高效性，因为追加操作通常比随机写入要快得多。

在之前关于 Kafka 的讨论中，我们已经了解到日志追加方式的优势。LSM 树的另一个关键特性是“合并”，即通过合并多个分散的日志片段来优化存储和访问效率。

LSM 树是为 NoSQL 存储系统而生的，NoSQL 基本都是 key-value 结构，因此最主要的功能只有两个：put 和 get。put：写入一个 key-value；get：给定一个 key 返回 Value。除此之外 LSM 还提供了排序能力，比如在 HBase 中，默认就是按照字典顺序排序的，因此 HBase 可以 scan 某一个区间段的数据，比如我要查询某个用户的订单列表并按下单时间倒序排列，就很适合用 HBase 来存储，这得益于 LSM 的支持。

LSM 树的架构与优势

LSM 树的优点就是写入速度快，写入快的秘密在于 LSM 树利用了磁盘的顺序写，这使得 NoSQL 的性能优于关系型数据库。

下图是 LSM 树的逻辑示意图，LSM 树是一个多层结构，自上而下存储的数据越来越多。最上层是位于内存的 C0 层，里面存储着最近写入的 key-value，默认情况下这里的 key-value 是有序的，这个顺序就是 key 的字典顺序，并且由于数据在内存里，所以可以方便我们增删改查。剩下的 C1 到 CN 层和 C0 是割裂的。因为除了 C0 层，其他层都在磁盘上，每一层都按照 key 的字典顺序进行排列。

下面我们聊聊写入的过程，假设一个 put 操作过来了，第一步数据会进入到最上方的 C0 层。然后 C0 层的数据越来越多，达到一定阈值后， C0 层的数据就会合并到 C1 层，这个合并过程就是大名鼎鼎的归并排序，在这里称作 Compaction。接下来 C1 层的数据越来越多，多出来的数据会 Compaction 到 C2 层，以此类推直到 CN 层。

假设有 2 个相同的 key 怎么办呢？

比如 key “ABC”由于前面的合并已经写入到 C2 层了，但是新的 put 请求又过来了，按这种设计，整个 LSM 树会出现多个“ABC”。实际上，你不用担心这个问题，LSM 会在 Compaction 过程中自动删除早期的 key。Compaction 是一个异步过程，不会影响写入性能。

讲完了写入，我们再讲讲查询过程，在上面的写入流程中可以看到，从 C0 到 CN，数据越来越“旧”，所以查询时也是先查 C0 层，如果没有查到需要的数据，再查 C1 层，逐层查。这样一来，即使 Compaction 还没来得及删除旧的“ABC”也没关系，我们会先找最新的“ABC”。

你会发现，针对 LSM 树的一次查询可能需要多层查询，看上去稍慢。这种情况下 NoSQL 如何保证高性能查询呢？这种情况下不同的 NoSQL 又针对查询做了优化，比如 HBase 把数据放在不同的 Region 里面，完成对数据的路由等等，针对读的优化和 LSM 树无关，我在这儿就不赘述了。

总结一下，LSM 树的结构其实就像是多层喷泉，上一层满了就会溢出，到下一层。

LSM 树实践

上面的模型是论文中的表述，我们知道理论到实践还是有点距离的。比如将 C0 跟 C1 合并的过程需要一个时间，这个时候新的 put 请求怎么办，会被阻塞住吗？另外，每次都要将这么多层合并，这个过程是怎样进行的？这里我将以 LevelDB 为例，分享一下 LevelDB 是怎么落地 LSM 树的。

我们先看看 LevelDB 中的 LSM 树架构，这个和上面的理论 LSM 树有些区别。要理解 LevelDB 中的 LSM 树，我们需要关注两种文件，第一种是内存中的 2 个 MemTable，MemTable 又分为 2 块区域，一块是普通内存 memtable，一块是不可变的内存 Immutable MemTable。另一个文件叫 SSTable，中文翻译是“有序的字符串表”，SSTable 是按照数据的 key 进行排序的，SSTable 位于磁盘上，一共有 7 层（L0 到 L6）。

我们来看看 put 的流程，首先将数据写到普通内存 MemTable 中，当普通内存 MemTable 溢出，就将这个普通内存 MemTable 转化成为不可变内存区域 Immutable MemTable，并再申请一个普通内存 MemTable 处理新的 put 消息。这样一来，不可变内存区域 Immutable MemTable 就不会接收新的消息了，意味着 Immutable MemTable 可以同步磁盘了，同步的方式很简单，Immutable MemTable 会直接放到 L0 层最后一个 SSTable 文件后面，并不奢求跟 L0 层的其他 SSTable 文件合并，也就是说 L0 的数据是无序的、可以冗余的。

从 L1 层开始，每往下一层空间都会比上一层大很多，通常是 10 倍左右。如果第 i 层的数据总大小超过第 i 层阈值限制了，会自动挑选一个文件和第 i+1 的文件合并，这里就和 LSM 树理论一致了。合并完成之后，除了 L0 层，其他每层的数据都是有顺序的，并且层与层之间也是有顺序的，也就是数据完全有序。

查询流程则很简单，先查 MemTable 区域，然后查询 Immutable MemTable 区域，接着从 L0 层的 SSTable 文件开始，逐层遍历。

LSM 树的挑战与优化

尽管 LSM 树在写入性能上具有优势，但它也面临着读写放大的问题。读写放大是指实际的 IO 操作次数超过了用户需求的次数，这会导致资源的浪费。例如，在查询一个数据时，可能需要遍历多个层级的 SSTable，增加了 IO 操作的次数。同样，在写入新数据时，也需要与其他 SSTable 进行合并排序，增加了写入的开销。

为了解决这个问题，LSM 树采用了分层结构，通过分摊计算过程来减少每次压缩操作的资源消耗，每次上一层溢出只需要将溢出的 SSTable 和下一层 SSTable 进行归并计算。此外，每层都会构造布隆过滤器来进一步优化查询性能，减少不必要的磁盘访问。

总结

今天我们聊了 LSM 树的相关知识，我们首先介绍了 LSM 树的原理，其实 LSM 并不是树，而是一个多层的读写流程，LSM 树本身是为了解决快速写入的问题而设计的，LSM 树利用了磁盘的顺序读写能力，通过多层喷泉一样的方式写入数据，层与层之间不断归并计算。

后面我们了解了 LSM 树是如何在 LevelDB 中落地的， LevelDB 利用了 MemTable 和 ImmutableMemTable2 个内存空间来解决并发问题，而一层中的每个文件叫做 SSTable。 SSTable 内部是有序的，并且在同一层中 SSTable 彼此也是有序的。最后，我们讨论了读写放大问题，并提出了一些可能的解决方案。