FaRM译文

No compromises: distributed transactions with consistency, availability, and performance

Aleksandar Dragojevic, Dushyanth Narayanan, Edmund B. Nightingale,

Matthew Renzelmann, Alex Shamis, Anirudh Badam, Miguel Castro Microsoft Research

摘要

1. 引言

2. 硬件趋势

2.1 非易失性DRAM

2.2 RDMA 网络

3. 编程模型与架构

4. 分布式事务与复制

5. 故障恢复

5.1 故障检测

5.2 重新配置

5.3 事务状态恢复

5.4 数据恢复

5.5 恢复分配器状态

6. 评估

6.1 设置

6.2 基准测试

6.3 正常情况下的性能

6.5 租约时间

7 相关工作

8 结论

摘要

具有强一致性和高可用性的事务简化了分布式系统的构建和推理。然而，之前的实现表现不佳。这迫使系统设计人员要么完全避免使用事务，要么削弱一致性保证，或者提供需要程序员自己划分数据的单机事务。在本文中，我们展示了在现代数据中心中无需妥协。我们展示了一种称为FaRM的主存分布式计算平台能够提供具有严格可串行化、高性能、持久性和高可用性的分布式事务。FaRM在90台机器上使用4.9 TB数据库实现了每秒1.4亿次TATP 事务的峰值吞吐量，并能在不到50毫秒内从故障中恢复。实现这些结果的关键在于从零开始设计的新事务、复制和恢复协议，充分利用了具有RDMA的通用网络以及一种新的、低成本的非易失性DRAM提供方式。

1. 引言

具有高可用性和严格可串行化的事务[35]通过提供一个简单而强大的抽象来简化分布式系统的编程和推理：一个永不失败的单一机器，按与实际时间一致的顺序逐个执行事务。然而，之前在分布式系统中实现这种抽象的尝试导致了性能不佳。因此，像 Dynamo[13]或 Memcached[1]这样的系统通过不支持事务或实现弱一致性保证来提高性能。其他系统（如[3， 6，9，28]）仅在所有数据位于同一台机器时提供事务，迫使程序员对数据进行分区，增加了正确性推理的复杂性。

本文展示了现代数据中心中的新软件如何消除这种妥协需求。我们描述了FaRM[16]的事务、复制和恢复协议，FaRM是一个基于主存的分布式计算平台。FaRM提供具有严格可串行化、高可用性、高吞吐量和低延迟的分布式ACID事务。这些协议从基本原则出发设计，以利用数据中心中出现的两个硬件趋势：具有RDMA的快速商用网络和一种提供非易失性DRAM 的廉价方法。非易失性是通过为电源单元连接电池，并在断电时将DRAM内容写入SSD来实现的。这些趋势消除了存储和网络瓶颈，但也暴露了CPU瓶颈，限制了它们的性能优势。 FaRM的协议遵循三个原则来解决这些CPU瓶颈：减少消息数量，使用单边RDMA读写代替消息通信，并有效利用并行性。

FaRM通过将对象分布在数据中心的机器上进行横向扩展，同时允许事务跨任意数量的机器。与通过Paxos复制协调器和数据分区（如[11]中的方法）不同，FaRM通过使用垂直Paxos[25] 的主备复制和直接与主副本和备份通信的非复制协调器来减少消息数量。FaRM使用乐观并发控制和四阶段提交协议（锁定、验证、提交备份和提交主副本）[16]，但我们通过消除锁定阶段的备份消息改进了原始协议。

FaRM通过使用单边RDMA操作进一步减少了CPU开销。单边RDMA不使用远程CPU，并避免了大多数本地CPU开销。FaRM事务在执行和验证过程中使用单边RDMA读取。因此，它们在远程只读参与者处不使用CPU。此外，协调器在将记录日志到事务中修改的对象的非易失性预写日志时，也使用单边RDMA。例如，协调器使用单个单边RDMA将提交记录写入远程备份。因此，事务在备份处不会使用前台CPU。CPU会在后台稍后用于延迟截断日志，以就地更新对象。

使用单边RDMA需要新的故障恢复协议。例如，FaRM无法依赖服务器在租约[18]过期时拒绝传入请求，因为请求是由NIC处理的，而NIC不支持租约。我们通过使用精确的成员资格[10]来解决这个问题，以确保机器一致同意当前配置的成员资格，并仅向成员机器发送单边操作。FaRM还无法依赖传统机制来确保参与者在准备阶段拥有提交事务所需的资源，因为事务记录在不涉及远程CPU的情况下写入参与者日志。相反，FaRM使用保留机制，以确保在开始提交之前，日志中有足够的空间来容纳所有提交和截断事务所需的记录。

FaRM中的故障恢复协议之所以快速，是因为它有效地利用了并行性。它在集群中均匀分配每个状态的恢复，并在每台机器的核心之间并行化恢复。此外，它使用两种优化来允许事务执行与恢复并行进行。首先，事务在锁定恢复阶段完成后开始访问受到故障影响的数据，该阶段仅需几十毫秒，而不是等待几秒钟才能完成其余的恢复。其次，未受到故障影响的事务可以继续执行而不被阻塞。FaRM还通过利用快速网络交换频繁的心跳信号提供快速的故障检测，并使用优先级和预分配来避免误报。

我们的实验结果表明，你可以兼得一致性、高可用性和性能。FaRM能够在不到50毫秒的时间内从单机故障中恢复，并且在只有几台机器的情况下，其性能超过了最先进的单机内存事务系统。例如，在仅三台机器上运行时，它的吞吐量优于Hekaton[14，26]，并且在吞吐量和延迟上都优于Silo[39，40]。

2. 硬件趋势

FaRM 的设计受到数据中心机器中丰富且廉价的DRAM供应的激励。典型的数据中心配置每台2插槽机器配备128-512GB的DRAM[29]，而 DRAM的成本不到每GB 12美元。这意味着，1PB的DRAM只需要2000台机器，这对于存储许多有趣应用的数据集是足够的。此外，FaRM 利用了两个硬件趋势来消除存储和网络瓶颈：非易失性DRAM和快速的商用网络与RDMA。

2.1 非易失性DRAM

“分布式不间断电源供应（UPS）”利用广泛可用的锂离子电池，降低了数据中心 UPS 的成本，相较于传统的集中式方法（使用铅酸电池）。例如，微软的开放云服务器（OCS）规范包括局部能源存储（LES）[30，36]，将锂离子电池与每个机架内24台机器的电源单元集成在一起。估计LES UPS的成本不到每焦耳0.005美元。这种方法比传统UPS更可靠：锂离子电池具有多个独立的过度配置单元，任何电池故障只会影响机架的一部分。

分布式UPS有效地使DRAM具有耐久性。当发生断电时，分布式UPS利用电池的能量将内存内容保存到商用SSD。这不仅通过避免对SSD的同步写入提高了常规性能，还在发生故障时才写入 SSD，从而延长 SSD 的使用寿命。另一种替代方法是使用非易失性 DIMM （NVDIMM），它们包含自己的专用闪存、控制器和超级电容器（例如[2]）。不幸的是，这些设备是专用的、昂贵的且体积庞大。相比之下，分布式UPS使用商用DIMM，并利用商用SSD。唯一的额外成本是SSD上保留的容量和UPS电池本身。

电池预留成本取决于将内存保存到SSD所需的能量。我们在标准的2插槽机器上测量了一个未优化的原型。在故障发生时，它关闭硬盘驱动器和网络接口卡（NIC），并将内存中的数据保存到单个M.2（PCIe）SSD上，保存每GB数据需要消耗110焦耳的能量。大约90焦耳用于在保存期间为机器的两个CPU插槽供电。额外的SSD可以减少保存数据的时间，从而降低能量消耗（见图1）。像将CPU置于低功耗状态这样的优化，将进一步降低能量消耗。

在最坏的配置下（单个SSD，无优化），以每焦耳0.005美元的成本，非易失性的能量成本为每GB 0.55美元，而保留SSD容量的存储成本为每GB 0.90美元。这两者的额外综合成本不到基础DRAM成本的15%，这相比于价格为DRAM的3至5倍的NVDIMM来说，显著降低了成本。因此，将所有机器内存视为非易失性RAM（NVRAM）是可行且具有成本效益的。FaRM 将所有数据存储在内存中，并在数据已写入多个副本的 NVRAM 后视为持久的。

2.2 RDMA 网络

FaRM在可能的情况下使用单边RDMA操作，因为它们不使用远程CPU。我们做出这一决定既基于我们之前的工作，也基于额外的测量。在[16]中，我们展示了在一个 20 台机器的 RoCE[22]集群上，RDMA读取的性能比在集群中所有机器随机选择小对象的可靠RPC通过 RDMA性能高出2倍。瓶颈在于NIC消息速率，而我们实现的RPC需要的消息数量是单边读取的两倍。我们在一个90台机器的集群上重复了这个实验，每台机器配备两块Infiniband FDR（56Gbps）NIC。这与[16]相比，显著提高了每台机器的消息速率，并消除了NIC消息速率的瓶颈。现在，RDMA和RPC都受限于CPU性能，性能差距扩大至4倍，如图2所示。这说明了降低CPU开销以实现新硬件潜力的重要性。

3. 编程模型与架构

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

FaRM事务使用乐观并发控制。在执行过程中，更新被缓存在本地，只有在成功提交后才会对其他事务可见。由于与并发事务的冲突或故障，提交可能会失败。FaRM为所有成功提交的事务提供严格的可串行化[35]。在事务执行期间，FaRM保证单个对象的读取是原子的，仅读取已提交的数据，同一对象的连续读取返回相同的数据，并且读取由事务写入的对象返回最新的值。它并不保证不同对象读取的原子性，但在这种情况下，确保事务不会提交，从而保证已提交的事务是严格可串行的。这使得我们可以将一致性检查推迟到提交时，而不是在每次对象读取时重新检查一致性。然而，这增加了一些编程复杂性：FaRM应用程序必须在执行期间处理这些临时不一致[20]。处理这些不一致的自动化是可能的[12]。

FaRM API 还提供无锁读取，这是优化后的单对象只读事务，以及局部性提示，使程序员能够将相关对象共置于同一组机器上。这些可以被应用程序用来改善性能，如[16]中所述。

图3显示了一个包含四台机器的FaRM实例。该图还展示了机器A的内部组件。每台机器在用户进程中运行FaRM，每个硬件线程都与一个固定的内核线程相对应。每个内核线程运行一个事件循环，该循环执行应用程序代码并轮询RDMA完成队列。

FaRM实例在时间推移中经历一系列配置状态，随着机器的故障或新机器的添加而变化。配置是一个元组 i, S, F, CM其中 i 是一个唯一的、单调递增的64位配置标识符，S 是配置中的机器集合，F 是一个将机器映射到预期独立故障的故障域的映射（例如，不同的机架），而 CM 是配置管理器。FaRM 使用 Zookeeper[21]协调服务确保机器就当前配置达成一致，并进行存储，类似于垂直Paxos[25]。但它并不依赖Zookeeper来管理租约、检测故障或协调恢复，这通常是通过CM使用高效实现来快速恢复的。CM在每次配置更改时调用Zookeeper 一次以更新配置。

FaRM 中的全局地址空间由2GB的区域组成，每个区域在一个主副本和 f 个备份上进行复制，其中 f 是所需的容错级别。每台机器在非易失性DRAM中存储多个区域，其他机器可以通过RDMA读取这些区域。对象始终从包含区域的主副本读取，如果该区域在本地机器上，则使用本地内存访问；如果是远程区域，则使用单边RDMA读取。每个对象都有一个 64 位版本，用于并发控制和复制。区域标识符到其主副本和备份的映射由配置管理器（CM）维护，并与区域一起进行复制。这些映射由其他机器按需获取，并与发出单边RDMA读取所需的RDMA引用一起缓存到线程中。

机器通过CM联系以分配新的区域。CM从单调递增的计数器中分配区域标识符并选择该区域的副本。副本选择在每台机器上平衡存储的区域数量，同时满足以下约束：确保有足够的容量，每个副本位于不同的故障域中，并且当应用程序指定局部性约束时，区域与目标区域共置。然后，CM向选定的副本发送包含区域标识符的准备消息。如果所有副本都报告成功分配区域，则CM向所有副本发送提交消息。这种两阶段协议确保在映射被使用之前，它在所有区域副本上都是有效且已复制的。

这种集中式方法提供了更大的灵活性，以满足故障独立性和局部性约束，相较于我们基于一致性哈希的先前方法[16]。它还使得在机器间平衡负载和在接近容量的情况下运行变得更加容易。对于2GB的区域，我们预计在典型机器上最多会有250个区域，因此单个CM可以处理数千台机器的区域分配。

每台机器还存储环形缓冲区，这些缓冲区实现了FIFO队列[16]。它们用作事务日志或消息队列。每对发送者-接收者都有自己的日志和消息队列，这些日志和队列物理上位于接收者上。发送者通过单边RDMA写入将记录附加到日志的尾部。这些写入操作由NIC确认，而不涉及接收者的 CPU。接收者定期轮询日志的头部以处理记录。它在截断日志时懒惰地更新发送者，从而允许发送者在环形缓冲区中重用空间。

4. 分布式事务与复制

FaRM 将事务和复制协议集成在一起，以提高性能。与传统协议相比，它使用的消息更少，并利用单边RDMA读取和写入来提高CPU效率和降低延迟。FaRM在非易失性DRAM中使用主备复制来存储数据和事务日志，并使用未复制的事务协调器与主副本和备份直接通信。它使用乐观并发控制和读取验证，类似于一些软件事务内存系统（例如TL2 [15]）。

图4显示了FaRM事务的时间线，表1和表2列出了事务协议中使用的所有日志记录和消息类型。在执行阶段，事务使用单边RDMA读取对象，并在本地缓冲写入。协调器还记录所有访问对象的地址和版本。对于与协调器在同一机器上的主副本，读取对象和写入日志时使用本地内存访问，而不是RDMA。在执行结束时，FaRM尝试通过执行以下步骤来提交事务：

1. 锁定：协调器在每个作为任何已写对象主副本的机器的日志中写入一个LOCK记录。此记录包含该主副本上所有已写对象的版本和新值，以及所有已写对象的区域列表。主副本通过尝试使用比较和交换（compare-and-swap）在指定版本上锁定对象来处理这些记录，并发送回一条消息报告所有锁定是否成功。如果在事务读取后任何对象的版本发生变化，或者对象当前被其他事务锁定，则锁定可能会失败。在这种情况下，协调器会中止事务，向所有主副本写入一个中止记录，并返回错误给应用程序。

2. 验证：协调器通过从其主副本读取所有被读取但未被事务写入的对象的版本来执行读取验证。如果任何对象发生变化，则验证失败，事务将被中止。验证默认使用单边RDMA 读取。对于持有超过 trtrtr 个对象的主副本，验证通过RPC 进行。阈值 trtrtr（当前为 4）反映了RPC相对于RDMA读取的CPU开销。

3. 提交备份：协调器在每个备份的非易失性日志中写入一个COMMIT BACKUP记录，然后等待NIC硬件的确认而不干扰备份的CPU。COMMIT BACKUP日志记录的负载与LOCK记录相同。

4. 提交主副本：在所有COMMIT BACKUP写入确认后，协调器在每个主副本的日志中写入一个COMMIT PRIMARY记录。当接收到至少一个此类记录的硬件确认或在本地写入时，它向应用程序报告完成情况。主副本通过就地更新对象、递增它们的版本并解锁来处理这些记录，从而使事务提交的写入得以暴露。

5. 截断：备份和主副本在日志中保留记录，直到被截断。协调器在接收到所有主副本的确认后，懒惰地截断主副本和备份的日志。它通过将截断事务的标识附加在其他日志记录中来实现这一点。在截断时，备份将更新应用于其对象的副本。

正确性：已提交的读写事务在获取所有写锁定的时刻是可串行化的，而已提交的只读事务则是在其最后一次读取时可串行化。这是因为在序列化点上，所有读取和写入对象的版本与执行期间所见的版本相同。锁定确保了写入对象的这一点，而验证则确保了只读取对象的这一点。在没有故障的情况下，这等同于在序列化点原子性地执行和提交整个事务。FaRM中的串行化也是严格的：序列化点始终在执行开始和向应用程序报告完成之间。

为了确保在故障发生时的可串行化性，在写入COMMIT-PRIMARY 之前，必须等待所有备份的硬件确认。假设协调器没有收到某个备份 b 对区域 r 的确认。那么，一个主副本可能会暴露事务修改，随后与协调器和区域 r 的其他副本一起失败，而备份 b 永远没有收到 COMMIT-BACKUP记录。这将导致丢失对区域 r 的更新。

由于读取集仅存储在协调器中，因此如果协调器失败且没有提交记录幸存以证明验证的成功，则事务将被中止。因此，协调器必须在向应用程序报告成功提交之前，等待至少一个主副本的成功提交。这确保至少有一个提交记录在报告给应用程序的事务中能够经受住任何 f 次故障。否则，如果协调器和所有备份在任何COMMIT-PRIMARY记录被写入之前都失败，则这样的事务可能仍然中止，因为只会幸存LOCK记录，而没有记录证明验证成功。

在传统的两阶段提交协议中，参与者可以在处理准备消息时保留资源以提交事务，或者如果没有足够的资源则拒绝准备事务。然而，由于我们的协议避免在提交过程中涉及备份的CPU，协调器必须在所有参与者中保留日志空间以确保进展。协调器在启动提交协议之前为所有提交协议记录（包括主副本和备份日志中的截断记录）保留空间。日志预留是协调器的本地操作，因为协调器向每个参与者的日志中写入它拥有的记录。预留在相应的记录被写入时释放。如果预留的截断记录与其他消息一起发送，则也会释放。若日志满了，协调器利用预留来写入明确的截断记录，以腾出日志空间。这种情况很少发生，但需要确保活性。

性能：对于我们的目标硬件，该协议相比传统的分布式提交协议具有多个优势。考虑一个带有复制的两阶段提交协议，例如Spanner [11]。Spanner使用Paxos [24]来复制事务协调器及其参与者，参与者是存储事务读取或写入的数据的机器。每个Paxos状态机充当传统两阶段提交协议中的单个机器 [19]。这需要 2f+1个副本来容忍 f 次故障，并且，由于每个状态机操作至少需要 2f+1 次往返消息，因此需要 4P(2f+1)条消息（其中 P 是事务中的参与者数量）。

FaRM使用主备复制而不是Paxos状态机复制。这减少了数据的副本数量到 f+1，并且还减少了在事务期间传输的消息数量。协调器状态不被复制，协调器与主副本和备份直接通信，进一步减少了延迟和消息数量。FaRM由于复制而产生的开销很小：向每个拥有已写对象备份的远程机器发送一次RDMA写入即可。只读参与者的备份根本不参与该协议。此外，通过RDMA进行读取验证确保只读参与者的主副本不会消耗CPU工作，并且使用单边RDMA 写入COMMIT-PRIMARY和COMMIT-BACKUP记录减少了对远程CPU的等待，同时也允许远程CPU的工作延迟和批处理。

FaRM 提交阶段使用 Pw(f+3)次单边RDMA写入，其中 Pw 是由事务写入的对象的主副本机器数量，而 Pr 次单边RDMA读取是从远程主副本读取但未写入的对象数量。读取验证为关键路径增加了两个单边RDMA延迟，但这是一个很好的权衡：在没有负载时，增加的延迟仅为几微秒，CPU开销的减少导致在负载下的更高吞吐量和更低延迟。

5. 故障恢复

FaRM通过复制提供持久性和高可用性。我们假设机器可以通过崩溃的方式发生故障，但可以在不丢失非易失性DRAM内容的情况下恢复。我们依赖于有界时钟漂移以确保安全性，并依赖于最终有界消息延迟以确保活性。

我们为所有已提交的事务提供持久性，即使整个集群发生故障或失去电源：所有已提交的状态可以从存储在非易失性DRAM中的区域和日志中恢复。即使每个对象最多有 fff 个副本丢失非易失性DRAM的内容，FaRM也能确保持久性。FaRM还可以在故障和网络分区情况下保持可用性，前提是存在一个包含大多数机器的分区，这些机器彼此连接并且连接到 Zookeeper 服务中的大多数副本，并且该分区至少包含每个对象的一个副本。 FaRM中的故障恢复分为五个阶段，具体如下：故障检测、重新配置、事务状态恢复、大量数据恢复和分配器状态恢复。

5.1 故障检测

FaRM使用租约 [18] 来检测故障。每台机器（除了协调器CM）在 CM处持有租约，而CM 在每台其他机器处持有租约。任何租约的到期都会触发故障恢复。租约的授予使用三方握手。每台机器向 CM 发送租约请求，CM 回复一条消息，该消息既是对机器的租约授予，也是 CM发出的租约请求。然后，机器向CM回复租约授予。

FaRM的租约时间极短，这是高可用性的关键。在重负载下，FaRM可以在90台机器的集群中使用5毫秒的租约，且没有假阳性。显著更大的集群可能需要两级层次结构，在最坏的情况下，这将使故障检测时间加倍。

在负载下实现短租约需要仔细的实现。FaRM使用专用的队列对来处理租约，以避免租约消息在共享队列中因其他消息类型而延迟。使用可靠传输将要求 CM 为每台机器额外设置一个队列对，这会导致因NIC的队列对缓存容量缺失而造成性能下降 [16]。相反，租约管理器使用Infiniband 发送和接收动词与无连接的不可靠数据报传输，这只需要在NIC上为额外的队列对预留一个额外空间。

默认情况下，租约续约每15个租约到期周期尝试一次，以考虑潜在的消息丢失。租约续约还必须及时在CPU上安排。FaRM使用专门的租约管理器线程，该线程以最高用户空间优先级（在Windows上为31）运行。租约管理器线程不固定到任何硬件线程，并使用中断而不是轮询，以避免对必须在每个硬件线程上定期运行的关键操作系统任务造成饿死。这会将消息延迟增加几微秒，但对于租约而言并没有问题。

此外，我们不将 FaRM 线程分配给每台机器上的两个硬件线程，而是为租约管理器保留它们。我们的测量显示，租约管理器通常在这些硬件线程上运行而不会影响其他FaRM线程，但有时会被更高优先级的任务抢占，导致它在其他硬件线程上运行。因此，将租约管理器固定到一个硬件线程可能会在使用短租约时导致假阳性。

最后，我们在初始化期间预分配租约管理器使用的所有内存，并将其使用的所有代码分页并锁定，以避免因内存管理造成的延迟。

5.2 重新配置

重新配置协议将FaRM实例从一个配置转移到下一个配置。使用单边RDMA操作对于实现良好的性能至关重要，但这对重新配置协议提出了新的要求。例如，实现一致性的一个常见技术是使用租约 [18]：服务器在回复访问对象的请求之前，会检查是否持有该对象的租约。如果服务器从配置中被驱逐，系统保证其存储的对象在租约到期之前不能被修改（例如，[7]）。 FaRM在处理与使用消息与系统通信的外部客户端请求时使用了这一技术。但由于FaRM配置中的机器通过RDMA读取对象而不涉及远程CPU，因此服务器的CPU无法检查是否持有租约。目前的NIC硬件不支持租约，未来是否会支持仍不清楚。

我们通过实现精确的成员资格 [10] 来解决这个问题。在发生故障后，新的配置中的所有机器必须在允许对象修改之前就其成员资格达成一致。这使得 FaRM 可以在客户端而不是服务器上执行检查。配置中的机器不会向不在其中的机器发出RDMA请求，来自不再在配置中的机器的RDMA读取回复和RDMA写入确认被忽略。图5展示了一个重新配置的时间线示例，包括以下步骤：

1. 怀疑。当 CM处的某台机器的租约到期时，它怀疑该机器发生故障并启动重新配置。在此时，它开始阻止所有外部客户端请求。如果非CM机器由于租约到期怀疑CM 发生故障，它首先请求少数几个“备份CM”中的一个来启动重新配置（使用一致性哈希的CM的kkk个后继）。如果在超时期间配置没有变化，那么它将尝试自行进行重新配置。该设计避免了在CM失败时发生大量同时的重新配置尝试。在所有情况下，发起重新配置的机器将尝试成为重新配置的一部分的新CM。

2. 探测。新的CM对配置中的所有机器发出RDMA读取请求，除了被怀疑的机器。对于读取失败的任何机器也被怀疑。这些读取探测允许通过一次重新配置处理影响多台机器的相关故障，例如电源和交换机故障。新的CM只有在获得大多数探测回复后才能继续进行重新配置。这确保了在网络分区的情况下，CM 不会位于较小的分区中。

3. 更新配置。在收到探测回复后，新的CM尝试将存储在Zookeeper中的配置数据更新为，其中 c 是当前配置标识符，S是回复探测的机器集，FFF是机器到故障域的映射，CMid是其自己的标识符。我们使用Zookeeper的znode序列号来实现一个原子比较和交换，仅在当前配置仍为c时成功。这确保只有一台机器能够成功将系统移至标识符为c+1的配置（并成为CM），即使多个机器同时尝试从标识符为ccc的配置进行配置更改。

4. 重新映射区域。新的CM随后重新分配之前映射到故障机器的区域，以恢复副本数量至 f+1。它尝试在容量和故障独立性约束的条件下平衡负载并满足应用程序指定的本地性提示。对于故障的主副本，它总是提升一个幸存的备份成为新的主副本，以减少恢复时间。如果它检测到区域失去了所有副本或没有空间重新复制区域，它会发出错误信号。

5. 发送新配置。在重新映射区域后，CM 向配置中的所有机器发送带有配置标识符、其自身标识符、配置中其他机器的标识符和所有新映射区域到机器的NEW-CONFIG 消息。NEW-CONFIG 还会在 CM 发生变化时重置租约协议：它充当新CM向每台机器的租约请求。如果CM未发生变化，则在重新配置期间租约交换继续进行，以快速检测额外的故障。

6. 应用新配置。当机器收到 NEW-CONFIG 并且配置标识符大于其自身时，它会更新其当前配置标识符和缓存的区域映射，并分配空间以容纳分配给它的任何新区域副本。从这一点开始，它不会向不在配置中的机器发出新请求，并拒绝来自这些机器的读取响应和写入确认。它还开始阻止来自外部客户端的请求。机器通过 NEW CONFIG-ACK 消息向CM回复。如果CM已更改，这既授予CM一个租约，也请求一个租约。

7. 提交新配置。一旦CM从配置中的所有机器接收到NEW-CONFIG-ACK消息，它将等待以确保在之前的配置中授予的任何租约（针对不再在配置中的机器）已过期。然后，CM向所有配置成员发送NEW-CONFIG COMMIT，这也充当租约授予。所有成员现在解锁之前被阻塞的外部客户端请求，并开始事务恢复。

5.3 事务状态恢复

FaRM在配置更改后使用分布在由事务修改的对象的副本上的日志来恢复事务状态。这涉及在修改的对象的副本和协调器处恢复状态，以决定事务的结果。图6展示了一个事务恢复的时间线示例。FaRM通过在集群中的线程和机器之间分配工作来实现快速恢复。排空（步骤 2）对所有消息日志并行进行。步骤1和步骤3–5对所有区域并行进行。步骤6–7对所有正在恢复的事务并行进行。

1. 阻止访问恢复中的区域

当某个区域的主副本发生故障时，在重新配置期间会将其中一个备份提升为新的主副本。在所有更新了该区域的事务被反映到新的主副本之前，我们不能允许访问该区域。我们通过阻止对该区域的本地指针和RDMA引用的请求，直到步骤4，当所有更新该区域的恢复事务的写锁已被获取。

2. 排空日志

单边RDMA写入也影响事务恢复。实现跨配置一致性的一般方法是拒绝来自旧配置的消息。 FaRM无法使用这种方法，因为NIC会确认写入事务日志的COMMIT-BACKUP和COMMIT PRIMARY记录，无论它们是在何种配置中发出的。由于协调器只在等待这些确认后才会公开更新并向应用程序报告成功，因此在处理这些记录时，机器无法始终拒绝来自先前配置的记录。我们通过排空日志来解决这个问题，以确保在恢复过程中处理所有相关记录：所有机器在接收到NEW-CONFIG COMMIT 消息时处理其日志中的所有记录。它们在完成后记录配置标识符到变量LastDrained中。

FaRM事务具有唯一标识符cmt，这些标识符在提交开始时分配，编码了提交开始时的配置 c、协调器的机器标识符m、协调器的线程标识符t和线程本地唯一标识符l。对于配置标识符小于或等于LastDrained的事务的日志记录将被拒绝。

3. 查找恢复中的事务

恢复中的事务是指其提交阶段跨越了配置更改，并且由于重新配置，某个已写对象的副本、某个已读对象的主副本或协调器发生了变化。在日志排空过程中，检查每个日志记录中的事务标识符和更新区域标识符列表，以确定恢复事务的集合。只有恢复事务会在主副本和备份中进行事务恢复，协调器仅对恢复事务拒绝硬件确认。

所有机器必须对给定事务是否为恢复事务达成一致。我们通过在重新配置阶段的通信中附加一些额外的元数据来实现这一点。CM在探测读取时读取每台机器的LastDrained 变量。对于自LastDrained以来映射发生变化的每个区域r，CM向该机器发送两个配置标识符的NEW CONFIG消息。这些标识符是LastPrimaryChange[r]（r的主副本发生变化时的最后配置标识符）和LastReplicaChange[r]（r 的任何副本发生变化时的最后配置标识符）。如果在配置c中开始提交的事务在配置c中恢复，除非满足以下条件：对于所有修改了该事务的对象的区域 r，LastReplicaChange[r] < c；对于所有被该事务读取的对象的区域r，LastPrimaryChange[r] < c；并且协调器没有从配置c中移除。

恢复事务的记录可能分布在由该事务更新的不同主副本和备份的日志中。每个区域的备份向主副本发送NEED RECOVERY消息，消息中包含配置标识符、区域标识符和更新该区域的恢复事务标识符的列表。

4. 锁恢复

每个区域的主副本等待本地机器日志排空并从每个备份接收NEED RECOVERY消息，以构建影响该区域的恢复事务的完整集合。然后，它根据标识符将事务分片到其线程中，使得每个线程t恢复协调器线程标识符t的事务状态。并行地，主副本中的线程从备份中获取未存储在本地的任何事务日志记录，然后锁定由恢复事务修改的任何对象。当区域的锁恢复完成后，该区域变为活跃状态，局部和远程协调器可以获得本地指针和RDMA引用，这使得它们能够在后续恢复步骤中并行读取对象和提交对该区域的更新。

5. 复制日志记录

主副本中的线程通过发送REPLICATE-TX STATE消息给备份，复制其缺失的任何事务的日志记录。消息中包含区域标识符、当前配置标识符和与LOCK记录相同的数据。

6. 投票

恢复事务的协调器根据由事务更新的每个区域的投票决定是否提交或中止该事务。这些投票由每个区域的主副本发送。FaRM使用一致哈希来确定事务的协调器，确保所有主副本在恢复事务的协调器身份上达成一致。如果协调器运行的机器仍在配置中，则协调器不会发生变化；但当协调器失败时，协调其恢复事务的责任将在集群中的机器之间分散。

主副本中的线程向其在协调器中的同级线程发送RECOVERY-VOTE消息，针对每个修改了该区域的恢复事务。投票如果任何副本看到了COMMIT-PRIMARY或COMMIT-RECOVERY，则为 commit-primary。如果任何副本看到了 COMMIT-BACKUP 且没有看到 ABORT RECOVERY，则投票commit-backup。否则，如果任何副本看到了LOCK记录且没有ABORT RECOVERY，则投票 lock。否则，投票为 abort。投票消息包括配置标识符、区域标识符、事务标识符和事务修改的区域标识符列表。

某些主副本可能不会为某个事务发起投票，因为它们要么从未收到该事务的日志记录，要么已经截断了该事务的日志记录。协调器向在超时期限内（设置为250微秒）尚未投票的主副本发送明确的投票请求。REQUEST-VOTE消息包含配置标识符、区域标识符和事务标识符。具有该事务日志记录的主副本在等待该事务的日志复制完成后，会像之前一样投票。

对于没有任何该事务日志记录的主副本，如果该事务已经被截断，则投票为truncated；如果未截断，则投票为unknown。为了确定事务是否已经被截断，每个线程维护一个事务标识符集合，该集合记录其日志中已被截断的事务标识符。该集合通过对未截断事务标识符使用下限来保持紧凑。下限根据每个协调器的下限进行更新，这些下限在协调器消息中和重新配置期间被附加。

7. 决策

协调器在收到任何区域的commit-primary投票时决定提交事务。否则，它将等待所有区域投票，并在至少一个区域投票 commit-backup 且所有其他修改了该事务的区域投票为 lock、 commit-backup 或 truncated 时提交事务。否则，它决定中止事务。然后，它向所有参与的副本发送COMMIT-RECOVERY或ABORT-RECOVERY消息。这两个消息都包含配置标识符和事务标识符。COMMIT-RECOVERY在主副本接收时的处理类似于COMMIT-PRIMARY，在备份接收时的处理类似于COMMIT-BACKUP。ABORT-RECOVERY的处理类似于ABORT。在协调器从所有主副本和备份接收到确认后，它发送TRUNCATE-RECOVERY消息。

正确性

接下来，我们提供一些关于事务恢复不同步骤如何确保严格串行化的直观理解。关键思想是，恢复过程保留了先前已提交或已中止事务的结果。我们说一个事务已提交，当主副本公开事务修改时，或协调器通知应用程序事务已提交时。一个事务被中止，当协调器发送中止消息或通知应用程序该事务已中止时。对于尚未确定结果的事务，恢复可以提交或中止该事务，但它确保从额外故障恢复不会影响结果。

未恢复事务的结果（步骤3）使用正常情况协议（第4节）进行决定，因此我们不会进一步讨论它们。对于一个已提交的恢复事务的日志记录，保证在日志排空（步骤2）之前或期间被处理和接受。这是因为主副本仅在处理COMMIT PRIMARY记录后才公开修改。如果协调器通知应用程序，它必须在接收到NEW-CONFIG之前接收到所有COMMIT BACKUP记录和至少一个COMMIT PRIMARY记录的硬件确认（因为它在更改配置后忽略确认）。因此，由于新配置包括每个区域的至少一个副本，至少一个区域的至少一个副本将处理 COMMIT PRIMARY 或 COMMIT BACKUP 记录，且其他每个区域至少有一个副本将处理 COMMIT PRIMARY、COMMIT BACKUP或LOCK记录。

步骤3和4确保修改该事务的区域的主副本能够看到这些记录（除非它们已被截断）。它们将这些记录复制到备份（步骤5），以保证投票在后续故障发生时产生相同的结果。然后，主副本根据它们已见到的记录向协调器发送投票（步骤6）。

决策步骤确保协调器决定提交任何已提交的事务。如果任何副本截断了事务记录，所有主副本将投票为 commit-primary、commit-backup 或 truncated。至少有一个主副本会发送非 truncated 的投票，因为如果不是这样，事务将不会处于恢复状态。如果没有副本截断事务记录，至少有一个主副本将投票commit-primary或commit-backup，其他主副本将投票commit primary、commit-backup 或 lock。

同样，如果事务之前被中止，协调器将决定中止，因为在这种情况下，要么没有 commit primary 或 commit-backup 记录，要么所有副本将收到ABORT-RECOVERY消息。

阻止对恢复区域的访问（步骤1）和锁恢复（步骤4）保证在恢复事务提交或中止之前，其他操作无法访问它修改的对象。

性能

FaRM使用多种优化来实现快速故障恢复。识别恢复事务将恢复工作限制在仅受重配置影响的事务和区域，这在大型集群中单台机器故障时可能只是总量的一个小子集。我们的结果表明，这可以将需要恢复的事务数量减少一个数量级。恢复工作本身在区域、机器和线程之间并行化。锁恢复后立即使区域可用，提高了前台性能，因为访问这些区域的新事务不会长时间被阻塞。具体来说，它们不需要等待这些区域的新副本更新，这需要大量的数据在网络上移动。

5.4 数据恢复

FaRM必须在区域的新备份中恢复（重新复制）数据，以确保它在未来能够容忍f个副本故障。数据恢复不是恢复正常操作所必需的，因此我们将其延迟到所有区域变为活跃状态，以最小化对延迟敏感的锁恢复的影响。每台机器在所有作为主副本的区域变为活跃后，向协调器（CM）发送一条REGIONS-ACTIVE消息。收到所有REGIONS-ACTIVE消息后，CM向配置中的所有机器发送消息ALL-REGIONS-ACTIVE。在此时，FaRM开始在前台操作的同时进行新备份的数据恢复。

区域的新备份最初具有新分配并且置零的本地区域副本。它将区域分割成工作线程并行恢复。每个线程通过单向RDMA操作一次从主副本读取一个块。目前我们使用8KB的块，这足够大以有效利用网络，但又小到不会影响正常操作。为了减少对前台性能的影响，恢复的节奏是通过在前一个读取的开始之后，随机选择一个时间间隔（设定为4毫秒）来调度下一个读取。

每个恢复的对象在复制到备份之前必须进行检查。如果对象的版本大于本地版本，备份将通过比较交换（compare-and-swap）锁定本地版本，更新对象状态，然后解锁。否则，说明该对象已被事务更新，版本大于或等于恢复的版本，此时不应用恢复的状态。

5.5 恢复分配器状态

FaRM 分配器将区域分割成块（1MB），这些块用作分配小对象的内存块。它保持两种元数据：块头，包含对象大小，以及块的空闲列表。每当分配新块时，块头会复制到备份中。这确保了在发生故障后，它们在新主副本上可用。由于块头在数据恢复中被使用，新主副本在收到NEW CONFIG-COMMIT 后立即将其发送给所有备份，以避免在复制块头时旧主副本失败造成的不一致性。

空闲列表仅在主副本上保存，以减少对象分配的开销。每个对象在其头部有一个位，通过分配设置并在事务执行期间通过释放清除。此对象状态的变化在事务提交时进行复制，如第4 节所述。发生故障后，通过在区域中扫描对象，在新主副本上恢复空闲列表，该过程在机器的所有线程中并行化。为了最小化对事务锁恢复的影响，分配恢复在收到 ALL-REGIONS ACTIVE后开始，并且为了最小化对前台工作的影响，每100微秒扫描100个对象。对象的释放将被排队，直到恢复完成一个内存块的空闲列表。

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 Gbps Infiniband NIC，每个NIC 由不同插槽上的线程使用，并通过一台Mellanox SX6512交换机相连，具有全双工带宽。FaRM 配置为使用3-way复制（一个主副本和两个备份），租约时间为10毫秒。

6.2 基准测试

我们使用两个事务基准测试来衡量FaRM 的性能。我们使用C++实现了这两个基准，并针对FaRM API进行了优化。由于FaRM使用非对称模型来利用局部性，每台机器既运行基准代码又存储数据。每台机器将基准代码与FaRM代码在同一进程中链接。在未来，我们将从安全语言（如SQL）编译应用程序，以防止应用程序错误导致数据损坏。

电信应用事务处理（TATP）[32] 是一个用于高性能主内存数据库的基准。每个数据库表都实现为FaRM哈希表[16]。TATP 以读取为主，70%的操作是单行查找，使用FaRM的无锁读取[16]。这些操作通常可以通过一次RDMA读取来完成，不需要提交阶段。10%的操作读取2-4 行数据，并在提交阶段需要验证。其余20%的操作是更新，并需要完整的提交协议。由于70%的更新只修改单个对象字段，我们将这些操作优化为发送给对象的主副本。我们使用的数据库包含 92 亿个用户（除非另有说明）。TATP 是可分区的，但我们没有进行分区，因此大多数操作访问远程机器上的数据。

TPC-C[38] 是一个著名的数据库基准，具有复杂的事务，访问数百行。我们的实现使用具有 16 个索引的模式。这12个索引仅需要无序（点）查询和更新，并实现为FaRM哈希表。四个索引还需要范围查询。这些范围查询使用FaRM B-树实现。B-树在每台机器上缓存内部节点，因此在一般情况下，查找只需一次FaRM RDMA读取。我们为每台机器保留8 GB的缓存。我们使用围栏键[17, 27]确保遍历一致性，类似于Minuet[37]。由于篇幅原因，我们省略了B树的详细描述。我们使用的数据库包含21,600个仓库。我们将大多数哈希表索引以及客户按仓库进行共同分区，这意味着大约10%的所有事务访问远程数据。根据基准的规定， “新订单”事务占事务组合的45%。我们运行完整组合，但报告的性能为成功提交的“新订单” 数量。

6.3 正常情况下的性能

我们将FaRM的正常情况（无故障）性能呈现为吞吐量-延迟曲线。对于每个基准，我们通过首先将每台机器的活动线程数量从2增加到30，然后增加每个线程的并发性，直到吞吐量饱和来改变负载。请注意，每个图表的左侧仍然显示出显著的并发性，因此吞吐量也很高。这并未显示FaRM可以达到的最低延迟。 TATP。图 7显示，FaRM以58微秒的中位延迟和645微秒的99百分位延迟执行每秒1.4亿个TATP事务。在图表的左侧，中位延迟仅为9微秒，99百分位延迟降至112微秒，FaRM 以每秒200万次操作的速度运行。TATP使用的多对象分布式事务在几十微秒内提交，最低吞吐量时平均提交延迟为19微秒，最高时为138微秒。 FaRM的性能超过了Hekaton[14, 26]的已发布结果，后者是一个单机内存事务引擎，超过了 33 倍。Hekaton 的结果是在不同硬件上获得的，但我们预计在我们的测试平台上运行Hekaton 时会提高20倍。在一个小规模实验中，FaRM在仅使用三台机器的情况下也超过了Hekaton。此外，FaRM支持更大的数据集，因为它能够横向扩展，并提供高可用性，与单机系统不同。 TPC-C。我们对TPC-C进行了60秒的测试，并在图8中报告了这一期间的延迟和平均吞吐量。FaRM每秒可执行高达450万次TPC-C的“新订单”事务，中位延迟为808微秒，99百分位延迟为19毫秒。通过小幅度降低10%的吞吐量，延迟可以减少一半。我们所知的最佳已发布的TPC-C性能来自Silo [39, 40]，这是一个单机内存系统，日志记录到FusionIO SSD。 FaRM 的吞吐量比Silo高17倍，且在该吞吐量水平下的延迟比Silo的日志记录版本好128 倍。读取性能。尽管本文的重点是事务性能和故障恢复，但我们也能够改善相对于[16]的只读性能。我们运行了一个仅进行键值查找的工作负载，使用16字节的键和32字节的值，并采用均匀的访问模式。我们实现了每秒790万次查找的吞吐量，中位延迟为23微秒，99百分位延迟为73 微秒。这比以前报告的同一基准在每台机器上的吞吐量提高了20%[16]。尽管将 NIC 的数量增加了一倍，但由于基准测试变成了CPU绑定，我们并未将性能翻倍。

6.4 故障

为了评估故障情况下的性能，我们运行了相同的基准测试，并在实验进行到35秒时终止了其中一台机器的FaRM进程。我们展示了存活的89台机器在1毫秒间隔下聚合的吞吐量时间线。这些时间线在实验开始时使用RDMA消息同步。图9和图10展示了在不同时间尺度上每个基准的典型运行。两者都显示了吞吐量的实线。 “达到完整吞吐量所需的时间”是围绕故障的缩放视图。它显示了故障机器在CM上的租约到期时间（“可疑”）；所有读取探测完成的时间（“探测”）； CM 成功更新 Zookeeper 的时间（“zookeeper”）；所有存活机器上新配置提交的时间（“配置提交”）；所有区域活跃的时间（“全活跃”）；以及开始后台数据恢复的时间（“数据恢复开始”）。 “完成数据恢复所需的时间”展示了一个缩放的视图，包括在备份上恢复所有数据的时间（“完成”）。虚线显示了数据恢复过程中随时间变化的备份区域累计数量。 TATP 图9展示了典型TATP运行的时间线。我们配置其以最大吞吐量运行：每台机器运行 30 个线程，每个线程同时处理8个事务。图9(a)显示，吞吐量在故障发生时急剧下降，但迅速恢复。系统在不到40毫秒的时间内恢复到峰值吞吐量。所有区域在39毫秒时变为活跃。图9(b)显示，数据恢复是有节奏的，不会影响前台吞吐量。故障机器托管了84个2GB区域。每个线程每2毫秒获取8KB的块，这意味着在单台机器上恢复2GB区域大约需要17秒。机器同时以大致相同的速度逐个区域进行恢复，因此恢复的区域数量以较大步伐变化。恢复负载（即在故障机器上有副本的区域数量）在整个集群中得到良好平衡：64 台机器恢复一个区域，10台机器恢复两个区域。这解释了为什么大多数区域的重新复制在大约17秒内完成，以及为什么所有区域在不到35秒内完全重新复制。由于某些区域未完全分配，因此它们的恢复时间较短，这也是一些区域的重新复制在不到17秒内完成的原因。图中还显示，即使没有故障，TATP的吞吐量也会出现一些波动。我们认为这是因为基准中的访问不均匀；当许多事务冲突并在热门键上同时回退时，吞吐量会下降。

TPC-C 图10展示了TPC-C的时间线。图10(a)显示系统在不到50毫秒的时间内恢复了大部分吞吐量，并且所有区域很快变为活跃。由于TPC-C的事务更加复杂，与TATP相比，系统在恢复事务锁上花费的时间稍长。主要的不同在于数据恢复时间较长（见图10(b)），即便在实验中TPC-C只需恢复63个区域。这是因为TPC-C将其哈希表共分区以利用局部性并提高性能，这导致恢复的并行度降低，因为多个区域在相同的一组机器上复制，以满足应用程序指定的局部性约束。在实验中，两台机器各恢复17个区域，导致数据恢复耗时超过4 分钟。请注意，在图10(b)中，TPC-C的吞吐量随着时间逐渐下降，这是由于数据库的大小快速增加所致。

CM失效 图11显示了CM进程失效时TATP吞吐量的变化。恢复速度比非CM进程失效时要慢。系统需要大约110毫秒才能恢复到故障前的相同吞吐量水平。恢复时间增加的主要原因是重新配置时间的增加：从图9(a)中的20毫秒增加到97毫秒。这段时间的大部分被用于新CM构建仅在CM处维护的数据结构。如果所有机器在从CM学习区域映射时增量维护这些数据结构，那么可以消除这段延迟。

恢复时间分布 我们重复了TATP恢复实验（不包括CM故障）40次，以获得恢复时间的分布。这些实验使用较小的数据集（35亿订户）进行，以缩短实验时间，但我们确认恢复吞吐量的时间与较大数据集相同。因为恢复时间主要受事务状态恢复的影响，而并发执行的事务数量对于两种数据集大小都是相同的。图12展示了恢复时间的分布。我们从CM怀疑故障机器的时刻开始测量恢复时间，直到吞吐量恢复到故障前平均吞吐量的80%。中位恢复时间约为50毫秒，超过70%的执行中恢复时间少于100毫秒。在剩余的情况下，恢复时间超过 100 毫秒，但始终少于200毫秒。

关联故障 一些故障会同时影响多台机器，例如电源或交换机故障。为了应对这种协调故障， FaRM 允许为每台机器指定故障域，CM（协调器）将每个区域的副本放置在不同的故障域中。我们将集群中的机器分成5个故障域，每个故障域包含18台机器。这与交换机中每个叶模块的端口数量相对应。为了模拟机架顶部交换机的故障，我们同时使其中一个故障域中的所有进程失效。

图13展示了72台未失效机器的TATP吞吐量随时间的变化。TATP配置为在每台机器上使用大约55个区域（整个集群共有69亿订户），以便在故障后有足够的空间重新复制失效的区域。FaRM在故障发生后不到400毫秒内恢复了峰值吞吐量。我们重复实验20次，这个恢复时间是所有实验的中位数。大部分时间花在恢复事务上。我们需要恢复所有修改了失效机器上区域的正在执行的事务，读取了主副本在失效机器上的区域的事务，或者协调器在失效机器上的事务。与单一故障相比，这导致大约需要恢复13万笔事务，而不是7500笔。数据重新复制耗时4分钟，因为有1025个区域需要重新复制。与之前的实验一样，这不会在恢复过程中影响吞吐量，因为恢复过程是有节奏进行的。需要注意的是，在此期间每个区域仍有两个可用副本，因此不需要更积极地进行重新复制。

数据恢复节奏 FaRM 通过节奏化的数据恢复来减少其对吞吐量的影响。这延长了在新备份上完成区域重新复制的时间。图14展示了非常激进的数据恢复情况下的TATP吞吐量随时间的变化：每个线程同时获取4个32KB的数据块。系统在大多数区域重新复制后800毫秒恢复峰值吞吐量。然而，数据恢复的速度要快得多：恢复83个区域副本（166GB）只需11 秒。我们仅在区域丧失到只剩一个副本时使用这种激进的恢复设置。与RAMCloud 相比，这种激进的恢复速率表现良好，RAMCloud在80台机器上恢复35GB数据需16秒。 TPC-C 对后台恢复流量的干扰不如TATP敏感，因为只有一小部分访问是对远程机器上的对象的。这意味着，在可以进行应用程序特定调优的情况下，我们可以更积极地重新复制数据而不影响性能。图15展示了在恢复过程中TPC-C吞吐量随时间的变化，线程每2毫秒获取 32KB 的数据块。重新复制在65秒内完成，比默认设置快了四倍，而且对吞吐量没有任何影响。

6.5 租约时间

为了评估租约管理器的优化（第5.1节），我们进行了一个实验，所有机器上的线程连续10 分钟重复向CM发出RDMA读取请求。我们禁用了恢复机制，并统计了不同租约管理器实现和不同租约时长下集群中的（假阳性）租约到期事件的数量。该基准测试是对CM的良好压力测试，因为它比我们描述的任何基准都产生了更多的流量。

图16比较了四种租约管理器的实现。第一种使用FaRM的RPC（RPC）。其他三种使用不可靠数据报：共享线程上的（UD）、普通优先级的专用线程上的（UD+线程）、以及高优先级的中断驱动且无固定处理器绑定的（UD+线程+优先级）。

结果显示，所有优化措施都是必要的，以便在不出现假阳性的情况下使用10毫秒或更短的租约时长。在共享队列对的情况下，即便是100毫秒的租约也经常到期。使用不可靠数据报可以减少假阳性事件的数量，但由于CPU争用，它无法完全消除。使用专用线程允许我们使用100毫秒的租约且无假阳性，但由于FaRM机器上运行的后台进程引起的CPU争用， 10 毫秒的租约仍会过期。使用高优先级的中断驱动租约管理器，我们可以在10分钟内使用 5 毫秒的租约且没有假阳性。当租约时间更短时，我们仍然会偶尔遇到假阳性。我们受到网络往返时间（在负载下最长可达1毫秒）和系统定时器分辨率（0.5毫秒）的限制。系统定时器分辨率有限，解释了为什么中断驱动的租约管理器在使用1毫秒租约时假阳性更多，而轮询驱动的租约管理器表现更好。

在所有实验中，我们保守地将租约设置为10毫秒，并且没有观察到任何假阳性事件。

7 相关工作

据我们所知，FaRM 是第一个同时提供高可用性、高吞吐量、低延迟和严格可串行化的系统。在之前的工作[16]中，我们概述了FaRM的早期版本，该版本通过将日志记录到SSD来实现持久性和可用性，但没有描述从故障中的恢复。本文介绍了一种新的快速恢复协议和优化的事务与复制协议，该协议大大减少了消息传递次数，并利用NVRAM避免将日志记录到SSD 中。与[16]中描述的事务协议相比，优化后的协议减少了高达44%的消息传递，并且在验证阶段用一侧 RDMA 读取替代了消息传递。[16]的工作仅评估了在没有故障的情况下，使用 YCSB 基准测试对单键事务的性能进行评估。而本文使用TATP和TPC-C基准测试评估了有无故障的事务性能。

RAMCloud[33, 34]是一个键值存储系统，它在内存中存储单份数据，并通过分布式日志来实现持久性。它不支持多对象事务。在发生故障时，RAMCloud会在多台机器上并行恢复，在此期间（可能需要数秒），故障机器上的数据不可用。FaRM 支持事务，在故障后的几十毫秒内即可使数据可用，且每台机器的吞吐量高一个数量级。 Spanner[11]在第 4 节中已经讨论过。它提供了严格的可串行化，但没有针对RDMA进行性能优化。它使用2f + 1个副本，而FaRM只需要f + 1，并且FaRM在提交时传递的消息更少。

Sinfonia[8]提供了一个带有可串行化事务的共享地址空间，使用两阶段提交实现事务，并在特殊情况下将读取请求嵌入两阶段提交。FaRM则提供了通用的分布式事务，优化后可充分利用RDMA。

HERD[23]是一个基于RDMA的内存键值存储系统，在客户端和服务器位于不同机器的非对称环境中提供高性能。它使用 RDMA 写入和发送/接收操作来进行消息传递，但不使用 RDMA 读取。[23]的作者表明，在非对称环境下，单侧RDMA读取的性能不如不具备可靠性的专门RPC实现。我们的结果使用了可靠通信，并且是在一个对称环境下，每台机器既是客户端又是服务器。这使我们能够利用本地性，因为访问本地DRAM比通过RDMA访问远程DRAM快得多[16]。Pilaf[31]是一个使用RDMA 读取的键值存储系统。Pilaf和HERD 都不支持事务。HERD没有容错能力，而Pilaf通过记录到本地磁盘实现了持久性，但没有实现可用性。

Silo[39, 40]是一个单机内存数据库，通过记录到持久性存储实现持久性。它将已提交的事务批量写入存储，以实现高吞吐量。故障恢复涉及从存储中读取检查点和日志记录。Silo的存储是本地的，因此当机器故障时会失去可用性。相比之下，FaRM是分布式的，并使用NVRAM 中的复制来实现持久性和高可用性。FaRM可以在故障后以比Silo快两个数量级的速度恢复峰值吞吐量，且适用于更大的数据库。通过扩展规模并使用NVRAM中的复制，FaRM也实现了比Silo更高的吞吐量和更低的延迟。

Hekaton[14, 26]也是一个单机内存数据库，不支持扩展或分布式事务。FaRM 在三台机器上的性能与Hekaton相当，而在90台机器上，其吞吐量是Hekaton的33倍。

8 结论

事务让编写分布式系统变得更加容易，但许多系统为了提高可用性和性能，选择避开事务或削弱一致性。FaRM是一个面向现代数据中心的分布式内存计算平台，提供了严格的可串行化事务，同时具有高吞吐量、低延迟和高可用性。实现这一目标的关键是设计新的事务、复制和恢复协议，这些协议从零开始设计，能够充分利用带有RDMA的商用网络，并采用了一种新的、廉价的方式提供非易失性DRAM。实验结果表明，FaRM在吞吐量和延迟方面远远优于现有的内存数据库。FaRM还可以在不到50毫秒的时间内从机器故障中恢复，恢复后即可提供峰值吞吐量，从而使故障对应用透明。致谢我们要感谢Jason Nieh，本文的指导者，以及匿名审稿人对本文的意见。我们还要感谢Richard Black 在性能调试中的帮助，感谢Andy Slowey和Oleg Losinets 保持测试集群的正常运行，感谢Chiranjeeb Buragohain、Sam Chandrashekar、Arlie Davis、Orion Hodson、Flavio Junqueira、 Richie Khanna、James Lingard、Samantha Lüber、Knut Magne Risvik、Tim Tan、Ming Wu、 Ming-Chuan Wu、Fan Yang 和 Lidong Zhou 的无数讨论，并感谢他们允许我们在长时间内使用整个集群进行最终实验。