摘要

远程直接内存访问(Remote Direct Memory Access，RDMA)通过提供对远程主机内存的低延迟、绕过cpu的访问，已被用于加速各种分布式系统。然而，在这些系统中使用的大多数分布式协议都不能很容易地用RDMA提供的简单的内存读和写来表示。因此，设计人员面临一个选择，要么引入额外的协议复杂性(例如，额外的往返行程)，要么完全放弃RDMA的好处。

本文认为对RDMA接口的扩展可以解决这一困境。我们介绍PRISM接口，它添加了四个新的原语:indirection、allocation、enhanced-CAS、operation chaining。这些增加了RDMA接口的表现力，同时仍然可以使用相同的底层硬件特性实现。我们通过设计三个使用PRISM原语的新应用程序来展示它们的实用性，这些应用程序几乎不需要服务器端CPU的参与:(1)PRISM-KV，键值存储;(2) PRISM-RS，一个复制的块存储;(3) PRISM-TX，分布式事务协议。通过使用PRISM原语的基于软件的实现，我们证明了这些系统优于之前基于rdma的等效系统。

1. 引言

远程直接内存访问(RDMA)已迅速成为数据中心系统中实现高吞吐量和低延迟的不可或缺的工具之一。随着网络带宽相对于CPU速度的不断增加，降低数据包处理的CPU成本变得至关重要。这使得RDMA,它提供了一个标准,加速一个主机接口直接访问另一个主机的内存：硬件RDMA实现完全绕过主机CPU[28],甚至软件实现提供显著的性能改进,简化了网络堆栈和减少上下文切换开销[26]。

大量的文献探讨了如何重新设计分布式系统以使用RDMA通信[6,10,14,31,44]。一个常见的主题是，使应用程序在RDMA上运行需要进行复杂且昂贵的修改。这种复杂性的根源在于RDMA接口本身：很少有分布式应用程序能够轻易地用简单的远程内存读写操作来表达它们的逻辑。因此，许多RDMA应用程序被迫添加额外的操作，即额外的网络往返，以牺牲一些延迟优势[10,31,32]。其他的使用混合设计，要求应用程序CPU参与一些操作[10,31,43]-或者，在某些情况下，仅仅使用RDMA来实现更快的消息传递协议[15,34]-这否定了CPU旁路的好处。

本文认为，超越基本的RDMA接口是实现构建低延迟系统的网络加速的全部潜力的必要条件。RDMA接口最初是为了支持并行超级计算应用而设计的，它无法满足当今分布式系统的需求。我们展示了通过使用一些额外的原语扩展接口，就可以完全使用远程操作实现复杂的分布式应用程序，比如复制存储。

我们在这篇文章中的目标是确定一组通用的(即非应用特定的)RDMA接口扩展，允许分布式系统更好地利用RDMA硬件的低延迟和CPU卸载能力。我们的提案是PRISM接口。PRISM用另外四个原语扩展了RDMA读/写接口：indirection、allocation、enhanced-CAS、operation chaining。结合起来，它们支持常见的远程访问模式，如数据结构导航、错位更新和并发控制。我们认为PRISM API非常简单，可以在RDMA NIC中实现，因为它重用了现有的微架构机制。我们还在基于软件的原型网络堆栈中实现PRISM接口，该网络堆栈使用专用CPU核心实现远程操作，其灵感来自谷歌的SNAP网络堆栈所采取的方法。

我们通过三个常见分布式应用程序的案例研究来演示PRISM API的优点。第一个是键值存储，它演示了PRISM可用于读取和操作远程数据结构，将读取延迟降低到Pilaf的75%，尽管我们的原型使用软件模拟单边操作。第二种是复制块存储，通过使用CAS和间接操作来实现ABD仲裁协议，提供容错存储，与传统的基于锁的方法相比，提供了50%的吞吐量改进，尽管使用专用的CPU内核来实现单边操作。第三种是事务性键值存储，它在分片存储系统上提供了强大的原子性保证。它的新协议使用CAS和间接操作，仅使用两次往返就提交事务。这使吞吐量比FaRM提高了20%，同时减少了18%的延迟。

综上所述，本文做出了以下贡献：

我们证明了现有的RDMA接口为分布式系统带来了额外的协议复杂性。
我们引入了PRISM接口，它通过额外的原语扩展了RDMA，以支持分布式应用程序中的常见模式。
我们展示了三个复杂的应用程序——键值存储、复制块存储和分布式事务——可以完全使用PRISM接口实现。
我们构建了PRISM接口的基于软件的原型，并展示了尽管与NIC相比它有额外的性能开销，但在PRISM之上构建的应用程序实现了延迟和吞吐量方面的好处。

2. 背景和动机

RDMA是一个广泛部署的网络接口，它允许远程客户端直接在远程主机上读或写内存，完全绕过远程CPU。

2.1 RPCs vs内存访问：RDMA的困境

RDMA提供两种类型的操作。双边操作具有传统的消息传递语义。一个SEND操作将消息发送给调用receive的远程应用程序。单边操作允许主机在远程主机上(在预先注册的区域)读或写内存。

在系统界，关于是使用单边操作还是双面操作的争论相当激烈[16,19,43]。单边操作更快，CPU效率更高，但仅限于简单的读写操作。双面消息传递，因为它允许在两端进行处理，可以产生一个整体上更快的系统，即使通信操作本身较慢。

要了解这种权衡是如何进行的，可以考虑例如Pilaf[31]，一个早期的基于rdma的键值存储。Pilaf将指向键值对象的指针存储在哈希表中，而实际数据存储在单独的区段结构中。这两种结构都是通过RDMA公开的，因此客户端可以通过远程读取哈希表来执行键-值查找，然后使用指针远程读取区段存储。这不需要服务器端CPU的参与，但是需要两次往返。使用双边操作构建的传统键值存储实现只需要一次往返，但每个操作都涉及CPU。

那么，系统设计人员的困境是，是在读写操作之外构建更复杂的协议，还是在消息传递方面构建更简单的协议？换句话说，是执行两个(或多个)单边RDMA操作更快，还是执行单个RPC更快?在RDMA的早期，选择是明确的：RDMA操作比RPC快20倍[31]。由于后续工作极大地降低了双向RPC的成本[16,19]，并且RDMA已经部署在具有更高延迟的大规模设置中[12,13]，使用哪一种的问题要复杂得多。

为了理解当前的权衡，我们在两台使用40GB以太网连接的服务器上测量单边RDMA操作与使用eRPC[16]实现的双边RPC的性能(4.3节描述细节)。使用单边读取完成512字节值的读取大约需要3.2us，比使用双面RPC快43% (5.6us)。但这意味着，像上面的例子一样，一个单边读的系统比一个纯软件实现慢0.8us。因此，单边RDMA操作只有在不需要更复杂的协议时才会提供性能优势。

2.2 后RDMA系统的原则

大多数关于RDMA系统的工作都假设我们被限制在当前的RDMA读/写接口。如果我们可以扩展RDMA接口呢?硬件供应商[29]和软件实现[26]以一种特别的方式添加了各种新的操作。在本文中，我们后退一步，询问需要哪些新功能来支持直接在RDMA上运行的分布式系统，而不需要CPU参与或额外的往返行程。

导航数据结构：当大小和位置已知时，RDMA支持远程读取。大多数应用程序，如Pilaf，使用更复杂的数据结构来构建索引，存储变长对象，并帮助处理并发更新。遍历这些结构需要多次RDMA读取。能够在指针上执行间接操作可以消除一些往返。

支持异地更新：修改远程数据结构尤其具有挑战性，因为读取操作可能同时发生。为了避免随之而来的一致性问题，许多系统[10,31,32]只从服务器CPU执行写操作。我们的目标是构建能够使用RDMA操作同时处理读写的系统。为此，我们提倡一种设计模式，将新数据写入到一个单独的缓冲区中，然后自动更新指针以从旧值交换到新值——这种方法类似于并发编程中的read-copy-update[27]。要实现这一点，需要新的RDMA支持，将数据写入新的缓冲区，并自动更新指向其位置的指针。

乐观并发控制：对复杂数据结构的更新需要同步。虽然现在可以使用RDMA来实现锁[44,45]，但性能损失可能很大。扩展RDMA的比较和交换功能将允许我们实现复杂的、基于版本的乐观并发控制[21]，这种方法很适合我们的异地更新方法。

链式操作：一个常见的主题是应用程序需要执行复合操作，其中后一个操作的参数取决于前一个操作的结果——先读取一个指针，然后读取它所指向的值，或写入一个对象，然后交换指针。现在，这需要将中间结果返回给客户机，并执行一个新的操作——以及另一个网络往返。如果我们有一种方法将操作链接起来，使一个操作依赖于另一个操作，但仍然在一个往返行程中执行它们，就可以避免这种开销。

2.3 扩展接口的案例

可以通过以各种方式扩展RDMA接口来解决上一节的原则。在本文中，我们论证了一组简单的、通用的扩展可以用于各种应用程序。使用简单的操作可以实现和部署这些扩展。

另一种方法是允许应用程序提供在远程主机上运行的自己的代码，即将自定义应用程序逻辑部署到智能网卡[3,37]。虽然这种方法很强大，但它在部署方面存在相当大的挑战。通过与部署了智能网卡的云提供商对话，即使在单租户环境中，推出智能网卡更新也是一项挑战，因为它涉及到主机上运行的所有东西的停机时间。允许多租户环境中的用户提供自己的代码带来了主要的安全性和性能隔离挑战[22,41]。

相反，我们主张一组简单的泛型原语。这样简单的扩展可能对更多的应用程序有用，无论是当前的还是未来的。这里的简单性也有助于实现：我们认为我们提出的原语可以添加到基于软件的网络堆栈、可重新配置的智能网卡，甚至可以添加到未来的固定功能网卡。本文的其余部分提出了这样的一般扩展，并演示了它们对于一般应用程序是有用的。

3 PRISM接口

为了解决使用RDMA构建分布式系统的固有挑战，我们提出了一个扩展网络接口PRISM(用于与系统内存远程交互的原语，Primitives for Remote Interaction with System Memory)。PRISM为现有的RDMA接口增加了四个额外特性。这些设计是为了支持我们在实现分布式协议时观察到的常见模式。

PRISM的接口是围绕三个原则设计的:(1)通用性——它们不应该编码特定于应用程序的功能;(2)界面复杂度最小;(3)最小的实现复杂性，实现了快速、可预测的性能，便于在各种平台上实现，包括未来的NIC ASICs。

遵循这些原则，我们以四种方式扩展RDMA接口。表1提供了PRISM API的摘要。

3.1 indirect操作

许多RDMA应用程序需要遍历远程数据结构。这些结构在许多方面使用间接：提供索引，支持可变长度数据，等等。目前，追逐指针需要额外的往返。

PRISM允许read、write和比较与交换(CAS)操作接受间接参数。这些操作的目标地址可以被解释为指向实际目标的指针的地址。此外，用于write或cas操作的数据可以从服务器端内存位置读取，而不是从RDMA请求本身读取。

对于read和write，目标可以被选择解释为一个⟨ptr,bound⟩结构。在这种情况下，操作的长度被限制为客户端请求的长度和边界的较小值。这支持变长对象:客户机可以执行大长度读取，但只接收实际存储的数据。

PRISM中的间接操作重用了现有的RDMA安全机制，这些机制确保远程客户端只能在被授予访问权限的主机内存区域上操作。为了通过间接操作访问内存区域，客户端必须包含主机在该区域第一次注册到NIC时生成的密钥。如果目标地址或目标地址所指向的位置在具有不同rkey的内存区域中(或者根本没有注册)，该操作将被主机拒绝。

3.2 内存分配

修改数据结构对于现有的RDMA接口来说尤其具有挑战性：必须将对象写入固定的、预先分配的内存区域，这使得处理大小可变的对象或位置不正确的更新变得困难。需要的是一个内存分配原语。PRISM提供了一个，它分配一个缓冲区并返回指向其位置的指针。

为了使用PRISM的分配原语，服务器端进程向NIC注册(RDMA术语为“post”)一个缓冲区队列。当NIC从远程主机接收到一个ALLOCATE请求时，它从这个空闲列表弹出一个缓冲区，将提供的数据写入缓冲区，并使用地址进行响应。这个操作与PRISM的请求链接机制结合起来特别强大，下面将讨论这个机制：PRISM客户机可以分配一个缓冲区，向它写入数据，然后在另一个数据结构中安装指向它的指针(通过CAS)。

PRISM在网卡(或软件网络栈)数据平面上进行内存分配。然而，内存注册是由服务器CPU完成的。这是必要的，因为注册内存需要与内核交互，以识别相应的物理地址和固定缓冲区。因为涉及到服务器CPU，所以对于应用程序重用这些缓冲区的正确性至关重要，因为只有当并发网卡操作完成时，回收的缓冲区才会被添加回空闲列表。虽然这只是将同步NIC和服务器CPU的负担转移到原语的实现上，但重要的是将这种同步移出了应用程序的常规路径。

管理客户端分配的内存可能具有挑战性;对于通过远程访问修改状态的应用程序来说，这是一个基本的挑战。特定的内存管理策略由应用程序自行决定。本文中的应用程序使用客户端来检测何时不再使用对象，例如，何时替换了以前的版本。它们将未使用的缓冲区报告给一个运行在服务器上的守护进程(通过传统RPC)，后者将其重新注册到NIC的空闲列表中;可以在客户端和服务器端使用批处理来最小化开销。另一种受垃圾收集启发的方法是，让服务器端应用程序代码定期扫描数据结构，以确定可以回收的缓冲区。

我们的分配器故意设计得很简单，只从特定队列中分配第一个可用的缓冲区。我们选择这个而不是一个更复杂的分配器，因为(如§4.2所述)现有的RDMA网卡已经有必要的硬件支持来实现它。结果是，使用整个预分配的缓冲区分配内存会带来空间开销。应用程序可以通过注册包含不同大小缓冲区的多个队列，并选择合适的队列来最小化这种影响。例如，使用大小为2的缓冲区可以保证最大空间开销为2倍。纯软件实现可能会选择使用更复杂的分配器。

3.3 增强的CAS

原子比较与交换(CAS)是在并行系统中更新数据的经典原语。RDMA标准已经提供了一个原子CAS操作[30]，但是它受到了高度的限制:它只进行一次相等比较，然后交换一个64位值。根据我们的经验，这不足以实现性能应用程序(包括§6-8中的应用程序)。事实上，除了实现锁之外，目前很少有应用程序使用RDMA原子操作[33,45]。虽然可以使用锁实现任意复杂的原子操作，但这需要多次昂贵的往返，并增加了争用。

为了解决这个问题，我们以三种方式扩展CAS原语。首先，我们采用Mellanox RDMA设备[30]目前提供的扩展原子接口，它允许最多32字节的CAS操作，并为CAS参数使用单独的位掩码，使比较结构中的一个字段和交换另一个字段成为可能。其次，我们将间接寻址(§3.1)用于目标地址或比较和交换值。我们不能保证对间接实参指针的解引用是原子的——只有cas本身是原子的——但这允许我们从内存中加载实参值。最后，我们在比较阶段支持算术比较操作符(大于/小于)，以及按位相等。这支持更新版本化对象的通用模式：检查新版本是否大于现有版本，如果大于，则同时更新版本号和对象。

PRISM的cas操作与其他PRISM操作相比是原子的。与现有的RDMA原子一样，对于并发CPU操作，它们不能保证原子性。

3.4 操作链接

分布式应用程序通常需要执行一系列与数据相关的操作来读取或更新远程数据结构。例如，他们可能希望分配一个缓冲区，写入它，然后更新指向它的指针。目前，每个操作必须返回到客户机，然后才能发出下一个操作。PRISM提供了一个链接机制，允许像这样的复合操作在单个往返行程中执行。

有条件的操作：通常，RDMA并不保证操作按顺序执行。我们添加了一个条件标志，它将一个操作的执行延迟到来自同一客户端的前一个操作完成，并且除非前一个操作成功，否则不会执行。比较失败的CAS操作在这里被视为不成功。

输出重定向：我们引入了另一个标志，它指定应该将操作的输出(READ或ALLOCATE)写入指定的内存位置，而不是发送到客户机。该内存位置通常是每个连接的临时缓冲区。例如，可以执行一个ALLOCATE，将其输出重定向到一个临时位置，然后使用一个带条件的write将指针存储到其他地方新分配的缓冲区。

3.5 讨论

PRISM原语一起实现了§2.2和§2.3的目标。间接操作减少了导航数据结构所需的往返次数。allocate和增强的cas原语，结合链接，支持异地更新：一个应用程序可以ALLOCATE一个新的缓冲区，写入数据到它，并使用CAS安装一个指向它的指针到另一个结构中，所有这些都在一个单一的往返行程中。最后，我们的cas操作的灵活性使得实现基于版本的并发控制机制成为可能。

4 PRISM实现

PRISM的API由简单的原语组成，因此可以轻松地将它们添加到各种RDMA实现中。为了评估它们在构建分布式应用程序中的有效性，我们构建了一个基于软件的实现(§4.1)。我们还分析了在NIC中实现PRISM的可行性(§4.2)。我们评估了我们的软件实现的性能和硬件实现的预期好处，以及智能NIC方法。(§4.3)。

4.1 软件PRISM实现

我们使用一个受谷歌的Snap[26]启发的软件实现来定量评估PRISM对应用程序的好处。这是一个在客户机和服务器上都使用的库，它同时支持传统的RDMA操作和PRISM扩展。它通过eRPC[16]与远程端的专用线程通信来实现PRISM扩展，专用线程实现适当的原语。

尽管软件实现使用服务器端CPU，但在网络堆栈中执行的单边操作通过避免上下文切换和应用程序级线程调度的成本，提供了性能优势。关于在谷歌[26]大规模部署Snap的报告指出了这些优点，以及更容易升级和更广泛的硬件支持等部署优点。软件方法也使得部署新的原语更加容易;Snap已经支持(及其应用程序使用)间接读取。

PRISM有限的接口使高效实现成为可能。虽然原则上可以在软件网络堆栈中运行任意复杂的、特定于应用程序的操作，但这会带来部署和安全方面的挑战。PRISM通过提供一个简单的、通用的原语库来避免这种情况。PRISM的每个原语都可以在很短的有限时间内运行，这对于防止饥饿非常重要。

智能网卡部署：原则上，该软件实现也可用于智能网卡；我们已经在Mellanox BlueField进行了实验。然而，正如下面(§4.3)所示，这种方法的性能低于软件实现，所以我们不提倡使用它，除非降低CPU利用率是主要目标。

4.2 硬件网卡可行性

PRISM被设计为可在未来的RDMA网卡中实现。我们分析的这一部分必然是推测性的，因为支持rdma的NIC asic是专有设计，我们没有扩展的能力。然而，我们认为实现PRISM原语是可行的，因为它们重用当今nic中已经存在的底层机制。例如，所有原语中常见的问题，如丢失、损坏和超时，将使用nic已经实现的相同的CRC和重传机制来处理，每个原语都重用现有的机制：

间接：间接读或写在概念上与直接读然后直接读或写是相同的，RDMA网卡已经异步处理内存访问，因此间接不会从根本上改变处理模型。但是，它增加了性能开销，特别是额外的PCIe往返，我们将在下一节中对其进行评估。

分配：虽然allocate在概念上是一个新函数，但我们观察到它的行为与传统的send/receive函数非常相似，NIC从接收队列中分配一个缓冲区来写入传入消息;现有的SRQ功能允许多个连接共享一个接收队列。我们用队列对的方式来表示空闲列表——这是一种标准的RDMA结构，包含了一组空闲缓冲区。当NIC处理ALLOCATE请求时，它弹出队列对中的第一个缓冲区，并返回指向该缓冲区的指针。对于不同大小的缓冲区，我们使用独立的、应用程序选择的队列对。

PRISM要求只有在完成NIC上的所有其他操作后才发布缓冲区。正常操作获取读写锁的读端，而发布缓冲区获取写端。在处理CAS操作的网卡上已经存在这种类型的同步机制。

增强的CAS：支持扩展原子的RDMA网卡已经支持高达32字节的屏蔽操作。我们允许用不等式代替相等比较。用于实现RDMA的FETCH-AND-ADD原语的加法器可以用来计算这个不等式。

链接：附加的标志允许条件执行和输出重定向。RDMA网卡已经在某些类型的操作之间强制执行排序关系，并在错误时停止处理;我们的条件标志只是添加了一个额外的约束。如果NIC缺乏足够的内存来缓冲链式操作，它可以像往常一样，用标准流控制机制接收器未就绪包(Receiver Not Ready packet)拒绝请求。

输出重定向要求将结果写入内存而不是网络。如果目标地址在主机内存中，其输出被重定向的操作将导致额外的PCIe往返，这可能会对性能造成重大影响。幸运的是，最近的NIC设计提供了一个用户可访问的NIC内存区域(Mellanox ConnectX5网卡[28]上的256kb)。使用输出重定向的应用程序应该在可能的情况下重定向到这个nic上的内存，并且只将其作为操作链的一部分临时存储。一个可能的问题是，我们的设计需要每个连接临时存储。历史上，每个连接状态限制了RDMA网卡可以有效支持的连接数量[10,18]。然而，与现有的每个连接状态(≈375B[16])相比，需要的临时空间很小——32b /连接就足以满足我们的应用。一个256kb的内存区域提供8192个32B位置，这超过了推荐的并发连接限制，以获得良好的性能[18]。

有线协议扩展 PRISM API需要对RDMA有线协议进行最小的修改。它需要在RDMA报头(IB BTH)中增加5个标志。其中三个用于间接——两个控制read、WRITE或cas的两个参数是否被视为间接，第三个指示read或write的目标地址是否是一个有边界的指针。链接使用两个标志，分别控制条件和输出重定向行为。

4.3 性能评估

在图1中，我们将PRISM的软件实现与现有RDMA操作的性能进行了比较。这些实验使用两台机器(Intel Xeon Gold 6138处理器，96GB RAM, Ubuntu 18.04)和Mellanox ConnectX-5 25 GbE RDMA网卡。为了排除网络延迟的影响，我们在两个网卡之间使用直接连接(没有交换机)。作为基准的RDMA操作延时为2.5us，PRISM的软件原型在此基础上增加了2.5-2.8us延时。

我们还比较了一个假设的基于asic的PRISM NIC的性能模型，计算方法是将额外的PCIe往返(使用预先测量[35])的成本添加到相应的RDMA操作的延迟中——例如，间接的treadis建模为RDMAREAD加上一个额外的指针大小的PCIe读取。我们还通过在Mellanox BlueField上运行我们的实现来建模智能网卡部署的成本，该实现将RDMA网卡与ARM Cortex A72 CPU(8核，800 MHz)结合起来，并添加访问主机内存的测量开销。可能令人惊讶的是，这个选项是最慢的：BlueField较慢的CPU使其具有更高的处理延迟，而且它对主机内存访问的延迟很高（约3us）。

PRISM的性能不仅取决于执行成本，还取决于网络延迟，因为与RDMA相比，它的性能优势在于消除了网络往返。图1通过使用一个直接的网络链接，考虑了PRISM的最坏情况。图2通过比较PRISM间接读取与执行两个RDMA读取的代价，评估了网络延迟的影响。我们考虑一个带有一个交换机的单机架部署，一个具有三层交换机层次结构的集群，以及从真实数据中心[12]报告的延迟数字，这也反映了网络拥塞。在每种情况下，PRISM的软件实现都优于RDMA基线，尽管有使用CPU的额外成本。

5 应用程序概述

为了演示PRISM的潜在好处，我们使用三个具有代表性的分布式应用的案例研究:

PRISM-KV:一个键值存储，在RDMA上实现读和写操作。(§6)
PRISM-RS:实现ABD[4]仲裁复制协议的复制存储系统。(§7)
PRISM-TX:一个事务性存储系统，它使用PRISM的原语实现基于时间戳的乐观并发控制协议。(§8)

每一类应用都广泛应用于实践，并已成为许多研究的主题。在接下来的每一节中，我们将回顾其中一个应用程序的现有RDMA实现，展示当前的RDMA接口如何导致过度的复杂性或成本，并使用PRISM原语设计一个新系统。

使用我们的基于软件的PRISM原型，我们展示了我们的PRISM应用程序优于以前的RDMA系统。我们使用多达12台机器的集群(规格如§4.3所示)，拥有40GB以太网。客户端和服务器连接到一台Arista 7050QX交换机（添加0.6us的延迟）。对于PRISM来说，这是一个具有挑战性的配置，因为更大的集群或更拥挤的网络将有更高的延迟，因此从减少往返中获益更多。

6 PRISM-KV:键值存储

键值存储是一种广泛使用的基础设施，是使用RDMA进行加速的一个自然机会。我们首先考虑一个简单的远程、未复制的键值存储，类似于memcached。它提供了GET/PUT接口，其中键和值可以是任意长度的字符串。

作为使用RDMA实现KV存储所面临的挑战的一个例子，再考虑一下Pilaf[31]。Pilaf使用单边操作来实现GET操作；PUT操作通过双边RPC机制发送，并由服务器CPU执行。它存储一个固定大小的哈希表，其中只包含一个有效的位和一个指向键值存储区的指针，键值存储在一个单独的区段区域中。为了执行GET操作，Pilaf客户端计算该键的哈希值，并向哈希表执行一个单边read，然后向它所指向的数据执行第二个read。哈希冲突通过线性探测或布谷鸟哈希来解决，这可能需要读取额外的指针。

Pilaf不使用单边操作来实现PUT请求。使用RDMA接口实现PUT是很有挑战性的：它支持可变大小的对象，因此PUT可能需要在区段区域分配新的空间，任何适当的修改必须以不与其他并发操作冲突的方式进行。

6.1 PRISM-KV设计

我们新的键值存储，PRISM-KV，遵循与Pilaf相同的一般设计，但是使用单边操作实现了get和put操作。它维护一个哈希表索引，其中包含指向数据项的指针；这些项现在都在使用PRISM分配原语所分配的缓冲区中。

PRISM-KV服务器最初为哈希表和数据分配内存区域，并注册用于RDMA访问。它还会发布一组缓冲区供ALLOCATE使用，并定期检查是否需要更多的缓冲区。

客户机通过使用键的哈希值探测正确的哈希表槽来执行GET操作。为此，它对设置了间接位的槽执行READ，检索槽所指向的数据(如果有的话)。然后，它验证键是否匹配，在出现哈希冲突的情况下，使用线性探测重新尝试。与Pilaf所需的2个READ相比，PRISM-KV每次访问(或重试)只需要一个PRISM操作。

要执行PUT，客户端首先确定正确的哈希表槽，如上所述。然后，客户机写入新值，并使用一个PRISM原语链更新散列表槽。首先，客户端使用allocate将值写入一个新的缓冲区，并将地址重定向到一个临时位置。然后，它对哈希表槽执行CAS，如果旧地址在客户端确定正确槽后没有更改，则将其替换为存储在临时位置的地址。为最后一个操作同时设置了适当的间接位和条件标志。如果cas失败，这表明并发客户机随后用新的值覆盖了相同的键。如果成功，客户端异步通知服务器将旧版本的缓冲区返回到空闲列表。

PRISM-KV在并发更新期间确保正确性，因为对象被写入到分开的缓冲区，并且指向这些缓冲区的指针被原子地安装到适当的哈希表槽中。与更新同时进行的读取也不会违反安全性，因为间接读取哈希表槽可以保证读取格式良好的地址，并且地址适合缓存行。请注意，刚刚完成更新的客户机可能试图释放缓冲区，而间接读尝试读取它。这对正确性来说不是问题，因为PRISM在将缓冲区添加回空闲列表之前要等待并发网卡操作完成。

整个PRISM原语链需要一次往返，就像Pilaf的双边PUT一样。然而，与Pilaf不同的是，它们可以在不涉及应用程序CPU的情况下执行。

6.2 评估

我们在同一个框架中实现了Pilaf和PRISM-KV，以评估使用PRISM进行键值存储的权衡。我们比较了使用RDMA硬件的版本和使用与PRISM相同的软件实现的版本。每个实验使用一台服务器机器和4.1节中描述的硬件，以及多达11台客户机。服务器使用16个专用核来处理rpc和实现PRISM原语，这足以为两个系统实现行速率。

我们评估了YCSB[7]工作负载A(50% R/50% W)和C(100% R)的性能。所有工作负载使用800万个512字节的对象和8字节的键。对象访问分布是统一的，并且我们使用了一个无碰撞哈希函数。

间接读可以减少延迟：只读工作负载(图3)表明PRISM-KV实现了延迟改进，主要是因为它可以用一个间接read替换两个RDMA read。正如预期的那样，当使用基于rpc的读取实现将PRISM-KV与Pilaf进行比较时，差异约为2倍（6us vs 14us）。另外的2us源于Pilaf用来检测并发更新的CRC计算；PRISM-KV的原子位置更新方法避免了这些需求。硬件RDMA实现将Pilaf的延迟降低到8us，仍然高于PRISM-KV。

复杂性增加了每个请求的网络使用：每个系统都可以使40 Gbps的网络饱和。然而，PRISM-KV实现了22%更高的读吞吐量，因为服务器每请求传输的数据更少;Pilaf需要发送两个已读回复及其相应的报头，以及上面提到的应用程序级CRC。

对于50/50读/写工作负载(图4)，Pilaf使用一个双边RPC处理每个put，平均需要6us。PRISM-KV使用两个往返行程，一个间接地标识正确的哈希表槽，另一个执行分配、写和cas链。在我们的软件原型中，这需要12us。(注意，我们做了一个悲观的假设，哈希表槽没有缓存；读-修改-写工作负载可以避免PUT的第一次往返)。

硬件实现：我们的软件PRISM实现在只读工作负载上优于启用RDMA的Pilaf的延迟和吞吐量，并与50/50混合工作负载匹配。根据§4.3的分析，我们预计PRISM的硬件实现可以进一步降低延迟2us。此外，它释放了执行RPC所需的CPU核心，提高了效率。

7 PRISM-RS:复制块存储

作为我们的下一个案例研究，我们考虑一个复制的块存储。块存储为具有固定标识符(即块)的对象提供get和put操作。这样的系统为可靠地实现更复杂的应用程序(如文件系统[11,39]或键值存储[6,10,43,44])提供了基础。

PRISM-RS是我们的块存储设计，保证线性化，保证可用性只要n = 2f+1台机器中不超过f台机器失效，并且在复制过程中只需要最少的CPU参与。它是通过使用PRISM操作实现ABD[4]原子寄存器协议的一个变体来实现的。

7.1 背景：ABD

ABD协议是一个经典的分布式算法，它实现了一个容错的、线性化的共享寄存器[4]。共享寄存器是多个客户端可以通过get和put操作并发访问的对象。我们关注Lynch和Shvartsman的多写入器变体[25]，因为允许多个客户机进行修改对于实际的存储系统是必要的。我们从单个寄存器的角度来描述该协议，尽管通过向消息添加寄存器标识符将其扩展到多个寄存器是很自然的。

8 PRISM-TX:分布式事务

我们接下来讨论提供分布式事务性存储的问题。具体地说，我们考虑这样一个存储系统，其中数据在多个服务器之间分区，客户端将操作分组到事务中。在事务的执行阶段，它们从不同的服务器读取或写入数据。随后，客户端请求提交一个事务，系统要么原子地提交它，要么中止它。所有提交的事务都是可序列化的。提供这些事务性语义一直是分布式数据库[5]的一个经典问题;最近的系统已经使用RDMA来加速事务性存储[6,10,19,43,44]。

8.1 背景：FaRM

FaRM是RDMA[10]上事务处理技术的一个典型例子。在FaRM中，数据存储在一个可通过RDMA访问的哈希表中，每个对象都与一个版本号和一个锁相关联。在事务执行期间，客户端使用单边的RDMA READ操作访问服务器内存来执行读取操作，并在本地写入缓冲区，直到提交阶段。对于FaRM的键值存储变体，每次访问都需要两个read，就像在Pilaf中一样。提交过程是一个需要CPU参与的三相协议。客户端首先锁定写集中的所有对象。这样做之后，它们将重新读取读集中的所有对象，以验证它们没有被同时修改。最后，它们更新已写入的对象并对其进行解锁。第二阶段可以使用read实现；另外两个需要rpc。

FaRM受益于RDMA的低延迟传输，但它仍然需要大量的服务器CPU参与。虽然读操作是使用单边RDMA操作实现的，但是提交阶段的更复杂的逻辑不能这样做。

8.2 PRISM-TX设计

我们能否构建一个分布式事务协议，使用远程操作同时实现其执行和提交阶段？使用PRISM的新原语，特别是增强的cas操作，我们在一个称为PRISM-TX的协议中实现乐观并发控制检查。

PRISM-TX的设计灵感来自Meerkat[38]，一种最新的分布式乐观并发控制协议。Meerkat是我们PRISMTX设计的一个很好的起点，因为它按Key划分并发控制元数据，为每个对象增加一个散列表(与维护和扫描活动事务列表[21]的传统OCC设计不同)。虽然Meerkat使用它来避免多核瓶颈，但我们利用它来提供远程访问:OCC元数据存储在定义良好的每个键的位置。

在PRISM-TX中，和在Meerkat中一样，每个事务都有一个时间戳。这些时间戳是在客户端使用松散同步的时钟选择的，这种策略在许多先前的系统中使用[1,8,38,40,46]。客户端使用RDMA操作执行读操作，本地执行缓冲区写操作。提交事务需要两个阶段。首先，在准备阶段，客户机检查冲突事务是否准备或提交，并记录其提交的意图。它通过使用PRISM的cas操作更新与它读写的记录相关联的时间戳来做到这一点。如果成功，则通过安装其写操作提交事务。

内存布局：PRISM-TX构建在PRISM-KV和PRISM-RS之上。与PRISM-KV一样，数据被安排在每个服务器上的一个哈希表中，通过探测正确的哈希表槽来访问键。与PRISM-RS一样，每个插槽包含并发控制元数据和一个指向已提交数据存储位置的指针。图8描述了散列表和元数据。特别地，对于每个密钥，维护以下信息:

PR——读取密钥并准备提交的最近事务的时间戳。
PW——需要写入密钥并准备提交的最近事务的时间戳。
C——写入此键的最近提交事务的时间戳。

执行阶段：客户端通过在相应的分区服务器上使用类似PRISM-KV的get(§6.1)的机制执行读操作，并缓冲写操作来执行事务。执行阶段产生一个Read-Set，一个包含元组⟨key，RC⟩的集合用于事务读取的每个密钥，其中RC是读取的密钥版本(即其C值)，以及一个包含元组⟨key，value⟩的集合，用于事务写入。

准备阶段：在执行阶段之后，客户端使用松散同步的逻辑时钟[1,40]为事务选择逻辑提交时间戳TS，方式与Meerkat相同:它选择一个元组⟨clock_time,cid⟩。clock_time初始被设置为客户机的本地时钟时间，但是对于所有读键的RC，它会被调整使得TS > RC。cid是客户端的id，被加上以确保时间戳是唯一的。然后，客户端执行一系列验证检查，以确定事务是否可以按TS排序。对于ReadSet中的每个密钥，客户端执行一个读验证检查:它检查没有并发事务准备写入该密钥，即该read事务可以读取最新版本。如果不是，它更新PR来记录它的读和块冲突写：

读验证：对于ReadSet中的每个key i和RC，如果RC == PWi，更新PRi = max(TS，PRi)。注意到条件等效于PC ≥ PW，因为PW不会减少而且一定大于C。因此，这可以表示为单个CAS操作用于检查是否RC|TS大于PW|PR（|为连接）。这将以原子方式执行更新。如果检查失败（RC < PW）或者更新是不必要的（PR一直比TS大），该CAS操作可能会失败；客户端可以通过CAS返回的结果区分这两种情况。如果所有读验证检查都成功，客户机将继续验证写操作。对于WriteSet中的每个键，客户端执行写验证检查：它检查写这个键的TS不会使并发读操作无效(读的事务可能看起来没有读过最新版本)。它通过检查TS > PR来做到这一点。客户端还通过检查TS > PW来检查它是否是最近的写入。
写验证：对于WriteSet中的每个key i，如果TS > PRi且TS > PWi，更新PWi = TS。该验证不能通过一个单独的CAS操作来执行。然而，请注意，更新不需要在两个条件下都以原子方式执行；只要在之后检查第一个条件，就可以用第二个条件原子地执行它。直观地说，这是因为增加PW总是安全的，因为这只会防止并发读者提交。换句话说，乐观地记录事务写入密钥的意图是安全的(即使最终没有成功)。这样做可能会导致不必要的中止，但并不违反正确性。因此，PRISM-TX执行TS > PW的检查并通过一个CAS操作更新PW = TS，如果它成功，再分别检查TS > PR。

提交阶段：如果所有验证检查都成功，客户端提交事务并使用一系列PRISM原语应用WriteSet中的每个write⟨key,value⟩。它遵循与PRISM-RS的写入阶段(§7.3)相同的ALLOCATE/WRITE/CAS特性，分配一个包含TS|key|value的新的缓冲区，并当TS > Ci时在适当的槽位上安装一个指向它的指针。如果任何验证检查失败，客户机将中止事务。典型的事务协议(包括Meerkat)会在准备阶段撤销元数据更新;PRISM-TX不能这样做，因为它只跟踪PR和PW的最新时间戳。相反，它让这些时间戳保持原样。如上所述，对PR和PW使用较高的(即保守的)值总是安全的。然而，这可能会阻止其他事务提交。为了减少这种影响，对于成功完成写检查的每个密钥，客户机更新C = TS如果TS > C。

正确性：PRISM-TX确保了顺序性：事务按照时间戳顺序执行。由于篇幅有限，我们无法提供详细的证明，但请注意，下面的证明是Meerkat协议[38]的扩展。直观地说，当任何一个具有更早时间戳的事务修改了事务T读的数据，或任何一个具有更晚时间戳的事务读取或更新了之前T所修改过的数据时，PRISM-TX会通过禁止事务T提交来防止异常。PRISM-TX基本上遵循与Meerkat相同的时间戳分配和验证协议，除了PRISM-TX的读写验证规则比Meerkat中使用的规则更严格保守，因为Meerkat跟踪读取或写入密钥的完整准备事务列表。PRISM-TX只跟踪读取(PR)或修改(PW)密钥的事务的最高时间戳。

8.3 评估

我们将PRISM-TX与FaRM协议的实现进行比较，同样使用了FaRM的硬件和软件RDMA实现。由于测试平台的大小有限，我们只使用一个分片(但仍然运行完整的分布式提交协议)。我们使用YCSB-T工作负载，由简短的读-修改-写事务组成，包含800万个512字节的对象。图9显示了使用统一访问模式的YCSB-T的性能结果。PRISM-TX在延迟和吞吐量方面都优于FaRM。由于PRISM原语支持较低的消息复杂性，PRISM-TX比FaRM快5us并且在网络饱和之前达到每秒100万次事务。

因为PRISM-TX使用不同的并发控制协议，性能权衡可能会随着不同的工作负载而变化。乐观协议在高争用下会受到影响。图10评估了不同工作负载倾斜级别(Zipf分布)下的峰值吞吐量。PRISM-TX在高竞争下保持其性能优势。

9 相关工作

RDMA系统：许多存储系统都是围绕RDMA接口构建的；我们的目的不是提供一个完整的列表，而只是强调相关的趋势。Pilaf的哈希表使用间接，因此它需要两次读取来执行GET，并使用RPC来执行PUT。Cell实现了一个B树，它需要更多的往返行程来执行读取(尽管缓存可以有效)。XStore用学习过的索引结构替换树，以更少的RDMA读取进行搜索，但仍然需要间接搜索。PRISM的间接原语可以帮助许多这样的系统。在事务系统中，FaRM使用RDMA读取数据，但使用RPC提交更新。DrTM从单边操作构建一个基于锁的协议。PRISM通过启用单边OCC协议扩展了设计空间。

其他研究认为，双边RPC的性能优于单边RDMA操作。HERD避免了单边读，而是混合了单边写和双边操作，FaSST使用RPC机制实现事务。DrTM+H通过一种单边/双边混合方法提高了DrTM的性能。Octopus对文件系统使用了类似的混合方法。PRISM通过提供更复杂的远程操作，提供了一个中间地带。

RDMA扩展：实现者偶尔会为RDMA模型定义新的扩展。Mellanox的扩展原子API允许CAS操作比较和交换一个较大的操作数和一个8字节的值。Snap的软件RDMA栈支持间接操作和模式搜索原语，这些在谷歌中使用，但没有公开详细描述。远内存数据结构的简单原语也被提出，包括间接寻址。

StRoM和RMC建议允许应用程序分别在FPGA和多核网卡上安装他们自己的一次性原语。这与我们添加服务器端处理以避免额外的网络往返的目标是一致的——并且确实支持更复杂的服务器端处理。然而，正如§2.3中所讨论的，运行自定义应用逻辑会带来部署上的挑战，而支持一个小型通用原语库可以提供更多的实现可能性。PRISM演示了这样的API是有用的。

HyperLoop实现了一种不同于PRISM的链接形式:它表明，通过一个特别设计的RDMA请求，发送方可以导致接收方向第三台机器发起RDMA请求。这可以与PRISM结合使用来实现其他通信模式。RedN进一步采用了这种方法，使用自修改RDMA链作为图灵机，这是在现有硬件上实现PRISM原语的一种潜在方法。

10 总结

我们已经介绍了PRISM，一个用于访问远程内存的扩展API。PRISM在RDMA READ/WRITE接口和RPC通信的全部通用性之间提供了一个中间地带。PRISM极大地扩展了网络加速应用程序的设计空间，使它能够以最小的服务器端CPU介入构建新型应用程序——正如我们的键值存储、复制存储和分布式事务示例所演示的那样。

通过使用PRISM的软件实现，我们展示了更高级的接口允许构建更高效的协议——通常优于使用硬件加速的RDMA的协议。展望未来，PRISM的硬件实现是可行的，并且可以实现更高的性能和更好的CPU效率——支持新的部署选项，如网络连接的内存节点。