ACM通信

实践

现代存储系统背后的算法

阿历克斯彼得罗夫
ACM通信，2018年8月，第61卷第8期，38-44页
10.1145 / 3209210
评论

应用程序处理的数据量在不断增长。随着这种增长，扩展存储变得更加具有挑战性。每个数据库系统都有自己的权衡。理解它们是至关重要的，因为它有助于从如此多的选择中选择正确的。

每个应用程序在读写工作负载平衡、一致性要求、延迟和访问模式方面都是不同的。熟悉数据库和存储内部结构有助于做出架构决策，有助于解释系统为何以某种方式运行，有助于在出现问题时排除故障，并针对您的工作负载微调数据库。

对一个系统进行全方位优化是不可能的。在理想的情况下，应该有数据结构保证在没有存储开销的情况下获得最佳的读写性能，但当然，在实践中这是不可能的。

本文将深入研究在大多数现代数据库中使用的两种存储系统设计方法——读优化b树^3.和写优化LSM(对数结构合并)树⁸并描述它们的用例和权衡。

回到顶部

b树

b树是一种流行的读优化索引数据结构和二叉树的泛化。它们有许多变体，在许多数据库中使用(包括MySQL InnoDB⁷和PostgreSQL¹⁰)，甚至文件系统(HFS+，¹在ext4 HTrees⁶)．B-tree中的B代表拜耳，原始数据结构的作者，或波音公司他当时在那里工作。

在二叉树中，每个节点都有两个子节点(称为左子节点和右子节点)。左子树和右子树分别保存小于和大于当前节点键的键。为了将树深度保持在最小值，二叉树必须保持平衡:当向树中添加随机排序的键时，树的一侧最终会比另一侧更深，这是很自然的。

重新平衡二叉树的一种方法是使用所谓的旋转:重新排列节点，将较长的子树的父节点推到其子树的下方，并向上拉该子节点，有效地将其置于其父树的位置。图1是用于二叉树平衡的旋转示例。在左边，二叉树在加入节点2后是不平衡的。为了平衡树，节点3被用作一个枢轴(树围绕它旋转)。然后节点5(以前是根节点和3的父节点)成为它的子节点。旋转步骤完成后，左侧子树的高度减少1，右侧子树的高度增加1。树的最大深度减小了。

图1。用于二叉树平衡的旋转例子。

二叉树作为内存中的数据结构最有用。由于平衡(需要将所有子树的深度保持在最小值)和较低的扇出(每个节点最多有两个指针)，它们在磁盘上不能很好地工作。b -树允许每个节点存储两个以上的指针，并且通过将节点大小匹配到页面大小(例如，4KB)，可以很好地与块设备一起工作。现在的一些实现使用更大的节点，跨越多个页面大小。

b -树具有以下性质:

• 排序。这允许顺序扫描并简化查找。
• 自动平衡。在插入和删除过程中不需要平衡树:当一个b -树节点满时，它被一分为二，当相邻节点的占用率低于某个阈值时，节点被合并。这也意味着叶节点与根节点之间的距离相等，在查找过程中可以使用相同的步骤来定位叶节点。
• 保证对数查找时间。这使得b树成为数据库索引的一个很好的选择，其中查找时间非常重要。
• 可变的。插入、更新和删除(以及后续的拆分和合并)在磁盘上执行。为了使就地更新成为可能，需要一定的空间开销。b -树可以组织为聚集索引，其中实际数据存储在叶节点上，或者存储为具有非聚集b -树索引的堆文件。

本文讨论B+树，⁵b树的现代变体，通常用于数据库存储。B+树不同于原来的B-树^3.因为它有额外级别的链接叶节点保存值，并且这些值不能存储在内部节点上。

b树的解剖。让我们首先仔细看看b -树构建块，如图所示图2．b -树有几种节点类型:根、内部和叶。根(顶部)是没有父节点的节点(也就是说，它不是任何其他节点的子节点)。内部节点(中间)有父节点和子节点;它们将根节点与叶节点连接起来。叶节点(底部)携带数据，没有子节点。图2描述了一个分支因子为4的b树(4个指针，内部节点有3个键，叶子上有4个键/值对)。

图2。b树的例子。

b -树具有以下特征:

• 分支系数:数量(N)的子节点指针。与指针一起，根节点和内部节点维持到n - 1钥匙。
• 居住:节点当前持有多少个指向子项的指针，超出了可用的最大值。例如，如果树分支因子是N，节点当前处于保持状态N / 2指针，入住率是50%。
• 高度:b树的层数，表示在查找过程中必须遵循多少个指针。

树中的每个非叶节点都坚持到n - 1键(索引项)，将树分隔为N可通过遵循相应指针定位的子树。指针我从一个条目K_我指向一个子树，其中所有的索引项都是K_我－1< =K_搜索>K_我(K是一组键)。第一个和最后一个指针是特殊情况，指向所有项都小于或等于的子树K₀对于最左边的子结点，或大于K_N在最右边的孩子的情况下。叶节点还可以保存指向同一层上的上一个节点和下一个节点的指针，形成兄弟节点的双链表。所有节点中的键总是排序的。

查找。在执行查找时，搜索从根节点开始，然后按照内部节点递归地向下到叶级。在每一层上，通过跟踪子指针，搜索空间被缩小到子树(该子树的范围包括搜索值)。图3显示了b -树中的查找，只进行了一次从根到叶的传递，遵循两个键之间的指针，其中一个键大于(或等于)搜索项，而另一个键小于搜索项。当执行点查询时，定位叶节点后搜索就完成了。在范围扫描期间，遍历找到的叶的键和值，然后遍历兄弟叶的节点，直到到达范围的末端。

图3。单一root-to-leaf通过。

就复杂性而言，b树可以保证日志（n)查找，因为在节点中查找键是使用二进制搜索执行的，如图4．二分搜索很容易解释为搜索字典中以某个字母开头的单词，其中所有单词都是按字母顺序排序的。首先你从字典的正中间打开。如果搜索的字母按字母顺序“小于”(出现在比打开的字母早)，则在字典的左半部分继续搜索;否则，你就在右半部分继续。你不断地将剩下的页面范围缩小一半，并选择要遵循的边，直到找到所需的字母。每一步都将搜索空间减半，使查找时间变成对数。b树中的搜索具有对数复杂度，因为在节点级别上键是排序的，并且执行二进制搜索是为了找到匹配。这也是为什么保持整个树的高占用率和统一是很重要的。

图4。b树的二叉搜索。

插入、更新和删除。执行插入时，第一步是定位目标叶。为此，使用了前面提到的搜索算法。定位目标叶之后，键和值被附加到它。如果叶没有足够的空闲空间，这种情况称为溢出，必须将叶一分为二。这是通过分配一个新的叶，将一半的元素移到其中，并将指向新分配的叶的指针附加到父节点来实现的。如果父级也没有空闲空间，则也会在父级执行拆分。操作将继续进行，直到到达根目录。当根节点溢出时，将在新分配的节点之间拆分其内容，并覆盖根节点本身，以避免重新定位。这也意味着树(及其高度)总是通过拆分根节点来增长。

LSM-trees。日志结构的合并树是一种不可变的常驻磁盘的写优化数据结构。在写操作比检索记录的查找更频繁的系统中，它最有用。lsm树得到了越来越多的关注，因为它们可以消除随机插入、更新和删除。

lsm -树的解剖。为了允许顺序写，lsm -树在内存驻留表中进行批量写和更新(通常使用允许对数时间查找的数据结构实现，例如二叉搜索树或跳过列表)，直到其大小达到阈值，然后将其写入磁盘(此操作称为冲洗)．检索数据需要搜索树中所有驻留在磁盘上的部分，检查内存表，并在返回结果之前合并它们的内容。图5显示了一个LSM-tree的结构:一个内存驻留表，用于写入，磁盘驻留sstable用于读取。只要内存表足够大，就将其排序的内容写入磁盘。读取操作同时访问磁盘表和内存表，需要一个合并进程来协调数据。

图5。LSM树的结构。

排序字符串表。许多现代的lsm树实现(如RocksDB和Apache Cassandra)将磁盘驻留表实现为排序字符串表(Sorted String table, SSTable)，因为它们简单(易于写入、搜索和读取)和合并属性(在合并期间，源SSTable扫描和合并结果写入是顺序的)。

SSTable是驻留在磁盘上的有序不可变数据结构。从结构上讲，SSTable被分为两部分:数据块和索引块，如图6．数据块由按顺序写入的惟一键/值对组成，按键排序。索引块包含映射到数据块指针的键，指向实际记录的位置。索引通常使用为快速搜索而优化的格式来实现，例如b -树，或者使用哈希表来进行点查询。SSTable中的每个值项都有一个与之关联的时间戳。这指定了插入和更新的写时间(它们通常是不可区分的)和删除的删除时间。

图6。SSTable的结构。

sstable有一些很好的属性:

• 点查询(即按键查找值)可以通过查找主索引快速完成。
• 扫描(即迭代指定键范围内的所有键/值对)可以通过从数据块中按顺序读取键/值对来有效地完成。

SSTable表示一段时间内所有数据库操作的快照，因为SSTable是由冲洗从驻留在内存中的表进行处理，该表在此期间作为针对数据库状态的操作的缓冲区。

查找。检索数据需要搜索磁盘上的所有sstable，检查内存驻留表，并在返回结果之前合并它们的内容。读取过程中的合并步骤是必需的，因为搜索的数据可以驻留在多个sstable中。

合并步骤也是必要的，以确保删除和更新工作。在lsm树中删除插入占位符(通常称为墓碑)，指定哪个键被标记为删除。类似地，更新只是带有后一个时间戳的记录。在读取过程中，被删除遮蔽的记录将被跳过，并且不返回给客户机。更新过程中也会发生类似的情况:在两个具有相同键的记录中，只返回时间戳较晚的记录。图7如图所示，Alex的记录是用时间戳100写的，用时间戳200更新的;约翰的记录被删除了。其他两个条目按原样处理，因为它们没有阴影。

图7。合并步骤的示例。

为了减少搜索的SSTable的数量并避免为搜索的键检查每个SSTable，许多存储系统采用了一种称为Bloom Filter的数据结构。²这是一种概率数据结构，可用于测试一个元素是否是集合的成员。它可以产生假阳性匹配(即，声明元素是set的成员，而实际上它并不存在于set中)，但不能产生假阴性(即，如果返回的是阴性匹配，则保证该元素不是set的成员)。换句话说，使用Bloom Filter来判断键“可能在SSTable中”还是“肯定不在SSTable中”。查询期间将跳过Bloom Filter已返回负匹配的sstable。

LSM维护。由于SSTables不可变的，它们是按顺序编写的，不为就地修改保留空白空间。这意味着插入、更新或删除操作将需要重写整个文件。所有修改数据库状态的操作都在内存驻留表中“批处理”。随着时间的推移，驻留在磁盘上的表的数量将会增长(位于多个文件中的相同键的数据、同一记录的多个版本、被删除遮蔽的冗余记录)，而读取的开销将继续增加。

为了减少读的成本，协调影子记录所占用的空间，并减少驻留在磁盘上的表的数量，lsm -树需要一个压实从磁盘读取完整的sstable并合并它们的进程。因为sstable是按键排序的，而且压缩工作类似于归并排序，因此该操作非常高效:从多个源依次读取记录，合并输出也可以立即按顺序添加到结果文件中。归并排序的优点之一是，它甚至可以有效地合并内存不适合的大文件。结果表保留了原始sstable的顺序。

在此过程中，合并的sstable被丢弃，并被它们的“压缩”版本所取代，如图8．压缩使用多个sstable并将它们合并为一个。一些数据库系统将相同大小的表逻辑地分组到相同的“级别”，并在特定级别上有足够多的表时启动合并过程。压缩之后，必须处理的sstable数量减少，从而使查询更加高效。

图8。压实。

回到顶部

原子性和持久性

为了减少I/O操作的数量并使它们具有顺序性，在进行实际更新之前，b -树和lsm -树都要在内存中批量操作。这意味着在发生故障的情况下无法保证数据的完整性原子性(原子地应用一系列更改，就好像它们是单个操作，或者根本不应用它们)和耐用性(确保在面对进程崩溃或电源丢失时，数据已到达持久存储)属性没有得到保证。

为了解决这个问题，大多数现代存储系统都使用WAL(预写日志)。WAL背后的关键思想是，所有数据库状态修改都首先持久地保存在磁盘上仅追加的日志中。如果进程在操作过程中崩溃，则会重放日志，确保没有数据丢失，所有更改都以原子方式显示。

---

b -树和lsm -树数据结构之间最大的区别之一是它们优化的目的以及这些优化的含义。

---

在b -树中，使用WAL可以理解为只有在记录数据文件之后才将更改写入数据文件。b -树存储系统的日志大小通常相对较小:只要对持久存储应用更改，它们就可以被丢弃。WAL用作动态操作的备份:任何未应用于数据页的更改都可以从日志记录中重做。

在lsm -树中，WAL用于持久化已经到达memtable但尚未完全刷新到磁盘上的更改。一旦一个memtable被完全刷新和切换，以便从新创建的SSTable执行读取操作，保存被刷新memtable数据的WAL段就可以被丢弃。

回到顶部

总结

b -树和lsm -树数据结构之间最大的区别之一是它们优化的目的以及这些优化的含义。

让我们比较b -树和lsm -树的性质。综上所述，b -树具有以下性质:

• 它们是可变的，通过引入一些空间开销和一个更复杂的写路径，允许就地更新，尽管它不需要完全的文件重写或多源合并。
• 它们是读取优化的，这意味着它们不需要从多个源读取(并随后合并)，从而简化了读取路径。
• 写操作可能会触发节点拆分级联，使某些写操作的开销更高。
• 它们针对分页环境(块存储)进行了优化，在这种环境中不可能进行字节寻址。
• 由频繁更新引起的碎片化可能需要额外的维护和块重写。但是，b -树通常需要比lsm树存储更少的维护。
• 并发访问要求读写器/写入器隔离，并涉及锁和锁扣链。

lsm -树具有以下属性:

• 他们是不可变的。sstable只写入磁盘一次，从不更新。压缩用于协调被删除项所占用的空间，并合并来自多个数据文件的同键数据。合并的sstable在成功合并后被丢弃并删除，这是压缩过程的一部分。来自不可变性的另一个有用的属性是，可以并发访问已刷新的表。
• 它们是写优化的，这意味着在磁盘上依次缓冲和刷新写操作，从而可能允许磁盘上的空间局部性。
• 读取可能需要从多个源访问数据，因为在不同时间写入的相同键的数据可能位于不同的数据文件中。记录在返回给客户端之前必须经过合并过程。
• 需要维护/压缩，因为缓冲的写写入磁盘。

回到顶部

评估存储系统

开发存储系统总是面临相同的挑战和需要考虑的因素。决定优化什么对结果有很大的影响。您可以在写过程中花费更多的时间，以便为更高效的读布局结构，为原位更新保留额外的空间，促进更快的写，并在内存中缓冲数据以确保顺序写操作。然而，一下子做到这一切是不可能的。理想的存储系统应该具有最低的读成本和最低的写成本，并且没有开销。在实践中，数据结构会在多个因素之间妥协。理解这些妥协很重要。

来自哈佛大学DASlab(数据系统实验室)的研究人员总结了数据库系统优化的三个关键参数:读取开销、更新开销和内存开销(RUM)。了解这些参数中哪一个对用例最重要，将影响数据结构、访问方法的选择，甚至影响对特定工作负载的适用性，因为算法是在考虑特定用例的情况下定制的。

朗姆酒猜想⁴指出为上述两项间接费用设定上限，同时也为第三项间接费用设定下限。例如，b -树以写开销为代价进行读优化，并且必须为对象保留空空间(从而导致内存开销)。lsm树的空间开销较小，但由于在读取过程中必须访问多个驻留在磁盘上的表而导致了读取开销。这三个参数形成了一个相互竞争的三角形，一方的改进可能意味着另一方的妥协。图9阐明了RUM猜想。

图9。朗姆酒猜想。

b树对读性能进行优化:索引以一种最小化遍历树所需的磁盘访问的方式布局。只需访问单个索引文件即可定位数据。这是通过保持该索引文件可变来实现的，这也增加了由于节点拆分和合并、重定位和碎片/不平衡相关维护而导致的写放大。为了分摊更新成本并减少分割的数量，b树在所有级别的节点中保留额外的空闲空间。这有助于将写放大推迟到节点已满。简而言之，b树用更新和内存开销来换取更好的读性能。

lsm树优化写性能。更新和删除都不需要在磁盘上定位数据(而b树需要)，它们通过在内存驻留表中缓冲所有插入、更新和删除操作来保证顺序写入。随之而来的代价是更高的维护成本和需要压缩(这只是减轻不断增长的读取价格和减少磁盘驻留表数量的一种方法)和更昂贵的读取(因为必须从多个源读取数据并合并数据)。与此同时，lsm树通过不保留任何空白空间(不像b -树节点，其平均占用率为70%，这是原地更新所需的开销)和允许块压缩来消除内存开销，因为最终文件的占用率更好，且不可变。简而言之，lsm树用读性能和维护来换取更好的写性能和更低的内存开销。

有针对每个所需属性进行优化的数据结构。使用自适应数据结构可以获得更好的读性能，但代价是更高的维护成本。添加元数据以促进遍历(如分级级联)将影响写时间并占用空间，但可以提高读时间。使用压缩优化内存效率(例如，算法如Gorilla压缩，⁹Delta编码和许多其他编码)将增加写入时打包数据和读取时解包数据的一些开销。有时候，你可以用功能来换取效率。例如，堆文件和散列索引可以提供很好的性能保证和更小的空间开销，因为文件格式简单，代价是只能执行点查询。您还可以通过使用近似的数据结构(如Bloom Filter、HyperLogLog、Count-Min草图等)来换取空间和效率。

这三个可调参数——读取、更新和内存开销——可以帮助您评估数据库，并更深入地了解数据库最适合的工作负载。所有这些都是非常直观的，通常很容易将存储系统分类到其中一个桶中，并猜测它将如何执行，然后通过广泛的测试验证您的假设。

当然，在评估存储系统时还需要考虑其他重要因素，例如维护开销、操作简单性、系统需求、频繁更新和删除的适用性、访问模式等等。RUM猜想只是一个经验法则，它有助于发展直觉，并提供一个初始方向。了解您的工作负载是构建可伸缩后端的第一步。

有些因素可能因实现而异，甚至两个使用类似存储设计原则的数据库最终的性能也可能不同。数据库是包含许多活动部件的复杂系统，是许多应用程序的重要组成部分。这些信息将帮助您窥探数据库的底层，了解底层数据结构及其内部操作之间的差异，从而决定什么是最适合您的。

相关文章
在queue.acm.org

《五分钟规则:20年后闪存如何改变规则》
Goetz Graefe
https://queue.acm.org/detail.cfm?id=1413264

二义性消除数据库
里克·理查森
https://queue.acm.org/detail.cfm?id=2696453

你做错了
Poul-Henning坎普
https://queue.acm.org/detail.cfm?id=1814327

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2018 ACM, Inc.

---

没有发现记录