阅读 1127

理解 LSM 树:写入密集型数据库的秘诀

原文: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 介于 dogdowngrade 之间。现在,只需从偏移量 17208 到 19504 进行扫描,即可找到该值(或确定该值是否丢失)。

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

压缩

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

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

删除数据

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

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

结论

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

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