Abstract

• 内存分解的新趋势是 CPU 和内存在物理上彼此分离，并通过超高速网络连接，例如，通过远程直接内存访问(RDMA)，允许计算(CPU) 和主内存的弹性和独立扩展。本文研究了如何在内存分解体系结构中有效地设计索引。尽管现有的研究已经针对这种新架构优化了 b 树，但它的性能并不令人满意。本文主要研究基于 LSM 的索引，提出了第一个高度优化的分解内存 lsm树—— dLSM。dLSM 引入了一套优化，包括减少软件开销、利用近数据计算、调优字节寻址能力，以及在 RDMA 上进行实例化，作为 RDMA 特定定制的案例研究，以提高系统性能。实验表明，与运行优化的 B-tree 和现有四种适配 DM 后 LSM-tree 索引的相比，dLSM 在分解内存上的写吞吐量提高了 2.3x 到 11.6x。dLSM 是用 C++ 语言编写的(大约有 54,400 个LOC)，并且是开源的。

Introduction

• DM 是现代数据中心的趋势，允许独立且弹性的扩展，区别于传统的聚合的服务器，DM 通过快速网络实现了存算分离，对应两种服务类型的节点：计算节点和内存节点。计算节点通常由丰富的计算资源，有限的内存，而内存节点则相反。DB 允许内存和计算独立和弹性扩展，从而获得更低的 TCO，且存储和计算故障隔离，而且打破了单机的内存限制。

• 本文聚焦在 DM 的索引技术，即大部分数据存储在远端内存，热数据缓存在本地内存，之前的工作 Sherman 研究了如何优化 DM 上的 B-tree 索引，然而写性能不满足要求。为了改善性能，本文聚焦在 DM 架构下的 LSM-tree 索引。

• 为什么使用分离的 LSM-tree？
• LSM-tree 天然就适合本地和远端两级的内存结构，新的写入在本地缓冲，后台刷回到远端，从而将网络访问移出了写路径；
• LSM-tree 聚合随机小写位大的写入可以更好地利用网络带宽，在我们对于 RDMA 实验中，传输 64B 和 1M 单位大小的数据表现出了 100x 的性能差距；
• 本文的实验表明 LSM-tree 如预期一样，在 DM 上表现很好，比优化的 B-tree （Sherman）在写方面要表现更好

• 挑战：
• 快速的网络显著降低了本地和远端内存的性能差距，因此传统的对于 HDD 和 SSD 场景不被重视的软件开销成为性能瓶颈。
• 内存节点有 CPU 来执行专门的计算任务，这一点其他内存架构不具备该能力
• 与传统存储设备中的块可寻址不同，远程内存是字节可寻址的。因此，索引设计需要注意字节可寻址性
• 另一个挑战是高效地使用复杂的通信接口，因为它们在内存分解的情况下变得至关重要，例如，RDMA 是 non-trivial 的，因为它涉及许多可选的原语，例如，单边与双边RDMA

• 本文方案的总结：
• 为分解内存专门构建的基于 LSM 的索引。dLSM 研究了这种设置下基于 LSM 的索引，并引入了许多优化来解决上述挑战。dLSM 减少了软件开销，例如同步。dLSM 选择性地将 LSM 树 Compaction 卸载到远程内存节点，以便尽可能利用内存节点中的 CPU 来减少数据移动。dLSM 调整索引布局以利用远程内存中的字节寻址能力。dLSM 优化了通信，包括自定义远程过程调用(简称 RPC) 和异步 I/O。
• 贡献总结如下：
• 在 DM 上的索引设计，第一个针对 DM 架构的 LSM-tree 索引；
• 减小软件开销，比如同步开销
• 远程 Compaction 来支持近数据处理，选择性下推 LSM-tree compaction 到内存节点来减少数据传输；
• 字节寻址的定制优化，弃用块结构的概念，利用分解内存中的字节可寻址性来提高性能
• RDMA 的定制优化：我们在支持 RDMA 的分解内存上实例化 dLSM。dLSM 使用特定于 RDMA 的优化，例如，异步 I/O 和自定义 RPC 以实现高性能

• 我们将通过 RDMA 实例化 dlsm 作为案例研究。然而，许多想法(例如，减少软件开销和针对字节寻址能力的定制优化)可以应用于其他技术，例如 CXL

• 会议论文 ICDE’23 dLSM: An LSM-based index for memory disaggregation. In: International Conference on Data Engineering (ICDE), 扩展

• 我们使用标准的 RocksDB 基准测试对 1 亿个键值对(超过 40GB 的数据集)进行实验来评估 dLSM。我们将 dLSM 与五种基准解决方案(Nova-LSM[49]、磁盘和内存优化的 RocksDB 和Sherman[80]) 在内存分解架构上进行了比较。实验表明，dLSM 的写吞吐量提高了 2.3x 到 11.6x，而损失高达 12.5x

• 关于 LSM-tree 的优化更具体来说是：
• 我们开发了新的自适应 Compaction 策略来自动调整 LSM-tree compaction 到远端内存节点，取决于远程内存节点的不同计算能力
• 我们引入了一种优化计算节点缓冲区内存使用的新技术，使索引在数据量大且本地缓冲区大小有限的情况下具有良好的性能
• 我们开发了一种非阻塞的事务一致性检查点技术，使dLSM具有持久性
• 我们提供了会议版本[82]中省略的更多技术细节，例如，线程本地队列对(第10.2.1节)，RDMA内存区域分配器(第10.2.2节)和基于RDMA的文件系统实现(第11.1节)。
• 为了更全面的评价，我们增加了新的实验

Background

DS & DM

• 两种资源分离：存算分离（存储和计算）、内存分离（内存和计算）
• 存算分离在现在的云厂商相关数据库产品中应用广泛；比较依赖传统的 RPC
• 分离式内存也逐渐在学术和工业界引起了关注，分离式内存更依赖于 RDMA

• DM 的通信互连依赖高速网络
• RDMA 允许直接访问远端节点的内存，跳过主机端的操作系统避免传输过程中的额外数据拷贝。RDMA 依赖于 IB 或者无损以太网，主要以可以 bypass 内核为特性
• CXL 是先进 CPU 和附带的设备之间的告诉传输通信方式，比如 CXL 扩展的内存、CXL 连接协议保证 CPU Cache 和内存之间的缓存一致性，使得 CPU 可以直接通过 load/store 访问远端的基于 CXL 的内存。

LSM-tree

• 略过

Overview

• 通过利用 DM 架构中资源不对称的特点，不同的节点存储 LSM-tree 的不同组件。
• 计算节点维护 Memtable、SST 元数据、索引块、BF
• 内存节点维护 SST

• 操作流程：
• 写：Memtable 是个无锁跳表，使用异步 I/O 将 Memtable Flush 到内存节点，Flush 完成后通过 CoW 的形式更新 LSM 的元数据
• Compact：为了减小节点间的数据移动，直接将 Compaction 任务 offload 到内存节点。计算节点决定哪些 SST 参与合并，然后通过 RPC 将元数据发送给内存节点，内存节点通过 RPC 获取到 SST 元数据以后执行 Compaction。Compaction 完成后计算节点收到修改 LSM-tree 元数据的回复。
• 读：读流程和原来基本一样，dLSM 使用 BF 和一个新的索引布局来直接定位键值对的位置，而不需要获取整个 Block，充分利用字节寻址

最小化软件开销

• DM 架构下软件开销成为瓶颈，以前的 HDD/SSD 架构下几乎可以忽略。

• 现在的 LSM-tree 的软件开销主要在于：Memtable 实现并发写的同时还要做并发控制。快照隔离 是一种并发技术来保证读一致
• 无锁跳表实现并发写入，然后 dLSM 使用一个原子的 seq_no 生成器为每个写入无锁地分配 seq。
• 但是当多个 writers 检测到 Memtable 满了之后如何正确切换成为了一个挑战，特别是我们想最小化锁同步开销的情况下。

• 一种直接的思路是 double-checked locking 来保证只有一个 writer 成功切换 Memtable。这种机制下只有容量满了才会有 writer 获取到锁，但存在问题。
• 因为我们无法保证 分配 seq 和将数据插入到 Memtable 这两个操作的组合是原子的，所以可能出现新版本数据的 writer 的数据插入到了老的 Memtable 的情况。

• dLSM 则是采用为每个 Memtable 在创建的时候就分配好预定义范围 seq，新的 Memtable 的 seq 范围自然更新，写线程插入数据到 Memtable 的时候检查 seq 是否匹配范围，从而决定是否要切换 Memtable。如下图就是一个例子。如果多个写线程都要切换 Memtable，使用 double-checked 锁保证只有一个线程来执行。

• 总感觉这个算法的 Else 有问题，即切换 Memtable 的时机。
• 不该是在切换之前再次检查是否满足当前 Seq 大于 Memtable 的范围吗？
• 做这个检查的目的是为了避免加锁之前 Memtable 被人切了，这个时候当前线程本质上其实不用切了。而如果 double check 的过程发现还是超过了该范围才说明，当前写线程需要切换 Memtable。
 

近数据处理的 Compaction

• 核心是利用远端内存上的计算资源来减小数据移动。但是远端内存上的计算资源可用的数量并不一致，需要自适应调整。

放置 LSM-tree 的元数据

• 元数据对于 LSM-tree 的各个操作很关键，比方说元数据放在远端内存就很容易实现 compaction 任务的卸载，但是会对读性能有影响，因为前台读需要从远端访问元数据。

• 本方案在计算节点维护元数据，当计算节点决定好了那个 SST 被 Compact 的时通过传统的 RPC 候触发近数据的 Compaction，内存节点收到 RPC 之后就把这些 SST 合并。为了减少从级别 0 开始的写延迟，它使用多个后台合并线程将一个大型合并任务划分为多个并行的子合并任务。合并完成后，内存节点向计算节点发送确认，计算节点随后发出另一个 RPC，将合并后的 sstable 的元数据复制到所需的工作空间

• dLSM 有几个优化，通过允许内存节点在本地分配内存来避免网络往返和内存复制。内存节点中的内存被划分为两个不相交的内存区域，其中一个区域由计算节点控制(和分配)，用于常规MemTable 刷新，而另一个内存区域由内存节点本身控制，用于近数据合并。然后，内存节点可以在其私有内存空间中执行合并。合并完成后，内存节点通过 RPC 应答将新 sstable 的元数据发送给计算节点。计算节点根据回复修改 LSM-tree 元数据，并使新的 sstable 对读者可见。从我们的实验来看，SSTable 元数据平均每 0.02 秒修改一次。因此，元数据更新由互斥锁同步。

GC

• 由于 dLSM 支持多个版本，因此有必要对过时的数据执行垃圾收集。即使 SSTable 合并在逻辑上清除旧的数据版本，这些过时的 SSTable 占用的远程内存也不能立即回收。这是因为可能仍有读者引用这些旧的数据版本。因此，远程内存的垃圾收集仍然是一项具有挑战性的任务。需要解决以下问题
• 当计算节点和内存节点都参与远程内存分配(由于近数据合并)时，如何有效正确地收集远程内存中废弃的 sstable？
• 何时执行对于 SST 的 GC？

• 为了解决第一个问题，在 dLSM 中，为近数据合并分配的内存由内存节点回收，而为刷新分配的内存由计算节点回收。在 dLSM 中，SSTable 元数据包含表示其起源的节点 ID。在垃圾收集过程中，计算节点的垃圾收集器从表最初创建的节点 ID 进行标识。如果它是本地的，垃圾收集器通过本地分配器回收其远程内存。否则，会触发 RPC (参见章节10.4) 来远程回收表内存。为了减少通信，多个垃圾收集任务首先在本地分组，然后分批发送到远程内存。

• 为了解决第二个问题，在读取期间，dLSM 的读取器在搜索 sstable 之前固定 lsm 树元数据的快照。lsm 树元数据快照进一步固定它包含的所有 sstable。当 MemTable flush 或 SSTable 合并完成时，以写时复制的方式修改 LSM-tree 元数据，创建多个 LSM-tree 元数据快照。当读取完成时，读取器将解锁 lsm 树元数据快照，并解锁自动进行垃圾收集的相关 sstable。

自适应的近数据 Compaction

• 近数据合并的另一个重要设计决策是确定哪些合并任务应该委托给远程内存节点，哪些合并任务应该在计算节点上执行。由于远程内存节点的计算能力有限，盲目地下推所有合并任务可能无法获得最佳性能。因此，最佳合并策略将动态地考虑硬件配置(在远程内存节点中)和工作负载，以便相应地调整其合并策略。

• 计算节点定期监控两边的CPU利用率，并动态确定应该在哪里执行合并(参见算法2)。由于对性能的影响较大，该算法优先考虑 Level-0 合并(行2)。对于 Level-0 合并，我们使用收集到的信息动态估计执行时间，然后将合并分配到估计时间较小的一侧。对于其他级别的合并，我们评估远程内存中计算资源 core 的可用性。如果有可用的 cores，dLSM 将合并委托给远程内存; 否则，在计算节点上执行合并。

• 实现自适应合并策略存在一些挑战。
• (1) 如何收集决策所需的必要信息？
• (2) 如何确定 0 级合并的优先级，并动态决定合并任务应该放在哪里？
• (3) 如何使用给定的信息估计 Level-0 合并的执行时间？

必要信息收集

• CPU 核数以及双方的动态 CPU 利用率是自适应合并策略的基本信息。当 dLSM 启动时，计算节点从两侧收集 CPU 信息。然后，内存节点每 t 毫秒向计算节点发送心跳 rpc(第10.4节)。远程内存在每次心跳中附加其当前 CPU 利用率。因此，远程 CPU 利用率每 t 毫秒刷新一次。t 应该远远小于合并任务所花费的时间，这样合并决策就可以快速响应工作负载的变化
• 测试发现 compaction 至少需要 100ms，所以 t 默认设置为了 25ms

自适应 Compaction 算法

• 自适应合并的一种直接算法是，只要远程端有可用的计算能力，就将合并任务分配给远程内存。如果计算节点检测到远程内存即将饱和其所有计算资源，则计算节点将合并调度到本地计算端线程。然而，由于两个原因，这种方法不是最优的。
• 首先，它像对待其他级别一样对待 Level-0 合并。这是有问题的，因为 Level-0 中的所有 sstable 都被合并在一起，因此 Level-0 的合并比其他级别的合并需要更长的时间。
• 此外，如前所述，Level-0 合并对性能的影响更大，因为只有 Level 0 中的过大大小才会导致写停滞。因此，Level-0 合并应该具有更高的调度优先级。
• 其次，这种方法忽略了一个事实，即始终将 Level0 合并下推到远程内存节点是不理想的。为了加速 Level-0 合并的执行，dLSM 将其分为多个并行任务。但是，如果合并总是向下推，那么远端较弱的计算能力可能会妨碍并行性。
• 例如，如果远程内存只有一个核心，那么在具有多个线程的计算节点上进行合并的性能会更好。

• 因此，计算节点有必要在调度 Level-0 合并之前估计两边的执行时间。

• 如算法 2 一样，dLSM 通过将 Level-0 合并与其他级别的合并(第2行)区分开来，以更高的优先级调度 Level-0 合并。它使用不同的策略来确定应该在何处执行合并。对于 Level-0 合并，它粗略地估计双方的执行时间(第5.3.3节)。根据估计双方的时间，它决定在哪里放置 Level-0 合并。

• 对于其他级别，当远程端有可用的 CPU 核心时，下推合并是有益的。原因是这些级别的合并任务只包含几个表，并且只由单个线程处理，因此如果有可用的远程 CPU 内核，则远程内存中的执行时间总是更短。因此，计算节点每次在 Level-0 之外调度合并时，都会检查远程内存上的 CPU 利用率。如果 CPU 利用率小于定义的阈值 θ，则在那里执行合并否则在计算节点上执行，直到本地计算能力耗尽。

• 简单概括就是：
• 对于 L0 高优的任务，估计任务时间，然后决定是否下推
• 对于其它层的任务，检查内存节点的利用率是否低于阈值，决定是否下推。

Compaction 任务执行时间估计

• 理论上，合并的执行时间与参与合并的 sstable 的总大小除以合并在执行期间可以实现的并行度成正比。sstable 的总大小可以通过需要合并的 sstable 的数量大致确定，因为大多数sstable 的大小差不多(64MB)。设 为合并 i 个 sstable 的估计执行时间，其中 K 可以是计算端(C)也可以是内存端(M)。 可以计算如下



• 其中 P 是合并任务可以支持的最大并行度，而不管给定的核数是多少。对应其实就是 Compaction 任务的第二层的文件数量
• μ 代表最近的 CPUY 利用率，c 代表对应的核心数，(1 − μK )×cK 表示的即为最近空闲的核心数
• t 代表了每个单元 SST 在单线程下的平均执行时间，我们测试发现内存节点的执行时间只有计算节点的一半，因为计算节点执行的话涉及到网络 I/O

• 上述估计函数对于短合并任务(小于1 μs)是准确的，但对于长合并任务则不准确。原因是 (1-μK)*cK 只能代表暂时可用的核心数。随着当前合并任务的完成，可用于 Level-0 合并的 CPU 核数逐渐增加，最终为 CPU 核总数。算法 2 优先考虑 Level-0 合并，使 Level-0 合并不会过载。因此，如果合并时间太长，我们将当前可用的核数 (1-μK)*cK 替换为总核数 cK，得到以下公式：

• 因此，在算法 2 中，计算节点先判断合并任务是否为长时间合并，然后再决定将合并放在哪一侧。请注意，合并是长还是短与当前正在执行的合并任务有关。因此，当估计执行时间比其他级别的执行时间长时，我们将 Level-0 合并分类为长合并，其中只包含少量 sstable。由于我们事先不知道合并会分配到哪一边，所以我们选择公式 2 作为内存端来粗略估计执行时间。由于非零级别的合并是由单个线程执行的，因此执行时间等于 i × t K avg。总的来说，我们使用下面的公式来划分合并是否长:

• 其中，左手边是根据公式2在内存节点上估计的时间，右手边是合并 s 个sstable的时间估计。根据经验，当 s 接近 5 时，dLSM 表现最好

字节寻址优化

• 现有的 BlockBasedTable 会导致读放大，而其他格式的比如 Cucckoo HashTable 不支持范围查询，Plaintable 依赖于 mmap 无法在远端内存高效应用。

字节寻址的表布局

• 重新设计表结构，如下图所示，减小了读放大，同时减少了写操作中的内存拷贝，因为不需要用 block 包装。为了支持范围查询，键值对在一个 SST 还是有序存储的。

• 索引布局：为了直接索引每个键值对，为每个键值对维护索引 key, offset, and length，二分查找。为了避免 RTT，计算节点缓存索引，索引大小预期能够缓存在本地内存。如果内存有限，使用一些优化来把一些冷的字节寻址的 SST 变回块表。

• 支持点和范围查询：
• 点查：计算节点首先使用 BF 检查，然后读取索引定位位置，再发起网络读来获取单个键值对。
• 范围查询通过顺序 I/O 预取大的 chunks，创建迭代器，每个子迭代器根据元数据和索引定位起始键，然后预取 data chunks，外部迭代器扫描所有的子迭代器。

有限缓存空间大小的优化

• 缓存不够大的时候导致大量的 RTT，而且字节寻址的索引大于原来的块索引。

• 当缓存大小达到了最大值，就需要把一些字节寻址的表转换成块表，实现最小化缓存 miss 和最大化字节寻址表的性能收益之间的权衡。

• 当从字节寻址的表转换成块表的时候，最好给最低 level 最高的优先级，因为相对更冷。

• 挑战：
• 如何动态调整字节寻址表的比例？目标是最小化 SST 转换对于性能的影响。
• 如何优先处理最底层的数据？

Compaction 过程决定 SST 类型

• 通过 Compaction 顺便做了减少计算开销。

• 开始阶段默认都是字节寻址的表，因为本地内存占用少，随着缓存空间大小达到限制，compaction 调度器就开始更喜欢生成块表，相反如果本地缓存大小减少且空闲的空间达到阈值，又重新变成字节寻址的 SST。

• dLSM 定期删除过时的 sstable 的条目，即那些已经被合并到下一级的条目，并立即在本地内存中缓存新创建的 sstable 的所有索引块。因此，决策模块可以获取更准确的实时缓存信息。

Level 优先级

• 使用一个权重因子对 cache 空间阈值加权，上层的权重更大，最底层的最小，所以最底层就更容易达到阈值。
• LSM-tree 的最大层数减去 Compaction 输入的上层的层数，再除以最大层数得到权重。即层次越深权重越低。
• 然后加权。
• 我们可以将剩余缓存空间的加权大小与预定义的阈值进行比较，以确定是否需要进行SSTable转换。

• 如果公式6成立，则可用空间接近极限。一个简单的后续步骤可以是仅当公式成立时生成基于块的sstable，否则生成字节可寻址的sstable。但是，如果合并工作负载很大，这种方法可能会转换更多的表，因为在合并结果生效之前存在延迟。为了避免一次转换许多sstable，我们引入了一个概率因子p来生成基于块的sstable。剩余缓存空间趋近于0时，概率趋近于1。剩余的缓存空间越少，我们就越渴望执行SSTable类型转换。相反，如果 s weighting 接近，则仍然有足够的缓存，因此我们可以安全地减慢转换速度。因此，将概率因子设计为:

• 优化后的算法如算法3所示。当加权剩余缓存空间大于 △ 时，合并只生成可寻址的sstable。如果加权剩余空间小于公式6中描述的阈值，则计算节点生成基于块的sstable的概率只有 p。

混合读写负载优化

• 禁用日志的 dLSM 在具有读写的混合工作负载上实现了中等的性能

• 为了解决这个问题，我们遵循 Nova-LSM 的方法[49]，根据范围信息将整个键范围划分为 λ (λ > 1) 个分片，并为每个分片构建一个单独的 LSM 树。这为 0 级合并增加了更多的并行性，也减少了读取器需要遍历的 sstable 的数量。我们在图 11 中评估了 λ 的影响。结果表明，混合工作负载的性能下降可以通过在计算节点内对数据进行分片来缓解。λ 越高，性能下降越小。

持久化

• dLSM 是一种 LSM 索引，用于具有内存分解功能的主存数据库(例如，voldb[11])。因此，我们没有在索引部分提供数据恢复的整个过程(遵循先前的索引工作，包括Sherman[80]，针对分解内存的优化 b 树索引，以及其他索引工作，例如[37,85,97,98])，因为数据持久化是在数据库层实现的。为了说明这一点，许多现代的主内存数据库，例如，voldb [11]， BatchDB[61]和PACMAN[84]，不使用传统的 重做/撤消 日志来实现持久性，以实现快速性能。相反，他们使用另一种称为命令日志的技术[62]，它记录高级操作，例如 SQL 和存储过程，而不是将物理更新记录到索引中。索引定期刷新到磁盘。如果系统崩溃，则从最后的事务一致性检查点重新执行记录的操作。
• 因此，只要索引提供了一个事务一致的检查点，就可以通过命令日志恢复整个数据库系统。如何实现这样一个事务一致的检查点是本节的研究问题。据我们所知，之前没有关于如何为内存中的 lsm 树实现事务一致检查点的工作。

• dLSM 提供了一个基于 lsm 的索引，该索引本身提供了一个事务一致的检查点。dLSM 中的检查点是定期将 sstable 及其元数据复制到持久存储中。与内存数据库系统中的检查点相比，内存 lsm 树中的检查点不需要每次对所有 sstable 进行完整的扫描和刷新；它只需要将上次检查点以来的更改同步到持久存储。因此，当在 dLSM 中完成 SSTable 合并或 MemTable 刷新时，远程内存上的后台线程确保对 SSTable 的任何添加、删除和元数据更改都会在持久存储中重播

• 此外，为了使检查点事务一致，事务将其所有更新写入单个 MemTable，该 MemTable 在刷新后成为单个 SSTable。只要检查点是在 sstable 的粒度中准备的，检查点就不可能只包含事务更新的一部分。因此，检查点保证是事务一致的。注意，新的更新存储在本地内存中，而检查点进程在远程内存中执行。这种隔离使 dLSM 能够自动提供非阻塞的事务一致检查点，这对于其他传统索引类型来说是很难实现的。

• 上面概述的设计面临一个挑战，即在写密集型工作负载下，持久存储中的检查点可能明显落后于分解内存中的 lsm 树。因此，这个问题会导致远程内存的无限使用，因为 sstable 只有在持久化到持久存储中才能被垃圾收集。落后的原因有两个方面。
• (1) MemTable 刷新和 SSTable 合并导致写入密集型工作负载增加和删除非常多的 SSTable。
• (2) 计算节点与分解内存之间的 I/O 带宽远大于分解内存与持久存储之间的 I/O 带宽，进一步降低了检查点速度。

• 为了应对这一挑战，我们合并了上一次检查点以来的 SSTable 合并结果，以减少检查点所需的 I/O 量。具体来说，我们观察到，当重放合并结果时，一个合并中的一些输出 sstable 是另一个合并中的输入 sstable。这些中间的 sstable 可以在检查点过程中省略。

• 例如，在图 5 中左边，连续有两次合并 (A,B,C → D,E,F)，然后 (E、F、H、I, J) → (K, L, M, N, O)。压实结果一起相当于压实结果右边 (A, B, C, H, I, J) → (D、K, L, M, N, O)，合并后的结果省略了中间结果 E 和 F，节省检查点操作的带宽。

Multi-compute and multi-memory node

• 为了服务大量数据并提高可伸缩性，dLSM 可以分布并部署在多个计算和内存节点上。dLSM 的横向扩展包括两个部分：计算节点的横向扩展和内存节点的横向扩展。对于计算节点来说，关键问题是如何保证多个计算节点之间的缓存一致性。现有的解决方案包括单写多读 [27,76]，软件级缓存一致性协议 [68,81] 或跨计算节点的范围分片[49]。
• 对于第一种解决方案，更新吞吐量受到单个写入节点的限制，而其他读取节点无法立即看到缓冲在 MemTables 中的更新。
• 第二种解决方案可能会给缓存一致性协议带来巨大的开销。

• 在 dLSM 中，我们遵循分片解决方案，这在现有的基于lsm的系统中很流行

• 要向外扩展内存节点，一个关键问题是如何在内存节点之间分布数据。更细的粒度(通过为每个SSTable均匀分布数据块)有利于负载平衡，但它强制近数据合并具有高网络 I/O。为了从近数据合并中获益，我们将数据分布在小分片的粒度中，以便相同范围内的所有数据存储在同一节点中。

• 设 c、m 和 λ 分别为计算节点、内存节点和计算节点内分片的数量。从图 6 中可以看出，dLSM 最初以轮询的方式将 c·λ 分片均匀地分配给 m 个内存节点，以实现最佳负载均衡。对于每个分片，dLSM 构建一个单独的 LSMtree，该 LSMtree 存储在单个内存节点中，MemTables 缓存在单个计算节点中。此外，这些碎片可以稍后在计算节点和内存节点之间移动它们的副本，以平衡工作负载。这种设计的一个优点是，单分片键值访问没有同步开销，但跨分片访问会牺牲分布式事务。第11.3.10节对 dLSM 的这种多节点设计进行了评估。

Instantiating dLSM over RDMA

• RDMA 支持的分解内存得到了很好的研究[42,80,90,98]。因此，我们使用它来实例化和测试 dLSM。然而，在这项工作中提出的一些设计也可以应用于基于 CXL 的内存分解，例如，第4,6,7,8,9节中讨论的设计。

Codebase

• 我们从头开始构建 dLSM，但重用来自 LevelDB 和 RocksDB 的某些数据结构和算法(例如，并发跳表，Bloom 过滤器，不可变 MemTables, SSTable 合并)。dLSM 包含大约 54,400 行 C 代码，其中 4,500 行代码来自RocksDB, 24,300行代码来自LevelDB。

RDMA Manager

• 有效地利用 RDMA 原语在分解内存上设计 LSM 索引中起着重要的作用。在 dLSM 中，RDMA 管理器是连接 dLSM 代码库和 RDMA 原语的中间实现。

Thread local queue pair for concurrent accesses

• 为了支持高度并发访问，RDMA 编程中的一个独特挑战在于如何组织系统中的多个队列对。由于单个队列对最多只能有一个完成队列，因此访问同一队列对的所有线程的完成通知将会混淆。现有的完成通知机制 (例如使用 wr_id )在队列中区分自己的完成引入了同步开销。为了消除同步开销，在 dLSM 中，需要执行单边 RDMA 的每个线程在 RDMA 管理器中都有一个本地队列对。在传输数据时，如果存在线程本地队列对，则线程使用它，否则创建一个。这样，线程在执行单侧 RDMA 时就不会发生冲突，访问队列对也不需要同步。

Allocating RDMA memory region

• 对于每个 RDMA 操作，源和目标内存缓冲区都需要通过 ibv_reg_mr 在网卡中注册。注册固定内存，防止内存被交换。执行频繁的 RDMA 注册会带来不可忽略的开销。尽量减少这种开销是很重要的。

• 许多系统 (例如[40,63]) 倾向于预注册大的内存区域，然后在用户空间中重新分配内存。dLSM 遵循这种方法。dLSM 在内存池方法中分配内存区域，因为内存池分配器具有更少的内存碎片和维护开销。初始化 dLSM 时，内存节点预注册多个 1GB 大小的内存区域。在执行期间，各种工作线程从不同的内存池请求内存。如果内存池内存不足，它们将通过 RDMA 管理器请求 1GB 内存区域，并将其划分为块。当线程分配内存块时，池分配器返回 ibv_mr，它不仅包含指针，还包含该块的本地/远程访问键。在 dLSM 中，为了减少 MemTable 刷新期间的 RDMA 往返，计算节点从远程内存预取 1GB 大小的内存区域，并通过内存池分配器在本地对其进行管理。因此，内存节点为计算节点保留了一些 1GB 大的内存区域。计算节点发出 RDMA RPC 以从内存节点获取注册的远程内存区域。然后，计算节点可以通过自己的内存池分配器分配远程内存。

Asynchronous I/O for MemTable flushing

• 计算节点的本地内存有限。因此，memtable 会定期刷新到远程内存中。当刷新无法赶上内存中的写入时，写入器会减慢其写入速率或等待，直到后台刷新完成。因此，提高 MemTable 刷新速度至关重要。

• RDMA 原语允许我们分别发出 RDMA 工作请求和检查工作请求的完成情况。我们重新设计了 MemTable 刷新过程，以利用这种异步特性。在 dLSM 中，后台工作程序不等待 I/O 完成，而是在新的缓冲区上继续序列化数据。

• 利用异步 I/O 并不是简单地替换 I/O 接口。一个问题是如何无缝地将异步I/O集成到刷新过程中。另一个问题是缓冲区的回收。当缓冲区中的数据通过 RDMA 写入成功地传输到远程节点时，我们称该缓冲区为已完成缓冲区。刷新线程需要回收已完成的缓冲区以减少内存占用。但是 RDMA 的异步 I/O 并不指定完成的 RDMA 操作指向哪个缓冲区。因此，它需要一种新的方法来回收已完成的缓冲区

• dLSM 方法。图 7 展示了 dLSM 的设计。为了解决第一个问题，dLSM 为 MemTable 刷新线程准备了多个缓冲区。dLSM 中的异步刷新过程如下:
• (1) 线程直接将数据序列化到写缓冲区 Flush buffer，而不进行任何数据复制。
• (2) 当缓冲区已满时，提交异步写工作请求 Send Queue，线程继续将数据序列化到下一个缓冲区，不会阻塞。
• (3) RDMA 网卡 RNIC 处理写请求。发送队列中可以挂起多个工作请求。
• (4) writer 线程在每次提交新请求时检查工作请求是否完成。如果它发现工作请求已经完成，它可以重用旧的缓冲区。否则，它将为下一个序列化和刷新任务分配一个新的缓冲区。

• 为了处理第二个挑战，dLSM 利用了 RDMA 工作请求队列的FIFO特性。挂起的刷新缓冲区组织为链接列表式队列，该队列反映发出的工作请求的顺序。刷新线程维护指向链表头部和尾部的指针。头部是即将完成数据传输的缓冲区，尾部是仍在序列化的最新缓冲区。当后台线程填充缓冲区并发出 RDMA 写操作时，线程可以分配一个新的缓冲区并将其附加到链表的尾部。当一个 I/O 在完成队列中完成时，链表的头被弹出并回收。

近数据 Compaction 的自定义 RPC

• 一种实现 RPC 的方法是用双边 RDMA 原语 send recrive，但是这需要一个集中式消息调度程序来将消息转发到目标线程。这可能会对通信量大的 RPC 吞吐量造成潜在的瓶颈。dLSM 利用单侧 RDMA 写来发出应答消息，这样消息就可以绕过调度程序。下面，我们将描述 dLSM 中用于处理简单操作(如建立队列对和远程内存分配)的通用 RPC，以及用于近数据压缩的定制 RPC。

通用 RPC

• 通用 RPC 的处理流程
• 请求者分配一个 rdma 注册的缓冲区来接收应答消息。
• 缓冲区的地址和远程访问密钥 (rkey) 附加到 RPC 请求(通过 RDMA 发送 send/receive 实现)
• 响应器处理 RPC，并通过 RDMA 写入 write 将结果返回到应答缓冲区
• 请求者在应答缓冲区的末尾连续轮询一个布尔 bool 标志。当轮询结果为 TRUE 时，保证消息已准备就绪。轮询线程可以直接处理回复消息

• 应答消息绕过调度程序。因此，dLSM 可以实现更高的 RPC 吞吐量。如果需要，dLSM 可以维护多个分派器和队列对

针对近数据 Compaction 的定制 RPC

• 比通用 RPC 更复杂，因为
• 近数据 Compaction 需要更长的时间，因此计算节点执行 sleep 和 wake up 来避免浪费计算节点的 CPU 资源
• RPC 参数的大小（如需要 Compact 的很多 SST 的元数据）通常比通用的 RPC 更大，需要特殊处理

• Sleep & wake up through RDMA write with immediate
• dLSM 使用 RDMA 立即写入，使 RPC 调度程序意识到应答消息，并唤醒相应的请求线程来处理应答消息。请求者在近数据压缩 RPC 请求中附加一个 4 字节的数字作为唯一 ID，然后进入睡眠状态。当响应方发送应答时，它将唯一 ID 设置为 RDMA 写应答消息中的 immediate。唯一 ID 帮助线程通知程序识别此回复消息属于哪个请求者，以便线程通知程序可以唤醒相应的线程

• Large RPC argument through RDMA read
• 为了支持高度并发的 RPC，通用 RPC 中的请求消息通常很小，例如 10s 字节，以减少响应端消息调度的开销。然而，对于近数据合并，参数大小更大，例如 100s 到 1000s 字节，因为参数包含 sstable 压缩所需的所有元数据
• dLSM 不会在 RPC 请求消息中附加 Compaction 元数据。相反，Compaction 元数据被序列化到 RDMA 注册的缓冲区中。然后，将序列化缓冲区的地址、大小和远程密钥附加到 RDMA 请求消息中。当有 RDMA 请求时，远程内存节点通过 RDMA 读取从计算节点获得所需的合并元数据。在访问元数据时，线程池中的 RPC Worker 可以在内存节点中本地读取远程表内容。合并完成后，内存节点通过 RDMA 写方式将新 sstable 的元数据发送给计算节点。

测试

• 对比对象：
• RocksDB-RDMA (8KB)：扩展 RocksDB 基于 RDMA 实现，块大小 8K，关闭日志；
• RocksDB-RDMA (2KB)：块大小 2KB，便于更好利用字节寻址；
• Memory-RocksDB-RDMA：接近一个键值对大小的块大小，在计算端缓存索引块，开启 compaction 读预取
• Nova-LSM：针对分离存储的 LSM-tree 实现，文件系统使用 tmpfs，基于内存的文件系统
• Disaggregated B-tree (Sherman [80])：针对 DM 高度优化的 B-tree