LSM树学习笔记

LSM-Tree即log structured merge tree。LSM-Tree是许多高度可扩展的NoSQL分布式键值类型数据库（如亚马逊的DynamoDB、Cassandra和ScyllaDB）的基础数据结构。众所周知，这些数据库在设计上支持的写入率远远超过传统关系数据库所能提供的写入率。

几乎所有NoSQL数据库都使用LSM树的变体作为底层存储引擎，因为它可以实现快速写入吞吐量和主键快速查找。了解LSM树的工作原理将为在调试使用这些数据库时遇到的任何问题时提供更好的帮助。例如，为了调优Cassandra满足特定工作负载，需要了解并选择不同的压缩策略，这是LSM树数据管理生命周期的关键阶段。

随着存储设备物理设计的进步，从旋转磁盘到NAND闪存SSD，以及最近的NVDIMM（如 Intel Optane），LSM 树也越来越受欢迎。传统的存储引擎（基于B+树）是专为旋转磁盘设计的，写入速度慢，并且只能提供基于块的寻址。然而，当今的应用是写入密集型的，会产生大量数据。因此，有必要重新考虑DBMS中现有存储引擎的设计。英特尔Optane 和其他NVMs等新型存储设备具有按字节寻址能力，速度比固态硬盘更快。这引发了一些探索，如Nova，它是一种用于持久化内存的日志结构文件系统。

除此之外，学习LSM树是进入复杂的数据库存储引擎内部世界的最快途径。与基于B+树的存储引擎相比，它们的设计非常简单。因此，如果你对NoSQL数据库如何存储数据感兴趣，或者正在尝试实现一个存储引擎，请继续阅读！

设计一个简单的键值数据库

如果不采用传统的SQL和关系型方法，让你从头开始设计一个非常简单的数据库，支持以键值对的形式插入数据，你会怎么做呢？最简单的方法是使用文件作为存储单元。每次收到键和值的输入请求时，就将键值追加到文件中：/var/local/data.db

k1: v1
k2: v2
...
...
...

在对给定键k提出获取请求时，系统会扫描并查找文件中的最新条目，然后返回相关值作为响应，如果键不存在，则返回空值。采用这种设计，写入速度非常快，因为它只是对文件末尾进行追加，但读取的最坏情况时间复杂度为 O(n)。在此基础上添加一个REPL接口，使用HTTP或GRPC等通信协议，你就拥有了一个非常简单的数据库服务器，尽管这在现实世界中并不实用。

虽然我们的简单数据库无法处理删除、去重和填满磁盘空间等棘手的情况，但这种简单的设计是现实世界中许多NoSQL数据库的核心。为了使这种设计具有实际用途，现实世界中的数据库通常会添加对事务、崩溃恢复、查询缓存、垃圾回收等功能的支持。它们还使用自定义数据结构，利用存储层次的访问延迟，并混合使用内存和磁盘结构，以支持高效的读/写性能。

这种只对记录文件进行追加的想法并不新鲜，已有存储设备的文件系统使用这种设计作为其存储管理逻辑。它们被称为日志结构文件系统。日志结构文件系统最早出现在20世纪90年代（论文）。后来人们发现，同样的想法和设计也可以用作数据库的存储引擎。

LSM树背后的动机

要了解LSM树，首先要了解日志结构文件系统（以下简称 LFS）产生的原因，因为LSM树在很大程度上是受其启发而产生的。日志结构文件系统由Rosenblum和Osterhout于1991年提出。虽然这一想法以LSM树的形式出现在数据库领域，但在文件系统领域并未得到广泛采用。

20世纪90年代，磁盘带宽、处理器速度和内存容量都在快速增长。磁盘带宽：是指传输的字节总数除以从第一次服务请求到最后一次传输完成之间的总时间。

随着内存容量的增加，现在可以在内存中缓存更多的内容。因此，大部分读取工作量都被操作系统页面缓存所吸收。然而，由于旋转磁盘中物理R/W磁头的寻道和旋转延迟，磁盘寻道时间仍然很高。旋转磁盘需要移动到指定磁道和扇区才能写入数据。在随机I/O的情况下，由于读写操作频繁，物理磁头的移动时间会超过写入数据的时间。

从LFS的论文来看，传统文件系统利用旋转磁盘写入新数据只占用磁盘原始带宽的5-10%，而LFS则占用65-75%（其余用于压缩）。传统文件系统在多个地方写入数据：数据块、恢复日志和对任何元数据的就地更新。文件系统的唯一瓶颈是写入。因此，文件系统需要减少写入，减少随机I/O。LFS的想法是，为什么不把所有内容（甚至是元数据）都写入一个日志中，并将其视为单一的真相源呢？

日志结构文件系统将整个磁盘视为日志。数据块连同其元数据（inodes）以只追加的方式写入磁盘。在追加到磁盘之前，写入的数据会在内存中缓冲，以减少每次写入时磁盘寻道的开销。当写入的内容达到一定大小时，就会以段（64kB-1MB）的形式追加到磁盘。段包含数据块，其中包含对多个文件及其 inodes 的更改。同时，每次写入时，都会更新inode映射（imap），以指向新写入的inode编号。在每次写入时，imap也会追加到日志中，因此只需一次寻道即可完成。

我们不会对LFS进行太深入的讨论，明白其中的含义即可。LSM Tree抓住了日志文件中仅追加式更新和写缓冲的理念，已被大量写密集型键值数据库系统用作存储后端。既然我们已经知道了它们的存在，那就让我们更仔细地了解一下它们吧。

LSM树深度挖掘

LSM Tree是一种数据结构，它将数据存储限制为只能进行追加操作，而数据存储只是一个包含完全有序的键值对的日志。排序顺序由键决定，键可以是任意字节序列。值也可以是任意字节序列。例如，在Cassandra的数据模型中，一个列族（类似于关系数据库中的表）包含一个行键（键）和任意键值序列（值），任意键值序列的cardinality是变化的。由于只能追加，这意味着对数据存储的任何修改，无论是写入、更新还是删除，都只是追加到日志的末尾。这听起来可能很不直观，但我们会看到这样的设计是如何实现的，以及它带来了哪些挑战。

为了利用存储层次结构，日志的实际物理实现变得更加复杂，日志通常在多个文件之间按segment划分，以便更有效地读取。

LSM Tree整体上不是一个单一的数据结构，而是结合了多个数据结构，利用了存储层次结构中不同存储设备的响应时间。由于只进行追加，它在提供高写入率的同时，还能通过在内存中维护的索引提供低成本读。与执行in-place更新的基于B+树的存储引擎相比，LSM树中没有in-place更新，这有助于避免随机I/O。在深入探讨之前，让我们先阐述一下在写密集型工作负载中使用基于B+树的数据库存储引擎的缺点。

大多数传统关系/SQL数据库都使用基于B+树的存储引擎。在这些数据库中，每次写不仅要执行写请求写入的记录，还要对B+树执行任何必要的元数据更新，这涉及到B+树结构中节点的移动/拆分/合并。因此，每次写入B+树结构时，写入放大率都会增加，从而导致写入速度变慢。

写入放大（WA）

写放大是要写入的逻辑数据量与写入底层存储引擎的实际物理数据量之比。该值被用作选择存储设备或引擎的评估标准。WA值越小，意味着写入速度越快。

在旋转磁盘上，由于写磁头需要执行大量的寻道操作，因此WA值肯定会很明显，但在固态硬盘上就不那么明显了。但即使在固态硬盘上，每次写入的I/O数量增加仍会降低固态硬盘的使用寿命，因为它们在使用期内只能承受有限数量的写入。

固态硬盘对页面更新采用"写入时复制"语义，任何修改都会首先擦除原始数据块，然后在新数据块中重写数据，之后再指向新写入的数据块。然后，固态硬盘闪存控制器会对旧块进行垃圾回收，这也会增加写入成本。因此，顺序写入对旋转磁盘和固态硬盘都有好处。

注：以上观点并不是说关系数据库不好，不应该使用，它只是适合读取量大的工作负载。尽管如此，还是应该根据应用中的数据模型和工作负载来选择数据库。采用用例和基准测试驱动的解决方案总是比技术驱动的解决方案更好。

剖析LSM树

LSM树凸显了这样一个问题：磁盘上的随机I/O有大量写入开销，而顺序写入要快得多，因为磁盘写磁头就在上次写入记录的位置旁边，旋转和寻道延迟极小。

LSM的论文中，将LSM树解释为一种抽象数据结构，同时还解释了使用分层存储架构的动机。日志结构一词是指数据的结构是一个接一个的，就像一个只能追加的日志。

合并(merge)一词指的是结构中管理数据的算法。树一词名称来源于这样一个事实，即数据被组织成多个层次，类似于典型计算机存储层次结构中的设备，其中最高层设备保存较小的数据子集，访问速度较快，而较低层设备保存较大的数据段，访问速度较慢。在裸机环境中，LSM Tree由两种数据结构组成，它们同时使用内存和持久化磁盘，以发挥各自的优势。

内存表(Memtable)

内存表是LSM树接收到的每个读写操作的第一个接触点。Memtable是一种内存结构，客户端传入的数据被刷新到磁盘之前，数据都是被缓存在这里。当Memtable达到一定大小的阈值（LevelDB 中约为4MB）时，就会被刷盘。不过，阈值大小因LSM树用于哪个数据库而异，同时要考虑其他组件的内存使用情况。Memtable使用何种数据结构通常取决于性能要求，但必须具备一个特性，即它应能对其内容进行排序迭代。我们可以天真地使用向量，也可以使用更高效的平衡二叉树，如AVL树、红黑树或Skiplist（在 LevelDB 中使用）。Memtable可容纳的数据量受内存限制，当超过设定的阈值大小时，Memtable的所有内容都必须写入一个文件，其中的项按键排序，并且必须创建一个新的Memtable来接收写入的内容。这些持久化文件被称为 SSTables。

SSTable

Sorted String table (SSTable)是从Google的BigTable借来的概念，是一种磁盘格式（文件），其中按排序顺序刷新Memtable中的键-值条目。当Memtable达到其容量或发生压缩时，就会创建SSTable文件。SSTable中的数据按排序存储，以提高读取效率。随着时间的推移，由于对Memtable的频繁写入，磁盘上可能会有多个SSTable。这些SSTable会被不断重新组织和压缩成不同的级别，这些级别通常被命名为0级到N级。Memtable的正下方（逻辑上）级别是0级，可能包含键值重叠的SSTable。这意味着在第0层可能有两个SSTable（比如 S1 和 S2），其中S1可能包含范围为[a..f]的键，而S2可能包含[c..h]的键，重叠的键为（c,d,e,f,g,h）。这是因为0级的SSTables是Memtable内容的纯转储。任何键的重复数据删除都会作为后台任务延迟进行。第1级及以上的SSTable文件在设计上只包含不重叠的键。尽管结构非常简单，但SSTable架构却能容纳和提供PB级的数据，谷歌在其分布式数据库项目中使用SSTable就证明了这一点。为了提高效率，数据库系统在SSTable的基础上做了一些改进。

SSTable的增强

在实际应用中，SSTable文件还增加了一个SSTable摘要和一个索引文件，作为从SSTable读取数据时的第一个接触点。在这种情况下，SSTable被分成数据文件、索引文件和摘要文件（在Casssandra和ScyllaDB中使用）。

SSTable数据文件

SSTable数据文件通常以特定格式编码，并包含任何所需的元数据，键值条目以块形式存储。这些块也可能被压缩，以节省磁盘空间。不同级别可能使用不同的压缩算法。它们还在每个块上使用校验和，以确保数据完整性。

SSTable索引文件

索引文件按顺序列出数据文件中的键，并给出每个键在数据文件中的位置。

SSTable摘要文件

SSTable摘要文件保存在内存中，提供键的采样，以便在索引文件中快速查找。可以把它看作是SSTable索引文件的索引。要搜索一个特定的键，首先要查看摘要文件，以找到可以找到该键的一个较小的位置范围，然后将该特定偏移加载到内存中。

SSTable如何提供快速读取？

如果我们所做的只是组合和合并SSTable，我们的SSTable在较低层次很快就会变得很大。从这些文件读取数据时，必须遍历许多键才能找到请求的键。在最低级的SSTables中，线性扫描是最糟糕的。

为了降低线性时间复杂度，在文件上建立索引是一个显而易见的解决方案。我们可以在内存中建立一个索引（哈希表），其中包含键到文件中字节偏移量的映射。这样，我们只需在文件中进行O(1)次查找即可。但如果把所有键都放在内存中，最终会占用大量内存。

实际的实现方法是，为每个SSTable维护一个稀疏索引，内存中只包含的键的子集，并利用二进制搜索快速跳过范围，缩小搜索空间。每次发生压缩时，稀疏索引也会保持更新，以便读取检索更新的数据。就SSTable格式的实现而言，稀疏索引通常编码在文件末尾或作为单独的索引文件。读取SSTable时，稀疏索引会被加载到内存中，然后用于查找任何读取请求所需的键。许多实际应用还包括对每个SSTable使用Bloom过滤器和稀疏索引，以便及早排除不存在键的情况。此外，实现方法还可以在内存中对SSTable进行内存映射，这样就可以在不接触磁盘的情况下进行查找。在SSTable上还做了很多其他优化，使其性能与B+树相当。

既然我们已经了解了LSM树的核心架构，下面我们就来讨论一下LSM树支持的核心操作及其工作原理。

对LSM树的操作

要适合在键值数据库中使用，LSM树至少必须支持以下API：

在LSM树中写入/更新数据

LSM树中的所有写入都在内存中缓存，并首先进入Memtable。Memtable配置了一个阈值，达到阈值后Memtable中的所有内容都会被写入一个文件，并被标记为0级SSTable的一部分。然后，该文件被标记为不可变的，不能修改。

在实际实现中，写入之前还会将条目追加到写前日志（WAL：Write Ahead Log）文件中，以防止崩溃并确保持久性。如果数据库崩溃时仍在Memtable中保存键值，WAL文件可以让我们在下次重启时重新构建并恢复Memtable中未提交的条目。当达到Memtable阈值时，WAL也会被刷新并被新的WAL替换。

对于已经存在的键，不会原地更新键值。相反，对给定键值的更新只会将新键值追加到日志中。数据的旧值会在稍后阶段通过压缩移除。

删除LSM树中的数据

当你第一次发现LSM Tree不会从日志中原地删除数据时，你可能会觉得它不切实际。这是因为这样做需要随机I/O，从而增加了写入性能的开销。

由于LSM树必须保持只追加式更新，以保持写入性能，因此在LSM树中删除数据与在日志中追加键值条目是一样的，但会写入一个被称为"tombstone"的特殊字节序列作为值。它可以是任何字节序列，但必须是唯一的，足以与其他可能的值区分开来。现有的旧值随后会在压缩阶段删除。

读取LSM树中的数据

在LSM树中的所有读取都是首先从Memtable中进行的。如果在Memtable中找不到键，就会在最近的L0层中查找，然后是L1、L2等，直到找到键或返回空值为止。由于SSTables已经排序，我们可以对文件执行二叉搜索，快速缩小可能找到键的范围。

通常，L0中的SSTables文件可能横跨整个键空间。这样，在最坏的情况下，读必须访问几乎所有文件，才能为来自L0的读取提供服务。为了减少读取所需的跳转次数，L0中的文件有时会被合并并从L0移到 L1。这有助于减少文件的多次I/O。在实际实现中，还使用了稀疏索引，它只在内存中保留每个SSTable的键值范围，有助于减少读取键值所需的扫描次数。

除此之外，还在每个SSTable上使用了Bloom过滤器，以便在文件中不存在键时提前退出。这使得检查键是否存在的查询变得非常快速。

在上述所有操作过程中，我们的日志必然会增长到非常大的规模，因为我们所做的只是追加条目，而不会删除重复/删除的旧条目。

压缩
随着时间的推移，磁盘上SSTable文件的数量最终会增加，因为Memtable满了后，需要不断刷新。在这种情况下，当读取给定的键时，LSM树在最坏的情况下将不得不查看多个SSTable文件，这将导致每次访问新文件时都要进行大量随机I/O。

例如，在Cassandra中，存储的值有很多列。在t1时刻对键k的更新可能会添加4列值（k -> (v1, v2, v3, v4)）。在t2时候，同一个键k可能会将第4列值更新为其他值，并删除第2列值（k -> (v1,v3,v4_1)）。在之后的t3时刻，需要读取该键，cassandra将需要聚合来自上述两次更改的更新，以建立k的更新值。 现在，如果给定键k的这些更改分布在多个SSTable文件中，读取时就需要执行大量随机I/O来检索更新值。这会降低读取性能，因此需要尽可能将这些更新合并到一个文件中。这可以通过一个名为"压缩"的阶段来实现。

除了减少多次I/O外，压缩还能帮助解决另一个问题，即某个键可能有多个旧条目或已删除的tombstone条目，最终占用了磁盘空间。当以后对现有键进行删除或更新时，就会出现这种情况。因此，为过时和已删除的键回收磁盘空间就变得非常重要，而压缩的方法就是在创建新的SSTable文件时丢弃旧的或已删除的条目。

在实现方面，使用专门的后台线程来执行压缩。压缩可以通过调用应用程序接口手动完成，也可以在满足特定条件时作为后台任务自动完成。压缩过程可以是同步的，也可以是异步的，这取决于为LSM树存储配置了哪些一致性保证。LSM树的读写性能在很大程度上受压缩方式的影响。作为一种优化，在一个给定的时间点（如在 RocksDB 中）可能有多个专门的压缩线程在运行，以压缩SSTables文件。压缩线程还负责在合并后更新稀疏索引，以指向新SSTable文件中键的新偏移量。每当第0级文件的大小达到配置阈值时，就会提取一个或多个文件，并与下一级（第 1 级）的所有重复键合并。从第1级到第2级也是如此，当这些级别达到其容量时也是如此。现在，根据不同的压缩策略，确定层级何时满的度量标准也不同。根据需求使用不同的压缩策略，这些策略决定了各级SSTables的形状。

压缩策略
压缩策略必须选择压缩哪些文件以及何时压缩。有许多不同的压缩策略会影响LSM树的读/写性能和空间利用率。生产系统中常用的一些压缩策略包括：
·大小分层压缩策略(Size-tiered compaction stratey):这是一种写优化压缩策略，是 ScyllaDB和Cassandra使用的默认策略。但它的空间放大率较高，因此开发了其他压缩策略，如分级压缩。
`分级压缩策略(Leveled compaction strategy ):比大小分级策略有所改进，可减少读取放大和空间放大。这是LevelDB的默认策略。
`时间窗口压缩策略(Time windowed compaction strategy):用于时间序列数据库。在该策略中，使用一个时间窗口来触发压缩。
上述并非唯一的策略，各种系统都开发了自己的策略，例如ScyllaDB中的混合压缩策略。

LSM树的缺点
任何技术的引入都会带来一系列折衷。LSM树也不例外。
LSM树的主要缺点是压缩成本高，影响读写性能。压缩是LSM树最耗费资源的阶段，原因是压缩/解压缩数据、复制和比较过程中涉及的键。所选的压缩策略必须尽量减少读取放大、写入放大和空间放大。
LSM树的另一个缺点是执行压缩所需的额外空间。这在大小分层压实策略中显而易见，因此需要使用其他压实策略，如分层。
在最糟糕的情况下，LSM树还会导致读取速度变慢。由于LSM树只具有追加的性质，因此读取时必须在SSTable的最底层进行搜索。在搜索过程中会涉及文件 I/O，从而导致读取速度变慢。

尽管存在这些缺点，但LSM树已在很多数据库系统中使用，并已成为很多存储场景中事实上的可插拔存储引擎。

LSM树的发展

许多NoSQL数据库都使用LSM树作为存储引擎。它们还被用作嵌入式数据库、以及场景简单但需要健壮的数据持久化的功能的场合，比如搜索引擎的索引。

最早使用LSM树的项目之一是Lucene搜索引擎（1999 年）。谷歌 BigTable（2005 年）是一个分布式数据库，在其底层设计中也使用了LSM树，并用于为谷歌抓取和分析保存PB级数据。BigTable的作者随后发现，BigTable的"tablet"（存储引擎节点）设计可以抽象出来，用作键值存储。

在此基础上，LevelDB（2011 年）应运而生，它由同一作者设计，使用LSM树作为底层数据结构。这催生了可插拔存储引擎和嵌入式数据库。大约在2007年的同一时间，亚马逊推出了DynamoDB，它底层使用相同的LSM树结构和无主分布式数据库设计。

Dynamo DB激发了Cassandra（2008 年）的设计灵感，Cassandra是一种开源分布式NoSQL数据库。Cassandra又启发了ScyllaDB（2015 年）等。时间序列数据库InfluxDB（2015 年）也使用了基于LSM树的存储引擎，称为时间结构合并树。

受LevelDB的启发，Facebook分叉了LevelDB并创建了RocksDB（2012 年），这是一种高并发、更高效的键值存储，使用多线程压缩来提高读写性能。最近，Bytedance对RocksDB进行了改进，也发布了一款名为terakdb的键值存储工具，Sled是Rust中的另一种嵌入式键值存储，它使用B+树和LSM 树（Bw 树）的混合架构。这些都属于嵌入式数据存储的范畴。