CIDR’2023 2Tree

Abstract

• 真实负载常常表现出倾斜性，传统的面向块的索引结构（如 B 树）对于倾斜数据并不是最优的，因为一个索引块通常包含少量的热记录和大量的冷记录。这将导致主内存利用率下降和成本增加。

• 为了缓解这个问题，我们提出了一种 2-树结构，其中热索引记录在一棵树中，冷索引记录在另一棵树中。热树块被频繁访问，并且很可能保留在主内存中，从而提高了主内存的利用率。我们的核心思想是采用一个轻量级的通用迁移协议，在适当的时候在树之间双向移动记录，并以较低的成本维护访问统计信息。

• 此外，两种树可以针对硬件差异进行单独配置。一种树可以针对主内存进行优化，而另一种则利用辅助存储。显然，2-树的思想也可以推广到多种存储层次和/或设备。展示了如何将 2-Tree 的思想和记录迁移应用于 B+ 树和 LSM 树，以在高度倾斜的工作负载下显著提高其内存利用率(分别提高 x15倍 和 x20倍)。我们还观察到，与使用相同主内存的传统单一 B+ 树或 LSM 树相比，Zipfian-skewed IO-bound 负载的吞吐量提高了 1.7 倍。与现有的以范围扫描性能为代价来提高内存利用率的方案不同，2-Tree 拒绝做出这样的妥协。

Introduction

• 现实世界中的键控数据总是高度倾斜的。数据的一个子集(工作集)的访问频率远远高于其他子集[3,6,7,33,39]。例如，社交媒体上的名人获得的页面浏览量比普通用户高几个数量级。在纽约证券交易所，40 只股票占每日交易量的 60%。通常，热点记录分布在整个键空间[8]中，而不是聚集在几个子空间中。最后，该工作集通常不是静态[4]。例如，推特趋势和突发新闻会随着时间的推移而变化。

• 索引键控数据集的传统方法是采用一种同构的数据结构，如带有主内存缓冲池的 B+ 树。这样，热数据块缓存在主存缓冲池中，而冷数据块驻留在辅助存储器中。这种方法以块粒度管理和迁移主存和磁盘数据。在偏斜数据集上，一个包含数百条冷记录的数据块中，主内存块可能只有一条热记录。这会导致内存利用率低和性能欠佳。

• 在本文中，我们提倡在记录级别迁移数据。研究了一种 2-树结构，其中有两个独立的树数据结构，一个(顶树)用于存储热记录，另一个(底树)用于存储冷记录。当热记录变为冷记录时，它从一个树迁移到另一个树。同样，记录可以向另一个方向移动。
• 该架构的核心是一个通用迁移协议，能够以较低的成本准确地检测和维护热记录。
• 它为每条 hot 记录增加 3 个比特位，并可用于任何树数据结构。通过对热记录进行聚类，2-Tree 显著提高了倾斜数据的内存利用率。

• 这种架构的另一个优点是，这两个数据结构可以针对其底层存储介质分别进行优化。对于主存储器，可以对热结构进行优化；对于二级存储器，可以对冷结构进行优化。因此，2-Tree 可以作为内存数据库索引的体系结构，扩展到大于内存的工作负载

• 还可以将 2-树结构推广为 n-树结构，以适应具有两个以上不同存储级别和/或设备的系统。虽然这有点类似于著名的多树结构，LSM-tree [28]， N-Tree 也会在读取时向上移动数据。在 LSM-tree 没有优化的读负载下，这种向上迁移有助于提高内存利用率。

• 在本文中，我们提出了三个应用 2-Tree 架构和记录级迁移的案例研究。首先，研究了 2-Tree 在大内存环境[11,13]下对内存数据库进行索引的应用，并表明其性能明显优于 Anti-Caching 的[11]方法。其次，通过使用相同数量的主内存来提高缓冲池内存利用率，两种缓冲区管理的 B+ 树结合记录迁移可以显著优于最先进的单个 B+ 树实现[19]。最后，我们展示了一个初步的 N-Tree 实现，通过简单地用记录级向上迁移扩充 LSM-tree。与普通的 LSM 树相比，这显著提高了它们在读取负载较大的情况下的性能
• Anti-Caching的核心思想是，在数据库比内存大的时候，利用硬盘来存储暂时不用的数据，使当前使用的数据可以完整的放入内存中。
• 在Anti-Caching中，一份数据要不就在memory中（数据库中），要不就在disk中，但是不会同时出现在这两个地方，但是传统数据库disk-based DBMS会将经常访问的数据从disk拷贝一份到buffer pool，也就是说有些数据在disk中（数据库中）同时也在buffer pool中（memory中）。

相关研究

LSM-tree

• LSM-tree 原生最初的建议是在磁盘上建立一个 B+ 树的层次结构，其容量呈指数级增长。写操作缓存在内存中的 B+ 树中。滚动合并操作用于批量地将更新从高层树传播到低层树。由于滚动合并到 B+ 树的复杂性，现代的 LSM-tree 实现[10,34]用一个不可变的基于块的排序字符串表(SST)替换了磁盘上每个级别的B+树。类似的合并过程称为合并(compaction)，用于合并具有重叠键范围的SST文件，以生成一个新的SST文件。为了加快读取速度，现代实现通常从内存中缓存SST文件的块。

• 从某种意义上说，LSM-tree 与 N-Tree 类似，都有多种树结构。经常写入工作集中的记录自然聚集在更高级别的 SST 上，从而使这些记录的内存利用率很高。但是，只接收读操作的记录仍然可能分散在不同级别之间，导致块缓存的利用率较低。LSM 树和 N 树架构的关键区别在于，数据在写入 LSM 树时，只会从较高的层移动到较低的层。另一方面，N 树架构在读写时主动地在两个方向上移动数据。因此，它也可以处理读取负载。尽管如此，我们证明了 2-Tree 迁移协议可以应用于普通的 LSM 树，以提高读负载下的内存利用率

Record Caching

• 提高基于页面的存储引擎内存利用率的一种一般方法是为从磁盘页或块中提取的热记录[23,34,40]维护单独的内存缓存。这些方法中的缓存通常用于服务只读查询。为了支持对内存记录缓存的修改，需要设计一种新的恢复机制，同时处理记录缓存和基于页的存储管理器[40]。另一方面，2-Tree 只能通过面向页面的访问进行操作。因此，它可以方便地重用现有的基于页面的恢复机制，如 ARIES[27]。这简化了系统的设计和实现

• 记录缓存的第二个问题是它不像块缓存[38]那样通用。记录缓存只能服务于点查询。例如，RocksDB[34]提供了一个只读的全局 row cache，将频繁访问的 SST 文件记录保存在内存中的哈希表中。热记录可以从全局行缓存中获取，避免了对 SST 文件的访问，提高了内存利用率。然而，行缓存对于其他重要的操作没有帮助，比如需要以块为单位扫描数据的范围查询和合并操作。此外，记录缓存占用了块缓存的内存，而块缓存本来可以用来加速范围查询。我们将在实验中展示，RocksDB 中的行缓存可以提高点读取的内存利用率，但代价是会降低其他操作的性能。向上迁移的 LSM-tree 只缓存利用率高的数据块，并保持具有竞争力的范围扫描性能。

Anti-Caching

• 另一个遵循异构设计哲学的例子是反缓存 Anti-Caching[11]，它以元组粒度管理热内存驻留数据，而不使用缓冲池接口来最大化内存利用率，并以页粒度保持磁盘上的冷数据。然而，反缓存将每个被删除记录的元数据保存在主内存中，并且要求所有辅助索引都驻留在内存中，这可能会占用内存[41]的很大一部分。事实上，反缓存的内存开销是𝑂(𝑁)，其中𝑁是被清除的记录的数量。相比之下，2-Tree 对删除记录的内存开销是固定的，这使得系统具有更好的可扩展性。另一个主要限制是反缓存无法高效地处理范围扫描。这是因为反缓存架构将被驱逐的元组无序地保存在磁盘上。另一方面，2-Tree 维护被删除数据的键顺序。因此，2-Tree 能够支持高效的范围扫描

Siberia

• 另一个与 2-Tree 相关的系统是 Siberia [13]，Hekaton[12]的一部分。Siberia在内存优化的数据存储(热存储)中索引热元组，在传统的基于页面的存储管理器(冷存储)中索引冷数据。2-Tree 与 Siberia 主要有两个不同之处。首先，在读取数据时，Siberia 不会将数据从冷存储迁移到热存储。对于只读或变化的工作负载来说，这不是最佳选择。其次，通过分析访问日志，使 Siberia 的热数据识别机制离线；相比之下，2-Tree 的轻量级在线方法需要更少的计算资源，能够更及时地适应工作负载的变化

2-Tree Design

• 为方便起见，我们在本文的其余部分中在多个上下文中使用record。在关系型数据库设置中，我们使用record来表示一个带键的数据库元组或一个存储它所指向的元组主键的辅助索引条目。在键值存储中，设置记录 record 指的是一个带键的二进制有效载荷

Overview

• 该架构的核心思想是在物理上将热记录与冷记录分开。图 1 说明了我们考虑的三种情况。
• 图1a 展示了反缓存架构的 2-Tree 版本。请注意，热树的数据完全保存在内存中，并以记录粒度进行索引，而不使用缓冲池。被删除的数据存储在磁盘上的树结构中，可以通过一个小的缓冲池访问。在内存中的热树和磁盘上的树之间，迁移工作在记录级别。
• 图1b给出了使用共享缓冲池的两个 B-tree 架构。使用相同的记录迁移。
• 最后，图1c 显示了向上迁移协议增强的 LSM 树。
• 说明图 1b 和图 1c 为基于磁盘的系统。因此，数据仍然存储在磁盘上。然而，存储在更高层次上的页或块被访问的可能性更大，占据了缓冲池的更大一部分，从而提高了内存利用率。

Migration Design Principles

Downward Migration 向下迁移 Clock 算法

• 当可用的内存预算耗尽时，我们必须决定从顶层树中移除哪些记录。一种经典的方法是选择最近最少使用 (LRU) 的记录进行删除。然而，经典的 LRU 算法必须维护一个有序的记录列表，因此每个记录的内存开销很高。本文利用树数据结构通常支持的范围扫描操作，设计了一种近似于 LRU 的时钟替换算法[9]。

• 如图 2 所示，用包含在记录访问时设置的引用位的元数据扩展顶层树中的记录。
• 内存中维护着一个时钟句柄，即一个键值，表示回收扫描的当前进度。
• 当需要清除时，系统从时钟句柄开始循环遍历每个记录。它收集记录的 ref 位为 off 则驱逐。它还清除所检查记录的 ref 位。扫描在收集到所需数量的记录时停止。

Probabilistically Deferred Upward Migration 概率延迟向上迁移

• 下一个要做的决定是什么时候将数据向上移动。一个简单的策略是在从底部树读取数据时始终向上移动数据。然而，这种方法可能会提升冷数据，迫使驱逐顶层树中的热数据。这种效应的一个经典例子是顺序扫描，即只访问一次所有数据。已经提出了许多缓存策略来防止这种颠簸。这些策略通常采用某种形式的缓存分区和/或频率跟踪，这导致了不小的的每条记录 bookkeeping 开销。

• 相反，我们采用一种基于抽样的方法，只向上移动被访问记录的样本。我们定义采样率为 𝐷(0 <𝐷≤1)。对于变得热门的数据，其访问频率会增加，因此它更有可能最终出现在样本集中。因此，该方法提供了一个可调水平的颠簸阻力与最小的内存和 CPU 开销。我们的方法还提供了缓存预热率和颠簸阻力水平之间的权衡。大的采样率可以快速升温缓存，同时提供很小的颠簸阻力。相比之下，较小的采样率通过牺牲预热率来提供颠簸阻力。

• 请注意，在采样率 𝐷= 1 时，我们的方法与“总是在访问时向上移动”相同。寻找最佳采样率是一个典型的旋钮调整任务，有许多可用的自动技术[35,36,42]。为简单起见，在本文中，我们手动找到在评估中工作良好的采样率。我们将这些参数的系统调整留作以后的工作

Inclusive versus Exclusive Migration Policy 包容性与排他性迁移策略

• 迁移记录时要做的另一个重要决策是在系统中保存记录的多少副本。

• 在排他策略中，系统只在顶部或底部树中保存一份记录副本。当从底部树向上迁移数据时，记录从底部树被删除。

• 在包容性策略中，当记录被复制到顶层树时，它将保留在底层树中。包容性策略避免了在迁移过程中修改底层树，这有利于 IO 瓶颈的工作负载。然而，随着重复的增加，包容性策略会导致树的总体大小变大。

• 本文的重点是包容性迁移政策。为了完备性，我们在算法的描述中涵盖了包容性和排他性。然而，我们将排他性政策的实验探索留作以后的工作

Base Operations

查询操作

• 如图 4 所示，查找操作首先在顶层树中搜索键。如果在顶部树中找到的记录正在迁移，则重试该操作(图 4 的第 4 行)。否则，我们更新记录的参考位以保留热度并返回值(图 4 的第 5 行)。

• 如果在顶部树中没有找到，则继续在底部树中搜索。如果找到，则执行向上迁移(图3)算法，该算法很可能将记录移动到顶层树。此外，如果系统配置了独占策略，则从树底部删除该记录。在最下面的树中找到的值返回给用户。

更新操作

• 与查找操作类似，如图 5 所示，更新操作首先在顶层树中搜索键。如果找到了键，则更新引用位、脏位和记录的内容。如果在顶部树中没有找到键，则更新操作继续到底部树。执行类似的向上迁移机制。

PUT 操作

• put 操作执行 upsert，但不检查记录是否存在于两个树结构中。这在加载数据或执行盲写时很有用。Put 操作总是首先将记录插入到顶层树中，并且参考位和脏位都是设置好的。当顶层树被填满时，它们会通过驱逐迁移到底层树。

插入操作

• 插入操作首先使用查找操作检查键值记录是否存在。这对于实现关系数据库中的主键很有用。如果记录不存在，则向顶层树中插入一条记录。如果系统采用包容性策略，则同时设置引用位和脏位。否则，只设置引用位。

删除操作

• delete 操作首先在顶层树中查找键。如果找到记录，则设置其删除位。如果没有找到记录，我们插入一个空有效 payload 的占位记录和被删除的 bitset。只有当记录被删除时，删除操作才会应用到树的底部。注意，我们不会更新引用位，以使记录以更高的概率被删除

Range Scan Operation

• 2-Tree 结构的扫描合并了单个树的扫描。许多 LSM-tree 实现都实现了这一点。在合并结果时，我们需要处理两种情况。
• 情况1：一条记录只存在于一棵树中。在这种情况下，系统返回记录。
• 情况2：记录同时存在于两棵树中。在这种情况下，系统返回顶层树中的记录，因为它反映了最新的版本。

淘汰

• 我们通过定期检查系统的内存消耗是否超过阈值来触发回收。如图 6 所示，清除过程从时钟柄之后开始对顶层树进行范围扫描开始。该过程遍历每条记录。如果记录的 ref 位是 on，则将其切换为 off。否则，将其添加到回收集。在回收集收集到所需数量的记录后，结束扫描操作。

• 我们首先对底层树中的记录进行删除操作。然后，所有脏记录 upserted 到底部的树中。对于非脏记录，如果系统配置了独占迁移策略，它们将被插入到底部。最后，从顶层树中擦除驱逐集合中的记录

Durability and Recovery

• 我们注意到迁移不会改变逻辑用户内容。它只是改变了物理数据结构的表示。因此，我们使用系统事务[15]作为一种通用的方法来保证迁移的原子性和持久性。

• 系统事务是轻量级的，因为它们不需要强制日志记录在提交时存储到稳定的存储中。一个系统事务可以由在正常树操作期间迁移单个记录或在回收期间迁移多个记录组成。
• 对于驻留磁盘的基于页面的 2-树系统(图1b)，使用ARIES[27]进行持久性和恢复。对于每个迁移系统事务，我们将事务更改页面的重做和撤销日志记录记录到日志文件中。当系统事务提交时，它也记录提交记录。但是，这些日志记录在提交时不会强制存入磁盘。相反，这些记录的持久化是由稍后的用户事务隐式地进行的，该事务将其日志记录强制存储到稳定的存储中。
• 对于用于反缓存的2-Tree(图1a)，原始论文[11]中描述的耐久性和恢复机制与2-Tree兼容。因此，我们省略了讨论。
• 对于向上迁移的 LSM-tree(图1c)，我们可以采用相同的系统事务思想，以低成本保证向上迁移操作的持久性和可恢复性。由于现代的 LSM-tree 实现会执行异地写操作，并对其内存写缓冲区采用 write-ahead-log，我们可以将向上迁移表示为普通的写操作。类似地，这样的写操作是轻量级的，因为它不需要保证持久性。

Implementations

Disk-Based Structures

2B+tree

• 我们使用两个磁盘上的 LeanStore B+树[19] 共享一个缓冲池，并实现了记录迁移。当热 B+ 树占用的缓冲池容量超过 90% 时，启动回收进程。我们选择这个阈值是为了确保冷 B+ 树的索引节点是内存驻留的[16]。我们发现LeanStore 中的替换策略随机选择一个页面作为回收候选页，这是我们不希望的，因为我们希望将热树页保存在内存中。尽管 LeanStore 在真正的迁移之前给了每个迁移候选者一个宽限期，但热树页面仍然经常被选择迁移，因为它们占据了绝大多数的缓冲池 frames。我们通过确保冷树中的页被移除的可能性是热树中的页的 10 倍来解决这个问题。

UpLSM-tree

• 如第 2 节所述，当工作集上的工作负载为只读时，普通 LSM-tree 会受到低内存利用率的影响。我们保留 LSM-tree 中向下的迁移，并应用 2-Tree 向上的迁移来解决这个问题。具体来说，我们考虑将一条记录向上迁移到最高级别(C0)。当读点操作导致块缓存缺失时，就会发生这种情况。这表明 I/O 可能发生在较低的级别，因为较高的级别通常较小，由块缓存缓存。因此，向上迁移这样的记录有助于频繁读取的聚集记录。我们使用相同的概率方法来确保只迁移 warm 记录，并减少过多的写操作

Memory-Optimized Structures

IM-2B+tree

• 我们使用内存优化的 B+ 树[5]作为顶部树，避免了缓冲池接口，并使用 LeanStore B+树作为底部树。我们将 90% 的可用内存用于直接在内存中存储数据的顶层树，并将 10% 的内存用于 LeanStore 缓冲池。当顶层树超出其内存预算时，激活回收进程。我们选择这个阈值是为了确保有足够的内存在磁盘上缓存冷 B+ 树的索引节点。

Trie+B+tree

• 这类似于 IM-2B+树，不同的是顶层树使用自适应基数树索引

实验

• 几个关键问题：
• 就点操作下的缓冲池内存利用率而言，2-Tree的概念在改进最先进的基于磁盘的索引方案(即 b 树的 LeanStore 和 LSM 树的 RocksDB)方面的效果如何
• 2-Tree 和 Anti-Caching 在数据集可扩展性方面有什么不同？
• 2-Tree 方法对范围扫描操作的开销有多大?

• Baseline
• LeanStore single B-Tree
• RocksDB LSM-tree
• LSM-tree with Row Cache：RocksDB具有行缓存功能，将频繁访问的SST文件记录保存在in-memory全局缓存中。RocksDB查找过程在查找每个文件之前都会查询全局缓存，从而提高内存利用率。对于给定的内存预算，我们将预算的90%配置为行缓存。然后，我们将剩余的10%预算留给块缓存，以确保所有包含 fence 指针和布隆过滤器的块都缓存在内存中。因此，每个SST文件最多允许一个I/O。
• Anti-Caching：实现了针对内存 DBMS的反缓存[11]。我们使用相同的主内存优化的 B+ 树[5]来索引记录，这些记录也链接在一个双向 LRU 链表中。我们使用类似于原始论文[11]中提出的基于采样的方法来减少 LRU 链表的维护开销。当内存耗尽时，我们将 LRU 链表中最冷的记录组合成一个 1KB 的块。我们使用另一个内存中的 B+ 树来索引每个被移除元组的元数据。元数据包括块 id 和块内记录偏移量。我们将数据块存储在磁盘上的 LeanStore B+ 树中，以数据块 id 为键。在访问被删除的块时，块中的所有记录都作为最冷的记录附加到内存中的 LRU 链表。

配置

• YCSB 5G， 20 million records, each with an 8-byte key and 248 random bytes
• Hotspot：该分布有一个随机选择记录的固定工作集。工作集中的每条记录都被统一 uniform 访问。这衡量了每种方法在内存中可以维护的工作集有多大。
• Zipfian：我们还评估了现实工作负载中常见的Zipfian访问分布。

• Google Cloud instance with 16 2.30 GHz virtual CPUs and 14.8 GB RAM.
• local SSD with a read latency of around 250 us
• Disable write-ahead logging and the Linux page cache for all experiments

• 为了突出内存利用率的重要性，我们将内存预算固定为 1 GB，这大约是原始数据集大小的 20%。在这种内存受限的设置中，利用率的提高可以转化为更好的性能。我们为 LeanStore 和 RocksDB 分别设置了 16 KB 和 32 KB的页面大小。在所有实验中，我们首先依次加载数据集，然后通过运行目标工作负载来预热系统，直到系统吞吐量稳定下来，然后测量平均吞吐量。默认情况下，2-Tree 配置为包含策略和延迟向上迁移，采样率 𝐷 为0.5，我们发现性能相当好。所有实验都是用一个工作线程运行的，该线程执行正常操作和迁移。我们把并发迁移留作以后的工作。

点操作

• 测试查询操作和 RMW 操作 UPDATE；两种分布

• Hotspot：热点集从 0.1% 到 30%
• B+Tree
• 只读负载，2-Tree 最多可以保留 15% 的数据集到内存。
• 对于传统的B+树，当工作集达到数据集的1%时，吞吐量急剧下降。
• 对于这种工作负载，2B+树可以成功地管理大于 B+ 树 15 倍的工作集。即使工作集仅为数据集的 0.1%，且所有方法都能在内存中维护工作集，2B+ 树仍然比 B+ 树性能高1.6倍。
• 原因是顶层树的容量受到内存预算的限制(数据集的 20%)。因此，它的索引节点比单个 B+ 树要小得多，从而提高了 CPU 缓存效率。
• 在图 7b 中，我们观察到更新工作负载上的 2B+ 树比 B+ 树的类似改进。
• LSM-Tree
• 类似地，在图 8a 所示的只读工作负载下， UpLSM-tree 和 带 row 缓存的 LSM-tree 可以在内存中保持比普通 LSM-tree 大得多(最多 20 倍)的工作集。
• 然而，对于图 8b 所示的更新工作负载，我们观察到 UpLSM-tree 和普通 LSM-tree 之间的内存利用率没有显著差异。
• 这是因为更新工作负载自然地将工作集中的记录聚集在 LSM 树的顶层，从而导致较高的内存利用率。
• 令人惊讶的是，带 rowcache 的 LSM-tree 的性能比普通 LSM-tree 和 UpLSM-tree 最多差 9 倍。原因如下。
• 更新操作由对同一个键的读和写组成。由于RocksDB执行错位写入，每次写入都将有效地使行缓存中的记录无效，这可能会导致对同一键的后续读取的 I/O。
• 因此，实际上行缓存中的记录是无法重用的。相比之下，在 UpLSM-tree 和普通 LSM-tree 的情况下，较大的块缓存可以通过缓存更多的 SST 文件来帮助减少 I/O，这解释了性能差异。

• Anti-caching
• 图 9a 和图 9b 展示了 2-Tree 和 Anti-Caching 的对比结果。当工作集可以保存在内存中时，所有系统的吞吐量类似。
• 然而，反缓存只能保持数据集 3% 的可用集。而所有的 2-Tree 都可以缓存工作集的 17%。这是因为在Anti-Caching中，内存中的回收表用于索引被回收的数据占用了太多的内存(54%)。

• Zipfian：将偏斜因子从 0.7 变化到0.9。当偏斜因子为 0.8 时，80% 的访问会导致 32% 的记录。
• B+Tree
• 图10a和图10b展示了2-Tree和单个B+树结构的比较结果。
• 对于2-B+树和B+树，我们观察到在倾斜因子0.9时，只读工作负载的吞吐量增加了1.54倍。
• 这是因为与单个B+树相比，在顶层树中对热点记录进行聚类时，缓冲池内存利用率会增加。
• 对于更新工作负载，我们观察到高达1.7倍的吞吐量提升。这是因为2B+树有助于减少写放大。因此，与单个 B+ 树相比，它每次操作的磁盘写开销更低。
• LSM-tree
• 图11a和11b给出了LSM-tree变种的比较结果。
• 由于块缓存利用率的提高，UpLSM-tree比普通LSM-tree在只读工作负载上的性能最高提高了1.73倍。在只读负载下，UpLSM-tree的性能优于具有行缓存的LSM-tree。
• 在更新工作负载上，我们没有观察到使用UpLSM-tree对LSM-tree的改进，因为这样的工作负载已经为普通LSM-tree保持了较高的内存利用率。
• 然而，基于5.3.1节中解释的相同原因，UpLSM-tree 的性能是带行缓存 LSM-tree 的1.6倍。

• Anti-caching
• 2-Tree 和 Anti-Caching 的对比结果如图 12a 和 12b 所示。在只读和更新工作负载上，反缓存的性能始终比其他 2-Tree 变体高出 4 倍和 3.1 倍。这主要是因为在Anti-Caching中被删除的表占用了54%的内存预算，几乎没有留给热记录的内存。而2-Tree的变体不保存被删除记录的元数据。因此，它们可以在内存中保存更多的热记录。Trie+B+树和IM-2B+树之间的差异并不显著(在10%以内)，因为在这种工作负载下，内存索引带来的性能提升与I/O延迟相比相形见绌。

• Summary：总而言之，我们发现2B+树比单个B+树显著提高了缓冲池的内存利用率。我们还发现，相对于普通的LSM-tree, UpLSM-tree提高了只读工作负载的块缓存内存利用率，而不会损害更新频繁的工作负载的性能。最后，2-Tree 的变体可以使工作集比在内存中缓存大得多。

范围查询

• 混合点查询和范围查询，范围查询比例从 25% 到 100%，扫描操作检查从特定键开始的 100 条连续记录。我们使用 Zipfian 访问分布，将偏斜因子设置为0.8。

• B-Tree
• 如图13a所示，当我们增加扫描操作的百分比时，2B+树的性能与单个B+树的性能类似。这是因为2B+树中的顶层树主要缓存在缓冲池中。因此，大多数的 I/O 操作都来自底层的B+树，与单个B+树相比，底层B+树的叶子节点数量相似。

• LSM
• 对于图 13b 所示的 LSM-tree 变体，随着扫描操作比例的增加，LSM-tree 和 UpLSM-tree 的表现没有区别，因为它们具有相同数量的块缓存。
• 然而，我们观察到带行缓存的 LSM-tree (带RC的LSM-tree)的吞吐量要低83%。这是因为LSM-tree中的范围扫描操作需要扫描SST文件中的块。在这种情况下，块缓存可以帮助减少 I/O，而行缓存则不能。因此，块级缓存比记录级缓存更通用

• Anti-Caching
• 结果如图 14 所示。IM-2B+ 树显著地提高了反缓存性能 35 倍，因为 IM2B+ 树会在磁盘上有序地保存被清除的数据。然而，AntiCaching设计对回收进行了优化，并将被回收的数据无序地保存在磁盘上。这导致每次扫描需要许多随机I/O操作。因此，它无法支持对磁盘数据的高效扫描。

未来方向

• 物理并发控制：本文只讨论了只有一个线程访问2-Tree数据结构的情况。这只适用于单线程架构，如H-Store/VoltDB[17,31,32]和Redis[30]。在未来的工作中，我们计划在 2-树结构中解决协调并发的问题。具体来说，我们需要保证数据结构在面对并发迁移和正常访问时保持一致。我们将利用在并发树数据结构[22,26]和同步技术[2,18,21]方面的丰硕研究成果。

• 适应非基于树的结构：我们没有根本的理由不能将此架构扩展到更多的数据结构以优化倾斜。例如，广泛使用的结构，如可扩展/线性[14,25]散列和堆文件，因为有两个结构而不是一个，所以很容易适合这种架构。作为未来的工作，我们计划推广 2-Tree 来处理非基于树的数据库索引和存储结构。

• 云原生数据库的应用：2-Tree架构可以直接应用于现代云原生数据库，其中存储从计算中分解出来[1,24,37]。这有助于提高计算节点上缓冲池的内存利用率，减少对存储节点的往返访问，这通常比访问本地存储设备更昂贵。此外，2 树结构和存储节点可以进行计算的事实为更多的优化提供了空间。例如，我们可以在计算和存储之间以记录粒度而不是页面粒度迁移数据，从而减少网络流量

• 多层内存层次结构：已经提出了几个多层解决方案，从本地内存(持久性内存)到远程内存(使用Compute Express链路和/或RDMA进行内存扩展和池化)，具有不同的性能和成本特征。我们希望将2-Tree架构扩展到多个层次。在如此多样化的设计空间中，可能需要新的缓存和数据迁移技术

• Compressed DRAM：压缩是一种很有希望在DRAM中保存更多数据的方法。例如，使用LZ4在主内存中解压一个大小为4 KB、包含随机数据的B+tree leaf页面，其延迟比从我们测试的几个NVMe ssd上读取相同的4 KB块要低5-50倍。因此，我们希望探索这种优化策略。除了使用压缩DRAM作为顶层存储外，还可以在未压缩DRAM和压缩SSD之间形成新的中间层存储。开放问题包括如何正确管理、提供和索引压缩DRAM，以及如何识别不可压缩的数据并避免将它们放置在压缩DRAM中；以及2-Tree在这些开放问题中的可能作用。

Conclusion

• 在本文中，我们提出了 2-Tree 架构来提高倾斜工作集的内存利用率。其核心思想是维护两棵树，并在它们之间迁移记录:基于热度，双向迁移，且成本较低。结果表明，对于倾斜数据，2-Tree 显著提高了 B+ 树的缓冲池内存利用率，同时保持了具有竞争力的范围扫描性能。我们还演示了将迁移应用于 LSM-tree，可以在不影响范围扫描和更新操作性能的情况下，帮助提高读负载大的块缓存内存的利用率。2-Tree 显著地提高了数据集的可扩展性和范围扫描的性能，因此在反缓存体系结构的索引方面也很有竞争力。由于工作负载总是倾斜的，我们相信 2-Tree 是数据库索引中提高内存利用率的有希望的一步。