No compromises: distributed transactions with consistency, availability, and performance——MIT6.824

发表于

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

Abtract

本文展示了一个名为FaRM的主存分布式计算平台，可以提供强串行化、高性能、高可用和耐用性等特质，为此设计了新的事务，复制和恢复协议。

Introduction

具有高可用性和严格序列化的事务虽然简化了编程，但在一定程度上也影响了系统的性能。因此，像Dynamo或者Memcached之类的系统通过不支持事务或者提供弱一致性来提高性能。有些系统则是仅在所有数据都停留在一台机器中时才提供事务。因此需要程序员费心思去考虑数据分区的问题。

FaRM提供了分布式的ACID事务，具有严格的可分级性，高可用性，高吞吐量和低延迟。设计的协议则利用数据中心中出现的两种硬件趋势——具有RDMA的快速网络和廉价的DRAM提供，通过在电源故障时将DRAM的内容写入SSD来实现非易失性。FaRM的协议遵循三个原则来解决CPU瓶颈：减少消息计数，使用单向的RDMA读写而不是消息，并有效地利用并行性。

FaRM通过使用单向RDMA操作进一步降低了CPU开销，因为并不会使用到远程CPU。为了使用单向的RDMA，需要设计新的恢复协议（例如RDMA的数据请求是通过网卡提供的，不能简单地在期限到时拒绝传入请求）。另外，恢复协议借助并行性，在集群中均匀地分配每个状态的恢复，并在每台机器的core之间作并行恢复。

前面讲过，FaRM的提出利用了两种硬件趋势——非易失性DRAM和具有RDMA的快速网络。

RDMA networking

FaRM尽可能使用单向的RDMA操作，这是一种远程直接数据存取，是为了解决网络传输中服务器端数据处理的延迟而产生的。文中的实验发现，RDMA读取比可靠性的RPC执行性能高2倍，而RDMA的性能瓶颈是网卡的消息速率。另外，RDMA和RPC都会受到CPU的限制，因此降低CPU开销才是挖掘硬件潜力的好方法。

Programming model and architecture

FaRM为应用程序提供了跨集群机器的全局地址空间的抽象，每个机器都运行独立的应用程序进程并存储对象在地址空间里。FaRM的API提供了对本地或者远程对象的透明访问，应用程序线程可以随时启动事务，在事务执行期间可以执行任意逻辑，随后可以调用FaRM来提交这些逻辑操作。

FaRM事务使用乐观并发控制，所有更新都被本地缓存，并且仅在成功提交后才对其他事务可见。如果并发事务冲突，事务的提交就会失败。

FaRM API还提供了无锁读取（优化的单对象只读事务）和位置提示，这样应用程序就可以将相关对象共存于同一组机器上，从而改善性能。

如下图所示，每台机器在用户进程中固定在每个硬件线程中的内核线程上运行FaRM，，每个内核线程运行一个事件循环，该循环执行应用程序代码并轮询RDMA完成队列。

随着计算机故障或添加新计算机，FaRM实例会随着时间推移逐步进行一系列的配置。配置是元组⟨i，S，F，CM⟩，其中i是唯一的，单调递增的64位配置标识符，S是配置中的一组计算机，F是从计算机到故障域的映射，CM则是配置管理器，FaRM使用Zookeeper来协调服务，确保机器就当前配置达成一致并进行存储。每个配置更改都会由CM调用一次Zookeeper，以更新配置。

FaRM中的全局地址空间由2GB的Region组成，每个Region都会备份到一个主备份和f个副备份中。每台机器在非易失性DRAM中存储多个Region，其他Region可以使用RDMA读取这些Region。读取对象必须要从包含该Region的主备份中完成，如果该Region位于本机，则使用局部地址空间读取。如果是远程，则使用单面RDMA读取。每个对象都有一个用于并行控制和复制的64位版本。Region标识符，即从主备份和副备份的映射由CM管理，并由线程与将单面RDMA读取发布到主备份所需的RDMA引用一起缓存。

所有机器都与CM沟通以分配新Region，从单调递增的计数器分配Region标识符，并选择该区域的副本。副本选择需要平衡存储在每台机器上的Region数量，同时受到以下限制：容量足够大，每个副本位于不同的故障域中，并且当应用程序指定位置限制时，该Region与目标Region位于同一位置。CM将准备消息发送给具有Region标识符的所选副本。如果所有副本都报告分配区域成功，则CM向所有副本发送一条提交消息。这是一个两阶段协议。

每台机器还存储实现FIFO队列的环形缓冲区。它们用作事务日志或消息队列。发送者会使用对尾部进行的单面RDMA写入，将记录追加到日志中。NIC会确认这些写入，但是不会涉及接收方的CPU。接收者定期轮询日志的开头以处理记录。

Distributed transactions and replication

FaRM集成了事务和备份的协议可以很好地提高性能，传统协议相比，它使用的消息更少，并且利用单面RDMA读取和写入来提高CPU效率和降低延迟。FaRM使用非易失性DRAM中的主备份复制来存储数据和事务日志，并使用单个事务协调器直接与primary和backup进行通信。

下图是FaRM事务的timeline。虚线和实线分别表示RDMA的读写，点线表示硬件的响应，矩形是对象数据。

在执行阶段，事务使用单向RDMA读取对象，并且它们在本地缓存写操作。协调器还记录所有访问对象的地址和版本，如果primary和backup与协调器位于同一个机器，对象访问会使用本地内存而不是RDMA来读取和写入日志。

提交事务：

  1. Lock：协调器将LOCK记录写入每台机器上的日志，这些机器是写入对象的主要机器。Primary的机器通过锁定特定版本对象的方式来处理这些记录。如果获取到所有的lock，那么将发送一条报告消息，否则会终止事务；
  2. Validate：协调器对primary机器执行读取验证，主要是读取所有对象的版本号，看是否一致。验证默认是通过单边的RDMA读取完成的；
  3. Commit backups：协调器在每次备份时将COMMITBACKBACK记录写入非易失性日志，然后等待NIC硬件的确认，而不是中断backup机器的CPU；
  4. Commit primaries：在COMMITBACKBACK写入backup机器之后，协调器开始对每台机器提交COMMIT-PRIMARY。Primary会更新对象的版本号；
  5. Truncate：在协调器收到所有主节点的响应之后，就会通过在其他日志记录中附带截断事务的标识符来实现记录的截断；

正确性

提交的读写事务在获取所有写锁时是可序列化的，而提交的只读事务在上一次读取时是可序列化的。在没有失败的情况下，这等效于在序列化时间点原子地执行和提交整个事务。

为了确保跨故障的可序列化性，必须在写入COMMIT-PRIMARY之前等待所有备份硬件的确认。否则一旦主节点在不接收COMMIT-BACKUP记录的情况下挂掉了，那么就可能丢失掉某个region的修改。

由于读集仅存储在协调器中，因此如果协调器失败并且没有提交记录可以生存以证明验证是成功的，则事务将中止。协调器必须要在其中一个主数据库上等待成功提交，然后再向应用程序报告成功提交。否则，如果协调器和所有相关backup节点都挂掉了，那么事务就会被终止了。因为没有可以用来做验证的记录。

Performance

对于FaRM来说，其协议比传统的分布式提交协议具有更多的优势，以带有备份的两阶段提交协议——Spanner的协议为例，Spanner使用Paxos复制事务协调器及其参与者，它们是存储由事务读取数据或写入数据的机器。每个Paxos状态机在传统的两阶段提交协议中都扮演着单独的机器的角色。因此这需要2f +1个副本才能容忍f个故障，每个状态机操作至少需要2f +1个往返消息，则需要4P（2f +1）个消息（其中P是事务参与者的数量）。

FaRM使用primary-backup复制而不是Paxos状态机复制。这将数据副本的数量减少到f+1，减少了在事务处理期间传输的消息的数量。并且由于协调器直接与主备节点交流，进一步减少了延迟和消息数。此外，通过RDMA进行的读取验证可确保只读参与者主节点不占用CPU，并且对COMMIT-PRIMARY和COMMIT-BACKUP记录使用单向RDMA写操作可减少对远程CPU的等待，另外CPU也可以批处理和懒惰处理。

Failure recovery

FaRM中的故障恢复有以下五个阶段：故障检测，重新配置，事务状态恢复，批量数据恢复和分配器状态恢复。

Failure detection

FaRM使用租约来检测故障。除CM之外，每台计算机都在CM上拥有租约，而CM在其他每台计算机上都拥有租约。租约到期就会触发故障恢复，租约是通过3次握手来授予的。每台机器向CM发送一个租赁请求，并以一条消息作为响应，该消息既充当对该计算机的租赁授权，又充当CM的租赁请求。然后非CM的计算机回复该租赁请求就行。

为了确保高可用性，FaRM的租期非常短。FaRM使用了专门的队列来实现租约，以避免其它消息类型在共享队列中，影响了其的延迟。为了提高性能，避免为每台机器在CM上增加一个队列，FaRM使用无限带宽的技术发送和接受各种操作。

租约的续期是在CPU上实现的，FaRM使用了专门的租约管理器线程，该线程以最高的用户空间优先级运行。

Reconfiguration

重新配置协议将FaRM实例从一种配置移到另一种。以下是重新配置的时间图：

  1. 怀疑。当某个机器的租约在CM到期时，它将怀疑该机器发生了故障。然后屏蔽所有外部客户端请求。
  2. 探测。新的CM向配置中的所有机器发出RDMA读取，但被怀疑的机器除外。同时也怀疑任何读取失败的机器，新CM仅在获得大多数探测的响应后才继续进行重新配置，避免CM处于小分区。
  3. 更新配置。在收到对探针的答复后，新的CM尝试将存储在Zookeeper中的配置数据更新为⟨c+ 1，S，F和CMid⟩，其中c是当前配置标识符，S是已回复的探测器，F是计算机到故障域的映射，而CMid是其自身的标识符。
  4. 重新映射区域。新CM重新分配先前映射到故障机器的区域，以将副本数恢复到f+1。
  5. 发送新配置。重新映射区域后，CM将NEW-CONFIG消息发送到配置中的所有计算机，其中包含配置标识符，其自身的标识符，配置中其他计算机的标识符以及区域到计算机的所有新映射。
  6. 应用新配置。当机器收到配置标识符大于其自身配置的NEW-CONFIG时，它将更新其当前配置标识符及其区域映射的缓存副本，并分配空间以容纳分配给它的所有新区域副本。
  7. 提交新配置。一旦CM从配置中的所有计算机接收到NEW-CONFIG-ACK消息，它将等待以确保先前配置中授予该配置中的计算机的租约均已到期。然后，CM将NEW-CONFIG-COMMIT发送给所有配置成员，这些成员拿到了租约的授权；

Transaction state recovery

在配置更改之后，FaRM使用分布在因事务而修改对象副本所产生的日志来恢复事务状态。下图展示了事务恢复状态的timeline，FaRM通过在集群中的线程和机器之间分配工作来实现快速恢复。

  1. Block access to recovering regions.

当一个primary挂掉，backup会被配置选举成新的primary，此时所有对相关区域的访问都会被屏蔽，知道上图第四步完成，重新获取读写锁。

  1. Drain logs.

要确保跨配置的一致性，一般是拒绝来自旧配置的消息。但FaRM无法这样做，因为NIC会提交写入事务日志的COMMIT-BACKUP和COMMIT-PRIMARY记录，而不会考虑它们的发布配置。FaRM通过drain日志的方式解决这个问题，即在收到NEW-CONFIGCOMMIT消息时都会处理其日志中的所有记录。完成后，它们会将配置标识符记录在变量LastDrained中，配置标识符小于或等于LastDrained的事务日志记录将会被拒绝。

  1. Find recovering transactions.

所有机器必须就给定事务是否为恢复事务达成一致，FaRM通过在重新配置阶段在通信中附带一些额外的元数据来实现此目的。协调器读取每台计算机上的LastDrained变量，对于自LastDrained之后其映射被更改的每个区域r，CM都会在NEW-CONFIG消息中向该计算机发送两个配置标识符——LastPrimaryChange[r]和LastReplicaChange[r]，分别是r的主备对象更改时的最后一个配置标识符，在配置c-1中开始提交的事务将在配置c中恢复。

用于恢复事务的记录可以分布在不同主数据库的日志中，以及由事务更新的备份机器中。region的每个备份都将NEED-RECOVERY消息与配置标识符，区域标识符以及更新该区域的恢复事务标识符一起发送给主数据库。

  1. Lock recovery.

每个region的primary都会一直等到本机的日志排干并且等待收到每台backup的NEED-RECOVERY消息，然后才去构建完整的恢复事务集合。然后，它通过其线程上的标识符对事务进行分片，以便每个线程t恢复具有协调器线程标识符t的事务状态。同时，主数据库中的线程并行地从尚未本地存储的备份中获取所有事务日志记录，然后锁定通过恢复事务修改的任何对象。

当某个区域的锁恢复完成时，该区域就处于活动状态，本地和远程协调器可以获得本地指针和RDMA引用。

  1. Replicate log records.

primary日志中的线程通过向backup发送缺失的事务的REPLICATE-TXSTATE消息来进行记录。该消息包含区域标识符，当前配置标识符以及与LOCK记录相同的数据。

  1. Vote.

正在恢复事务的协调器根据事务更新的每个区域的投票来决定是提交还是中止事务。

  1. Decide.

如果协调器收到来自任何region的commit-primary投票，则决定进行事务。否则，它将等待所有区域投票，如果至少一个区域对 commit-backup投票，而其他所有区域被事务投票锁定、提交备份或截断，则它将等待提交。

Recovering data

FaRM必须在某个region的新备份中恢复（重新复制）数据，以确保将来可以容忍复制失败。一个区域的新备份最初具有新分配的零区域副本。它将区域划分为多个工作线程，以并行方式恢复该工作线程。

在复制到备份之前，必须检查每个恢复的对象。如果对象的版本大于本地版本，则备份将通过比较和交换锁定本地版本，更新对象状态，然后将其解锁。

Recovering allocator state

FaRM分配器将区域划分为块（1 MB），用作分配小对象的slabs。它保留了两个元数据：块标头（包含对象的大小）和slab的空闲列表。

分配新块时，块头将复制到备份中。这样可确保它们在发生故障后在新的主数据库上可用。slab空闲列表仅保留在primary上，以减少对象分配的开销。