题目太长，标题又放不下了。。。

FAST23-ROLEX: A Scalable RDMA-oriented Learned Key-Value Store for Disaggregated Memory Systems

FAST 23 的 best paper

作者的主页 ：https://iotlpf.github.io/

论文的 GitHub ：https://github.com/iotlpf/ROLEX

论文的链接 ：https://www.usenix.org/system/files/fast23-li-pengfei.pdf

简介

分离式内存（Disaggregated memory）系统，内存节点计算资源稀缺，计算节点通过 RDMA 访问内存结点。该文针对有序键值存储（例如基于B树和学习索引）在该系统架构下性能不佳（基于树的实现需要多次网络往返搜索数据，基于学习索引的实现依赖内存节点的计算资源）的问题，设计实现了一种基于 RDMA 的可扩展并使用学习索引的键值存储 ROLEX。ROLEX 使用重新训练分离（retraining-decoupled）的学习索引方案，通过为学习模型添加偏差和一些数据移动约束来将模型重新训练与数据修改操作分离。基于操作分离，计算节点通过通过单边 RDMA 进行数据修改，具有高可扩展性。将模型重新训练从数据修改的关键路径中删除，并使用内存节点中的专用计算资源异步执行。在 YCSB 和实际工作负载上的实验结果表明，ROLEX 在静态工作负载上具有竞争性能，并且在动态工作负载上的性能显著提高，最高性能是内存解聚系统上现有方案的 2.2 倍。

背景

Disaggregated Memory Systems

分离式内存系统将单体服务器分解为独立的网络附加组件，通过独立扩展硬件资源，来满足各种应用需求。不同节点通过远程直接内存访问（RDMA）网卡进行通信。RDMA 的重要特性是能通过单边 verbs（包括 RDMA READ， WRITE，ATOMIC）使计算节点直接访问内存节点，而不涉及远端的 CPU。ATOMIC 操作的粒度为 8B，并且可以通过门铃批处理完成多个 READ 和 WRITE 操作减少网络延迟。此外，即使内存池中没有强大的 CPU，每个内存节点通常包含由 FPGA 或 NIC 中的 ARM 核提供的专用计算资源，用于操作卸载。

Network-Attached Ordered KV Store

该文主要关注的是网络附加（network-attached）的有序键值存储，包括基于树的索引和学习索引，这些索引保持所有数据排序并满足范围查询需求。

基于树的结构（Tree-based Structures）。基于树的结构（如B+-树）将数据存储在叶节点中，并构建多级内部节点来搜索叶子节点。然而，该结构的缓存索引占用的空间比较大，本地机器无法缓存整个索引结构，必须消耗多个RTT 来搜索内部节点，使得使用单边 RDMA 访问远程数据时变得低效。

学习索引（Learned Indexes）。学习型索引将搜索数据的过程视为回归模型，通过排序的键（key）的近似累积分布函数（CDF）记录来所有数据的位置。学习模型比基于树的结构节省了 2-4 个数量级的空间，使得本地机器能够缓存整个索引结构，避免使用多个 RTT 来搜索。先前的工作 XStore 用内存节点来处理数据修改，扩展了过时的模型到较大的预测范围，以确保新插入的数据被包含。但是在分离式内存系统上，内存节点的计算资源有限，无法高效地处理密集的修改请求。新模型无法及时重训练，而过时的模型由于模型扩展，无法保证能在一个 RTT 内搜索到远程数据，本地缓存变得无效，随后的数据请求通过经典的 RPC 传输到内存节点，但是 RPC 需要消耗内存节点的计算资源，整体性能显著降低。

现有的键值存储的性能分析

FG 和 Sherman 设计了支持 RDMA 的 B-link 树，使计算节点能够通过单边 RDMA verbs 修改 B-link 树。EMT-D 是即基于 eRPC 的 Masstree，XStore-D 是之前基于学习索引的 B 树，他们两用来以分析基于 RPC 的 KV 存储在分离式内存系统上效率低下的原因。

下图的 a，b，c 子实验图分为说明了：1. 学习索引在大规模静态工作负载上的表现优于基于树的结构；2. 在动态工作负载下，索引缓存会失效；3. 分离式系统需要有效的单边 RDMA 操作。（详细的分析看原文）

3 个挑战

文章总结了有序键值存储在分离式系统中的 3 个挑战：

1. Limited computing resources on memory nodes. 内存节点计算资源有限。

2. Overloaded bandwidth for data transferring. 数据传输带宽过载，具体来说，计算节点需要消耗大量网络带宽来平衡基于树的结构（如，多级节点拆分和合并）或获取大量数据以重新训练学习索引的模型（由计算节点来训练模型）。

3. Inconsistency issue among different nodes. 一致性问题老生常谈了。

设计与实现

Overview

与之前的方案不同，ROLEX 不在内存节点上维护 B 树 处理数据请求。ROLEX 在存储数据上构建了重新训练分离（retraining-decoupled）的学习索引，计算节点通过单边 RDMA 操作处理数据请求。ROLEX 采用原子设计执行索引操作，并通过具有一致性保证的分离插入和重新训练操作异步地重新训练模型。

下图展示了 ROLEX 的总体架构。在内存池中，ROLEX 将所有数据存储到固定大小的叶子节点中（一个叶子就是一个数组），并基于这些数据构建了一个基于插入和重训练操作解耦的学习索引。对于处理动态工作负载，计算节点直接修改远程叶子节点而无需重新训练模型。通过添加一些偏差和数据移动约束，未重新训练的模型能够正确识别所有数据。为了使用单边 RDMA 为新数据构建足够的数据叶，提出了叶原子移位方案（leaf-atomic shift scheme），该方案还保持所有数据排序以进行范围查询并避免不同计算节点之间的冲突。因为内存节点获取所有待处理的重训练数据到计算节点来进行模型训练会消耗大量网络带宽，且再训练开销主要来自数据合并和重新排序，而训练算法的复杂度仅为 O(N)，所以 ROLEX 借助叶表（leaf table）在内存节点上异步重新训练模型。重新训练后，ROLEX 使用阴影重定向方案（shadow redirection scheme）更新内存池中的模型，而计算节点直到下次读取之前不会同步重新训练的模型。

Retraining-decoupled Learned Indexes

在动态工作负载中，学习索引的挑战数据位置变动后避免学习模型数据丢失（及无法通过模型获取数据位置）。

在动态工作负载中合并学习索引的挑战在于保持所有数据排序和在插入期间避免学习模型数据丢失的高开销。如下图所示，红线代表在黑点上（即训练数据）训练的线性回归模型。只要数据未移出预测范围[pred-ε，pred+ε]（即蓝色块），就可以在此预测范围内找到所有数据，其中 ε 是预定义的最大模型误差。当插入一些新数据后，点 a 移动到 a'，超出了预测范围。为记录新位置，需要逐步重新训练模型，包括数据重排序、重训练模型和将模型同步到所有计算节点。这时系统会被阻塞，直到重新训练和同步完成，进而产生长延迟并降低整个系统的性能。

该文修改了训练算法并添加了一些约束条件，以帮助非重新训练的模型在不重新训练的情况下始终找到所有数据，避免了频繁重新训练模型。

训练算法。使用改进的 OptimalPLR 算法来训练分段线性回归（piecewise linear regression，PLR）模型，其中 OptimalPLR 算法已经被证明在保证较小的时间和空间复杂度（O(N)）的同时具有最小数量的 PLR 模。OptimalPLR 的关键思想是在训练数据上构建多个具有 2ε 宽度的最优平行四边形，其中最优平行四边形被定义为一个垂直方向上宽度为 2ε 的平行四边形，使得没有训练数据在平行四边形之外，如上图所示的蓝色块。为确保训练出的模型即使在插入数据后仍能找到所有数据，在预测计算中添加偏差（表示为δ），以及添加一些数据移动的限制，改进了 OptimalPLR 算法。

如公式 1 ，优化的平行四边形通过保证所有数据的预测位置 f(Xi) 和真实位置 Yi 之间的距离不大于预定义的最大模型误差（ε）来确定，而预测范围 Prange 则是通过添加额外的 δ 来计算。因此，所有数据预测范围的覆盖面积大于确定的优化平行四边形，即图 3 中将蓝色块扩展为黄色块。在这种情况下，只要数据移动的位置不超过 δ，模型就不需要重新训练。

数据移动约束。1. 在固定大小的叶内移动数据。 在训练阶段将数据存储到固定大小的数组（称为叶节点）中，每个叶节点最多包含 δ 个数据。 所有数据只允许在分配给它们的叶内移动。再将位置预测转换到叶节点预测，即，学习模型通过公式 2 给出一系列可能包含数据的叶节点。因为数据移动被限制在叶节点内，所以可以通过单边 RDMA 操作读取 Lrange 来获取数据。2. 同义词叶共享（Synonym-leaf sharing）。当一个叶节点（l）内的插槽不够时，会分配一个新的叶节点（nl）来存放更多的数据，其中 nl 与 l 使用相同的位置（即用于训练的标签）。该文将 nl 定义为 l 的同义词叶子，并通过指针链接。同义词叶子的数据相互移动以便于数据排序。nl 不会改变模型记录的位置，因此学习索引仍然通过 公式 2 计算 Lrange，但是需要搜索由 Lrange 范围内叶节点的同义词叶子。

当一个叶子(l)的插槽不足时，我们分配一个新叶子(nl)来容纳更多的数据，其中nl与l使用相同的位置（即用于训练的标签）共享。我们将nl定义为l的同义词叶子，通过指针链接。同义词叶子的数据相互移动以便于数据排序。由于nl不会改变模型记录的位置，因此学习索引仍然通过方程2计算Lrange。此外，我们需要搜索由Lrange引用的同义词叶子，因为数据可能位于预测和同义词叶子中。

ROLEX Structure

Memory pool stores data. 所有数据被存储在固定大小的叶节点中，所有叶子都存储在一个 RDMA 注册内存区域中分配的连续区域中（称为叶节点区域）。叶子区域的结构如 Figure 2 所示，其中前两个 8B 数据分别用于指示已分配的叶子数量（alloc_num）和叶子区域可以分配的总数（那个图貌似看不出）。其余的叶子区域存储大量的叶节点，每个叶节点包含 δ 个键值对。分配新叶节点时，使用原子操作 FAA 读取 alloc_num 并写入alloc_num + 1，然后将数据存储到 alloc_num 指向的叶节点中。通过叶节点区域的起始位置加上偏移量来访问叶节点。因为ROLEX 通过固定大小的叶子分配和回收空间，在 ROLEX 中可以有效地减轻碎片化和垃圾收集。

在存储的叶子上会训练多个 PLR 模型，模型之间不存在位置依赖关系，每个模型由四个部分组成，包括覆盖的最小键、模型参数、叶表（leaf table，LT）和同义词叶表（synonym leaf table，SLT），如 Figure 4 所示。LT 和 SLT 存储叶号（即分配时的alloc_num），以访问叶节点。通过在最小键上训练上层模型（upper models）来对获得的 PLR 模型进行索引（我猜就是还有个上层模型来确定用哪个 PLR 模型），其中上层模型不包含叶表。重复这个过程，并构建多级模型，类似于 PGM-index，由于空间消耗较小，这些模型在计算节点中被完全缓存。

Compute pool caches indexes. 新添加的计算节点通过 RNIC 识别共享的内存池，并获取模型和叶节点区域的起始地址。新的计算节点从模型区域读取学习模型后，根据学习模型的预测范围高效地访问远程数据，其中预测范围条目包含叶节点区域号和叶节点号。ROLEX 通过单边 RDMA 操作在计算节点上处理各种数据请求（例如搜索、更新、插入和删除）。

One-sided Index Operations

ROLEX 提出了一种叶原子转换方案（leaf-atomic shift scheme），既保证了计算节点同时修改时的数据一致性，又只需要少量的的RDMA 操作。 该设计为不同的计算节点自动分配共享内存池中的写入区域，并使每个计算节点能够通过陈旧的索引结构访问数据。

LT 和 SLT 的结构。 ROLEX 通过原子操作 FAA 利用叶区域中的 8B 的 alloc_num 来实现无锁叶节点分配，并使用 LT 中的 8B 条目来保证一致的叶节点修改。 LT 和 SLT 的结构如上面的 Figure 4 所示。SLT 中的第一个槽位（slot_use）表示 SLT 中槽位被使用了多少，在构造新的同义词叶时修改。LT 和 SLT 的其他槽存储 8B 大小的条目（entries），每个条目由锁（1 位）、叶区号（7 位）、指针（8 位）和叶号（48 位）组成。 由于只锁定当前叶子而不是模型下的所有叶子，因此锁是轻量级和细粒度的。使用叶区号和叶号来确定叶节点，而指针指向 SLT 的偏移量以链接同义词叶节点。 例如，如 Figure 4 中，叶子 0 的指针指向 3，说明叶子 0 有一个同义词叶节点存储在SLT 的第 3 个位置，而这个同义词叶子存储在叶子区域的第 6 个位置。 LT 的大小在训练阶段确定，而 SLT 的大小固定为包含 2 的 8 次方个槽。 每个叶区域最多注册 2 的 48 次方个叶子，而一个模型最多可以构造 (2 的 8 次方 - 1) 个同义词叶子。

Point query. 对于给定的键，计算节点通过以下步骤搜索远程数据：1. 根据公式 2 用本地学习索引预测 Lrange；2. 通过查找 LT 和 SLT 将叶节点位置转换为物理地址，计算方式如公式 3；3. 根据物理地址通过 doorbell 批量的读取叶节点；4. 搜索读取的叶节点，根据值（value）指针进一步读取值。

Range query. 和上面步骤相似。

Insert. 步骤如下：1. Fetching.  计算节点像点查询一样获取远程叶子；2. Fine-grained locking. 计算节点根据数据顺序确定要插入的叶节点，通过CAS 操作将 LT 表项的锁位置改为 1 来锁定。加锁后，计算节点读取该叶节点及其同义词叶节点以保证数据是最新的。即使叶节点及其同义词叶子在被锁定之前被其他计算节点修改，向其中插入数据仍然保持所有数据排序，因为叶节点中的数据只允许在 叶节点及其同义词叶节点内移动。3. Writing and unlocking. 计算节点按照数据顺序向获取到的叶节点中插入数据，并通过 CAS 解锁。当获取的叶节点没有足够的空槽时，计算节点会构造一个新的同义词叶节点，如 Figure 5。

Update. 和点查询一样获取远程叶节点，当给定的键在其中一个获取的叶子中时，锁定并重新读取相应的叶子以确保数据是最新的，最后更新键值项并解锁远程叶子。

Delete. 先像插入操作一样获取和锁定远程叶节点，如计算节点获取叶节点 L1 及其同义词叶节点 L5-8，当 Key 在其中一个叶节点，例如 L6，计算节点删除 L6 中的 Key，而其他叶节点不被修改。 当删除后 L6 变为空时，计算节点通过修改叶子表的方式删除 L6，即将 L5 链接到 L7。  计算节点将 L6 写入内存节点并解锁叶子。直到下一次保留时才删除空的训练叶子 L1，以避免预测错误。其他计算节点在观察到同义词叶节点中的数据未排序时识别出被删除的叶子，从而进一步同步叶子表并读取远程数据。

Asynchronous Retraining

再训练开销来自数据排序和再训练算法。ROLEX 在内存节点上异步重新训练数据，以实现网络消耗和计算资源利用之间的有效权衡。ROLEX 维护一个循环队列 (CirQ) 来识别待处理的再训练模型，并使用阴影重定向方案在不阻塞系统的情况下再训练模型。 具体来说，当模型消耗了 2 的 7 次方个 SLT 槽时，计算节点在 CirQ 的末尾插入模型的指针。内存节点定期检查 CirQ 的头部进行再训练，CirQ 在后台重新训练模型并构建新的 LT 以合并旧的 LT 和 SLT，而计算节点能并发访问旧模型。（估计一次是训练一个 PLR 模型）

一致性保证。如 Figure 6 显示了当内存节点重新训练叶节点 L1-5 时的一致性保证，其中 L5 是 L3 的同义词叶节点。 因为是异步的重训练，计算节点可以在重训练的同时修改数据，当数据的位置没有被新模型重新训练时，这会导致不一致，例如，构造了 L5 的新同义词叶节点 L8 和在同义词叶子内移动数据。ROLEX 通过将未重新训练的数据重定向到新模型的新 SLT 中来确保数据的一致性。

1. ROLEX 通过查看出现在旧 LT 或 SLT 中但未出现在新 LT 中的条目被识别为未重新训练的叶节点（如 L8）。 如 Figure 6 ，重训练后用新模型替换旧模型时，ROLEX 锁定旧模型并将 L8 插入新 SLT，并在解锁前将模型指针更新。类似地，通过检查旧叶表和新叶表来识别移除的叶。

2. ROLEX 通过检查之前训练过的叶子来识别移动的数据的新位置。 如 Figure 6 ，在重训练开始前，将每个叶节点中最左边和最右边的数据分别表示为 Xl 和 Xr，如 X3l 表示 L3 的最左边数据。 重训练时，旧模型在 L3 中插入 15，在新构造的同义词叶节点 L9 中插入 18 和 24。问题在于确保新模型正确识别被旧模型修改的数据，包括叶节点中的训练数据（例如，X3l 和 X3r 之间的数据）和两个排序的叶节点之间的新数据（例如，X3r 和 X5l 之间的数据）。 根据公式 2，新模型预测 L3 中 X3l 和 X3r 之间的数据，如这里的 5 和 18 之间改变的数据 15 和 18，新模型仍然能预测到在 L3 及其同义词叶节点中，但是 X3r 和 X5l 之间的数据（如 24）会出现不一致状态，因为新模型可能会预测 24 在 L5 中而不是在 L3 的同义词叶节点 L9 中。为避免此类错误，ROLEX 会检查前一叶（即 L3，直面说过有叶节点有同义词叶，会一起检查）以正确识别修改后的数据。

ROLEX 不需要重新训练或移动任何数据，因为所有数据都已在运行时按叶表排序。在重新训练期间没有数据丢失，因为所有叶节点要么被新模型重新训练，要么被插入到新的 SLT 中。文章认为重训练频率较低，训练模型的速度比填充同义词叶节点的速度要快得多。 此外，ROLEX 有一个优先级队列来识别和训练 SLT 几乎要满了的模型，以避免该模型在 SLT 中的插槽不足。

实验

实验相关事项

3 个计算节点和 3 和存储节点，通过在内存结点限制只能使用一个 CPU core 来模拟计算资源有限。

Workload: YCSB; Lognormal & Normal distributions. 8B keys and values

对比对象：FG [SIGMOD19]，Sherman [SIGMOD'22]，Masstree [NSDI19]，XStore-D [OSDI20]（本来都是有论文链接的，但是 b 站只能放站内链接。。。。。。）

YCSB 的实验结果

不同场景的性能

可拓展性实验

优化措施可行性验证

个人看法

乍一看确实以为和 XStore 很像，但 2 个工作还是很有大的差别的，是新场景下的旧系统表现出的新问题的新解决方法。学习索引了解不深，看起来文章内容确实很充实，可能个人水平问题，文章有的部分看起来描述上有点绕。zuo pengfei 在分离式内存场景下，就老的系统优化配置做了好几篇工作了，可以学着取搞搞。

按着论文章节来是不是太详细了，又太花时间了。。。。

如有问题，欢迎批评指正！！