原文：yetanotherdevblog.com/lsm/

日志结构的合并树（log-structured merge-tree LSM 树）通常是在处理大量写任务时使用的数据结构。通过顺序写来优化写入路径。 LSM 树是许多数据库（包括 BigTable, Cassandra, Scylla,和 RocksDB）背后的核心数据结构。

排序字符串表

LSM 树使用排序字符串表（Sorted Strings Table 简称 SSTable）的格式保存到磁盘。如名称所示，SSTables 是一种用于存储键-值对的格式，其中键按有序排列。SSTable 将由多个名为段（Segments）的有序文件组成。一旦将这些数据段写入磁盘后，就是不可变的。简化示例如下：

我们可以看到，每个段中的键-值对都是按键排序的。接下来看看什么是片段以及它是如何生成的。

写数据

回想一下，LSM 树只执行顺序写入。我们可能想知道，当值以任意顺序写入时，如何以有序格式的顺序写入数据？这可以通过使用内存中的树结构来解决。通常被称为内存表（memtable），但底层数据结构通常是某种形式的排序树，如红黑树。当写入数据时，将添加到此红黑树中。

我们的写入将存储在这个红黑树中，直到树达到预定义的大小。一旦红黑树有足够的条目，它就会按有序的顺序作为磁盘上的一个段刷新到磁盘。这就允许我们将段文件顺序写入，即使插入时的顺序是不固定的。

读数据

那么，如何在 SSTable 中找到对应的值呢？一种简单的方法是扫描数据段来查找所需的键。从最新的段开始，扫到最旧的段，直到找到我们想要的键。这意味着我们会优先检索最近写入的键。一个简单的优化是在内存中保存sparse index 稀疏索引。

我们可以使用这个索引来快速找到目标键之前和之后的值的偏移量。现在，只需根据这些界限扫描每个段文件的一小部分。我们考虑一个场景，假如我们想要在上面的段中查找键 dollar。我们可以对稀疏索引执行二分搜索，发现 dollar 介于 dog 和 downgrade 之间。现在，只需从偏移量 17208 到 19504 进行扫描，即可找到该值（或确定该值是否丢失）。

这是一个很好的改进，但是如果查找不存在的记录呢？仍然需要循环遍历所有段文件，并且找不到目标键。布隆过滤器可以帮助我们解决这个问题。布隆过滤器是一种节省空间的数据结构，它可以告诉我们数据中某个键是否存在。我们可以在写入数据时将数据添加到过滤器中，并在读取开始时对其进行检查，以便有效地响应不存在的数据的请求。

压缩

随着时间的推移，系统在运行时会积累越来越多的段文件。这些段文件需要清理和维护，以防止段文件的数量失控。这个过程称为压缩。压缩是一个将连续旧段合并到新段的后台进程。

在上面的示例中可以看到，segment 1 和 segment 2 都存有 dog 键的值。较新的段包含了最新的写入值，因此 segment 2 中的值将结转到 segment 4 中。一旦压缩进程为输入段写入了新段，旧段文件将被删除。

删除数据

我们已经讨论了读数据和写数据，但是如何删除数据呢？当段文件被认为是不可变的时，如何从 SSTable 中删除数据呢？删除实际上遵循与写入数据完全相同的路径。每当收到删除请求时，都会为该键写入一个名为 tombstone（也就是标记为删除的 key）的唯一标记。

上面的示例显示，键 dog 在过去的某个时候的值是 52，但现在它有了一个删除标记。这表示如果我们收到键为dog 的请求，那么会返回一个响应，表明该键不存在。这意味着删除后实际上还会占用磁盘空间，这可能会让许多开发人员感到惊讶。最终，该删除标记将被压缩，这样该值就不再存在于磁盘上。

结论

我们现在了解了 LSM 树存储引擎的工作原理：

1. 写入数据存储在内存树（也称为内存表）中。任何支持的数据结构（布隆过滤器和稀疏索引）也会在必要时更新。
2. 当此树变得足够大时，它会被刷新到磁盘，键按有序排列。
3. 当读取数据时，先检查布隆过滤器。如果过滤器表示该值不存在，则返回客户端没有此键。如果过滤器表示该值存在，则我们以新到旧的顺序迭代段文件。
4. 对于每个段文件，我们检查稀疏索引，并扫描目标关键字的偏移量，直到找到关键字。一旦在段文件中找到该值，将立即返回。