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 中是万物是否提交即 T P 。
3、 针对T P 中的每个事务t ， S 检测 t 的 undo log 的 change 部分是否有对应数据记录
4、 S 重组状态信息，并广播到所有存活节点。状态信息包含 P 和 S 的 ID ， T P 中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