FaRM

来自微软的论文 No compromises: distributed transactions with consistency, availability, and performance

强一致性和高可用的事务简化了分布式系统的构建，但实际性能很差，迫使我们尽量避免使用事务，弱化一致性保证；或是需要切分数据做单机事务。而在现代数据中心没必要妥协。本文的 FaRM 是一个内存分布式平台，能提供严格序列化、高性能和高可用的分布式 ACID 事务。在有着 4.9 TB 数据的 90 台机器上，FaRM 实现了最高每秒 1.4 亿次 TATP，并能够不到 50 ms 就从故障中恢复。做到这些的关键在于利用有 RDMA 的商业网络方案和廉价的非易失性 DRAM 重新设计事务、复制（replication）和恢复协议。

1. 介绍

高可用和严格串行化的事务提供了一种既简单又强大的抽象：一台永不失败且按真实时间顺序依次执行事务的机器。但以往在分布式系统中的实际性能不佳，因此像 Dynamo 和 Memcached 弱化一致性保证或直接不支持事务来提高性；其他系统（MySQL）仅在所有数据驻留在单台机器上时才提供事务。

现代数据中心出现两个硬件趋势，RDMA 网络和非易失性 DRAM：用电池供电，在断电的那一刻将 DRAM 的内容写入 SSD 来实现非易失性。

由于 CPU 也存在瓶颈，FaRM 遵循三个原则来设计协议：

• 减少消息数量

  FaRM 通过将对象分布到数据中心的各机器上来扩展，允许事务跨任意数量的机器，利用垂直 Paxos 的主备复制来减少消息数量，未复制的协调器直接与主备节点通信。FaRM 使用四阶段提交协议（上锁，校验，提交备节点，提交主节点）的乐观并发控制，取消上锁阶段对备节点发送消息，从而提升了性能。

• 使用单边 RDMA 读写代替消息

  FaRM 事务在执行和验证期间使用单边 RDMA 读数据进一步降低 CPU 开销；另外协调器将事务中对象的变更记录到备节点的 WAL 时也使用单边 RDMA。事务在备节点上不使用前台 CPU，稍后就地更新时才会。

  单边 RDMA 需要新的故障恢复协议。

• 有效利用并行

  之所以故障恢复非常快是因为有效利用了并行。FaRM 将每个状态位的恢复均匀分布在集群中，在每台机器上并行恢复，另外还允许并行执行事务和恢复。FaRM 还通过利用快速的网络频繁交换心跳信号来提供故障检测，用优先级和预分配来避免误报。

实验结果表明一致性、高可用和性能皆可拥有，在只有少量机器的情况下，FaRM 的性能优于最先进的单机内存事务系统。

2. 硬件趋势

FaRM 的设计离不开数据中心大量的廉价内存：每台双插槽机器配备 128-512 GB 的 DRAM，成本不到 $12/GB，也就是说 1PB DRAM 只要 2000 台机器，足以存储许多应用程序的数据集。

2.1 非易失性 DRAM

“分布式不间断电源（UPS）”集成锂电池与机架内机器的电源单元：内置多个独立的单元，任何电池故障只会影响一部分机架。分布式 UPS 使得 DRAM 可被持久化：当电源故障时，利用电池将内存中的内容保存到 SSD。另一种方法是使用非易失性 DIMM，包含专用闪存、控制器和超级电容，但又贵体积又大。相比之下前者额外的成本在于 SSD 上的保留容量和 UPS 电池本身。

电池方案的成本取决于将内存保存到 SSD 所需的能量。我们在一台标准的双插槽机器上测试了一个未优化的原型，在故障时它会关闭磁盘和网卡，并将内存数据保存到单个 M.2 SSD，每 GB 数据消费 110 焦耳。还有大约 90 焦耳为机器的两个 CPU 供电。

2.2 RDMA 网络

FaRM 尽可能使用单边 RDMA，因为不会使用远程 CPU。实验测量，集群中所有机器从其他机器随机读取小对象时，纯 RDMA 性能比基于 RDMA 的 RPC 高两倍。瓶颈在于网卡的消息速率，RPC 的实现需要单边读取两倍的消息数量。

3. 编程模型和架构

FaRM 为应用程序提供了跨集群机器的全局地址空间抽象，在每台机器上运行应用程序线程并在地址空间中存储对象，由 API 提供事务中对本地和远程对象的透明访问。应用程序可随时启动事务，并成为该事务的协调器。在事务执行期间，该线程可以读取、写入、分配和释放对象；执行结束，调用 FaRM API 提交事务。

FaRM 事务使用乐观并发控制。在执行期间先将更新缓存在本地，并在成功提交后才对其他事务可见，提交可能会因为并发事务的冲突或本身故障而失败。FaRM 为所有成功提交的事务提供严格的串行化。在事务执行期间，FaRM 保证单个对象的读取是原子的，只读取已提交的数据；不保证跨不同对象读取的原子性，但在这种情况下保证不提交事务，从而确保已提交的事务是严格串行化的。这使得我们将一致性检查推迟到提交时而非每次读取对象时重新检查一致性，增加了一点编程复杂性：FaRM 应用程序必须在执行期间处理这些临时的不一致。

FaRM 还提供无锁读取 API，这种是优化的单个对象读取事务，可提高应用程序的性能。

图 3 展示了 4 台机器的 FaRM 实例。每台机器用内核线程在用户空间运行 FaRM，还绑定了 CPU。每个内核线程运行事件循环执行应用程序代码还有轮询 RDMA 完成队列。

FaRM 实例会随着时间推移加减机器，它使用 ZooKeeper 存储机器的配置，但不用于管理租约、故障检测或协调恢复，通常大家都会这么做。

FaRM 中的全局地址空间有 2GB 的区域，每个区域在 1 主 F 备上复制（F 是容错级别）。每台机器存储多个区域在非易失性 DRAM 中，可被其他机器通过单边 RDMA 读取。每个对象都有一个 64 位的版本用于并发控制和复制。区域标志符（索引）到其副本的映射由 CM（configuration manager）维护并随区域复制，其他机器需要这些映射来 RDMA 访问副本。

某台机器联系 CM 以分配一个新区域，CM 根据一个单调递增的计数器分配区域标识符并为该区域选择副本。选择副本时会均衡每台机器上存储的区域数量，并满足：

• 有足够的容量
• 每个副本在不同的故障域中

然后 CM 向选定的副本发送携带区域标识符的准备消息，如果所有选定的副本报告分配区域成功，CM 将向所有副本发送提交消息。该二阶段协议确保所有区域中副本在被使用前被正确复制。

这种集中的方式比以往基于一致性哈希的方法更灵活，更容易均衡机器之间的负载。对于 2GB 大小的区域，我们期望一台机器上有多达 250 个区域，因此单个 CM 可以处理几千台机器的区域分配。

每台机器还存储环形缓冲区（ring buffer）实现了 FIFO 队列，用作事务日志或消息队列。每个发送者-接收者都有自己的日志和消息队列，物理上位于接收者端。发送者使用单边 RDMA 写操作将记录追加到日志尾部。这些写操作由网卡确认，无需动用接收者的 CPU。

4. 分布式事务和复制

FaRM 比传统事务协议产生更少的消息，利用主备复制数据和事务日志。图 4 展示了 FaRM 事务的时间线：在执行阶段，事务使用单边 RDMA 来读取对象，并在本地缓冲写。协调器还会记录所有访问过对象的地址和版本；如果协调器在同一台机器上，直接读取内存和写入对象日志。在执行结束时提交事务（四步）：

1. 上锁

   协调器在每台已写入对象的主机上写一条 LOCK 记录到日志，包含已写对象的版本、值和区域列表。如果事务读取时任何对象发生变化，或另一个事务持锁，就有可能上锁失败。这时协调器会中止事务，向所有主机写入一条中止记录，并向应用程序返回错误。

2. 校验

   协调器通过从主节点读取校验，如果任何对象发生变化，验证失败，事务中止。

3. 提交备节点

   协调器向每个备节点的非易失性日志中写入一个 COMMIT-BACKUP 记录，然后等待来自备节点网卡的确认，而非中断远端的 CPU。COMMIT-BACKUP 日志和 LOCK 记录的有效负载相同。

4. 提交主节点

   在所有 COMMIT-BACKUP 写入被确认后，协调器在每个主节点上写下 COMMIT-PRIMARY 记录。当至少一台机器如此确认后，FaRM 向应用程序返回完成。主节点就地更新对象，更新其版本并解锁来处理这些记录。

正确性

已提交的读写事务在获取锁的时间点是串行化的；已提交的只读事务在其最后一次读取的时间点是串行化的。这是因为在串行化的时间点所有读写对象的版本和执行期间的相同：对于被写入的对象来说由锁确保；对于被读取的对象来说由校验确保。

为确保故障时的串行化，有必要在写 COMMIT-PRIMARY 之前等待所有备份的确认。

由于读取集合仅存储在协调器处，如果协调器故障并且没有任何提交记录来证明校验成功，事务将中止。因此协调器有必要在向应用程序上报成功之前，等待一个主节点提交成功。确保至少有一个提交记录在故障中幸存。

性能

FaRM 相较传统分布式提交协议有些许优势。以 Spanner 为例，它使用 Paxos 来复制事务协调器和参与者。传统的二阶段提交协议需要 2f + 1 个副本来容忍 f 个故障，由于每次状态机操作至少要 2f + 1 趟来回消息，那就要 4P(2f + 1) 个消息（P 为事务参与者数量）。

FaRM 使用主备复制而非 Paxos 状态机复制，这将副本数量减少到 f + 1，也减少了事务过程中消息的数量。协调器直接与主备节点通信，进一步减少延迟和消息数量。FaRM 因复制导致的开销被最小化：对于每个写入对象备份的机器，只需一次 RDMA 写操作。只读参与者完全不参与协议。此外基于 RDMA 的读取验证确保只读参与者的主节点没有 CPU 工作，还有通过单向 RDMA 写 COMMIT-PRIMARY 和 COMMIT-BACKUP 记录降低了远端 CPU 的等待时间。

5. 故障恢复

FaRM 通过副本提供持久化和高可用。即使整个集群断电，所有已提交的状态都可以从存储在非易失性 DRAM 中的数据和日志恢复。故障恢复包括五个阶段：故障检测、重组、事务状态恢复、批量恢复数据和分配器状态恢复。

5.1 故障检测

FaRM 用租约来检测故障：每个节点在 CM 处持有租约，CM 也在每个节点处持有租约，任何租约到期都会触发故障恢复。

FaRM 的租约期限极短，这是高可用的关键。即使在高负载时，90 台机器的集群使用 5ms 的租约也没有误报。这需要精妙的实现，FaRM 使用专有的队列来管理租约，避免在共享队列中因其他消息延迟，实现可靠的专有消息传输仅需要在每台机器的网卡上增加两个队列。FaRM 使用一个单独的租约管理线程，以最高用户空间优先级运行。该线程不绑核，使用中断而非轮询，是为了避免饿死操作系统自己的任务。还在初始化时为租约管理器预先分配内存并固定它的代码，避免因内存管理导致延迟。

5.2 重组

重组协议用于更新 FaRM 实例的配置。单边 RDMA 操作对实现良好的性能至关重要，但也为重组协议提出了新需求。如果一台服务器从配置中移除，系统保证它上面存储的对象在其租约到期前不能被修改。在出现故障后，新配置中所有的机器必须就其成员资格达成一致才允许修改对象。

图 5 展示重组的时间线和步骤：

1. 怀疑

   CM 侧：当机器在 CM 的租约到期，CM 怀疑机器发生故障并启动重组。它会阻止所有外部客户端的请求。

   节点侧：如果当机器因 CM 租约到期怀疑它发生故障时，先请求一个“备用 CM”启动重组。如果超时（配置未变更），它会尝试自己重组，启动重组的机器尝试在期间成为新的 CM。

2. 探测

   新 CM 对配置中所有机器发起 RDMA 读取请求，任何读取失败的机器也会被怀疑。只有在收到绝大多数的探测应答后，新 CM 才会继续重组。这确保了如果出现网络分区，CM 不会处于较小的分区中。

3. 更新配置

   在收到探测请求的回复后，新 CM 尝试更新存储在 Zookeeper 中的配置，使用 znode 序列号来实现原子比较和交换。

4. 重映射区域

   新 CM 随后重新分配之前映射到故障机器的区域，恢复副本数量到 F + 1。如果检测到某些区域丢了所有副本或空间不足以重新复制区域，CM 会通知错误信号。

5. 发送新配置

   CM 给配置中的所有机器发送 NEW-CONFIG 消息。如果 CM 变更，NEW-CONFIG 还会重置租约协议：它作为新 CM 给所有节点发送的租约请求；如果 CM 未变，在重组期间继续租约交换以快速检测其他故障。

6. 应用新配置

   当一台机器收到配置 ID 大于其自身的 NEW-CONFIG 消息，会更新其当前的配置 ID 和缓存的区域映射副本。从此它只向在配置中的机器发送新请求，并拒绝来自它们的读取响应和写入确认，还阻塞来自外部客户端的请求。随后向 CM 回复 NEW-CONFIG-ACK 消息。

7. 提交新配置

   当 CM 从配置中的所有机器收到 NEW-CONFIG-ACK 消息，会等待一会确保不再有机器租约到期。然后向所有配置成员发送 NEW-CONFIG-COMMIT 消息，这起到了租约授予的作用。至此所有成员解除对外部客户端请求的阻塞并启动事务恢复。

5.3 事务状态恢复

FaRM 在配置变更后通过分布式的对象修改日志来恢复事务状态，包括事务中变更的对象副本和协调器。

1. 阻塞对恢复区域的访问

   当一个区域的主节点故障，在重组期间会将其中一个备节点提升为新的主节点，在所有更新该区域的事务都还原到新主节点之前该区域是不允许被访问的。

2. 排空日志

   单边 RDMA 写操作也会影响事务恢复，FaRM 通过清空日志来解决网卡不管何种配置都会确认写入事务日志的 COMMIT-BACKUP 和 COMMIT-PRIMARY 记录这个问题。

3. 寻找恢复中的事务

   恢复中的事务是指在提交阶段配置变更的那些事务，重新配置导致写入对象的某些副本、读取对象的主节点或协调器已经发生变化。在排空日志时，每个日志记录都会被检查，来确定要恢复事务的集合。

4. 锁恢复

   每个区域的主节点等待本机日志清空并从每个备份接收 NEED-RECOVERY 消息，来构建完整的恢复事务集合。同时其上面的 FaRM 进程会从备份中获取尚未存储到本地的事务日志记录，然后锁定事务修改的对象。

   当区域的锁恢复后，该区域就处于激活状态。

5. 复制日志记录

   主节点通过给备节点发送 REPLICATE-TX-STATE 消息来复制缺失的事务日志记录。

6. 投票

   恢复事务的协调器根据每个区域的投票决定是提交还是中止这些事务，投票由每个区域的主节点发送。FaRM 使用一致性哈希确定事务的协调器，确保所有主节点一致认同恢复事务的协调器的身份。当协调器故障，其恢复事务的协调责任将分布到集群的多台机器上。

7. 决策

   如果协调器收到来自任意区域的 commit-primary 投票，就会提交事务；否则等待所有区域的投票，并在至少一个区域投票 commit-backup 且所有其他被事务修改的区域投票 lock、commit-backup 或 truncated 时提交。

• 正确性

  不同步骤恢复事务确保严格的可串行的关键在于恢复会保留先前已提交或中止的事务的结果。

  • 提交：主节点公开事务的修改；或协调器通知应用程序事务已提交
  • 中止：协调器发送中止消息通知应用程序

  对于结果尚未确定的事务，恢复既可能提交也可能中止事务，但会确保结果保留。

• 性能

  FaRM 使用几个优化技术来快速恢复故障：

  • 识别恢复中的事务将工作限制在仅受重新配置影响的事务和区域，大规模集群中发生故障的机器可能只占总数的一小部分。结果表明这可以将需要恢复的事务数量减少一个数量级。
  • 在区域、机器和进程之间并行化恢复工作本身。在锁恢复后立即使区域可用能够提高响应性能，短时间阻塞访问这些区域的新事务。

5.4 恢复数据

FaRM 必须在一个区域的新备份中恢复（重新复制）数据，确保能够在未来容忍 f 个副本的故障。

一个区域的首次备份最初有一个已清零的本地区域副本。FaRM 将该区域分配给多个工作线程并行恢复，每个线程发起单边 RDMA 操作，每次从主节点读取一个块。目前使用 8KB 大小的块以有效利用网络。

每个恢复的对象在复制到备份之前都必须经过检查：如果其版本高于本地版本，则备份用 CAS 锁定本地版本，更新后解锁；如果已经或正在被事务更新，创建了更新的版本，则忽略。

5.5 恢复分配器的状态

分配器将区域拆分成块（1MB），用作分配小对象的 slab。保留了两部分元数据：

• 块头（block header）：包含对象大小
• slab 空闲列表

分配新块时，块头会被复制到备份中，确保了故障后它们在新的主服务器上仍可用。

为了减少对象分配的开销，slab 空闲列表仅在主节点保留。每个对象头部都有一个在分配时设置在事务执行期间释放时清除的比特。对象状态的变更在事务提交时复制。故障发生后，通过扫描区域中的对象并行地恢复新主节点上的空闲列表。为了尽量减少对事务锁恢复的影响，每 100 微秒只扫描 100 个对象。在恢复某个 slab 的空闲链表之前，对象释放操作会进入队列等待。

6. 评估

6.1 搭建

实验集群由 90 台 FaRM 集群的机器和 5 台 ZooKeeper 实例组成：

• 每台机器有 256 GB DRAM 和两个 8 核的 Intel E5-2650 CPU，运行 Windows Server 2012 R2。
• 启用超线程，前 30 个线程用于前台任务；其余 2 个用于租约管理器。
• 每台机器两张 Mellanox ConnectX-3 56 G Infiniband 网卡，每张网卡由不同 socket 上的线程使用，并通过一个全双工带宽的 Mellanox SX6512 交换机连接。

FaRM 配置为使用三向复制（一个主和两备），租约时间为 10 毫秒。

6.2 基准测试

使用两个事务的基准测试来衡量 FaRM 的性能：

1. TATP（Telecommunication Application Transaction Processing）
2. TPC-C

6.3 常规性能

将 FaRM 无故障情况下的性能展示为吞吐量-延迟曲线。

• TATP

  FaRM 每秒执行 1.4 亿次 TATP 事务，中位延迟为 58µs，P99 延迟为 645µs。

  TATP 使用的多对象分布式事务在数十微秒内提交，最低吞吐量时的平均提交延迟为 19µs；最高吞吐量时为 138µs。

  FaRM 的性能是单机事务引擎 Hekaton 所公布的 TATP 结果的 33 倍。

• TPC-C

  运行 60s TPC-C，FaRM 每秒执行多达 450 万次“新订单”事务，中位延迟为 808µs，P99 延迟为 1.9ms。

  当时已知 TPC-C 性能最好是 Silo，它是一种单机内存系统，使用 FusionIO SSD 记录日志。FaRM 的吞吐量是 Silo 无日志记录时的 17 倍，在这个吞吐量水平下，其延迟比Silo 有日志记录时好 128 倍。

• 读性能

  每秒 7.9 亿次查找的吞吐量，中位延迟为 23µs，P99 延迟为 73µs。

6.4 故障性能

为了评估在故障情况下的性能，运行了相同的基准测试，在实验进行到 35s 时干掉了一台机器上的 FaRM 进程。

• TATP

  

  图 9(a) 中吞吐量在故障时急剧下降，但迅速恢复。系统在不到 40ms 内恢复到峰值吞吐量；图 9(b) 数据恢复是有节奏的，不影响前台吞吐量。故障机器托管了 84 个 2GB 的区域。每个线程每 2ms 获取 8KB 的块，这意味着单机恢复一个 2GB 区域大约需要 17s。

  即使在没有故障的情况下，TATP 也会出现一些吞吐量下降，我们认为这是基准测试中访问不均衡所致；当许多事务发生冲突时，吞吐量也会下降。

• TPC-C

  

  图 10(a) 表明系统在不到 50ms 内恢复了大部分吞吐量。由于 TPC-C 的事务更复杂，系统恢复事务锁的时间比 TATP 略长。主要区别在于数据恢复时间更长（图 10(b)），即使在实验中 TPC-C 仅恢复了 63 个区域。导致恢复并行性降低是因为因为多个区域在同一组机器上复制以满足应用程序指定的局部性约束。在实验中，两台机器各自恢复了 17 个区域，导致数据恢复花费超过 4 分钟。

• CM 故障

  

  图 11 展示了 CM 进程失败时 TATP 吞吐量随时间的变化，恢复速度更慢：吞吐量恢复到故障前同一水平大约需要 110ms。主要原因是重新配置时间增加，从图 9(a) 中的 20ms 增加到 97ms。

• 恢复时间的分布

  

  从 CM 检测到故障机器开始测算恢复时间，直到吞吐量恢复到故障前平均吞吐量的 80%。中位恢复时间大约是 50ms，执行超过 70% 的时间在 100ms 以内，剩下的恢复时间超过了100ms，但始终少于 200ms。

• 其他故障

  有些故障会同时影响多台机器，比如电源或交换机故障。为了应对这种协调故障，FaRM 允许为每台机器指定一个故障域，并且 CM 在不同的故障域中放置区域的每个副本。同时使其中一个故障域中的所有进程失效，来模拟顶层交换机的故障。

  

  图 13 展示了 72 台未故障机器的 TATP 吞吐量随时间的变化，FaRM 在故障后不到 400ms 内恢复到峰值吞吐量。

• 数据恢复进度

  

  FaRM 加快了数据恢复的速度，以减少对吞吐量的影响。图 14 展示了 TATP 的吞吐量在数据恢复非常活跃的情况下随时间变化：每个线程并发获取四个 32KB 的数据块。只有在故障发生 800ms 后系统重新复制大部分区域后，才能恢复峰值吞吐量。然而数据恢复的速度要快得多：恢复 83 个区域副本（166GB）仅需 1.1s。

6.5 租约时间

为了评估租约管理器的优化，进行了一个实验，所有机器上所有线程反复向 CM 发出 RDMA 读取请求，持续 10 分钟。禁用了恢复功能并统计在不同的租约管理器实现和不同的租约时间下集群中出现的（误报）租约到期事件的数量。

图 16 比较了四种租约管理器的实现：第一个使用 FaRM 的 RPC；其他方案则使用 UDP：共享线程（UD）、正常优先级的专用线程（UD + thread）以及高优先级、中断和无核绑定的线程（UD + thread + pri）。结果表面所有优化都是必要的，使用 10ms 甚至更短的租约时间而不误报。