RDMA网络下重思数据库高可用
摘要
高可用数据库系统常常使用用数据复制来达到容错的目的。Active-passive和active-active复制算法都是严重依赖于时延，网络常常成为性能的主要瓶颈。从某种意义上说，这些技术旨在最小化副本之间的网络通信。然而，下一代网络的出现，以期高吞吐低延迟的特性，使得需要重视这些假设。
首先提出，现代RDMA网络使得瓶颈转向CPU，因此现代网络优化的复制技术不再是最优选择。提出了一个新高可用机制active-memory复制，充分利用RDMA达到消除在复制中处理多余工作的目的。使用active-memory，所有replica都将CPU能力专用于执行新事物，而不是复制的冗余计算。当出现故障时，active-memory通过基于RDMA的undo机制，维护高可用和数据正确性。实验表明，active-memory比第二种协议在RDMA网络上快2倍。
引言
任何传统数据库系统都有一个关键功能：高可用。单机情况下，故障会导致数据库服务不可用并且会造成数据丢失。高可用通常通过分布式数据复制来完成。主机上update会复制到备机从而当主机故障时可以被备机替代。
传统分布式系统设计时针对的是：网络是服务性能的瓶颈。在同一个数据中心内通过传统的10-千兆以太网发送消息，例如，与访问本地内存相比，网络传输在高延迟和低带宽上会差上2-3个数量级。高可用方法主要有active-passive和active-active，这两种方法都是为了优化网络负载。
随着下一代网络的出现，传统的高可用协议不再适用，尤其是在局域网环境中。基于RDMA的网络，具有和主存相近的带宽，只有其10倍的高延迟。我们对active-passive和active-active机制实验表明，现代RDMA网络下，性能瓶颈转向CPU的计算负载。因此传统网络优化高可用机制不再是最优的方案。需要设计新的协议全力释放RDMA硬件的红利。
为此，我们提出active-memory复制协议适配RDMA硬件。在执行数据复制时，active-memory优化目标在于最小化CPU负载而不是最小化网络负载。该机制核心思想：使用RDMA单边特性，直接在远方备机上直接update记录，而不需要远程CPU的参与。这种设计的挑战在于，备机CPU不参与复制协议下如何达到故障容错。为解决这个问题，我们设计了意向新型的undo-logging based replication protocol，所有逻辑都由主机单方面执行。每个事务经历两个阶段：（1）undo logging和本地update（2）日志空间回收，其中每个update都由单独的RDMA写来执行。我们证明了在不同故障场景下该机制的正确性。和active-passive、active-active相比，active-memory快两倍。
本文贡献如下：
重视下一代网络上传统高可用协议，证明优化网络负载不再是最合适的设计目标。
提出active-memory协议，部署在RDMA高速网络上。
关系型关系数据库中的高可用
因各种不同原因，数据库系统会发生故障：硬件故障、网络通信故障、软件bugs、人为故障等。高可用系统可以保证数据库系统发生这样故障时仍提供服务达到零宕机时间。
高可用通常通过复制来完成：数据库每个记录都会复制到一个或多个机器。为了达到容忍k个机器故障的目的，需要将事务的数据复制到至少k+1节点。例如，当k等于1时，每个记录存储在两个不同的及其上，这样不论哪个机器故障都不会阻塞系统服务的持续性。
Gray对复制进行了分类：eager或lazy复制。强一致性要求不高的场景下常常应用lazy复制，能够接受丢失数据的可能，例如Amazon Dynamo和Facebook Cassandra。
本文我们关注eager复制，即以share-nothing架构下的强一致性复制。数据库必须保证事务的update需要倒到replica后才能提交。强一致性处理机器故障变得简单，因为所有副本在同一个时间内都是相同的。
强一致性复制可分为两类：active-passive和active-active。讲解了这两类复制的有点和缺点并讨论他们耗费和限制。
active-passive复制
一个主，接受写操作；主将其数据复制到一个或多个从。一旦主故障，则选择一个从提升为主。学术型或者商业数据库的active-passive复制实现有多种方式，通常通过日志复制，备机进行回放从而获得主机上的写数据。
图1显示了active-passive机制下日志如何传输。假设数据库有2个分区（P1和P2），每个分区都有一个备份（B1和B2）。实际上B2和P1可能在同一台机器上，而另外两个在同一台机器上。蓝色，T1是一个单分区事务，数据只在P1上。因此P1执行事务，提交前将日志发向所有备份。当接收到备份的ack后，P1才能提交。同样事务也可以扩展到多分区，正如T2，复制协议一样，只是两阶段提交。
该模式的复制因其简单性和通用性而被广泛使用。然而有2个缺点。事务日志包含所有改动，造成日志很大。由于通用网络的带宽限制，造成严重瓶颈。主备间的通信延迟可能成为瓶颈。
active-active复制
第二类复制时eager复制，无论哪个节点都可以更新。系统允许多节点更新并将其改动传播到各个副本。由于可能事务冲突，所以需要节点进行更多协作。这样的数据库系统主要通过副本上的执行顺序解决这个问题。active-active复制为了减少网络通信需要传输日志并且和其他副本以active-passive机制进行协作。尤其是，事务分组成批，副本上按同样的顺序执行这批事务，这样所有的节点最终数据都是一样的。副本只需要将事务分批，之后不会再进行通信协作，减少了网络通信。H-store和Calvin使用active-active复制机制。
图2是H-store的复制协议。H-store中所有事务会提前注册成存储过程。H-store中事务不会获取记录锁，只锁需要的分区。事务按分区顺序执行。单分区事务T1，primary将存储过程的ID复制到所有replica，所有的备份包括primary并行执行事务。和日志传输不同，副本不需要协作，因为他们执行相同的事务序列。对于多分区事务，primaries的一个作为事务协调者，发送存储过程及其参数到其他分区。每个分区需要加排它锁，并将存储过程发送到其备节点，从而所有节点执行相同事务构建写集合。最终，协调者发起两阶段提交确保其他primary也可以提交。单分区事务TPS很高，多分区事务性能指数级下降。由于多分区事务会对分区加锁。
如图3所示，Calvin是一个和H-store不同方法的active-active系统。所有事务首先进入sequencer，进行排序。事务的输入被记录下来并发送到所有副本。每个分区的锁管理线程遍历该历史链表并获取每个事务的锁。如果锁被占用，这个事务就需要等待。因此，Calvin需要提前知道事务的读写集合，这样锁管理器才能知道加什么锁。所有事务加锁后，副本上的worker线程无需协作执行事务。对于多分区事务，参与的分区通过推送结果的方式进行互相通信。
H-store对单分区事务消耗较小，Calvin在多分区事务上有较好性能。
基于RDMA网络的复制
随着网络技术的快速发展，传统日志传输和active-active复制机制不再是最优方案。本节介绍传统复制机制的设计方案和为什么下一代网络上需要新的高可用机制，然后介绍RDMA的一些背景。
瓶颈分析
上文介绍的复制机制针对网络通信时延为瓶颈来设计的。因此减少访问网络是高效复制算法的设计原则。这两类技术通过交换网络请求和更多冗余处理来实现这个原则。图4说明该思想。日志传输到replica后，需要回放。Active-active技术减少了网络通信，当网络是瓶颈时，能够提高性能。
复制中网络通信非常昂贵的因素：网络带宽的限制；操作系统处理信息的成本；网络通信高延迟。随着下一代RDMA网络的出现，这些因素需要重新评估是否是瓶颈。网络带宽大大提高。RDMA为新算法的设计提供了可能。RDMA低延迟，零拷贝、CPU旁路特性。RDMA网络的出现，瓶颈转向CPU而不是玩过，如图4b。
RDMA背景
RDMA特性可以使机器无需远端机器操作系统进行操作而直接访问其内存，即zero-copy数据。由于支持RDMA的网络技术在以太网上变得更具成本竞争力，所以数据库中使用RDMA释放其硬件红利也更具吸引力。RDMA实现技术的三种方式：InfiniBand、RoCE和iWarp。通过绕过操作系统、完全卸载网络协议栈，在网卡上允许RMDA具高吞吐量、低延迟和低CPU使用率。例如，Mellanox ConnectX-6 RNICs能够每秒传输200GB的数据，延迟不到1us，每秒能够处理200million信息。
RDMA接口提供两种操作类型：单边（read，write和原子操作）和双边（send、receive）。单边操作，不用远程机器CPU参与，提供用户级别的内存访问接口直接访问远程内存进行读写。双边操作，提供两边用户级别的信息传出接口用于交换RPC信息。和单边操作不同，双边操作需要两边的CPU参与。
两种处理方式通过queue pairs进行彼此通信。Reliable Connected pairs下，包顺序传输并且不会丢失。这两种特性是我们复制和故障容错协议的关键。
active-memory：基于RDMA的复制
这一部分首先介绍active-memory复制，然后介绍基于RDMA的高可用解决方案，最后提出详细的复制算法。
并发控制和复制假设
本文针对分布式shared-nothing数据库提出active-memory复制机制。Master节点上有记录的主副本，其他backup节点上都有一个备份副本。事务只访问primary的副本，而其他节点值被复制更新。这是避免有事务在备机上读取到未提交的数据。
本文，关注两阶段NO_WAIT加锁策略。但是我们要求，事务内对数据结构的修改都是原子的，如果没有这要求，那么通过RDMA进行内存拷贝就会复制到未提交的修改。通过在共享数据结构上使用排他latch来确保这个前提。当然还有其他方法确保。最后假设每个节点部署在NVM上。
概述
active-memory在RDMA-enabled网络上采用主备复制机制。协作者通过RDMA的单边写操作直接将事务的数据写到备机的内存，而不是将日志复制到备机。因此备机的CPU不再掺和到数据复制的逻辑中，而全心的投入到处理新事务上。准确的说，对于每个事务，复制协议涉及两个阶段：1）undo log传输及本地更新；2）日志空间回收。
active-memory突出的特点：
强一致性：active-memory提供强一致性。备节点数据总是显示最近提交的事务，并且不会落后主。新备支持快速、直接故障切换。
零处理冗余：和日志传输和active-active不同，active-memory全面消除了复制协议中的冗余处理。逻辑上事务只执行一次。备节点不需执行事务代码并不需回放日志。备机的CPU用来处理新事务。
消息处理零开销：依赖RDMA单边操作，active-memory能够避免send、receive RPC消息造成的开销，包括TCP/IP开销，以及在每个数据库节点分发机制的消息带来的开销。
简单快速容错：无论普通执行模式下复制协议执行的有多高效，从故障中恢复必须是可靠并一致的，当然更要快。本文充分利用RDMA，提供一种故障容错的快速简单的机制。
active-memory中CPU消耗的减少，带来的是网络流量的增加。然而，在新一代的RDMA网络中以其高带宽的特性使得这不是问题。
设计挑战
active-memory机制非常简单，但也有设计挑战：支持故障容错及非阻塞快速恢复。为了确保正确性，协调者必须保证他的修改要么全部复制到所有备节点，要么都没有复制到。和日志传输协议不同，备节点不参与复制协议。因此协调者必须单方面保证故障容错，这使得设计更具挑战性。
为达到这个目标，active-memory依赖undo日志机制，而不是传统的redo日志机制。协调者在直接更新备节点内存状态前，将undo日志写到备节点。
另一个挑战是无阻塞恢复，当一个或多个协调者或者备节点故障后，要求系统快速恢复到一致性状态。active-memory确保至少有一个节点总是有足够的信息，从而能够恢复到一致性状态。
undo log buffer
active-memory使用基于RDMA的undo日志机制确保故障原子性。每个server节点都会有一个预分配的RDMA buffer。这个buffer维护一系列固定大小的日志记录，并以环形的方式部署。每个buffer仅能被一个远程server节点更改。因此不会有并发访问问题。
每个节点维护一个链表，该链表是其他对应机器的可用undo log记录。也就是说，每个机器指定远程log buffer的链表头和尾指针。通过发起一个RDMA写操作，将一个日志记录放到远程buffer。Buffer以环形的方式意味着：不再使用的日志记录空间可以被重复使用。
日志记录的结构如图5所示。每个日志条目存储该事务修改前的内容。例如修改3个记录的2个字段的一个事务将会拥有6个改动字段（ChangesCnt=6），对于每个改动字段，每个条目包含自己的HostID以及在其机器上的字段内存偏移，长度（Len），Payload中的未更改前内容。只存储更改字段的值，而不是整个记录的内容，大大减小了日志大小，从而也减小了每个事务需要发送的日志量。每个日志条目都有一个唯一符LogID。如果日志超出了条目固定大小，会在后面紧接着一条日志条目存储剩余内容，该日志条目和上个LogID相同。IsLast为false的日志条目表示后续还有日志。协调者会在每条日志后面设置和LogID相同值的LogID_Check。只有LogID和LogID_Check相同，才认为该日志是有效的。由于receiver端，NICs确保RDMA的写以地址增长的方式进行，也就是说LogID_Check不会再LogID之前。因此这样的机制保证记录自己能够校验正确性。最后ISCommitted表示事物的提交状态。
对于一些负载场景，undo log buffer不能够放下所有的write-sets。这样的场景能够依赖RPC-based 日志传输，协调者发送给每个备RPC消息。备进行回放并向主发送ack。通常情况下，系统必须满足给定的负载，需要的话，就需要扩大log buffer大小。
复制算法
下面详述active-memory复制协议。主一旦构建了读写集合，就启动这个复制。active-memory假设，针对每个事务，主包含一个本地的write-set（包含一系列唯一键以及即将更改的新值）。执行结束时，事务准备提交并将这些write-set集合内容合并到数据库。当协调者启动复制阶段时，进行本地更新并将日志提交（复制阶段有两步）。
第一步：undo log及本地更新
这一步的目标：1）复制undo log；2）直接更改write-set里的记录。这两步在事务涉及到的分区上及其副本上必须执行，此后称为活动节点。该算法必须保证每个活动节点，记录undo log后才会进行本地更新。
Listing 1为这一步的算法伪代码。概括起来说，协调者扫描他的write-set并形成每个活动节点RDMA操作的链表。链表的第一条信息是undo log RDMA写操作，剩下的是：针对分区上记录本地更新的RDMA写。可靠连接队列对儿的有序消息传输的保证，远端NIC在本地更新消息前，接收到的日志信息。这样的保证传输顺序是故障容错机制的关键。
协调者针对事务中每个活跃节点p执行下面流程：
1）检索并更新节点P上的undo log buffer的尾指针
2）初始化一个日志条目（后续会在P上复制到replicas；IsCommitted设置为false）
3）检索并获取p上write-set的记录（第6行）
4）将更改的字段值添加到日志条目（8-13行）
5）通过添加一个undo log条目（16-18）和数据更新（20-25），构建RDMA信息链表。如图6所示。
6）发启将这个链表传输到p及其所有replicas（27-30）。
将这个链表一次发布，而不是单独发布。这样允许底层驱动进行优化，在发送端使用更少的CPU，从而提升性能。
未简洁起见，假设所有的更改都能够放到一条日志信息里。多条目日志信息处理方式相同。IsLast只有在最后一条日志设置TRUE。
一旦发送了日志和更改信息，事务等待远端发送接收到日志反馈的ACK。表示事务日志和更改数据已经复制到所有活跃节点，协调者可以进入下一步操作。
第二步：提交日志
这一步的目的：完成k-safe特性。协调者首先通过RDMA写将每个活跃节点的IsCommitted设置为TRUE，如图7所示。协调者的NIC将RDMA写消息发送后，本地将对应undo log buffer的头指针加1，表示这个条目可以被后续事务重用了。同时将日志放到NVM，释放锁并返回用户。
active-memory充分利用RDMA中可靠连接队列对儿的有序消息传输。使用这样的连接类型，接收端NIC接收的消息顺序和发送顺序相同。即使协调者在复制中途出错，本地更新的RDMA消息不会影响接收端。
故障容错
这一部分介绍如何在不牺牲正确性和高效下，在各种故障场景下保证故障容错。先介绍单分区事务的恢复机制，然后扩展到多分区事务。
备故障恢复
备机故障恢复比较简单明了。不需要执行任何复制流程，而且由协调节点（S）维护复制状态。我们复制协议中，只有所有更新都复制到备后才会返回用户。因此，S成功完成复制过程的第二步前备机故障，S不会返回客户端，而是等集群管理者广播新配置，一旦接收到，S就知道是否提交或者需要复制到更多机器。在步骤二中间或者结束时故障，协调者不会回滚一个事务。
主机故障恢复
主机故障恢复具有挑战性。通过这些日志，备份为了维护系统事务一致性，可以知道是否重建、提交或放弃该事务。P机器故障，S可以执行下面过程：
1、S关闭到P的RDMA队列对儿，一旦S开启恢复，即使P从故障中返回并发起新的RDMA操作也不会成功。
2、S检查S本地内存中P的log buffer，标记buffer中是万物是否提交即TP。
3、针对TP中的每个事务t，S检测t的undo log的change部分是否有对应数据记录
4、S重组状态信息，并广播到所有存活节点。状态信息包含P和S的ID，TP中t的两个条目：（t的ID和t的状态），分别为事务的ID和S上事务的当前状态。t的状态可能四种的一种：1）损坏日志：t的日志至少有一个LogID_check和LogID不匹配，或者最后一个日志的IsLast=true。这种情形下，数据记录保持不变，因为在更新前传输undo日志。2）Logged，日志条目正确，但是CommitBit是0。数据可能保持不变（比如update消息没有接收到），数据损坏（直接收到部分update消息），或者fully update（接收到所有update消息）。3）commit-ready：CommitBit为1.接收到所有undo log和数据记录必须更新。
5、S将他的状态信息广播到所有存活节点，并接收存活节点的状态信息。
6、一旦接收到状态信息，如果所有相关节点的事务是Commit-ready状态，那么S提交事务。否则放弃该事务，通过undo日志回滚并释放本地的log buffer。
一旦所有备份节点恢复并提交了正在执行的事务，通知集群管理选新主并继续常规处理。
多分区事务恢复
多分区事务处理多主的数据，其中一个分区作为协调者。在复制阶段，协调者负责构造日志条目和本地更新。所有节点都反馈给协调者ack后，多分区事务才提交。
恢复过程和单分区事务类似。如果故障节点不是活跃事务的协调者，协调者在集群重配后决定是否复制更多机器。如果协调者故障，所有其他节点本地构造并广播事务状态。唯一不同的是所有涉及到的分区上的节点都是Commit-ready状态才会提交。
总结
本文提出了active-memory一个基于RDMA的机制，提供高可用功能并具备强一致性。通过使用新型的RDMA兼容的undo log机制；通过RDMA单边写操作直接更改数据记录，从而减少CPU使用率。
原文
Rethinking Database High Availability with RDMA Networks
