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

开源代码：https://github.com/dmemsys/FUSEE

一作作者暂时看起来还是特别有名，且没找到个人主页啥的

简介

分布式内存键值（key-value，KV）存储正在采用分离式内存（disaggregated memory，DM）架构来实现更高的资源利用率。然而，现有的 DM 上的 KV 存储采用的是半分离（semi-disaggregated）设计，即将 KV 存储在 DM 上，但另外使用单体元数据服务器（monolithic metadata servers）来管理元数据，因此元数据服务器上依然存在资源效率低的问题。为了解决这个问题，该文提出了 FUSEE，一种完全内存分离式（fully memory-disaggregated）的 KV 存储，来分离式的管理元数据。FUSEE 在内存节点上复制元数据（索引和内存管理信息），直接在 client 上进行管理，并在 DM 架构下处理复杂的故障。为了可扩展地在 client 上复制索引，FUSEE 提出了一个 client 中心的复制协议，允许 client 同时访问和修改复制的索引。为了有效地管理分散化内存，FUSEE 采用了两级内存管理方案，将内存管理职责分配给 client 和内存节点。最后，为了处理 client 故障下的元数据损坏，FUSEE利用嵌入式操作日志方案以低的日志维护开销修复元数据。用微基准测试和 YCSB 混合基准测试对 FUSEE 进行评估，实验结果表明，FUSEE 比 DM 上的最先进的 KV 存储性能高 4.5 倍，且资源消耗更少。

（先喷起来，不排除个人见识水平有限，眼光不足，看了好几篇分离式内存架构下的 KV 设计了，第一次看到 client （client）这个称呼，关键顺着看下来，一开始还不好猜这个 client 涵盖哪些东西，文字迷惑性高得一批，最后在喷，这里为了好理解，个人认为可以先将 client 理解为运行在计算节点上的程序，能发出并执行如 KV  操作等任务 ）

先放前面，通俗点，这篇文章针对的是 ATC 20 的 Disaggregating persistent memory and controlling them remotely: An exploration of passive disaggregated key- value stores. （这篇文章好歹刚开始是用 client/compute nodes 来方便理解 client）

背景动机挑战

分离式内存架构

DM 将单体服务器（monolithic servers）的 CPU 和内存分为两个独立的硬件资源池，包含计算节点（compute nodes，CNs）和内存节点（memory nodes，MNs）。CNs 拥有丰富的 CPU core 和少量内存作为本地缓存。MNs 托管各种内存介质，例如 DRAM 和持久性内存，具有较弱的计算能力。CNs 中的 CPU 使用快速的远程访问互连技术，例如单边 RDMA 等直接访问 MNs 中的内存。

分离式内存下的 KV 存储

如下图 Clover（ATC20 的那篇文章）采用半分离设计，将数据和元数据分离，以降低所有权成本并防止数据节点的计算能力成为性能瓶颈。Clover 用额外的单体元数据服务器来管理元数据，包括内存管理信息（memory management information，MMI）和哈希索引。对于搜索请求， client 从元数据服务器查找 KV 对的地址，然后使用 RDMA_READ 操作从 MNs 中获取数据。对于插入和更新请求， client 通过 RPC 从元数据服务器分配内存块，使用 RDMA_WRITE 操作将 KV 对写入 MNs，并通过 RPC 更新元数据服务器上的哈希索引。为防止 client 的频繁请求压垮元数据服务器， client 一次分配一个批次的内存块，并在本地缓存哈希索引。

然而，Clover 的半分离式设计由于基于单体服务器来管理元数据，无法充分利用 DM 架构的资源效率。一方面，单体式元数据服务器消耗额外的资源，包括 CPU、内存和 RNIC。另一方面，由于元数据管理的 CPU 密集型特性，必须保留和分配许多计算和内存资源给 Clover 的元数据服务器才能实现良好的性能。

为了解决 Clover 存在的问题，FUSEE 采用了完全的内存分离式设计，使 client 能够直接访问和修改哈希索引，并在 MN 上管理内存空间，如上图 b。

挑战

Client-Centric Index Replication

挑战一。

在完全内存分离的情况下实现线性化复制哈希索引（或者说备份）的关键挑战来自于 DM 的 client 中心计算（client-centric computation）性质。

第一，现有的方法都是 server 中心（server-centric）性质，数据副本由管理数据的 CPU 进行独占式访问和修改，很依赖 server 端的 CPU。挑战在于，在完全内存分离的情况下，没有这样的管理 CPU，因为所有 client 都使用单边 RDMA 直接访问和修改哈希索引。（个人理解就是不好照搬之前的方法，不好管理，说的云里雾里的）

第二，简单地采用共识协议或远程锁定等方法会导致请求序列化的性能问题。

Remote Memory Allocation

挑战二。

DM 的关键挑战在于在哪里执行内存管理计算。若将内存管理元数据存储在 MNs 上，并允许 client 通过直接修改MNs 上的元数据来分配内存空间，但是内存管理元数据由所有 client 共享，会存在同步问题，因此该方法会因为在 DM 上昂贵且复杂的远程同步过程，使得内存分配延迟升高。若将所有内存管理元数据让计算能力弱的 MNs 处理，MNs 的内存端计算能力可能无法承担来自 client 的频繁的细粒度 KV 分配请求。

Metadata Corruption

挑战三。

崩溃的 client 可能会危及整个 KV 存储系统的正确性。首先，崩溃的 client 可能会使索引处于部分修改的状态，其他正常 client 可能无法访问数据，甚至使用已经损坏的索引访问错误的数据。其次，崩溃的 client 可能会分配内存空间，但不使用它们，导致严重的内存泄漏。为了确保 KV 存储的正确性，在 client 故障时必须修复损坏的元数据。

设计

如下图，FUSEE 由client、MNs 和一个 master 组成。client 提供 SEARCH，INSERT，DELETE 和 UPDATE 接口来使得应用程序访问 KV 对。MNs 存储复制的内存管理信息（memory management information，MMI）、哈希索引和 KV 对。master 是一个集群管理进程，仅负责初始化 client 和 MNs，并在 client 和 MNs 故障时恢复数据。

RACE Hashing

ATC 20 中 One-sided rdma-conscious extendible hashing for disaggregated memory 的哈希。

如下图，该文使用的是一种单边 RDMA 友好的哈希索引 RACE hashing，它包含多个 8 字节的 slot，每个 slot 存储一个指向 KV 对地址的指针，一个 8 位指纹（fingerprint，Fp）即键的哈希值的一部分，以及 KV 对的长度（Len）。对于 SEARCH 请求，client 先根据目标键的哈希值读取哈希索引的 slot，然后根据 slot 中的指针读取 MN 上的 KV 对。对于 UPDATE，INSERT 和 DELETE 请求，先将 KV 对写入 MN，然后使用 RDMA_CAS 操作原子地修改哈希索引中相应的 slot 中的指针（先写真实的数据，再替换指针）。

The SNAPSHOT Replication Protocol

解决挑战一。

为了有效地维护复制哈希索引中 slot 的强一致性，FUSEE 提出了 SNAPSHOT 复制协议，这是一种 client 为中心的复制协议。

在完全内存分离的情况下有效地实现线性化有两个主要的挑战。第一个是如何使得 reader 在读写冲突期间避免读取不完整的状态。第二个是如何在不昂贵地对所有冲突请求进行序列化的情况下解决写-写冲突（how to resolve writewrite conflicts without expensively serializing all conflicting requests）。

对于读取数据的操作，之前的 RACE hash 已经提过，写入数据是先将真实的 KV 数据写入，再去用 RDMA 原子操作替换 slot 中的值，读取时先用 RDMA READ 操作读取 slot，因为原子操作的原子性，读取 slot 不会读到不完整的状态，之后再根据 slot 中的信息读取真实的数据，而真实的数据是在 slot 更新前写入的，所以也不会出现数据不完整的情况。所以读取数据没啥问题。

对于写冲突的处理，原文描述有点多，这里就以下图为例子。首先有一个主 slot 和 3 个备份， client 1 和 2 同时准备更改 slot（真实数据先写完了），client 1 想将 A 写成 B，client 2 想将 A 写成 C。

第 1 步，client 们先读取主 slot 的值，这里是 A。

第 2 步，client 们先用广播的 RDMA CAS 操作试图去操作备份 slot 中的值（这里如果 slot 中是 A，就将 A 改为想写的值），因为 CAS 操作的原子性，旧值只能被更改一次，client 1 将 A 改了 B，client 2 就无法改为 C 了，这里从 AAA 改为了 BBC。因为 CAS 操作会返回操作时 slot 中的值，所以每个 client 可以根据返回值推测出最后的结果（只有返回值是期待值 A，才会替换为自己想写的值）， 所以如 client 1 可以根据返回值 AAC 推测出更改后的值为 BBC。

第 3 步，首先有 3 个规则。规则 1：成功修改所有备份 slot 的 client 是最后写入者（last writer）。

规则 2：已成功修改大部分备份 slot 的 client 是最后写入者。

规则 3：如果前两条规则都不能确定最后写入者，则写入最小目标值的 client 被认为是最后写入者。

总体上就是多数优先，最后写入者就是获胜者，就是本次冲突最后保留和更改的值。如这里根据规则，client 1 是最后写入者，所以 client 1 先将备份 slot 全写为 B，再将主 slot 也改为 B，而 client 2 知道自己不是最后写入者，它反复的读取主 slot 的值，直到主 slot 的值被改变，即不为 A。

SNAPSHOT 保证有界的最坏情况延迟，在触发规则 1 的情况下，需要 3 个 RTT 才能完成一次 WRITE 操作。在触发规则 2 或规则 3 的情况下，分别需要 4 或 5 个RTT。

Two-Level Memory Management

解决挑战二。

该方法的关键思想是将以 server 为中心的内存管理任务拆分为在 MN 和 client 上运行的计算轻型粗粒度管理和计算密集型细粒度管理。

FUSEE 首先对多个 MN 上的 48 位内存空间进行复制和分区，使用一致性哈希将一个区域映射到哈希环中的一个位置，然后将副本存储在该位置之后的 r 个 MN 中，并将主要区域放置在第 r 个 MN 中。

下图是 FUSEE 的两级内存分配。第一层是低计算要求的粗粒度 MN 端内存块分配，每个 MN 将其本地内存区域划分为粗粒度的内存块，例如 16 MB（应该就是下图中一个 block 16 MB 的意思吧），并在每个内存区域之前维护一个块分配表， 对于每个内存块，块分配表记录了它被分配给的 client 的 ID (CID)。 Client 通过向 MN 发送 ALLOC 请求来分配内存块，MN 收到 ALLOC 请求后，从其主内存区域之一分配内存块，将 client ID 记录在主区域和备用区域的块分配表中，并将内存块的地址回复给 client。 第二层是细粒度的 client 对象分配，分配小对象来保存 KV 对。 Client 使用 slab 分配器来管理从 MN 分配的块，slab 分配器将内存块拆分为不同大小级别的对象，然后从适合它的最小尺寸类中分配一个 KV 对（大致就是每个块内又被分为了各种大小固定且一致的 object，要存 KV 的时候选个合适大小的空闲 object）。

为了使 client 高效回收释放的内存对象，FUSEE 在每个内存块之前存储了一个空闲位图，其中每个位表示一个对象在内存块中的分配状态。分配块时，空闲位图被初始化为全零。释放对象时，client 使用 RDMA_FAA 操作将空闲位图中的相应位设置为 1。通过读取空闲位图，client 可以很容易地知道自己的内存块中被释放的对象，并在本地回收它们。FUSEE 使用后台线程以批处理的方式周期性释放和回收内存对象，避免在 KV 访问的关键路径上进行额外的 RDMA 操作。

Embedded Operation Log

解决挑战三。

大致是，如下图，用日志来容灾和恢复。为了减少DM上的日志维护开销，FUSEE 用一个 RDMA_WRITE 操作，将嵌入式日志条目与其对应的 KV 对一起写入。然后日志里有前一个对象的指针，后一个对象的指针，旧的值，CRC 验证位，操作码，和 used 位。 used 位指示对象是在使用中还是空闲，在整个对象的末尾存储 used 可以用来检查整个对象的完整性（RDMA 的性质来保证）。因为有前后对象的指针，这些操作就被组织成了一个链表，可以方便管理日志和用于故障修复。

那么如何知道每个对象的前后指针呢？这和前面的设计有关，如下图 b，因为由 client 本身来管理其得到的内存块，对于每个大小级别，client 在本地将远程空闲对象的地址组织为一个空闲列表，然后对象总是从本地空闲列表的头部分配，每个大小类别的分配顺序是预先确定的，前后指针也就是已知的了。

Optimizations

自适应索引缓存。 搞个阈值判断写入密集型和读密集型，只有读密集型用缓存读数据，具体看原文。

RDMA-related optimizations. 如下图

Failure Handling

看原文吧。

实验

实验配置

Run all experiments on 22 physical machines (5 MNs and 17 CNs) on the APT cluster of CloudLab. Each machine is equipped with an 8-core Intel Xeon E5-2450 processor, 16GB DRAM, and a 56Gbps Mellanox ConnectX3 IB RNIC. These machines are interconnected with 56Gbps Mellanox SX6036G switches.

Microbenchmark Performance

时延结果如下图，FUSEE 在 INSERT 和 UPDATE 上表现最好，因为 SNAPSHOT 复制协议限制了 RTT。FUSEE 的 SEARCH 延迟略高于 Clover，因为 FUSEE 在单个 RTT 中读取哈希索引和 KV 对，这比在 Clover 中仅读取 KV 对慢。FUSEE 的 DELETE 延迟略高于 pDPM-Direct，因为 FUSEE 在单个 RTT 中写入日志条目并读取哈希索引，这比 pDPM-Direct 仅读取哈希索引慢。

吞吐结果如下：pDPM-Direct 的吞吐量受其远程锁的限制。 Clover，但可扩展性仍然低于 FUSEE，因为元数据服务器的 CPU 处理能力限制了它的吞吐量。 FUSEE 通过消除元数据服务器的计算瓶颈并有效解决与 SNAPSHOT 复制协议的冲突，提高了整体吞吐量。

YCSB Performance

还有很多，看原文。

个人看法

感觉这篇和上一篇 ROLEX 都像是针对之前的顶会中的一个工作，进行适配或者优化，然后都是分离式内存系统下的 KV store，不过 ROLEX 侧重的是 KV store 中的一个点，学术界的感觉浓一点，这篇侧重整体 KV Store，功能完整性多点，工业界的感觉浓一点，设计很巧妙，但是累了不想喷了，写的是真难看。

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