高效单边RDMA程序设计准则探讨

KunlunBase 昆仑数据库 2023-09-08

1311

点击上方蓝字关注我们

文章目的

构建在单侧远程直接内存访问技术 (RDMA, Remote Direct Memory Access) 之上的远程数据结构是如今流行的存算分离数据库管理系统的核心。数千用户同时访问这些数据结构需要高效的同步方案。值得注意的是，现有研究揭示了已有的同步方案在性能和可扩展性方面表现出巨大的差异。更糟糕的是，一些方案甚至不能正确地达到同步的目的，导致难以检测的数据损坏。

受这些观察的启发，我们引用Sigmod 2023的一篇论文“Design Guidelines for Correct, Efficient, and Scalable Synchronization using One-Sided RDMA”对单侧RDMA的同步方案进行了第一次全面分析技术并提供使用单侧RDMA进行正确同步的一般原则。研究表明遵守这些原则不仅可以保证单边RDMA同步方案的正确性，而且可以给应用程序带来实质性的性能提升。

关键词：RDMA、LINUX、内核、远程内存直接访问、学术研究

文章背景

远程直接内存访问（RDMA）已迅速成为构建存算分离数据库不可或缺的工具之一。它不仅具有个位数毫秒级的网络访问延迟，同时也提供了高效的原语用于远程内存访问。特别是，RDMA单侧原语允许计算节点不需要远端存储节点CPU参与，直接读取或者写入远端存储服务器。存储服务器的计算能力通常是比较弱的，大多数计算能力集中在计算层。在这种情况下，单侧RDMA被证明非常适合存算分离数据库。最近也有较多的研究集中在如何在存算分离数据库中高效使用单侧RDMA。这些系统的关键部件就是诸如单侧的哈希表、B-Trees、以及跳表(SkipLists)等数据结构，用来实现对远端数据的高效访问。由于单侧操作不需要远端CPU介入，传统的依赖存储端的CPU同步技术发挥不了作用。因此，研究人员提出了各种单侧同步技术。这些技术可以分为悲观和乐观两大类。悲观方案阻止并发修改，而乐观方案检测并处理并发修改。这些方法在扩展性和性能方面有着根本上的不同。

远程数据结构可能需要为来自多个计算节点的数千个客户端连接提供服务。这么高的并发下，性能取决于单侧同步方案的实现。虽然各种论文提出了不同的单侧同步方案，令人惊讶的是，尚未有研究在可比较的工作负载和条件下对这些方案进行系统性研究。该论文首次提供了深入的性能分析，向我们展示了一个方案实现中微小的设计决定都可能会严重影响其性能并导致性能瓶颈。实现高性能的同步无疑是有价值的，但确保正确性是必须的前提。论文发现，早期文献提出的技术无法准确对并发操作进行同步，可能导致难以检测的数据不一致。考虑乐观同步方案的场景：通常假设RDMA操作按地址升序有序进行——许多论文中的常见假设。该方案实现的更新方式是先写数据头部的版本号，然后修改数据，最后数据末尾的版本。假设操作按递增地址顺序执行，并发读取可以通过比较头版本和尾版本来检测并发修改。不幸的是，与许多论文中的一般假设相悖，RDMA读取操作并不按地址递增顺序执行。事实上，RDMA规范没有说明RDMA中的字节读取顺序。因此上述提到的同步方案就可能出现问题。假如，我们有如下的数据结构：[version-data-version]

并且设计的应用程序尝试在单个RDMA read中读取它。则数据部分可能会在初始版本值之前返回。因此，并发writer可以同时修改数据，并在之后递增版本。发出RDMA读取操作的reader可以在读取旧版本值之前获取新数据值。然后，当它最后验证版本时，它仍将与读取的初始旧值匹配，因此读取器不会检测到并发修改。令人惊讶的是，这问题还不为大众所知，并且基于按地址顺序读取的假设仍然非常流行。论文认为这个问题背后的主要原因是单个RDMA请求需要许多协议— 不仅是RDMA，还包括PCIe和缓存一致性 — 协同工作。因此，了解相应规范提供了哪些保证具有一定的挑战性。如图1所示，RNIC通过PCIe总线连接到多核处理器的内存控制器（MCH，Memory Control Hub），这个模块负责CPU和外部设备的内存访问请求。其中,MCH包含内存控制器、一致性协议，并充当PCIe总线的根联合体。现代服务器架构实现了缓存一致直接 I/O，例如 Intel DDIO和ARM CCI ，因此RDMA对系统内存的访问将监听（查找）CPU缓存是否存在冲突地址，这是必不可少的一个步骤。如果发现冲突地址，则可以从CPU缓存中提供服务；否则，需要从主存中获取。缓存一致性I/O是许多应用的主要推动因素。

图1. RDMA操作涉及的相关硬件模块

以下，我们从悲观和乐观两大类单侧RDMA的同步实现详细探讨构建RDMA应用程序时值得研究的可能陷阱。测试平台采用广泛使用的InfiniBand规范与相关设施，该规范与可替代RDMA协议具有共性，这使测试结果适用于大范围的一般部署场景。

单侧RDMA悲观同步实现

为了防止同时修改远程端数据结构，例如B树或哈希表，单侧悲观同步技术使用单侧RDMA相关操作实现闩锁[1] 。在本节中，我们将介绍此类闩锁的基本实现并将其用作运行示例来讨论可能的优化。由于RDMA原子指令是这些单侧闩锁的基本构建单元，论文深入研究了这些RDMA原子指令的可扩展性特征和性能。之后，概述并评估可能的单侧闩锁优化。

2.1 RDMA原子操作性能

由于每种悲观同步方法都依赖于RDMA原子指令（CAS 和 FAA），因此在讨论如何优化基本的闩锁实现之前，重要的是先了解它们的并发隔离性能。在第一个实验中，检查竞争和非竞争RDMA原子操作的可扩展性。这两种情况同样重要。虽然激烈的争用很少见，但在某些工作负载中是不可避免的，例如，热元组。为了展示争用的效果，论文进行了一个实验，其中所有工作线程都针对同一个8字节原子计数器执行RDMA CAS指令。为了解无竞争原子可以达到的规模，给每个工作线程分配了一个私有的8字节远程原子计数器。作为参考，比较无竞争情况下RDMA原子操作与RDMA读性能的差异。

图2. 随着工作线程的增加，竞争和非竞争 RDMA 原子操作的可扩展性。工作节点（4个计算节点和1个存储节点）

图2分别显示了随着工作线程的增加，无竞争和竞争情况下RDMA原子操作的可扩展性特征。如图所示，无竞争的原子操作类似于单侧 RDMA 读操作，在128个线程的时候性能达到峰值，吞吐量约为每秒5120万次操作。这表明并行的无竞争原子操作请求不会相互干扰，但稍后将证明这并不适用于所有场景。注意，512个工作线程中无竞争原子操作的性能下降与原子操作无关，其原因主要是客户端计算机上的RDMA工作队列对(QP, Queue Pair)抖动[2]。QP抖动意味着QP状态不能缓存在RNIC网卡上，需要经常被换入换出。正如预期的那样，在竞争的情况下原子操作的峰值明显低于无竞争的情况，每秒只有232万次操作，只能扩展到8个工作线程。

在一些文献中，RDMA原子操作似乎因不可扩展而名声不佳 —— 即使对于无竞争的工作负载也是如此。然而，上述实验表明无竞争的情况下原子操作的吞吐量可以很好地随着线程数量的增加而增加。事实上，它们在可扩展性方面的表现与RDMA读操作旗鼓相当。虽然这个实验提供了对原子操作可扩展性方面的有益见解，正如下面将演示的那样，这并不是RDMA原子操作的完整故事。

显然，RDMA原子操作的可扩展性取决于并行度。然而，诸如数据对齐之类的微妙细节也会影响扩展性。在上述的实验中，数据被放置在64字节的数据块（即一个高速缓存大小）。使用前8个字节作为原子计数器，忽略其余56个字节。然而，在实践中，RDMA原子操作通常被放置在更大的数据块上，用以保护各种大小的数据，例如4KB的B树节点。

下面的实验通过改变原子计数器之间的距离来测量大数据块的效果。与之前无竞争的实验一样，每个工作线程都拥有一个私有闩锁以避免争用。因此，预期结果应该类似于图2中没有竞争的结果。令人惊讶的是，下图3的结果显示数据块大小会严重损害可扩展性。也就是说，数据块越大，拐点就越明显。吞吐量峰值(突出显示红色)提前到达。若采用64字节数据块大小，性能峰值为128线程对应的50M，即与图2的上限相同；若数据块大小为256字节，峰值性能为128线程对应的40M；若采用512字节大小的数据块，峰值性能减半，可扩展性只能达到64线程。请记住，这里没有真正的闩锁争用，我们只改变原子计数器之间的距离，而没有其它操作。这观察到的行为应该归结于RNIC中的物理争用。通过逆向工程，论文作者认为RNIC使用内部锁表来串行化原子操作。由于锁表的工作原理类似对于哈希表，可能会发生冲突。即使无竞争的原子操作也会被分配在同一个槽，严重限制了并发无竞争原子操作的吞吐量。锁表的槽位由原子操作的目标地址的最后12位来确定。如图4b(i)所示，4KB的数据页的最后12位都是为零，因此这些数据页上的原子操作被分配在相同的锁表槽位，造成物理上的竞争，如图4a所示。这就解释了图3的现象：当没有恰当地选择数据块的对齐，逻辑无冲突的原子操作也可能不具有扩展性。因此，为了改进无竞争操作的可扩展性，我们必须避免锁表的冲突。可以控制这一点的唯一方式是更改数据布局，改变闩锁在锁表中的地址。目标是在锁表中地址，以便最后 12 位（用于锁槽计算）不同。考虑图 4(b) ii) 中的示例；不是连续分配4KB块，而是在闩锁之前放置8字节的填充。现在，闩锁地址的最后12位不全为零，因此将被分配给不同的锁槽。这种缓解技术的效果如图3右图所示。当然也可以采用将闩锁与数据分离的设计，但是这种数据存放方式对高速缓存不友好。

图3. 不同数据块大小、非竞争场景的原子操作可扩展性

图4. RNIC的内部构造影响悲观同步实现

然而，很难将上述结论推广到一般情况，因为RNIC厂商并没有公开实现细节。因此，与其他论文一样，这里只能推断实现细节。这里强调NIC硬件细节至关重要，并展示了构建高性能系统时应仔细评估潜在的瓶颈。

[1]闩锁(latch)指的是物理上的锁，用于保护程序的物理临界区和相关数据结构，它的实现依赖机器的原子指令例如Compare-and-Swap或Test-and-Set；注意区别于数据库中的锁(lock)，后者是逻辑上的概念，实现上依赖哈希表和锁相容矩阵原理。

[2]现代网络通讯协议通常采用异步网络框架。这意味着网络操作被分派到 NIC。一旦该操作完成的时候，由NIC通知应用程序任务完成了。RDMA 的接口使用所谓的发送/接收队列对(Send/Receive Queue Pair)来发布相关操作。

2.2 优化悲观闩锁实现

图5. 闩锁优化演进

在了解如何最优地使用原子操作以后，就可以专注于设计最优的悲观闩锁。回想一下，在基本闩锁以及变体下所有操作都是同步执行。每次操作后都需要轮询完成队列，等待操作的完成。虽然这是正确的，但它效率低下并且会增加每个操作的延迟。投机读取优化将闩锁的申请与读申请重叠进行，最小化读取等待延迟。这个优化取决于操作顺序的保证。也就是，必须保证原子操作的顺序在读操作之前。幸运的是，InfiniBand规格满足该要求。第二个优化是将写操作与解锁原子操作重叠执行，如果恰巧最后一个操作是写操作。该优化能够利用解锁操作屏蔽最后写操作的延迟。异步解锁更进一步，不同步等待解锁操作完成就执行下一个操作。这需要谨慎维护缓冲区，避免覆盖写。最后一个优化是，仅使用写操作而不用单独的原子操作解锁。例如在一个采用RDMA的key-value存储中，value附带上解锁信息达到解锁目的。但是这个优化需要与CAS一起使用，但不是FAA。此外也限制了锁只能有一个排他模式。图5显示了上述几个优化方法的运行方式。

单侧RDMA乐观同步实现

在前面的内容，我们已经看到没有竞争时悲观锁同步具有较好的扩展性。然而，在某些数据结构中，锁争用是不可避免的，事实上这是由数据结构固有的设计决定的。例如，B-Tree操作必须都遍历B树根节点。虽然根节点主要处于共享模式锁定，当使用悲观同步时，这也会在RNIC上产生（物理）争用，对性能产生负面影响。这就是为什么许多研究避开RDMA原子操作并提出乐观同步的原因：乐观读取不需要物理锁住数据而是通过检测是否存在并发修改。下面我们列举一些正确的乐观同步方案。

3.1 简单的乐观同步实现

在乐观同步的实现中读者乐观地进行，然后进行验证。同时writer获取物理上的悲观锁以避免写写冲突。为了达到与共享悲观锁存相同的保证，reader必须检查在其操作期间数据项没有被更改。这一般是通过带有版本计数器的增强数据项实现，并在每次修改时递增计数器，这允许reader检测并发写入。

这种增强乐观锁的数据布局如下所示图6(a)。它由用于独占访问的悲观锁存器和版本计数器组成。使用此版本计数器，读者可以验证版本在操作期间没有更改。如果验证失败，则重启操作。

图6. 乐观同步实现

一个最朴素的乐观同步锁实现如图6b所示。该方法使用单个RDMA将闩锁、版本和数据复制到工作线程私有空间。然后工线程可以检查该数据是否是排他的。如是，则重新启动。否则，通过锁的检测，执行相应操作，例如B树节点中的二分搜索是乐观执行的。操作完成后，再次读取版本（通过RDMA）并与初始值进行比较。这种事后验证对于检测并发修改至关重要，获得与悲观闩锁相同的保证。因此，验证实际上相当于解锁操作。

3.2 PCIe的顺序保证

遗憾的是，上述朴素的乐观同步实现并不正确。正如可参考文献所指出的，影响数据传输顺序的因素有3个：

消息的顺序，
单个消息内的数据包的顺序，
DMA 顺序。

前两个因素一般由InfiniBand和RoCE保证。但即使保证了消息顺序，也不能保证DMA操作按地址顺序执行。InfiniBand RDMA规范本身不提供关于单个RDMA读操作中按字节顺序操作的保证。因此，要充分理解为什么RDMA读操作可能不会按递增地址顺序执行，调研PCIe和缓存一致性协议的影响至关重要。了解底层协议之后我们才能够设计正确的同步技术。如图1 所示，RDMA读取请求通过网络发送到远程节点。然后，RNIC将请求分派给PCIe控制器，后者获取位于主机内存所请求的数据。接着，数据通过PCIe回传到RNIC。最后通过一个或多个RDMA数据包发送回请求者。一个重要的方面是在现代服务器架构上PCIe请求是缓存一致的。由于实际数据从远程内存传输到远程RNIC是通过PCIe发起和执行的，因此，这一层硬件堆栈提供的保证发挥着举足轻重的作用。我们必须查看PCIe规范才能找到问题的根源。

PCIe 规范指出，“内存读取请求通过多个完成报文来服务的，将按完成报文的地址顺序返回。” 从这里可以看到，PCIe以完成报文的顺序返回，而不按从内存中检索数据的地址来确定返回顺序。事实上，实现规范允许“请求多个缓存行的单个内存读操作允许从主机内存同时获取多个缓存行”这就是问题所在！由于可能并行获取缓存行，我们无法可靠地使用图6(b)中的简单实现检测并发修改。想象如下场景：reader和writer并发执行。由于没有顺序保证，reader可以首先读取当前所在的第二个缓存行，而writer此时正在修改数据。与此同时，writer增加版本号并解锁数据。此时，reader才会读取包含闩锁和版本的第一个缓存行。这个后果是，尽管最后的验证步骤将再次读取版本号，reader也会错误地认为版本没有改变，导致了不可检测的数据损坏。

图7. 正确的乐观闩锁实现

下面给出正确的乐观闩锁的实现。

版本控制（两次读，分别获取版本和数据）。这种技术与朴素实现没有太大区别；然而，它要求在开始时需要执行两次串行的RDMA读取。第一个RDMA读仅针对锁和版本，并且仅第二个读才是获取数据。有人或许会想到，是否可以使用类似图5中重叠执行，来屏蔽两次RDMA读的开销。很遗憾，由于读操作很可能在PCIe甚至是网络中重新排序这个优化无法在读操作场景中实现。正确的实现如图7a所示。

CRC+版本控制。该方案通过使用数据校验和来检测不一致性，例如，CRC64，允许工作线程以高概率正确的方式验证数据。如果有并发写入，则损坏的数据不匹配CRC。因此，在最好的情况下，只需一次 RDMA 读取。然而，缺点是（1）CRC的生成是通过计算来实现的，代价昂贵并且（2）它只是基于概率性的。
给每个缓存行附加一个版本信息，从而规避一个额外的专门读取版本与闩锁信息的RDMA操作。附加的代价就是需要检测每个缓存行的版本信息是否一致以及额外的存储空间。

虽然正确的乐观同步需要额外的代价，例如单独的一个串行RDMA读获取版本信息、额外的存储空间等，但是乐观并发控制被证明具有较好的扩展性。在大并发情况下，较悲观并发能够提升2倍左右。另一个有趣的发现是，结合乐观闩锁实现，可以通过使用write-unlatch优化来提高写入的可扩展性。总而言之，悲观方案和乐观方案在计算和存储方面有不同的权衡和要求。

总结

作为RDMA同步原语的第一个分析研究，其目标是让读者从实践工作中汲取经验教训。

作者精炼了如下观点。

单次 RDMA 读取中的缓存行顺序没有保障；
重叠的RDMA读几乎同样没有顺序上的保障；
谨慎的对待将 RDMA 写与RDMA 原子操作相结合的设计。在某些情况下缺乏原子性并不会破坏语义，且可以产生更好的性能；
数据对齐影响 RDMA 原子可扩展性；
乐观同步在高竞争情况下表现最佳；
乐观同步方案有不可忽略的开销；
系统设计者在优先考虑生产稳定性时应倾向于简单的悲观同步，直到社区成功探索了RDMA 读写的明确定义以及相关内存语义。

论文从现有的技术出发，强调了RDMA同步在正确性方面的细微之处，提供了关于现有同步技术及其优化上全面的性能分析，同时也展示了现有设计的缺陷，是一篇值得阅读和学习的佳文。

图片来源：

论文：《Design Guidelines for Correct, Efficient, and Scalable Synchronization using One-Sided RDMA》

END

产品文档

Klustron 快速入门：

https://doc.kunlunbase.com/zh/Klustron_Instruction_Manual.html

Klustron 快速体验指南：

https://doc.kunlunbase.com/zh/Klustron_Quickly_Guide.html

Klustron 功能体验范例：

https://doc.kunlunbase.com/zh/Klustron-function-experience-example.html

Klustron 产品使用和测评指南：

https://doc.kunlunbase.com/zh/product-usage-and-evaluation-guidelines.html

同时欢迎大家扫码👇添加小助手（备注：加入Klustron技术交流群）欢迎大家在交流群共同探讨更多问题及主题。

点击👆上方，关注获取源代码及技术信息~

远程工作线程 rdma kunlunbase klustron

文章转载自KunlunBase 昆仑数据库，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

高效单边RDMA程序设计准则探讨

2.1 RDMA原子操作性能

2.2 优化悲观闩锁实现

3.1 简单的乐观同步实现

3.2 PCIe的顺序保证

评论