更新高效数据结构
介绍
更新最优解
日志/日记
日志结构合并树
B树
LSM树的实践
概括
参考
介绍
RUM系列的第一篇博文介绍了RUM猜想。它描述了在设计数据结构和访问方法时应该考虑的读取（RO）、更新（UO）和内存（MO）开销之间的权衡。
在这篇文章中，我们将仔细研究一些在实践中常用的、更新开销较低的数据结构，例如日志和日志记录、日志结构合并树，以及 B 树和一些 B 树扩展。
这篇博文是 RUM 系列的第三部分：
为了比较不同的实现方式，我们使用了与其他文章中相同的示例。这次的任务是实现一个整数集合，重点在于尽可能减少更新开销。
本文结构如下。第一部分回顾了首篇文章中提出的更新开销最小的解决方案。第二部分阐述了如何在实际场景中应用更新最优方案（也称为日志记录或日志式记录）。第三部分介绍了日志结构合并树（LSM 树）的概念，这是一种结合了不可变日志和高效读取数据结构的数据结构。接下来的部分简要讨论了 B 树，因为它们在数据库索引以及 LSM 树中都扮演着重要角色。倒数第二部分将阐述在选择基于 LSM 树实现的数据库时需要考虑的实际问题。最后，我们将总结本文要点。
更新最优解
实现恒定（且最小）更新开销的最简单方法是将每次更新追加到事务日志中。以要实现一组整数的用例为例，我们将插入和删除操作存储在一个序列中，始终追加最新的操作。由于点查询可能需要遍历整个日志，而日志也可能无限增长，因此我们推导出了以下 RUM 开销：
- RO → ∞
- UO = 1
- MO → ∞
与读取最优解相比，更新最优方法在实践中实际应用更为广泛。根据上下文，它也被称为日志记录或日志日志。
日志/日记
概念
下图展示了{0..6}经过几次更新操作后，该集合可能的样子。
写入操作是顺序进行的，因为我们只追加新数据，而不会触及日志的其余部分。研究表明，磁盘上的顺序写入速度与内存中的随机访问速度相当，甚至更快。[1]
日志记录/日志日志的用途是什么？日志存在的时间越长，其读取性能和内存开销就越低。
这种非常简单的数据结构读取性能差，可以通过两种方式（或两者结合）来弥补。首先，我们可以限制对日志的读取次数，方法是只按顺序读取一次日志，然后将数据异步传输到读取效率更高的数据结构（例如树）。
PostgreSQL等数据库将事务存储在预写式日志文件中。通过直接 I/O绕过页面缓存，并结合追加日志操作，可以最大限度地缩短数据库确认事务所需的时间，同时避免数据丢失的风险。之后，数据库可以异步遍历日志，将事务应用到实际的表中。日志仅在事务应用时读取一次。如果发生崩溃，数据库还可以使用日志来重放尚未执行的事务。利用预写式日志，我们可以在不牺牲吞吐量的前提下，实现事务的持久性和原子性。
另一个非常类似的用例是日志文件系统（JFS）。在JFS中，更改首先存储在日志中，然后再应用到主文件系统结构中。
其次，我们可以通过构建一个索引来避免搜索整个日志，该索引包含特定事务或消息的日志文件偏移量。虽然这对于我们的整数集示例并不实用，因为索引的大小不会比实际数据小多少，但它在消息队列系统（例如Apache Kafka ）中得到应用，这些系统依赖于高消息吞吐量并且仅按顺序消费消息。
如何应对可能无限增长的内存开销？一种方法是对日志大小进行限制。Kafka 允许用户配置基于时间（log.retention.hours）或大小（log.retention.bytes）的保留策略。
另一种常用的技术称为压缩。以上面的集合示例为例，只有当某个值之前被添加到集合中时，才需要存储该值已被删除的信息。在压缩过程中，我们会移除那些不会影响最终状态的事务。
下图展示了如何使用压缩来减小上述整数集的大小。我们移除了冗余事务，从而缩短了日志长度。压缩可以基于时间或空间约束执行。
朗姆酒开销
在最简单的日志实现中（不进行任何压缩、保留或索引），RUM 开销与更新最优方案相同。对于大小为m 的日志，最多需要m 次读取操作才能确定某个值是否属于集合。更新开销为 1，因为我们只进行追加操作。除非实施保留策略，否则内存开销将无限增长。压缩也有助于降低内存开销。
渐近复杂度
渐近复杂度直接对应于 RUM 开销。读取和内存需求随日志大小线性增长，而更新复杂度在平均情况和最坏情况下均保持不变。如果我们定期进行数据压缩，就可以使事务数m接近整数数n。
| 类型 | 平均的 | 最坏情况 |
|---|---|---|
| 读 | O(m) | O(m) |
| 更新 | O(1) | O(1) |
| 记忆 | O(m) | O(m) |
研究人员和数据库开发人员花费了大量时间，将日志与其他数据结构和技术相结合，以弥补读取和内存开销过大的问题。一种常用的、更新效率高的数据结构，即日志结构合并树，结合了日志记录和索引功能。
日志结构合并树
概念
日志结构合并树（LSM 树）[2] 与其说是一种实际的数据结构，不如说是一个用于组合不同层级数据结构的框架。它们在概念层面上解决了上一节讨论的仅追加日志的问题，我们将在本节中对此进行探讨。LSM 树的实际性能很大程度上取决于具体的实现方式和所使用的数据结构。
LSM 树的主要思想是维护一个数据结构层次结构，其中每一层都针对底层存储介质进行了优化。在两层 LSM 树中，第一层通常存储在内存中，而第二层存储在磁盘上。下图展示了两层 LSM 树的概念。
原文建议使用类似B 树的结构来构建各个树。这样做的好处在于，我们可以根据文件系统的块大小调整节点大小。然而，由于第一层驻留在内存中，我们也可以使用其他自平衡树，例如2-3 树或AVL 树。
像Bigtable [3] 或Apache Cassandra [4]这样的数据库实际上并不以树状结构存储高层数据，而是以排序字符串表 (SSTable) 文件格式存储。SSTable 是一个按键排序的键值对文件。此外，通常还会在数据文件中存储键到偏移量的映射关系。
如前所述，在内存中存储第一层时，我们通常会将更新持久化到一个简单的预写式日志（WAL）中，以确保数据持久性。读取查询首先访问内存层，这是一个读取效率很高的数据结构。如果找不到键，则继续访问下一层。为了避免扫描所有层级，我们可以使用近似索引（例如布隆过滤器）来确定某个键是否包含在 LSM 树的某些部分中。
更新操作在内存层直接执行。这不会造成问题，因为 RAM 的速度足以支持随机访问，而且一旦到达预写式日志，我们就可以立即确认事务。当内存层已满时，我们会将数据持久化到下一层。如果所有层级都使用 B 树，则可以直接持久化树结构。对于 SSTable，我们会将记录存储为排序后的键值对，并在需要时添加索引。
基于磁盘的更新最终会填满磁盘空间。这时，数据压缩就派上用场了。我们可以定期合并不同的树/SSTable，从而有效地减小总大小。合并成功后，我们可以丢弃过时的数据。这也是“日志结构合并树”名称的由来。我们将更新存储在树的日志中，通过合并树来压缩数据，从而减少不断增长的读取和内存开销的影响。
朗姆酒开销
LSM树的实际RUM开销很大程度上取决于具体的实现方式。它们对应于不同层级的RUM开销。此外，我们还需要考虑将数据从一层持久化到下一层所消耗的资源，以及在压缩情况下合并数据的开销。
渐近复杂度
当然，渐近复杂度也取决于实际的实现方式和所使用的数据结构。如果我们尽可能地压缩数据，并且对所有层级都使用排序数据结构，那么就集合n中的实际元素数量（而非事务数量m）而言，我们可以实现对数级的读取性能。更新复杂度将与内存数据结构相对应。但是，如果我们使用预写式日志，则可以使其看起来接近常数时间复杂度。
如果数据库负载过高，同时接收到大量查询，其性能就会下降到普通日志所能保证的水平。一些实现，例如SwayDB，提供了反压机制，以防压缩无法满足需求。
我们现在明白了为什么 LSM 树是数据库提升更新性能的强大工具。由于 LSM 树的原始论文建议对各个层级使用类似 B 树的结构，因此我们将在下一节简要介绍一下 B 树。
B树
概念
B 树 [5] 是自平衡二叉搜索树的推广，其中每个节点可以有两个以上的子节点。对于每个节点，其左子树仅包含小于当前值的元素，从而实现了对数级的搜索复杂度。下图展示了一个最大块大小为 4 的 B 树，其中包含集合{0..6}。
B 树与二叉搜索树具有相同的渐近读取复杂度、更新复杂度和内存复杂度。那么，为什么我们要在一篇关于高效写入数据结构的文章中提到它们呢？
在 B 树中，您可以调整节点中存储的元素数量，使其分别适应文件系统的块大小或硬盘的扇区大小。这使得它们比常规二叉搜索树（例如上一篇文章中提到的红黑树）更适合顺序存储介质。此外，还有许多扩展和衍生版本致力于降低更新开销。B 树及其扩展版本广泛应用于数据库和文件系统实现中。
两个 B 树扩展
B+树
与 B 树不同，B+ 树仅在叶节点中存储记录。虽然这种扩展在我们的整数集示例中用处不大，但它会显著影响数据库的性能，尤其是在 B+ 树常用作索引的情况下。
它们并非专门针对提升更新性能而优化，但由于中间节点仅存储键值，因此允许比 B 树更高的分支因子。这使我们能够将所有非叶子节点存储在内存中，从而仅在需要修改数据库记录时才进行磁盘 I/O 操作。
此外，B+ 树存储从一个叶节点到下一个叶节点的指针，从而显著加快跨越多个叶节点的查询速度。
分形树
分形树[6]与B树具有相同的渐近读取复杂度，但其更新性能更佳。这是通过在每个节点中维护缓冲区，并将插入操作存储在中间位置来实现的。这改善了B树的最坏情况性能，因为在B树中，每次磁盘写入可能只会更改少量数据（另见写入放大）。
分形树可作为MySQL和MariaDB（参见TokuDB）以及MongoDB（参见TokuMX）的存储引擎。
朗姆酒开销
B 树的 RUM 开销取决于分支因子和树的当前状态。搜索查询必须从根节点开始，在节点内执行二分查找以找到相应的子节点指针。虽然与二叉搜索树相比，我们需要跟踪的指针数量可能更少，但需要在节点内执行更多的比较操作。因此，读取开销与树中的元素数量成正比。
更新开销等于读取开销加上插入或删除元素所需的一次操作。为了保持树的平衡，我们可能需要拆分（插入）或合并（删除）节点。与红黑树类似，这可能会影响树的更大部分。
内存开销与树中存储的值的数量成正比。但是，我们可以通过增加每个节点的最大大小来降低内存开销。这样，树就会更小，需要存储的指针也会更少。我们还可以将节点大小与机器的页面大小/块大小相匹配。
渐近复杂度
如上所述，渐近复杂度等价于二叉搜索树的渐近复杂度。
| 类型 | 平均的 | 最坏情况 |
|---|---|---|
| 读 | O(log n) | O(log n) |
| 更新 | O(log n) | O(log n) |
| 记忆 | 在） | 在） |
LSM树的实践
现在我们已经对更新高效的数据结构有了大致了解，接下来让我们来看一些具体数据。目前我想重点介绍 LSM 树，因为它们在各种数据库中被广泛使用。以下列表（并非完整列表）列出了使用或支持 LSM 树进行数据持久化的数据库。
选择用于处理持久化数据的数据库并非易事。选定数据库后，您可以选择使用默认配置，也可以根据自身需求进行微调。
我想利用SwayDB开发者进行的基准测试，来可视化不同配置参数下的几种权衡取舍。SwayDB 是一个高度可配置、类型安全且非阻塞的键值存储库，支持单磁盘/多磁盘和内存存储，使用 Scala 编写。测试数据来自一台2014 年中期的 MacBook。
我们将考察不同场景下的读取和写入吞吐量（每秒操作数）。
- 第一个变量是读取和写入操作是按键的升序（顺序）还是打乱顺序（随机）执行。
- 第二个变量是数据库的设置方式。我们正在比较一个 2 级内存 LSM 树、一个 8 级内存映射文件 LSM 树（
java.nio.MappedByteBuffer）和一个 8 级常规文件 LSM 树（java.nio.channels.FileChannel）。
内存数据结构速度快，但持久性差。内存映射文件虽然能提供持久性和读写性能，但由于无法保证在服务器崩溃时数据能够写入，因此其持久性不如常规文件访问。使用直接 I/O 可以实现最大程度的持久性，但我不太确定 SwayDB 是否支持这种配置。
首先，我们来看一下压缩过程对数据库性能的影响。下图比较了随机读取操作在压缩期间和压缩后的读取吞吐量。
无论持久化配置如何，压缩过程都会使数据库的随机读取性能降低约 50%！在使用 LSM 树时，压缩至关重要，它可以保持良好的读取性能并避免占用过多空间。然而，压缩策略的选择必须谨慎，因为如果压缩过于频繁或过于低效，都可能带来高昂的性能代价。
第二个值得关注的问题是键的顺序对写入性能的影响。下图比较了在两级内存 LSM 树中使用有序键和乱序键时的写入吞吐量。
太棒了！当写入操作按顺序进行而非随机打乱时，速度提升可达 100% 左右。这表明，根据查询语句和数据结构的不同，性能差异可能非常显著。SwayDB 底层使用跳跃表，顺序插入操作只是将元素追加到跳跃表的末尾，并根据需要提升元素。而随机插入操作则会导致修改和重新链接跳跃表中间的多个元素和层级。
最后，我们想研究牺牲持久性来换取吞吐量对性能的影响。下图比较了我们针对两级内存内、八级内存映射文件型和八级常规文件型 LSM 树的随机写入和混洗写入的写入吞吐量。
正如预期，内存中的 LSM 树结构性能最佳。虽然常规文件访问提供了最佳的持久性，但其性能最差。如果可以接受数据丢失，并在发生致命崩溃时从预写日志 (WAL) 中恢复数据，则内存映射文件可以提供不错的性能。
概括
本文探讨了更新最优方案（也称为日志记录/日志式记录）及其在实践中的应用。我们发现，通过维护树状结构（LSM 树）的日志，可以在不牺牲太多读取性能的情况下实现不错的写入吞吐量。
我们还简要介绍了B树，因为它们在LSM树和数据库索引中扮演着重要角色。虽然B树并非专门为提高更新效率而设计，但有一些扩展旨在减少写入放大等问题。
最后，我们看到根据需求调整数据库可以显著提升性能。在使用 LSM 树时，压缩和归零等策略也至关重要。
你用过使用 LSM 树来持久化状态的数据库吗？你最喜欢的数据库使用的数据结构是什么？你知道还有哪些 B 树的扩展旨在降低更新开销吗？它们是如何工作的？请在下方评论区留言！下一篇文章将重点介绍空间高效的数据结构。
参考
- [1] Jacobs, A., 2009. 大数据的病理学。《ACM通讯》，52(8)，第36-44页。ACM队列邮报
- [2] O'Neil, P., Cheng, E., Gawlick, D. 和 O'Neil, E., 1996. 日志结构合并树 (LSM 树)。Acta Informatica, 33(4), pp.351-385。
- [3] Chang, F., Dean, J., Ghemawat, S., Hsieh, WC, Wallach, DA, Burrows, M., Chandra, T., Fikes, A. 和 Gruber, RE, 2008. Bigtable：用于结构化数据的分布式存储系统。ACM 计算机系统学报 (TOCS)，26(2)，第 4 页。
- [4] Cassandra 文档“数据是如何写入的？”
- [5] Comer, D., 1979. 无处不在的 B 树。ACM 计算调查 (CSUR)，11(2)，第 121-137 页。
- [6] Bender, MA, Farach-Colton, M., Fineman, JT, Fogel, YR, Kuszmaul, BC 和 Nelson, J., 2007 年 6 月。缓存无关的流式 B 树。第十九届 ACM 并行算法与架构年会论文集（第 81-92 页）。ACM。
- 封面图片来自美国国会图书馆版画与照片部。数字ID：fsa.8c35555。公共领域，https://commons.wikimedia.org/w/index.php? curid=543535
如果你喜欢这篇文章，可以在 ko-fi 上支持我。
文章来源：https://dev.to/frosnerd/update-efficient-data-structs-7cn