毫不妥协:具有一致性、可用性和性能的分布式事务
摘要（Abstract）
具有强一致性和高可用性的事务简化了分布式系统的构建和推理。然而，以前的实现表现不佳。这迫使系统设计者完全避免事务，削弱一致性保证，或者提供要求程序员对其数据进行分区的单机事务。在本文中，我们展示了在现代数据中心中没有必要妥协。我们展示了一个名为FaRM的主内存分布式计算平台可以提供具有严格序列化性、高性能、持久性和高可用性的分布式事务。FaRM在拥有4.9 TB数据库的90台机器上实现了每秒1.4亿次TATP事务的峰值吞吐量，并且在不到50毫秒的时间内从故障中恢复。实现这些结果的关键是设计新的事务、复制和恢复协议，从第一原则出发，利用具有RDMA的商用网络和提供非易失性DRAM的新的廉价方法。
1、介绍（Introduction）
具有高可用性和严格序列化性的事务[35]通过提供简单、强大的抽象简化了分布式系统的编程和逻辑:一台永远不会宕机的机器，以与实时一致的顺序执行一个事务。然而，之前在分布式系统中实现这种抽象的尝试导致了较差的性能。因此，Dynamo[13]或Memcached[1]之类的系统通过不支持事务或实现弱一致性保证来提高性能。其他(例如，[3 - 6,9,28])仅在所有数据驻留在单个机器内时才提供事务，这迫使程序员对数据进行分区，并使关于正确性的推理复杂化。
本文证明了现代数据中心的新软件可以消除妥协。它介绍了FaRM [16] (一个主内存分布式计算平台)中的事务、复制和恢复协议。FaRM提供分布式ACID事务，具有严格的序列化性、高可用性、高吞吐量和低延迟。这些协议的设计初衷是利用数据中心中出现的两种硬件趋势:使用RDMA的快速商用网络和提供非易失性DRAM的廉价方法。非易失性是通过将电池连接到电源单元，并在电源故障时将DRAM的内容写入SSD来实现的。这些趋势消除了存储和网络瓶颈，但也暴露了CPU瓶颈，限制了它们的性能优势。FaRM协议遵循三个原则来解决这些CPU瓶颈:减少消息计数，使用单侧RDMA读写而不是消息，以及有效地利用并行性。
FaRM通过在数据中心的机器上分布对象进行扩展，同时允许事务跨越任意数量的机器。FaRM不是使用Paxos复制协调器和数据分区(例如[11])，而是通过使用带主备份复制的垂直(vertical)Paxos[25] 和直接与primaries和replicas通信的非复制协调器来减少消息计数。FaRM使用乐观并发控制和四阶段提交协议(锁(lock)、验证(validation)、提交备份(commit back-up)，和提交主机(commit primary))[16]，但我们通过去除了锁定阶段的发送到backups的消息进而改进了原始协议。
FaRM通过使用单侧RDMA操作进一步降低了CPU开销。单侧RDMA不使用远程CPU，避免了大部分本地CPU开销。FaRM事务在事务执行和验证期间使用单侧RDMA读取。因此，它们在远程只读参与者上不使用CPU。此外，协调器在将log记录到事务中修改的replicas中的对象的非易失性预写日志时使用单侧RDMA。例如，协调器使用单个单侧RDMA将提交记录写入远程备份。因此，事务在备份时不使用前台CPU。稍后在后台延迟截断日志以就地更新对象时使用CPU。
使用单侧RDMA需要新的故障恢复协议。例如，FaRM不能依赖服务器在它们的租约[18]到期时拒绝传入的请求，因为请求是由网卡服务的，而网卡不支持租约。我们通过使用精确的precise membership[10]来解决这个问题，以确保机器同意当前的配置成员资格，并仅向作为成员的机器发送单边操作。FaRM也不能依赖传统机制来确保参与者在准备阶段拥有提交事务所需的资源，因为事务记录被写入参与者日志不涉及远程CPU。作为替代的，FaRM使用reservation来确保日志中有空间用于提交所需的所有记录，并在开始提交之前截断事务。
FaRM中的故障恢复协议速度很快，因为它有效地利用了并行性。它在整个集群中均匀地分配每个状态位的恢复，并在每台机器的核心之间并行地进行恢复。此外，它还使用了两种优化来允许事务执行与恢复并行进行。首先，事务在锁恢复阶段(只需几十毫秒即可完成)之后开始访问受故障影响的数据，而不是等待几秒钟进行其余的恢复。其次，不受故障影响的事务继续执行而不阻塞。FaRM还通过利用快速网络交换频繁的心跳来提供快速故障检测，并使用优先级和预分配来避免误报。
我们的实验结果表明，您可以同时拥有这一切:一致性、高可用性和性能。FaRM可以在不到50毫秒的时间内从单台机器故障中恢复，并且它的性能优于仅使用几台机器的最先进的单台内存事务系统。例如，仅在三台机器上运行时，它比Hekaton[14,26]实现了更好的吞吐量，并且比Silo[39,40]具有更好的吞吐量和延迟。
2、硬件的发展趋势（Hardware trends）
FaRM的设计灵感来自于数据中心机器中大量廉价的DRAM。典型的数据中心配置每台2插槽机器[29]有128-512 GB的DRAM，而DRAM的成本低于12美元/GB1。这意味着一个pb的DRAM只需要2000台机器，这足以容纳许多需要的应用程序的数据集。此外，FaRM利用两种硬件趋势来消除存储和网络瓶颈:非易失性DRAM和具有RDMA的快速商用网络。
2.1、非易失性DRAM（Non-volatile DRAM）
“分布式不间断电源(UPS)”利用锂离子电池的广泛可用性来降低数据中心UPS的成本，而不是使用铅酸电池的传统集中式方法。例如，微软的开放云服务器(OCS)规范包括本地能量存储(LES)[30,36]，它将锂电池与电源单元集成在机架内的每个24机机箱中。估计LES UPS的成本低于每焦耳0.005美元。这种方法比传统的UPS更可靠:锂离子电池有多个独立的电池单元，任何电池故障只影响机架的一部分。
分布式UPS有效地提高了DRAM的耐用性。当电源发生故障时，分布式UPS利用电池提供的能量将内存中的内容保存到商用SSD上。这不仅通过避免对SSD进行同步写操作来提高一般情况下的性能，而且还通过仅在发生故障时才对SSD进行写操作来保持SSD的生命周期。另一种方法是使用非易失性dimm (nvdimm)，它包含自己的专用闪存、控制器和超级电容器(例如[2])。不幸的是，这些设备是专门的，昂贵的，笨重的。相反，分布式UPS使用商品内存，并利用商品ssd。唯一的额外成本是SSD的预留容量和UPS电池本身。
电池配置成本取决于将内存保存到ssd所需的能量。我们在标准的2插座机器上测量了一个未优化的原型。在出现故障时，它关闭HDDs和NIC，并将内存中的数据保存到单个M.2 (PCIe) SSD，每保存1GB数据消耗110焦耳。大约90焦耳用于在保存期间为机器上的两个CPU插座供电。额外的ssd减少了保存数据的时间，从而减少了能耗(图1)。优化，如将cpu置于低功耗状态，将进一步降低能耗。
在最坏情况下，(单个SSD，未优化)每焦耳0.005美元，非易失性的能源成本为0.55美元/GB，保留SSD容量的存储成本为0.90美元/GB3。合并后的额外成本不到基本DRAM成本的15%，与成本为DRAM 3 - 5倍的nvdimm相比，这是一个显著的改进。因此，将所有机器内存视为非易失性RAM (NVRAM)是可行且实惠的。FaRM将所有数据存储在内存中，并且在多个副本上将数据写入NVRAM时认为它是持久的。
2.2、RDMA网络（RDMA networking）
FaRM在可能的情况下使用单侧RDMA操作，因为它们不使用远程CPU。我们的这个决定是基于我们之前的工作和额外的测量。在[16]中，我们展示了在20台机器的RoCE[22]集群上，当所有机器从集群中的其他机器随机选择小对象时，RDMA读取的性能比基于RDMA的可靠RPC高2倍。瓶颈是NIC消息速率，我们的RPC实现需要的消息数量是单侧读取的两倍。我们在一个90台机器的集群上复制了这个实验，其中每台机器有两个Infiniband FDR (56 Gbps)网卡。与[16]相比，这使每台机器的消息速率增加了一倍以上，并消除了NIC消息速率瓶颈。RDMA和RPC现在都受CPU限制，性能差距增加到4倍，如图2所示。这说明了减少CPU开销以实现新硬件潜力的重要性。
3、编程模型和体系结构（Programming model and architecture）
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∈si是配置管理器。FaRM使用Zookeeper[21]协调服务来确保机器同意当前配置并存储它，就像Vertical Paxos[25]一样。但它不像通常那样依赖Zookeeper来管理租约、检测故障或协调恢复。CM使用一种利用RDMA快速恢复的高效实现来完成这些工作。每次配置更改时，CM都会调用Zookeeper一次，以更新配置。
FaRM中的全局地址空间由2 GB区域组成，每个区域在一个主机和6个备份上复制，这是所需的容错性。每台机器在非易失性DRAM中存储几个区域，这些区域可以由使用RDMA的其他机器读取。对象总是从包含区域的主副本中读取，如果区域在本地机器上，则使用本地内存访问，如果是远程的，则使用单侧RDMA读取。每个对象都有一个64位版本，用于并发控制和复制。区域标识符到主区域和备份的映射由CM维护，并随区域复制。这些映射由其他机器根据需要获取，并由线程与向主服务器发出单侧RDMA读取所需的RDMA引用一起缓存。
机器与CM交互以分配新区域。CM从单调递增的计数器中分配一个区域标识符，并为该区域选择副本。副本选择平衡存储在每台机器上的区域数量，以满足以下约束:有足够的容量，每个副本位于不同的故障域中，当应用程序指定局域性约束时，该区域被放置在目标区域。然后，它向带有区域标识符的选定副本发送一条准备消息。如果所有副本报告分配区域成功，CM将向所有副本发送提交消息。这个两阶段协议确保映射是有效的，并在使用之前在所有区域副本上进行复制。
与之前基于一致哈希[16]的方法相比，这种集中式方法在满足故障独立性和局域性约束方面提供了更大的灵活性。它还可以更容易地在机器之间平衡负载并接近容量运行。对于2 GB的区域，我们预计一台典型机器上最多有250个区域，因此单个CM可以处理数千台机器的区域分配。
每台机器还存储实现FIFO队列[16]的环缓冲区。它们可用作事务日志或消息队列。每个发送方-接收方都有自己的日志和消息队列，它们物理上位于接收方上。发送方使用单侧RDMA写入其尾部将记录追加到日志中。这些写操作由NIC确认，而不涉及接收器的CPU。接收器定期轮询日志的头部以处理记录。它在截断日志时惰性地更新发送方，从而允许发送方重用环缓冲区中的空间。
4、分布式事务和复制（Distributed transactions and replication）
FaRM集成了事务和复制协议，以提高性能。它比传统协议使用更少的消息，并利用单侧RDMA读写来提高CPU效率和低延迟。FaRM在非易失性DRAM中对数据和事务日志使用主备份复制，并使用非复制事务协调器直接与主机和备份通信。它使用带有读验证的乐观并发控制，就像在一些软件事务性内存系统(例如tl2[15])中一样。
图4显示了FaRM事务的时间轴，表1和表2列出了事务协议中使用的所有日志记录和消息类型。在执行阶段，事务使用单侧RDMA读取对象，并在本地缓冲写操作。协调器还记录访问的所有对象的地址和版本。对于与协调器在同一台机器上的主服务器和备份，对象读取和写入日志使用本地内存访问而不是RDMA。在执行结束时，FaRM尝试通过执行以下步骤提交事务:
1、锁（Lock）
协调器向每台机器的日志中写入一条LOCK记录，该记录是任何写入对象的主记录。它包含该主节点上所有写入对象的版本和新值，以及包含写入对象的所有区域的列表。主节点通过尝试使用compare-and-swap将对象锁定在指定的版本来处理这些记录，并返回一条消息，报告是否已成功获取所有锁。如果对象的版本在被事务读取后发生了变化，或者对象当前被另一个事务锁定，则锁定可能会失败。在这种情况下，协调器终止事务。它向所有主程序写入一个中止记录，并向应用程序返回一个错误。
2、验证（Validate）
协调器通过从它们的主节点读取所有已读取但还未被事务写入的对象的版本来执行读验证。如果任何对象发生了更改，则验证失败并终止事务。默认情况下，验证使用单侧RDMA读取。对于拥有超过$t_{r}$个对象的primary，验证是通过RPC完成的。阈值$t_{r}$(目前为4)反映了RPC相对于RDMA读取的CPU开销。
3、提交备份（Commit backups）
协调器在每次备份时将COMMIT-BACKUP记录写入非易失性日志，然后等待来自NIC硬件的回复，而不会中断备份的CPU。COMMIT-BACKUP日志记录与LOCK记录具有相同的负载。
4、提交主机（Commit primaries）
在所有COMMIT-BACKUP写操作都被打包之后，协调器将一条COMMIT-PRIMARY记录写入每个主服务器的日志。如果至少接收到一个这样的记录的硬件应答，或者它在本地写了一个，它就会向应用程序报告完成情况。primary通过更新对象、增加其版本和解锁来处理这些记录，这暴露了事务提交的写操作。
5、截断（Truncate）
主机和备份将记录保存在其日志中，直到它们被截断。协调器在主节点截断日志，并在接收到来自所有主节点的回复后进行惰性备份。它通过在其他日志记录中附带截断事务的标识符来实现这一点。备份在截断时将更新应用于它们的对象副本。
正确性（Correctness）
提交的读写事务在获得所有写锁时是可序列化的，而提交的只读事务在最后一次读取时是可序列化的。这是因为在序列化点读取和写入的所有对象的版本与在执行期间看到的版本相同。锁定确保写入的对象是这样，验证确保只读取的对象是这样。在没有故障的情况下，这相当于在序列化点自动执行和提交整个事务。FaRM中的可序列化性也是严格的:序列化点总是在开始执行和向应用程序报告完成之间。
为了确保跨故障的可序列化性，有必要在写入commit - primary之前等待来自所有备份的硬件ack。假设协调器没有收到来自某个区域r的备份b的回复。那么主服务器可能会公开事务修改，然后在没有接收到COMMIT-BACKUP记录的情况下，与协调器和其他副本一起失败。这将导致丢失对r的更新。
由于读集仅存储在协调器中，因此如果协调器失败并且没有提交记录存活以证明验证成功，则事务将被中止。因此，协调器有必要在向应用程序报告提交成功之前，等待其中一个主节点上的提交成功。这确保至少有一个提交记录在报告提交给应用程序的事务失败时仍然存在。否则，如果协调器和所有备份在写入任何COMMIT-PRIMARY记录之前都失败了，这样的事务仍然可能中止，因为只有LOCK记录会保存下来，并且不会有验证成功的记录。
在传统的两阶段提交协议中，参与者可以在处理准备消息时保留资源以提交事务，或者在没有足够的资源时拒绝准备事务。然而，由于我们的协议避免在提交期间涉及备份的cpu，协调器必须为所有参与者保留日志空间以保证进度。协调器在启动提交协议之前为所有提交协议记录保留空间，包括主日志和备份日志中的截断记录。日志保留是协调器上的本地操作，因为协调器将记录写入它在每个参与者上拥有的日志。当相应的记录被写入时，保留将被释放。如果截断被附加在另一条消息上，也会释放截断记录保留。如果日志已满，协调器将使用保留来写入显式截断记录，以释放日志中的空间。这种情况很少见，但却是确保存活的必要条件。
性能（Performance）
对于我们的目标硬件，该协议比传统的分布式提交协议有几个优点。考虑一个带复制的两阶段提交协议，比如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提交阶段使用$P_{w}(f+3)$个单侧RDMA写操作和$P_{r}$个单侧RDMA读操作，其中$P_{w}$是事务写入对象的主机器数量，$P_{r}$是从远程主服务器读取但未写入的对象数量。读验证为关键路径增加了两个单侧RDMA延迟，但这是一个很好的权衡:在没有负载的情况下，增加的延迟只有几微秒，CPU开销的减少会带来更高的吞吐量和更低的负载下延迟。
5、故障恢复（Failure recovery）
FaRM通过复制提供持久性和高可用性。我们假设机器可能因崩溃而失败，但可以在不丢失非易失性DRAM内容的情况下恢复。我们依靠有限的时钟漂移来保证安全性，最终依靠有限的消息延迟来保证活跃性。
即使整个集群发生故障或断电，我们也为所有提交的事务提供持久性:所有提交的状态都可以从存储在非易失性DRAM中的区域和日志中恢复。即使每个对象最多有f个副本丢失了非易失性DRAM的内容，我们也能确保持久性。FaRM还可以维护故障和网络分区的可用性，前提是存在一个分区，该分区包含大多数保持相互连接的机器和Zookeeper服务中的大多数副本，并且该分区至少包含每个对象的一个副本。
FaRM中的故障恢复有以下五个阶段:故障检测、重新配置、事务状态恢复、批量数据恢复和分配器状态恢复。
5.1、故障检测（Failure detection）
FaRM使用租约[18]来检测故障。每台机器(CM除外)在CM上持有一个租约，CM在其他每台机器上持有一个租约。任何租约到期都会触发失败恢复。租约是通过三次握手授予的。每台机器向CM发送一个租约请求，并使用一条消息进行响应，该消息既是对机器的租约授予，又是来自CM的租约请求。然后，机器向CM返回一个租约授权。
FaRM租约非常短，这是高可用性的关键。在高负载下，FaRM可以为一个90台机器的集群使用5毫秒的租约，没有误报。更大的集群可能需要两级层次结构，在最坏的情况下，这将使故障检测时间加倍。
在负荷下实现短期租赁需要仔细执行。FaRM为租约使用专用pair队列，以避免租约消息在其他消息类型后面的共享队列中延迟。使用可靠的传输需要在CM上为每台机器增加一个队列pair。由于NIC的队列对缓存[16]中的容量丢失，这将导致性能不佳。相反，租约管理器使用Infiniband发送和接收谓词以及无连接的不可靠数据报传输，这在NIC上只需要一个额外队列对的空间。默认情况下，每隔1/5的租约到期尝试一次租约更新，以考虑潜在的消息丢失。
租期续订还必须在CPU上及时安排。FaRM使用一个专用的租约管理器线程，该线程以最高的用户空间优先级运行(在Windows上为31)。租约管理器线程没有绑定任何硬件线程，它使用中断而不是轮询，以避免使每个必须在硬件线程上定期运行的关键操作系统任务饿死。这会使消息延迟增加几微秒，这对于租约来说不是问题。
“starving”指的是关键的操作系统任务没有足够的CPU时间来正常运行，因为另一个进程或线程正在使用过多的CPU时间。
此外，我们没有将FaRM线程分配给每台机器上的两个硬件线程，而是将它们留给租约管理器。我们的测量表明，租约管理器通常在这些硬件线程上运行，而不会影响其他FaRM线程，但有时它会被更高优先级的任务抢占，导致它在其他硬件线程上运行。因此，在使用短租约时，将租约管理器绑定到硬件线程可能会导致误报。
最后，我们预先分配租约管理器在初始化期间使用的所有内存，并将它使用的所有代码分页并固定，以避免由于内存管理而导致的延迟。
5.2、重新配置（Reconfiguration）
重新配置协议将FaRM实例从一个配置更改为另一个配置。使用单侧RDMA操作对于实现良好的性能很重要，但它对重新配置协议提出了新的要求。例如，实现一致性的一种常用技术是使用租约[18]:服务器在响应访问对象的请求之前检查它们是否持有该对象的租约。如果服务器从配置中被申删去，系统保证它存储的对象在其租约到期(例如[7])之前不会被更改。FaRM在服务来自使用消息与系统通信的外部客户机的请求时使用此技术。但是，由于FaRM配置中的机器使用RDMA读取来读取对象，而不涉及远程CPU，因此服务器的CPU无法检查它是否持有租约。当前的NIC硬件不支持租约，而且不清楚将来是否会支持。
我们通过实现精确的precise membership[10]来解决这个问题。发生故障后，在允许对象变化之前，新配置中的所有机器必须就其成员关系达成一致。这允许FaRM在客户端而不是在服务器上执行检查。在配置中的机器不会向不在配置中的机器发出RDMA请求，并且不再在配置中的机器对RDMA读的应答和对RDMA写的应答将被忽略。
图5显示了一个由以下步骤组成的重新配置时间轴示例:
1、怀疑（Suspect）
当一台机器的租约在CM上到期时，它会怀疑该机器出现故障并启动重新配置。此时，它开始阻止所有外部客户机请求。如果非CM机器怀疑CM由于租约到期而出现故障，它首先要求少数“备份CM”中的一个启动重新配置(使用一致散列的CM的k个后继者)。如果配置在一段超时时间后没有改变，那么它会尝试自己重新配置。这种设计避免了在CM失败时同时进行大量的重新配置尝试。在所有情况下，启动重新配置的机器将尝试成为新的CM，作为重新配置的一部分。
2、调查（Probe）
新的CM向配置中的所有机器发出RDMA读取，但可疑的机器除外。任何读取失败的机器也会被怀疑。这些读调查允许处理影响多台机器的相关故障，例如，电源和开关故障，通过一次重新配置。新的CM只有在获得大多数探测的响应时才会进行重新配置。这确保了如果网络是分区的，CM不会在较小的分区中。
3、更新配置（Update configuration）
在收到对调查的响应后，新的CM尝试将存储在Zookeeper中的配置数据更新为< c + 1, S, F, CMid >，其中c是当前配置标识符，S是响应调查的机器集合，F是机器到故障域的映射，CMid是它自己的标识符。我们使用Zookeeper znode序列号来实现原子比较和交换，只有当当前配置仍然为c时才会成功。这确保了即使多台机器同时尝试从标识符为c的配置更改配置，也只有一台机器可以成功地将系统移动到标识符为+1的配置(并成为CM)。
4、重新映射区域（Remap regions）
然后，新的CM重新分配以前映射到故障机器的区域，以将副本的数量恢复到f + 1。它在容量和故障独立性约束下尝试平衡负载并满足应用程序指定的局部性提示。对于失败的主服务器，它总是将幸存的备份提升为新的主服务器，以减少恢复时间。如果它检测到区域丢失了所有副本，或者没有空间来重新复制区域，则会发出错误信号。
5、发送新的配置（Send new configuration）
在重新映射区域之后，CM向配置中的所有机器发送一条new - config消息，其中包含配置标识符、CM自己的标识符、配置中其他机器的标识符以及区域到机器的所有新映射。如果CM发生更改，new - config还会重置租约协议:它展示了从新CM到每台机器的租约请求。如果CM未更改，则在重新配置期间继续进行租约交换，以快速检测其他故障。
6、应用新配置（Apply new configuration）
当一台机器接收到配置标识符大于其自身的一个NEW-CONFIG时，它会更新其当前配置标识符和区域映射的缓存副本，并分配空间来容纳分配给它的任何新区域副本。从这一点开始，它不再向不在配置中的机器发出新的请求，并且拒绝来自这些机器的读响应和写应答。它还开始阻止来自外部客户端的请求。机器用NEW-CONFIG-ACK消息回复CM。如果CM发生了更改，这将向CM授予租约并请求租约。
7、提交新的配置（Commit new configuration）
一旦CM从配置中的所有机器接收到new - config - ack消息，它将等待以确保以前配置中授予不再在配置中的机器的任何租约都已过期。然后，CM将NEW-CONFIG-COMMIT发送给所有配置成员，这些配置成员也充进行租约授予。所有成员现在解除先前阻止的外部客户端请求并启动事务恢复。
5.3、事务状态恢复（Transaction state recovery）
FaRM使用分布在被事务修改的对象副本上的日志恢复配置更改后的事务状态。这包括恢复被事务修改的对象副本的状态和协调器的状态，以决定事务的结果。图6显示了一个示例事务恢复时间轴。FaRM通过在集群中的线程和机器之间分配工作来实现快速恢复。Draining(步骤2)是对所有消息日志并行执行的。步骤1和步骤3-5对所有区域并行执行。步骤6-7是对所有并行恢复事务执行的。
1、禁止访问恢复区域（Block access to recovering regions）
当一个区域的主要备份发生故障时，其中一个备份将在重新配置期间提升为新的主要备份。在更新该区域的所有事务都反映在新的主服务器上之前，我们不能允许访问该区域。我们通过阻塞对本地指针和对区域的RDMA引用的请求来实现这一点，直到步骤4为更新该区域的所有恢复事务获得了所有写锁。
2、写入日志（Drain logs）
单侧RDMA写入也会影响事务恢复。跨配置保持一致性的一般方法是拒绝来自旧配置的消息。FaRM不能使用这种方法，因为NICs接收写入事务日志的commit - backup和COMMIT-PRIMARY记录，而不管它们是在哪个配置中发出的。由于协调器在向应用程序公开更新并报告成功之前只等待这些应答，因此机器在处理以前配置的记录时不能总是拒绝它们。我们通过提取日志来解决这个问题，以确保在恢复期间处理所有相关记录:所有机器在接收到NEW-CONFIG-COMMIT消息时都会处理其日志中的所有记录。当它们完成时，它们在一个变量LastDrained中记录配置标识符。
FaRM事务具有在提交开始时分配的唯一标识符< c, m, t, l >，这些标识符编码了启动提交时的配置、协调器的机器标识符m、协调器的线程标识符t和线程本地唯一标识符l。配置标识符小于或等于LastDrained的事务的日志记录将被拒绝。
3、查找恢复事务（Find recovering transactions）
恢复事务是指其提交阶段跨越配置更改，并且由于重新配置而导致写入对象的某些副本、读对象的某些主对象或协调器发生更改的事务。在写入日志期间，将检查每个日志中的每个日志记录中的事务标识符和更新的区域标识符列表，以确定恢复事务的集合。只有恢复事务才会在主节点和备份节点上进行事务恢复，协调器只会在恢复事务时拒绝硬件应答。
所有机器必须就给定事务是否为恢复事务达成一致。我们通过在重新配置阶段在通信上附加一些额外的元数据来实现这一点。CM在每台机器上读取LastDrained变量，作为调查读取的一部分。对于自LastDrained以来其映射已更改的每个区域r，CM将在NEW-CONFIG消息中向该机器发送两个配置标识符。当r的主节点发生变化时的最后一个配置标识符是LastPrimaryChange[r]，当r的任何副本发生变化时的最后一个配置标识符是LastReplicaChange[r]。在配置c−1中开始提交的事务在配置c中恢复，除非:对于所有包含被事务更改过对象的区域r有LastReplicaChange[r]<c成立，对于所有包含被事务读取过对象的区域r ‘有LastPrimaryChange[r ‘] < c成立，且协调器尚未从配置c中移除。
恢复事务的记录可能分布在由事务更新的不同主备份的日志中。区域的每个备份都向主服务器发送一条NEED-RECOVERY消息，其中包含配置标识符、区域标识符和更新该区域的恢复事务标识符。
4、锁的恢复（Lock recovery）
每个区域的主服务器将一直等待，直到耗尽本地计算机日志并从每个备份接收到NEED-RECOVERY消息，以构建影响该区域的恢复事务的完整集合。然后，它根据标识符在其线程之间对事务进行分片，以便每个线程t恢复具有协调线程标识符t的事务状态。与此同时，主线程中的线程从尚未存储在本地的备份中获取任何事务日志记录，然后锁定通过恢复事务修改的任何对象。
当一个区域的锁恢复完成时，该区域处于活动状态，本地和远程协调器可以获得本地指针和RDMA引用，这允许它们在随后的恢复步骤中读取对象并向该区域提交更新。
5、 复制日志记录（Replicate log records）
主服务器中的线程通过向备份发送REPLICATE-TX-STATE消息来复制日志记录它们丢失的任何事务。该消息包含区域标识符、当前配置标识符以及与LOCK记录相同的数据。
6、投票（Vote）
恢复事务的协调器根据事务更新的每个区域的投票来决定是提交还是中止事务。这些选票由每个地区的主机产生。FaRM使用一致哈希来确定事务的协调器，确保所有主节点独立地就恢复事务的协调器身份达成一致。如果协调器运行的机器仍在配置中，则它不会更改，但是当协调器失败时，协调其恢复事务的责任将分散到集群中的机器上。
对于修改区域的每个恢复事务，主线程向协调器中的对等线程发送RECOVERY-VOTE消息。如果任何replica看到COMMIT-PRIMARY或COMMIT-RECOVERY，则投票为COMMIT-PRIMARY。否则，如果任何副本看到commit-backup而没有看到ABORT-RECOVERY，它就会投票选择commit-backup。否则，如果任何副本看到了一个lock记录，并且没有ABORT-RECOVERY记录，那么它将投票锁定。否则，它将投反对票。投票消息包括配置标识符、区域标识符、事务标识符和由事务修改的区域标识符列表。
有些主服务器可能不会发起对事务的投票，因为它们从未收到该事务的日志记录，或者它们已经截断了该事务的日志记录。协调器向在超时时间(设置为250 μs)内尚未投票的primary发送显式投票请求。REQUEST-VOTE消息包括配置标识符、区域标识符和事务标识符。在等待该事务的日志复制完成后，确实像以前一样拥有事务投票的日志记录的主节点。
如果事务已被截断，则没有任何事务投票日志记录的primary将被截断，如果未被截断则未知。为了确定事务是否已经被截断，每个线程维护其日志中记录已被截断的事务的标识符集。该集合通过使用非截断事务标识符的下界来保持紧凑。下限是根据每个协调器的下限更新的，这些协调器是在协调器消息和重新配置期间承载的。
7、决策（Decide）
如果协调器收到来自任何地区的commit-primary投票，则决定提交事务。否则，它等待所有区域投票并提交，如果至少有一个区域投票了commit-backup，并且被事务修改的所有其他区域都投票了lock、commitbackup或truncated。否则，它决定中止。然后，它向所有参与副本发送COMMIT-RECOVERY或ABORT-RECOVERY。两个消息都包含配置标识符和事务标识符。如果在主服务器上接收到commit - recovery，则与在备份服务器上接收到COMMIT-BACKUP类似。ABORT- recovery的处理类似于ABORT。协调器从所有主服务器和备份服务器接收回消息后，将发送一条TRUNCATE-RECOVERY消息。
正确性（Correctness）
接下来，我们将直观地介绍事务恢复的不同步骤如何确保严格的序列化性。关键思想是恢复保留了先前提交或终止的事务的结果。我们认为当主服务器公开事务修改，或者协调器通知应用程序事务已提交时，事务就提交了。当协调器发送终止消息或通知应用程序事务已终止时，事务将被终止。对于结果尚未确定的事务，恢复可以提交或中止事务，但它确保从其他失败中恢复的任何恢复都保留结果。
未恢复的事务(步骤3)的结果是使用正常情况协议(第4节)确定的。因此，我们将不再进一步讨论它们。
提交的恢复事务的日志记录保证在日志抽取之前或期间被处理和接受(步骤2)。这是正确的，因为primary仅在处理COMMIT-PRIMARY记录之后才公开修改。如果协调器通知了应用程序，那么在接收NEW-CONFIG之前，它必须已经接收到所有COMMIT-BACKUP记录和至少一个COMMIT-PRIMARY记录的硬件ack(因为它在更改配置后忽略了ack)。因此，由于新配置为每个区域至少包含一个副本，因此至少有一个区域至少有一个副本将处理COMMIT-PRIMARY或COMMIT-BACKUP记录，并且每个区域至少有一个副本将处理COMMIT-PRIMARY、COMMIT-BACKUP或LOCK记录。
步骤3和4确保被事务修改的区域的主服务器看到这些记录(除非它们已被截断)。他们将这些记录复制到备份中(步骤5)，以保证即使出现后续失败，投票也会产生相同的结果。然后，主机根据他们看到的记录将选票发送给协调器(步骤6)。
决策步骤保证协调器决定提交先前已提交的任何事务。如果任何副本截断了事务记录，则所有主将投票commit-primary、commit-backup或truncated。至少有一个主节点将发送投票，而不是被截断的投票，否则事务将无法恢复。如果没有副本截断事务记录，则至少有一个主节点将投票给commit-primary或commit-backup，其他节点将投票给commit-primary、commit-backup或lock。类似地，如果事务先前被中止，协调器将决定中止，因为在这种情况下，要么没有提交主记录，要么没有提交备份记录，要么所有副本都收到了abort - recovery。
阻塞对恢复区域的访问(步骤1)和锁定恢复(步骤4)保证在恢复事务提交或终止之前，没有其他操作可以访问它修改的对象。
性能
FaRM使用了几个优化来实现快速故障恢复。识别恢复事务将恢复工作限制为仅受重新配置影响的事务和区域，当大型集群中的单个机器发生故障时，这些事务和区域可能只是总数的一小部分。我们的结果表明，这可以将恢复的事务数量减少一个数量级。恢复工作本身是跨区域、机器和线程并行进行的。锁恢复后立即使区域可用可以提高前台性能，因为访问这些区域的新事务不会长时间阻塞。具体来说，它们不需要等待这些区域的新副本更新，这需要通过网络大量移动数据。
5.4、恢复数据（Recovering data）
FaRM必须在一个区域的新备份中恢复(重新复制)数据，以确保它能够容忍将来的复制失败。数据恢复对于恢复正常的case操作不是必需的，因此我们将其延迟到所有区域变为活动状态，以尽量减少对延迟关键锁恢复的影响。当以每台机器为主的所有区域都处于活动状态时，每台机器都会向CM发送一条regions - active消息。在接收到所有的REGIONS-ACTIVE消息后，CM向配置中的所有机器发送一条all -REGIONS-ACTIVE消息。此时，FaRM将与前台操作并行地开始新备份的数据恢复。
一个区域的新备份最初有一个新分配的、归零的本地区域副本。它将该区域划分为多个并行恢复该区域的工作线程。每个线程发出单侧RDMA操作，每次从主线程读取一个块。我们目前使用8 KB的区块，这足够大，可以有效地使用网络，但又足够小，不会影响正常的案例操作。为了减少对前台性能的影响，通过将下一个读取调度为在前一个读取开始后的一段时间内的随机点开始(设置为4ms)来调整恢复的节奏。
在将每个恢复对象复制到备份之前，必须对其进行检查。如果对象的版本大于本地版本，则备份将使用compare-adn-swap锁定本地版本，更新对象状态并解锁它。否则，对象已经或正在被创建的版本大于或等于恢复的版本的事务更新，并且不应用恢复的状态。
5.5、分配器状态恢复（Recovering allocator state）
FaRM分配器将区域划分为块(1mb)，这些块称为slabs被用于分配小对象。它保留了两部分元数据:包含对象大小的块头和无块列表。分配新块时，将块标头复制到备份中。这确保了它们在发生故障后可以在新的主服务器上使用。由于块标头用于数据恢复，新主服务器在收到new - config - commit后立即将它们发送给所有备份服务器。这避免了在复制块标头时旧主服务器失败时出现的任何不一致。
slab空闲列表只保留在主节点，以减少对象分配的开销。每个对象在其头中都有一个位，由分配设置，并在事务执行期间由free清除。在事务提交期间复制对对象状态的更改，如第4节所述。发生故障后，通过扫描该区域中的对象，在新的主服务器上恢复空闲列表，该区域在机器上的所有线程之间并行化。为了尽量减少对事务锁恢复的影响，分配恢复在接收到ALL-REGIONS-ACTIVE后开始，并且为了尽量减少对前台工作的影响，每100 μs扫描100个对象。对象释放被排队，直到slab的空闲列表被恢复。
6、测评（Evaluation）
6.1、设置（Setup）
我们的实验测试平台包括用于FaRM集群的90台机器和用于复制Zookeeper实例的5台机器。每台机器都有256gb的DRAM和两个运行Windows Server 2012 R2的8核英特尔E5-2650 cpu。我们启用了超线程，并将前30个线程用于前台工作，其余2个线程用于租约管理器。机器有两个Mellanox ConnectX-3 56 Gbps Infiniband网卡，每个网卡由不同套接字上的线程使用，并通过单个Mellanox SX6512交换机连接，具有全对分带宽。FaRM被配置为使用3路复制(一个主复制和两个备份复制)，租用时间为10毫秒。
6.2、基准（Benchmarks）
我们使用两个事务性基准来度量FaRM的性能。我们在c++中针对FaRM API实现了这两个基准测试。由于FaRM使用对称模型来利用局部性，因此每台机器都运行基准代码并存储数据。每台机器在同一进程上运行与FaRM代码链接的基准代码。将来，我们将使用安全语言(如SQL)编译应用程序，以防止应用程序错误损坏数据。
远程通信应用事务处理[32]是高性能主存数据库的基准。每个数据库表都被实现为一个FaRM哈希表[16]。TATP是读主导的。70%的操作是单行查找，使用FaRM的无锁读取[16]。它们通常可以通过单个RDMA读取来执行，并且不需要提交阶段。10%的操作读取2-4行，并且需要在提交阶段进行验证。其余20%的操作是更新，需要完整的提交协议。由于70%的更新只修改单个对象字段，因此我们将这些字段作为优化发送到对象的主节点。我们使用了一个拥有92亿订阅者的数据库(除非另有说明)。TATP是可分区的，但是我们没有对它进行分区，因此大多数操作访问远程机器上的数据。
TPC-C[38]是一个著名的数据库基准，具有访问数百行的复杂事务。我们的实现使用具有16个索引的模式。其中12个只需要无序(点)查询和更新，并作为FaRM散列表实现。其中四个索引还需要范围查询。这些都是使用FaRM b树实现的。B-Tree在每台机器上缓存内部节点，因此查找通常需要一次FaRM RDMA读取。我们为每台机器保留8 GB的缓存。我们使用栅栏键(fence key)[17,27]来确保遍历一致性，类似于Minuet[37]。由于篇幅原因，我们省略了对b树的更详细的描述。
“fence key” 是一种用于实现分布式锁的机制。它是一个由多个节点共享的值，用于协调不同节点之间的访问。当一个节点想要获取某个资源的锁时，它会向其他节点发送一个请求，并提供一个 “fence key” 值。如果其他节点上的 “fence key” 值比当前请求中提供的值小，则说明当前请求已经过时，因为有其他请求已经成功获取了该资源的锁。这样可以避免不同节点之间出现竞争条件和死锁等问题。
6.3、通常情况下的性能（Normal-case performance）
我们将FaRM的正常情况(无故障)性能表示为吞吐量-延迟曲线。对于每个基准测试，我们首先将每台机器的活动线程数从2增加到30，然后增加每个线程的并发性，直到吞吐量饱和。请注意，每个图的左端仍然显示显著的并发性和吞吐量。它没有显示FaRM可以实现的最小延迟。
TATP
图7显示FaRM每秒执行1.4亿次TATP事务，中位延迟为58 μs，第99百分位延迟为645 μs。在图的左侧，中位延迟仅为9 μs，第99个百分点延迟降至112 μs, FaRM每秒执行200万次操作。TATP使用的多对象分布式事务提交时间为数十微秒，最低吞吐量的平均提交延迟为19 μs，最高吞吐量的平均提交延迟为138 μs。
FaRM比Hekaton14,26发表的TATP结果高出33倍。Hekaton的结果是使用不同的硬件获得的，但是当我们在一台测试机器上运行Hekaton时，我们预计会有20倍的改进。在一个较小规模的实验中，FaRM仅用三台机器就超过了Hekaton。此外，FaRM支持更大的数据集，因为它可以向外扩展，并且与单机系统不同，它提供了高可用性。
TPC-C
我们运行TPC-C 60秒，我们在图8中报告了这段时间内的延迟和平均吞吐量。FaRM每秒执行多达450万次TPC-C“新订单”事务，中位延迟为808 μs，第99百分位延迟为1.9 ms。延迟可以减半，而吞吐量的影响只有10%。我们所知道的最好的TPC-C性能来自Silo[39,40]，这是一个单机内存系统，记录到FusionIO ssd。FaRM的吞吐量比没有日志记录的Silo高17倍，在这个吞吐量水平上的延迟比有日志记录的Silo好128倍。
读取性能（Read performance）
尽管本文的重点是事务性能和故障恢复，但相对于[16]，我们也能够提高只读性能。我们运行了一个只有键值查找的工作负载，其中包含16字节的键和32字节的值，以及统一的访问模式。我们实现了7.9亿次查询/秒的吞吐量，中位延迟为23 μs，第99百分位延迟为73 μs。这比之前报告的同一基准的每台机器吞吐量提高了20%。尽管nic数量增加了一倍，但我们并没有使性能增加一倍，因为基准测试受到CPU限制。
6.4、故障（Failures）
为了评估故障情况下的性能，我们运行了相同的基准测试，并在其中一台机器上关闭了FaRM进程。我们显示了89台幸存机器的吞吐量的时间轴，它们以1毫秒的间隔聚合。时间线在实验开始时使用RDMA消息同步。
图9和图10显示了每个基准测试在不同时间尺度上的典型运行。两者都将吞吐量显示为实线。“达到完全吞吐量所需的时间”是故障的放大视图。它显示了故障机器的租约在CM(“suspect”)上到期的时间;所有读调查完成的时间(“probe”);CM成功更新Zookeeper(“Zookeeper”)的时间;在所有幸存的机器上提交新配置的时间(“config-commit”);所有区域活动的时间(“all-active”);后台数据恢复开始的时间(“data-rec-start”)。“到完全数据恢复的时间”显示了一个缩小视图，其中包括在备份时恢复所有数据的时间(“完成”)。虚线表示一段时间内通过数据恢复恢复的备份区域的累积数量。
TATP
典型的TATP运行的时间轴如图9所示。我们将其配置为最大吞吐量:每台机器运行30个线程，每个线程8个并发事务。图9(a)显示，吞吐量在故障时急剧下降，但很快恢复。系统在不到40毫秒的时间内恢复到峰值吞吐量。所有区域在39毫秒内变得活跃。图9(b)显示了数据恢复，这是有节奏的，不会影响前台吞吐量。故障的机器托管了84个2 GB的区域。每个线程每2毫秒获取8 KB块，这意味着在一台机器上恢复2 GB区域需要大约17秒。机器以大致相同的速度并行地恢复一个区域，因此恢复的区域数量会大幅增加。恢复负载(即，在故障机器上有副本的每台机器的区域数量)在集群中很好地平衡:64台机器恢复一个区域，10台机器恢复两个区域。这就解释了为什么大多数区域的复制在17s左右完成，而所有区域的完全复制在不到35s的时间内完成。有些区域没有完全分配，因此恢复所需的时间较少。这就是为什么一些区域的复制在不到17秒的时间内完成。
该图还显示，即使没有故障，TATP的吞吐量也会有所下降。我们认为，这是由于基准的准入存在偏差;当许多事务发生冲突并同时缓和热键时，吞吐量会下降。
TPC-C
图10显示了TPC-C的时间轴。图10(a)显示，系统在不到50 ms的时间内恢复了大部分吞吐量，在此之后不久，所有区域都变得活跃起来。由于TPC-C具有更复杂的事务，因此系统恢复事务锁所需的时间比使用TATP稍微多一些。主要区别在于，尽管TPCC在实验中只恢复了63个区域，但恢复数据所需的时间更长(图10(b))。这是因为TPC-C对其哈希表进行了共同分区，以利用局部性并提高性能，这导致恢复并行性降低，因为在同一组机器上复制了多个区域，以满足应用程序指定的局部性约束。在实验中，两台机器分别恢复17个区域，导致数据恢复时间超过4分钟。注意，在图10(b)中，TPC-C吞吐量随着时间的推移逐渐降低，因为数据库的大小增长得非常快。
CM故障（Failing the CM）
图11显示了CM流程失败时随时间变化的TATP吞吐量。恢复速度比非cm进程失败时慢。吞吐量需要大约110 ms才能恢复到故障前的水平。恢复时间增加的主要原因是重新配置时间的增加:从图9(a)中的20 ms增加到97 ms。大部分时间都花在新CM构建仅在CM中维护的数据结构上。通过让所有机器在从CM获取区域映射时增量地维护这些数据结构，应该可以消除这种延迟。
恢复时间的分布（Distribution of recovery times）
我们重复了TATP恢复实验(没有CM故障)40次，以获得恢复时间的分布。实验使用较小的数据集(35亿订阅者)来运行，以缩短实验时间，但我们确认，故障后恢复吞吐量的时间与较大的数据集相同。这是因为这段时间主要用于恢复事务状态，并且对于两种数据集大小，并发执行事务的数量是相同的。图12显示了恢复时间的分布。我们测量了从CM怀疑出现故障的机器开始的恢复时间，直到吞吐量恢复到故障前平均吞吐量的80%。恢复时间的中位数大约是50毫秒，超过70%的执行的恢复时间少于100毫秒。在其他情况下，恢复时间超过100毫秒，但总是少于200毫秒。
相关故障（Correlated failures）
有些故障会同时影响多台机器，例如电源或开关故障。为了处理这种协调的故障，FaRM允许为每台机器指定一个故障域，CM将一个区域的每个副本放在不同的故障域中。我们将集群中的机器分为五个故障域，每个域有18台机器。这对应于交换机中每个叶子模块的端口数量。我们同时对其中一个故障域中的所有流程进行故障处理，以模拟顶架交换机的故障。
图13显示了72台未发生故障的机器随时间变化的TATP吞吐量。TATP配置为在每台机器上使用大约55个区域(整个集群中的69亿个订阅者)，以便在故障发生后有足够的空间重新复制失败的区域。FaRM在故障发生后不到400毫秒恢复峰值吞吐量。我们重复了这个实验20次，这次是所有实验的中位数。大部分时间用于恢复事务。我们需要恢复所有运行中的事务，这些事务修改了故障机器中带有副本的任何区域，读取了故障机器中带有主区域的区域，或者在故障机器上拥有协调器。这导致大约130,000个事务需要恢复，而单个故障需要恢复7500个事务。数据的重新复制需要4分钟，因为有1025个区域需要重新复制。正如在以前的实验中一样，这不会影响恢复期间的吞吐量。请注意，在此期间，每个区域仍然有两个可用的副本，因此不需要更积极地重新复制。
数据恢复速度（Data recovery pacing）
FaRM调整数据恢复的速度，以减少其对吞吐量的影响。这增加了在新备份中完成区域重新复制的时间。图14显示了具有非常积极的数据恢复的TATP随时间的吞吐量:每个线程同时获取4个32 KB块。故障发生800毫秒后，大部分区域被重新复制，系统才能恢复峰值吞吐量。但是，数据恢复的完成速度要快得多:恢复83个区域副本(166 GB)只需1.1秒。只有当区域丢失除一个副本外的所有副本时，我们才使用此主动恢复设置。积极的恢复速度与RAMCloud[33]相比更具优势，RAMCloud[33]在1.6秒内恢复80台机器上的35 GB。
与TATP相比，TPC-C对来自后台恢复流量的干扰不太敏感，因为只有一小部分访问远程机器上的对象。这意味着，在可能进行应用程序特定调优的设置中，我们可以更积极地重新复制数据，而不会影响性能。图15显示了当线程每2毫秒获取32 KB块时，TPC-C在恢复期间随时间的吞吐量。重新复制在65秒内完成，这比默认设置快了四倍，而且对吞吐量没有任何影响。
6.5、租约时间（Lease times）
为了评估我们的租约管理器优化(第5.1节)，我们运行了一个实验，其中所有机器中的所有线程重复向CM发出RDMA读取，持续10分钟。我们禁用了恢复功能，并针对不同的租约管理器的实现和不同的租约持续时间计算了整个集群的租约到期事件(误报)数量。这个基准测试是一个很好的压力测试，因为它在CM上生成的流量比我们描述的任何基准测试都多。
图16比较了四种租约管理器实现。第一个使用FaRM的RPC (RPC)。其他的使用不可靠的数据报:在共享线程(UD)上，在正常优先级的专用线程(UD+thread)上，以及在高优先级、中断和无固定(UD+thread+pri)上。
结果表明，所有优化都是必要的，以启用使用10 ms或更少的租赁时间而不出现误报。使用共享队列对，即使是100毫秒的租约也经常到期。通过使用不可靠的数据报可以减少误报的数量，但由于CPU的争用，误报的数量并没有消除。使用专用线程允许我们使用100毫秒的租约而没有误报，但是由于FaRM机器上运行的后台进程的CPU争用，10毫秒的租约仍然会过期。在中断驱动的租赁管理器以高优先级运行的情况下，我们可以在10分钟内使用5毫秒的租赁，没有误报。对于较短的租期，我们有时仍会出现误报。我们受到网络往返时间和系统计时器分辨率的限制，前者在负载情况下最多为1毫秒，后者为0.5毫秒。系统计时器的有限分辨率解释了为什么中断驱动的租约管理器比基于轮询的租约管理器有更多的误报。
在我们所有的实验中，我们保守地将租约设置为10毫秒，并且在执行过程中没有观察到任何误报。
7、相关工作（Related work）
据我们所知，FaRM是第一个同时提供高可用性、高吞吐量、低延迟和严格串行化的系统。在之前的工作[16]中，我们概述了FaRM的早期版本，该版本将log记录到SSDs以获得持久性和可用性，但我们没有描述从故障中恢复。本文描述了一个新的快速恢复协议和一个优化的事务和复制协议，该协议发送的消息大大减少，并利用NVRAM避免记录到SSDs。与[16]中描述的事务协议相比，优化后的协议发送的消息最多减少44%，并且在验证阶段还通过单方面的RDMA读取来替换消息。[16]中的工作仅使用YCSB基准测试在没有故障的情况下评估单键事务的性能。在这里，我们使用TATP和TPC-C基准测试来评估有故障和没有故障的事务的性能。
RAMCloud[33,34]是一个键值存储，它在内存中存储数据的单个副本，并使用分布式日志来保持持久性。它不支持多对象事务。发生故障时，它在多台机器上并行恢复，在这段时间内(可能需要几秒钟)，故障机器上的数据不可用。FaRM支持事务，使数据在发生故障的几十毫秒内可用，并且每台机器的吞吐量提高了一个数量级。
Spanner[11]已在第4节中讨论。它提供了严格的可序列化性，但没有针对RDMA的性能进行优化。它使用2f + 1个副本，而FaRM使用2f + 1个副本，并且比FaRM发送更多的消息提交。Sinfonia[8]提供了一个共享的地址空间，通过使用两阶段提交实现可序列化的事务，并在特殊情况下将读取装载到两阶段提交中。FaRM提供了利用RDMA优化的一般分布式事务。
HERD[23]是一种基于内存RDMA的键值存储，它在客户端与服务器运行在不同机器上的非对称设置中为每台服务器提供高性能。它使用RDMA写入和发送/接收verbs进行消息传递，但不使用RDMA读取。[23]的作者表明，在不对称设置中，单侧RDMA读取的性能比没有可靠性的专用RPC实现更差。我们的结果在对称设置中使用可靠的通信，其中每台机器既是客户机又是服务器。这允许我们利用局部性，这很重要，因为访问本地DRAM比使用RDMA访问远程DRAM[16]要快得多。Pilaf[31]是一个使用RDMA读取的键值存储。Pilaf和HERD都不支持事务。HERD不能容错，而Pilaf通过记录到本地磁盘获得持久性，但不是可用性。
Silo[39,40]是一个单机主存数据库，它通过将log记录到持久存储来实现持久性。它将已提交的事务分批写入存储，以实现高吞吐量。故障恢复包括从存储中读取检查点和日志记录。Silo中的存储是本地的，因此当机器出现故障时，可用性将丢失。相比之下，FaRM是分布式的，并在NVRAM中使用复制来实现持久性和高可用性。对于一个大得多的数据库，FaRM在故障后恢复峰值吞吐量的速度比Silo快两个数量级。通过向外扩展和在NVRAM中使用复制，FaRM还实现了比Silo更高的吞吐量和更低的延迟。Hekaton[14,26]也是一个单机主存数据库，不支持横向扩展或分布式事务。拥有3台机器的FaRM与Hekaton的性能相当，拥有90台机器的吞吐量是Hekaton的33倍。
8、总结（Conclusion）
事务使分布式系统编程更容易，但许多系统避免使用事务或削弱它们的一致性以提高可用性和性能。FaRM是用于现代数据中心的分布式主存计算平台，提供严格序列化的事务，具有高吞吐量、低延迟和高可用性。实现这一目标的关键是根据第一原则设计的新的交易、复制和恢复协议，利用RDMA的商品网络和一种新的、廉价的方法来提供非易失性DRAM。实验结果表明，FaRM比现有的内存数据库提供了更高的吞吐量和更低的延迟。FaRM还可以在不到50毫秒的时间内从机器故障恢复到提供峰值吞吐量，使故障对应用程序透明。
