PDF现代存储系统背后的算法
读优化 B 树和写优化 LSM 树的不同用途
Alex Petrov
应用程序处理的数据量在不断增长。随着这种增长，扩展存储变得更具挑战性。每个数据库系统都有其自身的权衡。理解这些权衡至关重要，因为它有助于从众多可用选择中选择合适的系统。
每个应用程序在读/写工作负载平衡、一致性要求、延迟和访问模式方面都不同。熟悉数据库和存储内部结构有助于架构决策，有助于解释系统为何以某种方式运行，有助于在问题出现时进行故障排除，并为您的工作负载微调数据库。
在所有方向上优化系统是不可能的。在理想的世界中，应该有数据结构能够保证最佳的读写性能，且没有存储开销，但当然，在实践中这是不可能的。
本文深入探讨了现代数据库中广泛使用的两种存储系统设计方法——读优化 B 树1 和写优化 LSM（日志结构合并）树5——并描述了它们的用例和权衡。
B 树
B 树是一种流行的读优化索引数据结构，是二叉树的推广。它们有许多变体，并在许多数据库（包括 MySQL InnoDB4 和 PostgreSQL7）甚至 文件系统（HFS+8，ext4 中的 HTrees9）中使用。B 树中的 B 代表 Bayer，即原始数据结构的作者，或 Boeing，即他当时工作的地方。
在 二叉树 中，每个节点都有两个子节点（称为左子节点和右子节点）。左子树和右子树分别保存小于和大于当前节点键的键。为了使树的深度保持最小，二叉树必须是平衡的：当随机排序的键被添加到树中时，树的一侧最终会比另一侧更深是自然的。
重新平衡二叉树的一种方法是使用所谓的旋转：重新排列节点，将较长子树的父节点向下推到其子节点下方，并将该子节点向上拉，有效地将其放置在其父节点的位置。图 1 是用于平衡二叉树的旋转示例。在左侧，在向其中添加节点 2 后，二叉树变得不平衡。为了平衡树，节点 3 用作枢轴（树围绕它旋转）。然后，节点 5，之前是根节点和 3 的父节点，变为其子节点。在旋转步骤完成后，左子树的高度减小一，右子树的高度增加一。树的最大深度已减小。
二叉树作为内存数据结构最有用。由于平衡（需要保持所有子树的深度最小）和低扇出（每个节点最多两个指针），它们在磁盘上表现不佳。B 树允许每个节点存储超过两个指针，并通过将节点大小与页大小（例如，4 KB）匹配来很好地与块设备配合使用。今天的某些实现使用更大的节点大小，跨越多个页的大小。
B 树具有以下属性
• 已排序。这允许顺序扫描并简化查找。
• 自平衡。在插入和删除期间无需平衡树：当 B 树节点已满时，它会分裂成两个，当相邻节点的占用率降至某个阈值以下时，这些节点会被合并。这也意味着叶节点与根节点的距离相等，并且在查找期间可以使用相同的步骤数定位叶节点。
• 保证对数查找时间。这使得 B 树成为数据库索引的良好选择，其中查找时间非常重要。
• 可变。插入、更新和删除（以及随后的分裂和合并）都在磁盘上就地执行。为了使就地更新成为可能，需要一定的空间开销。B 树可以组织为聚集索引，其中实际数据存储在叶节点上，或者组织为带有非聚集 B 树索引的堆文件。
本文讨论了 B+树3，它是 B 树的现代变体，常用于数据库存储。B+树与原始 B 树1 的不同之处在于：（a）它具有一个额外的链接叶节点层，用于保存值，以及（b）这些值不能存储在内部节点上。
B 树的剖析
让我们首先仔细看看 B 树的构建块，如图 2 所示。B 树有几种节点类型：根节点、内部节点和叶节点。根节点（顶部）是没有父节点的节点（即，它不是任何其他节点的子节点）。内部节点（中间）既有父节点又有子节点；它们将根节点与叶节点连接起来。叶节点（底部）携带数据且没有子节点。图 2 描绘了一个分支因子为 4 的 B 树（内部节点中有四个指针、三个键，叶节点上有四个键/值对）。
B 树的特征如下
• 分支因子 - 指向子节点的指针数 (N)。除了指针之外，根节点和内部节点最多可以容纳 N-1 个键。
• 占用率 - 节点当前持有的指向子项的指针数，占最大可用指针数的百分比。例如，如果树分支因子为 N，并且节点当前持有 N/2 个指针，则占用率为 50%。
• 高度 - B 树的层数，表示在查找期间必须遵循多少个指针。
树中的每个非叶节点最多可以容纳 N 个键（索引条目），将树分成 N+1 个子树，可以通过跟踪相应的指针来定位这些子树。来自条目 Ki 的指针 i 指向一个子树，其中所有索引条目都满足 Ki-1 <= Ksearched < Ki （其中 K 是一组键）。第一个和最后一个指针是特殊情况，指向子树，其中对于最左边的子节点，所有条目都小于或等于 K0，或者对于最右边的子节点，所有条目都大于 KN-1。叶节点还可以保存指向同一级别的上一个和下一个节点的指针，形成兄弟节点的双向链表。所有节点中的键始终是排序的。
查找
执行查找时，搜索从根节点开始，并递归地向下跟踪内部节点到叶节点级别。在每个级别，通过跟踪子指针，搜索空间被缩小到子子树（此子树的范围包括搜索值）。图 3 显示了在 B 树中进行查找，进行单次从根到叶的传递，跟踪“介于”两个键之间的指针，其中一个键大于（或等于）搜索项，另一个键小于搜索项。当执行点查询时，在定位叶节点后，搜索完成。在范围扫描期间，遍历找到的叶节点以及兄弟叶节点的键和值，直到到达范围的末尾。
在复杂度方面，B 树保证 log(n) 查找，因为在节点内查找键是使用二分搜索执行的，如图 4 所示。二分搜索很容易用在字典中搜索以某个字母开头的单词来解释，其中所有单词都按字母顺序排序。首先，你将字典正好翻到中间。如果搜索的字母在字母表上“小于”（出现在之前）打开的字母，则继续在字典的左半部分搜索；否则，继续在右半部分搜索。你不断将剩余的页面范围减半，并选择要跟踪的一侧，直到找到所需的字母。每个步骤都将搜索空间减半，使查找时间呈对数级。B 树中的搜索具有对数复杂度，因为在节点级别键已排序，并且执行二分搜索以找到匹配项。这也是为什么保持高占用率并在整个树中保持均匀性很重要的原因。
插入、更新和删除
执行插入时，第一步是定位目标叶节点。为此，使用前面提到的搜索算法。在定位目标叶节点后，键和值被附加到它。如果叶节点没有足够的可用空间，则这种情况称为溢出，并且叶节点必须分裂成两个。这是通过分配一个新的叶节点，将一半的元素移动到它，并将指向这个新分配的叶节点的指针附加到父节点来完成的。如果父节点也没有可用空间，则也会在父节点级别执行分裂。操作一直持续到到达根节点。当根节点溢出时，其内容在新分配的节点之间分裂，并且为了避免重新定位，根节点本身会被覆盖。这也意味着树（及其高度）始终通过分裂根节点来增长。
LSM 树
日志结构合并树是一种不可变的、驻留在磁盘上的写优化数据结构。它在写入比检索记录的查找更频繁的系统中最为有用。LSM 树越来越受到关注，因为它们可以消除随机插入、更新和删除。
LSM 树的剖析
为了允许顺序写入，LSM 树将写入和更新批量处理到一个驻留在内存中的表中（通常使用允许对数时间查找的数据结构实现，例如 自平衡二叉搜索树 或 跳跃列表），直到其大小达到阈值，此时它会被写入磁盘（此操作称为刷新）。检索数据需要搜索树的所有驻留在磁盘上的部分，检查内存表，并在返回结果之前合并它们的内容。图 5 显示了 LSM 树的结构：用于写入的驻留在内存中的表。每当内存表足够大时，其排序后的内容就会被写入磁盘。读取操作会同时命中驻留在磁盘和内存中的表，需要合并过程来协调数据。
排序字符串表
许多现代 LSM 树实现（例如 RocksDB 和 Apache Cassandra）将驻留在磁盘上的表实现为 SSTable（排序字符串表），因为它们的简单性（易于写入、搜索和读取）和合并属性（在合并期间，源 SSTable 扫描和合并结果写入是顺序的）。
SSTable 是一种驻留在磁盘上的有序不可变数据结构。在结构上，SSTable 分为两个部分：数据块和索引块，如图 6 所示。数据块由按键排序的顺序写入的唯一键/值对组成。索引块包含映射到数据块指针的键，指向实际记录所在的位置。索引通常使用针对快速搜索优化的格式实现，例如 B 树，或者使用哈希表进行点查询。SSTable 中的每个值项都关联有一个时间戳。这指定了插入和更新（通常无法区分）的写入时间以及删除的删除时间。
SSTable 具有一些不错的属性
• 点查询（即，通过键查找值）可以通过查找主索引快速完成。
• 扫描（即，迭代指定键范围内的所有键/值对）可以通过简单地从数据块顺序读取键/值对来有效地完成。
SSTable 表示数据库在一段时间内所有操作的快照，因为 SSTable 是由刷新过程从内存表中创建的，该内存表充当针对此期间数据库状态的操作的缓冲区。
查找
检索数据需要搜索磁盘上的所有 SSTable，检查内存表，并在返回结果之前合并它们的内容。由于搜索的数据可能驻留在多个 SSTable 中，因此读取期间需要合并步骤。
合并步骤也是确保删除和更新工作的必要步骤。LSM 树中的删除操作插入占位符（通常称为墓碑），指定标记为删除的键。同样，更新只是一个带有较晚时间戳的记录。在读取期间，被删除操作遮蔽的记录会被跳过，并且不会返回给客户端。更新也会发生类似的事情：在具有相同键的两个记录中，仅返回时间戳较晚的那个。图 7 显示了一个合并步骤，用于协调存储在同一键的单独表中的数据：如图所示，Alex 的记录以时间戳 100 写入，并使用新电话和时间戳 200 更新；John 的记录被删除。其他两个条目按原样获取，因为它们未被遮蔽。
为了减少搜索的 SSTable 的数量并避免检查每个 SSTable 以查找搜索键，许多存储系统采用了一种称为 布隆过滤器10 的数据结构。这是一种概率数据结构，可用于测试元素是否是集合的成员。它可以产生误报匹配（即，声明元素是集合的成员，而实际上它并不存在于那里），但不能产生漏报（即，如果返回否定匹配，则保证该元素不是集合的成员）。换句话说，布隆过滤器用于判断键“可能在 SSTable 中”还是“肯定不在 SSTable 中”。查询期间会跳过布隆过滤器返回否定匹配的 SSTable。
LSM 树维护
由于 SSTable 是不可变的，因此它们是顺序写入的，并且没有为就地修改保留任何空闲空间。这意味着插入、更新或删除操作将需要重写整个文件。所有修改数据库状态的操作都在内存表中“批量处理”。随着时间的推移，驻留在磁盘上的表的数量会增加（同一键的数据位于多个文件中，同一记录的多个版本，被删除操作遮蔽的冗余记录），并且读取操作将继续变得更加昂贵。
为了降低读取成本，协调被遮蔽记录占用的空间，并减少驻留在磁盘上的表的数量，LSM 树需要一个压缩过程，该过程从磁盘读取完整的 SSTable 并合并它们。由于 SSTable 按键排序，并且压缩的工作方式类似于归并排序，因此此操作非常高效：记录从多个源顺序读取，并且合并后的输出可以立即顺序地附加到结果文件。归并排序的优点之一是即使对于不适合在内存中合并的大文件，它也可以高效地工作。结果表保留了原始 SSTable 的顺序。
在此过程中，合并的 SSTable 被丢弃，并替换为其“压缩”版本，如图 8 所示。压缩采用多个 SSTable 并将它们合并为一个。一些数据库系统在逻辑上将大小相同的表分组到相同的“级别”，并在特定级别上有足够的表时启动合并过程。压缩后，必须寻址的 SSTable 的数量减少，从而使查询更有效。
原子性和持久性
为了减少 I/O 操作的数量并使其成为顺序操作，B 树和 LSM 树都在内存中批量处理操作，然后再进行实际更新。这意味着在故障情况下不能保证数据完整性，并且不能确保原子性（原子地应用一系列更改，就好像它们是单个操作一样，或者根本不应用它们）和持久性（确保在进程崩溃或断电的情况下，数据已到达持久存储）属性。
为了解决这个问题，大多数现代存储系统都采用 WAL（预写日志）。WAL 背后的关键思想是，所有数据库状态修改都首先持久地保存在磁盘上仅追加的日志中。如果进程在操作过程中崩溃，则会重放日志，确保不会丢失任何数据并且所有更改都以原子方式出现。
在 B 树中，使用 WAL 可以理解为仅在更改被记录后才将更改写入数据文件。通常，B 树存储系统的日志大小相对较小：一旦更改应用于持久存储，就可以丢弃它们。WAL 充当正在进行的 operations 的备份：任何未应用于数据页面的更改都可以从日志记录中重做。
在 LSM 树中，WAL 用于持久化已到达内存表但尚未完全刷新到磁盘的更改。一旦内存表被完全刷新和切换，以便可以从新创建的 SSTable 提供读取操作，就可以丢弃保存已刷新内存表数据的 WAL 段。
总结
B 树和 LSM 树数据结构之间最大的区别之一是它们优化什么以及这些优化有什么影响。
让我们比较一下 B 树和 LSM 树的属性。总而言之，B 树具有以下属性
• 它们是可变的，这允许通过引入一些空间开销和更复杂的写入路径进行就地更新，尽管它不需要完全的文件重写或多源合并。
• 它们是读优化的，这意味着它们不需要从多个源读取（并随后合并），从而简化了读取路径。
• 写入可能会触发级联节点分裂，从而使某些写入操作更加昂贵。
• 它们针对分页环境（块存储）进行了优化，在分页环境中，字节寻址是不可能的。
• 由频繁更新引起的分片可能需要额外的维护和块重写。但是，B 树通常比 LSM 树存储需要更少的维护。
• 并发访问需要读/写器隔离，并涉及锁和闩锁链。
LSM 树具有以下属性
• 它们是不可变的。SSTable 在磁盘上写入一次后永不更新。压缩用于协调已删除项占用的空间，并将来自多个数据文件的相同键数据合并。合并的 SSTable 在成功合并后作为压缩过程的一部分被丢弃和删除。来自不可变性的另一个有用的属性是，可以并发访问刷新的表。
• 它们是写优化的，这意味着写入操作会被缓冲并顺序刷新到磁盘，从而有可能在磁盘上实现空间局部性。
• 读取可能需要从多个源访问数据，因为在不同时间写入的同一键的数据可能落在不同的数据文件中。记录必须经过合并过程才能返回给客户端。
• 需要维护/压缩，因为缓冲的写入操作会刷新到磁盘。
评估存储系统
开发存储系统始终面临相同的挑战和需要考虑的因素。决定优化什么对结果有重大影响。你可以花费更多时间在写入期间，以便为更有效的读取布局结构，为就地更新保留额外的空间，促进更快的写入，并在内存中缓冲数据以确保顺序写入操作。但是，不可能一次完成所有这些操作。理想的存储系统应具有最低的读取成本、最低的写入成本且没有开销。在实践中，数据结构在多个因素之间做出妥协。理解这些妥协很重要。
哈佛大学 DASlab（数据系统实验室）的研究人员总结了数据库系统优化的三个关键参数：读取开销、更新开销和内存开销，或 RUM。了解这些参数中哪些对您的用例最重要，会影响数据结构、访问方法的选择，甚至适用于某些工作负载，因为算法是根据特定的用例量身定制的。
RUM 推测2 指出，为提到的两个开销设置上限也会为第三个开销设置下限。例如，B 树以读取优化为目标，但以写入开销以及必须为（因此导致内存开销）保留空闲空间为代价。LSM 树的空间开销较小，但以读取开销为代价，这是由于在读取期间必须访问多个驻留在磁盘上的表而引起的。这三个参数形成一个竞争三角形，并且在一侧的改进可能意味着在另一侧的妥协。图 9 说明了 RUM 推测。
B 树针对读取性能进行优化：索引的布局方式最大限度地减少了遍历树所需的磁盘访问次数。只需访问单个索引文件即可定位数据。这是通过保持此索引文件可变来实现的，这也增加了由节点分裂和合并、重新定位以及与碎片/不平衡相关的维护引起的写入放大。为了分摊更新成本并减少分裂次数，B 树在所有级别的节点中都保留了额外的可用空间。这有助于延迟写入放大，直到节点已满。简而言之，B 树以更新和内存开销为代价来换取更好的读取性能。
LSM 树针对写入性能进行优化。更新和删除都不需要定位磁盘上的数据（B 树需要这样做），并且它们通过在驻留在内存中的表中缓冲所有插入、更新和删除操作来保证顺序写入。这是以更高的维护成本和对压缩的需求（这只是一种减轻不断增长的读取成本和减少驻留在磁盘上的表的数量的方法）以及更昂贵的读取（因为必须从多个源读取数据并合并）为代价的。同时，LSM 树通过不保留任何空闲空间（与 B 树节点不同，B 树节点的平均占用率为 70%，这是就地更新所需的开销）并允许块压缩来消除内存开销，因为最终文件的占用率和不可变性更好。简而言之，LSM 树以读取性能和维护为代价来换取更好的写入性能和更低的内存开销。
有一些数据结构针对每个所需的属性进行了优化。使用自适应数据结构可以在以更高的维护成本为代价的情况下获得更好的读取性能。添加有助于遍历的元数据（例如 分数级联）将对写入时间产生影响并占用空间，但可以改善读取时间。使用压缩（例如，Gorilla 压缩6、增量编码 和许多其他算法）优化内存效率将为写入时打包数据和读取时解包数据增加一些开销。有时，你可以为了效率而牺牲功能。例如，堆文件和哈希索引 可以提供出色的性能保证和更小的空间开销，因为文件格式简单，但代价是除了点查询之外无法执行任何操作。你还可以通过使用近似数据结构（例如布隆过滤器、HyperLogLog、Count-Min sketch 和许多其他数据结构）来换取空间和效率的精度。
读取、更新和内存开销这三个可调参数可以帮助你评估数据库，并更深入地了解它最适合的工作负载。所有这些参数都非常直观，并且通常很容易将存储系统归类到其中一个桶中，并猜测它的性能如何，然后通过广泛的测试来验证你的假设。
当然，在评估存储系统时，还有其他重要因素需要考虑，例如维护开销、操作简易性、系统要求、是否适合频繁更新和删除、访问模式等等。RUM 推测只是一种经验法则，可以帮助你培养直觉并提供初始方向。了解你的工作负载是构建可扩展后端的首要步骤。
某些因素可能因实现而异，甚至两个使用类似存储设计原则的数据库最终也可能表现不同。数据库是具有许多活动部件的复杂系统，并且是许多应用程序的重要组成部分。这些信息将帮助你了解数据库的内部结构，并了解底层数据结构及其内部运作之间的差异，从而决定什么最适合你。
参考文献
1. Comer, D. 1979. 无处不在的 B 树。计算调查 11(2); 121-137; http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.96.6637.
2. 哈佛大学数据系统实验室。RUM 推测； http://daslab.seas.harvard.edu/rum-conjecture/.
3. Graefe, G. 2011. 现代 B 树技术。数据库基础与趋势 3(4): 203-402; http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.219.7269&rep=rep1&type=pdf.
4. MySQL 5.7 参考手册。InnoDB 索引的物理结构； https://dev.mysqlserver.cn/doc/refman/5.7/en/innodb-physical-structure.html.
5. O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. 1996. 日志结构合并树。Acta Informatica 33(4): 351-385; http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.2782.
6. Pelkonen, T., Franklin, S., Teller, J., Cavallaro, P., Huang, Q., Meza, J., Veeraraghavan, K. 2015. Gorilla：快速、可扩展的内存时间序列数据库。VLDB 基金会会议录 8(12): 1816-1827; http://www.vldb.org/pvldb/vol8/p1816-teller.pdf.
7. Suzuki, H. 2015-2018。PostgreSQL 的内部结构； http://www.interdb.jp/pg/pgsql01.html.
8. Apple HFS Plus 卷格式； https://developer.apple.com/legacy/library/technotes/tn/tn1150.html#BTrees
9. Mathur, A., Cao, M., Bhattacharya, S., Dilger, A., Tomas, A., Vivier, L. (2007)。新的 ext4 文件系统：当前状态和未来计划。Linux 研讨会会议录。加拿大渥太华：Red Hat。
10. Bloom, B. H. (1970), 具有允许错误的哈希编码中的空间/时间权衡, 通讯, 13 (7): 422-426
相关文章
五分钟规则：20 年后以及闪存如何改变规则
Goetz Graefe，惠普实验室
旧规则不断发展，而闪存增加了两条新规则。
https://queue.org.cn/detail.cfm?id=1413264
消除数据库的歧义
Rick Richardson
使用为您的访问模型构建的数据库。
https://queue.org.cn/detail.cfm?id=2696453
你做错了
Poul-Henning Kamp
认为你已经掌握了服务器性能的艺术？再想一想。
https://queue.org.cn/detail.cfm?id=1814327
Alex Petrov (http://coffeenco.de/, @ifesdjeen (GitHub) @ifesdjeen (Twitter)) 是 Apache Cassandra 提交者和存储系统爱好者。在过去的几年中，他曾在数据库领域工作，为多家公司构建分布式系统和数据处理管道。
版权所有 © 2018 归所有者/作者所有。出版权已许可给 。
最初发表于 Queue vol. 16, no. 2—
在 数字图书馆 中评论本文
更多相关文章
Pat Helland - 关注你的状态，为了你的心态
应用程序在进入分布式和可扩展世界后经历了有趣的演变。同样，存储及其近亲数据库也与应用程序并肩发展。许多时候，存储和应用程序的语义、性能和故障模型在微妙地共舞，因为它们会随着业务需求和环境挑战的变化而变化。向其中添加规模确实引起了轰动。本文着眼于其中一些问题及其对系统的影响。
Mihir Nanavati, Malte Schwarzkopf, Jake Wires, Andrew Warfield - 非易失性存储
在大多数执业计算机科学家的整个职业生涯中，一个基本观察始终成立：CPU 的性能和成本都远高于 I/O 设备。CPU 可以以极高的速率处理数据，同时为多个 I/O 设备提供服务，这一事实对所有尺寸系统的硬件和软件设计产生了深远的影响，几乎从我们开始构建它们以来就是如此。
Thanumalayan Sankaranarayana Pillai, Vijay Chidambaram, Ramnatthan Alagappan, Samer Al-Kiswany, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau - 崩溃一致性
数据的读取和写入，作为任何冯·诺伊曼计算机最基本的方面之一，出人意料地微妙且充满细微差别。例如，考虑在具有多个处理器的系统中访问共享内存。虽然一种称为强一致性的简单直观的方法最容易让程序员理解，但许多较弱的模型也在广泛使用（例如，x86 总存储顺序）；这些方法提高了系统性能，但代价是使对系统行为的推理更加复杂且容易出错。
Michael Cornwell - 固态硬盘解剖
在过去的几年中，一种新型存储设备已进入笔记本电脑和数据中心，从根本上改变了人们对存储的功率、尺寸和性能动态的期望。SSD（固态硬盘）是一种已经存在了 30 多年的技术，但由于价格过于昂贵而未能得到广泛采用。
© 保留所有权利。