我们将深入探讨日志结构合并树，也称为LSM Tree：这是许多高度可扩展的NoSQL分布式键值型数据库的基础数据结构，例如Amazon的DynamoDB、Cassandra和ScyllaDB。这些数据库的设计被认为支持比传统关系数据库更高的写入速率。我们将看到LSM Tree如何使它们能够实现宣称的写入速度，并以及如何促进读取。

在开始之前

?首先，我们需要一些背景信息。典型的数据库管理系统（DBMS）由多个组件组成，每个组件负责处理数据存储、检索和管理的不同方面。?其中一个组件是存储引擎，它负责提供可靠的接口，以从/向底层存储设备高效读写数据。?存储引擎的性能在选择数据库时非常重要，因为它是最接近正在使用的存储设备的组件。?用于实现存储引擎的两种流行数据结构是B+树和LSM树。在本文中，我们将覆盖LSM树。

LSM Tree 深度解析

?LSM Tree并不是一个完整的单一数据结构，而是结合了多个数据结构，利用存储层次结构中不同存储设备的响应时间。?由于是追加写入，它提供了高写入速率，同时通过在RAM中维护的索引仍然提供低成本的读取。?与基于B+树的存储引擎相比，它执行原地更新，但在LSM Tree中没有原地更新，这有助于避免随机I/O。在我们深入研究之前，让我们详细讨论在写入密集工作负载中使用基于B+树的数据库存储引擎的缺点。?大多数传统的关系型/SQL数据库使用基于B+树的存储引擎。在这些数据库中，每次写入都必须执行不仅是记录的请求写入，还必须执行对B+树不变式的任何所需的元数据更新，这涉及在B+树结构中移动/拆分/合并节点。

解剖LSM Tree

?LSM Trees凸显了磁盘上的随机I/O存在大量写入开销的问题，而顺序写入则更快，因为磁盘写入头紧挨着上一个记录的位置，且旋转和寻道延迟最小。?“Log-structured”这个术语意味着数据结构像追加日志一样被组织。?“merge”这个术语指的是用于管理结构中数据的算法。其名称中的“tree”一词来自于数据被组织成多个级别，类似于典型计算机中存储层次结构中的设备，其中顶层设备包含较小的数据子集，访问速度更快，而较低级别包含较大的数据段，访问速度较慢。?在最基本的设置中，LSM Tree由两个数据结构组成，充分利用RAM和持久磁盘的优势：LSM树被优化用于快速写入。

1. Memtable

?LSM树的工作方式不同。写入在内存中按到达的顺序进行批处理，存储在称为Mem table的结构中。Mem table按对象-键对进行排序，通常实现为平衡二叉树。

?当Mem table达到一定大小时，它将被刷新到磁盘作为不可变的有序字符串表。一个SS table以有序序列存储键值对。这些写入都是顺序I/O，在任何存储介质上都很快。

2. SS Tables

?新的SS表成为LSM树的最新段。随着更多数据的到来，越来越多的这些不可变SS表被创建并添加到LSM树中，每个都代表传入更改的小时间段。

?由于SS表是不可变的，对现有对象键的更新不会覆盖旧的SS表。相反，将在最新的SS表中添加新条目，这将取代旧的SS表中对象键的任何条目。

LSM Tree上的操作

1. 删除

?删除对象需要特殊处理，因为我们无法标记SS表中的任何内容为已删除。?为执行删除操作，它会在对象键的最新SS表上添加一个称为墓碑的标记。当我们在读取时遇到墓碑时，我们知道该对象已被删除。是的，删除会占用额外的空间。

2. 读取

?为了响应读取请求，我们首先尝试在Mem table中查找键，然后在LSM树中的最新访问表中查找，然后在下一个SS表中查找，依此类推。由于SS表是有序的，查找可以有效进行。

?SS表的积累产生了两个问题。随着SS表数量的增加，查找键将需要越来越长的时间。随着SS表的累积，随着键的更新和墓碑的添加，旧条目变得越来越多。这些会占用宝贵的磁盘空间。?为了解决这些问题，后台运行定期的合并和压缩过程，以合并SS表并丢弃过时或已删除的值。这可以回收磁盘空间并限制读取时必须查找的SS表数量。由于SS表是有序的，因此这个合并和压缩过程是简单而高效的。该方法类似于归并排序算法的合并阶段。

3. 写入

?LSM树会在内存中缓冲传入的写入。当缓冲区填满时，我们对其进行排序并将其刷新到磁盘作为不可变的SS表。?随着更多的缓冲区刷新到磁盘，这会为读取创建问题，因为每个读取都必须搜索这些SS表以执行查找。?为了限制每个读取时必须搜索的SS表数量，LSM树会在后台合并SS表并进行压缩。

4. 压缩策略

?让我们更仔细地看看压缩过程。当合并SS表时，它们会被组织成级别。这是LSM树名称中“树”的部分发挥作用的地方。

?有不同的策略来确定何时以及如何合并和压缩SS表。有两种广泛的策略：大小分层压缩和级别压缩。大小分层压缩针对写入吞吐量进行了优化，而级别压缩则更多地针对读取进行了优化。?压缩可以使SS表数量保持在可管理的水平。SS表被组织成级别，每个级别的SS表随着来自上一级别的SS表的出现而呈指数增长。?压缩会消耗大量I/O。错误调整的压缩可能会使系统饿死，并减慢读取和写入速度。

LSM Tree 的增强

最后，让我们了解一些生产系统中LSM树的标准优化。

?为了查找键，它会在每个级别的SS表上执行搜索。尽管在排序数据上搜索很快，但在所有这些SS表上进行搜索会消耗大量I/O。?许多系统在内存中保留一个摘要表，其中包含每个级别的每个磁盘块的最小/最大范围。这允许系统跳过那些键不在范围内的磁盘块上的搜索，从而节省大量随机I/O。?另一个可能昂贵的问题是查找不存在的键。这将需要查找所有级别的所有合格块。大多数系统在每个级别上保留了一个Bloom过滤器。?Bloom过滤器是一种空间高效的数据结构，如果键不存在，则返回确定的“不存在”，如果键可能存在，则返回“可能存在”。这允许系统跳过一个级别，如果键在那里不存在，从而大大减少了需要的随机I/O数量。

LSM Tree 的缺点

?LSM树的主要缺点是压缩的成本，它影响读取和写入性能。由于涉及数据的压缩/解压缩、复制和比较，压缩是LSM树中资源占用最高的阶段。?所选的压缩策略必须试图最小化读取放大、写入放大和空间放大。?LSM树的另一个缺点是执行读取在最坏情况下会变慢。由于是追加方式，读取必须在最低级别的SSTable中进行搜索。这涉及到寻找的文件I/O，这会导致读取变慢。