类Paxos共识算法研究进展

王 江 章明星 武永卫 陈 康 郑纬民

(清华大学计算机科学与技术系 北京 100084) (北京信息科学与技术国家研究中心 北京 100084) (清华大学深圳研究生院 广东深圳 518055)

随着互联网技术的迅猛发展，单机服务早已无法满足业务需求，越来越多的应用需要分布式系统的支持.由于数据量的快速增长，集群机器数目越来越大，因为服务器宕机等问题使得各类业务组件失效的可能性也越来越高.如何保证服务的可靠性和高可用性变得越来越重要.

副本复制技术是提供可靠性的基础技术之一，为数据或者服务提供冗余.副本状态机能够在有效隐藏服务器宕机问题的情况下，保证整个系统的强一致性,是分布式容错系统的一个基本结构.图1是副本状态机的基本原理，图1中展示了上下2个副本状态机的状态变化过程，实际中可能用到更多的副本状态机来保证更高的可靠性.2个状态机的初始状态都为S0，此后每1个状态变化都是一样的，且状态变化是具有确定性的.“确定性”的含义是只要输入相同，由输入引起的状态变化是确定且唯一的.根据数学归纳法，在保证了初始状态一样、状态切换顺序一致的情况下，所有状态机到达的最终状态也是一样的.

Fig. 1 The principle of replicated state machine图1 副本状态机工作原理

越来越多的系统使用副本状态机作为核心协同服务，例如Google公司的Spanner[1]、Oracle公司的MySQL[2]等数据库系统，以及Ceph[3]等分布式文件系统.为了能够发挥副本状态机技术的优势，也陆续有机构将该技术实现成为一种独立的可靠性服务，如Google公司的chubby[4]、Yahoo!公司的ZooKeeper[5-6]、腾讯公司的phxpaxos[7]以及CoreOS公司的etcd[8]等.

维护副本之间的强一致性就是让一组副本进程(通常分布在不同服务器上)共同决策一系列操作的顺序.于是核心问题就是在多机情况下，如何让各个副本进程就某个操作达成一致，这就涉及到分布式共识算法(distributed consensus algorithm).Paxos就是一个著名的分布式共识算法.从Lamport[9-10]提出Paxos算法开始，此后基于Paxos变形的分布式共识算法越来越多.近些年来，网络方面RDMA、软件定义网络(sofware defined networking， SDN)等技术发展迅猛，也有部分研究人员结合网络技术的发展和变化以及具体硬件重新设计共识算法提升分布式系统的性能.

本文主要从Paxos算法演进历程的角度出发，介绍在Paxos演进过程中4个关键的变种算法，并对这些算法作一些对比分析以及适用场景说明.同时也简要介绍了最近几年类Paxos算法在实现和使用上的一些新的优化思路.希望籍此能够帮助推进相关算法的进一步改进和使用，并为分布式容错场景下共识算法的选择提供参考.

1 分布式共识

分布式共识算法试图让一组分布式的进程达成共识，共同决定1个值.总体来说，一个正确的分布式共识算法需要满足4个基本条件：

1) 可终结性(termination).每个正常工作的进程最终都会决定1个值.

2) 合法性(validity).如果1个进程决定1个值,那么这个值一定是某个进程提出的，这避免了一些只决定无意义值的算法.

3) 完整性(integrity).决定出来的值不能被修改，结论不能推翻.

4) 一致性(agreement).所有正常的进程都只能同意同一个值.

以上4个条件，常常被归结为2个方面：活性(liveness)和安全性(safety).活性主要包含可终结性；安全性方面主要包含合法性、完整性以及一致性.

解决分布式共识问题最基本的解决思路就是投票.一组相互独立的进程之间进行投票操作，一旦投票的结果被大多数进程(quorum)所认可，就可以被认为是完成了共识过程.当然，这其中会涉及到网络的消息延迟、消息重复，以及节点的宕机、掉线等情况.虽然基本的思路很简单，但是给出一个切实可行的算法非常不容易.其中一个非常著名的算法就是由Lamport[9-10]提出的Paxos算法.

2 Paxos算法

Paxos算法中定义了3种角色：提议者(Proposer)、接受者(Acceptor)以及学习者(Learner).3种角色的作用如表1所示：

Table 1 The Function of the Roles in Paxos表1 Paxos算法中的角色及其作用

Paxos 算法基于一系列的假设，其中2个关于通信方面的假设：

1) 异步通信环境，即多个进程中的操作指令可以以任意速度执行，多个进程之间的通信时间或长或短，通信消息在传递过程中可能会发生丢失、顺序错乱以及多次重复发送，也允许进程执行失败退出，退出后也可能会再次启动并运行；

2) 非拜占庭模型，即每个参与共识的进程都忠实地遵守算法约束，不参与破坏，不篡改消息.

在实际分布式系统中，异步通信普遍存在，同时用于做共识的节点往往都运行在数据中心中，能够保证大多数情况下节点不被劫持，且节点之间通信正常，因此这2点假设具有比较好的普适性.后来出现的很多共识算法的设计也都是基于这2点假设的，本文将基于这2个假设的分布式共识算法统称为类Paxos算法.

一般来说，假设分布式系统中有2F+1个副本进程，这些算法通常容忍其中F个副本进程故障，即失效.也就是说只要其中有F+1个副本进程正常工作，系统就能够正常提供服务.

Paxos算法关键的地方在于提议者不能随便提出自己的提议.原因很简单，如果系统中所有的接受者已经达成了一致的意见，那么提议者就不能提出有可能破坏一致意见的提议.这么做的原因当然是为了满足分布式共识算法的上述4点性质.这样，Paxos算法分为2个阶段:1)提议者去了解一下当前接受者群体的一些情况；2)提出合适的提议.这样的2个阶段如图2所示，分别被称为准备提议阶段和接受提议阶段.

Fig. 2 The main procedure of Paxos图2 Paxos算法主要过程

阶段1. 准备提议阶段.

阶段1.1. 提议者准备提案编号n，向系统中大多数(超过半数以上)接受者发送这个编号n，消息被称作是Prepare消息.

阶段1.2. 接受者接收到带有提案编号为n的Prepare 消息.根据接受者之前是否接受过比n编号更大的Prepare消息，接受者有2种状态：1)接受过；2)没有接受过.针对第1种状态，接受者直接忽略编号为n的消息即可.在第2种状态下，根据是否接受过阶段2.2的Accept消息，又分为2种情况：1)没有接受过；2)接受过.接受者的任务是将自己的最新状态反馈给提议者，这个最新状态包括自己接受过的最大提案编号以及提案内容.没有接受过则反馈空集即可.

阶段2. 接受提议阶段.

阶段2.1. 提议者收到半数以上的接受者反馈的情况之后，会向所有接受者发送Accept消息，这个Accept消息中包含提案编号和提案内容.提案编号在之前就确定了，关于提案内容有2个来源.首先，可能有一部分接受者反馈了它们之前接受过的提案，提议者会从中选择一个提案编号最大的提案内容作为Accept消息中的提案内容.其次，如果接受者反馈的提案的内容都为空，那么提议者可以任意选择一个值作为Accept消息的提案内容.

Fig. 3 Livelock in Paxos图3 Paxos算法中的活锁

阶段2.2. 如果接受者接收到了提案编号为n的Accept消息，且在此之前接受者没有响应过具有比编号n更大的消息，那么接受者接受这个Accept消息，即接受这个提案.

对于学习者而言，它们的工作比较简单，就是调查接受者，看看是不是有大多数的接受者接受了相同的提案(包括提案编号以及提案的值).若有，则算法结束;若没有，投票需要继续.算法中角色的分配是灵活的，在实际系统中，一个副本进程可以同时扮演多个角色.

3 类Paxos算法发展以及分类

第2节介绍了基础Paxos算法原理，系统经历2个阶段可以确定一个操作或值.这一整个过程可被称为一个实例(instance).一个实例是不够的，多个实例可以用来维护副本状态机的一致，即可以形成副本状态机所必须的日志序列.在执行一个实例时，可能会出现如图3所示的活锁情况，图3中ServerA和ServerE反复交替执行2个阶段形成活锁，Paxos算法并不能保证这种情况不会出现.从原则上来看，活性的条件并不能保证，不能保证算法一定得出一个最终的共识结果.为了能够让算法尽量得出共识结果，类Paxos算法还需要一个重要的假设，即在一段时间内大部分的参与者以及它们之间的网络连接是良好的.实际系统的情况也符合这样的假设.这一段时间就被用来完成共识过程.

有了上述假设之后，在实际实现过程中，通常需要在系统中选取一个唯一的领导者来尽量避免活锁情况的出现.选完领导者以后的一段时间内，所有操作指令的先后顺序都由领导者决定.当然这个领导者是可变化的，即当领导者进程发生故障后，系统通过选举算法产生新的领导者，再继续提供服务.从Lamport[9-10]提出Paxos算法以来，有许多类Paxos共识算法研究陆续出现，以适应不同的工程实践环境.其中，就有一类采用了类似上文选取稳定领导者的思路，本文将这一类算法称作为强领导者(leader-based)共识算法.

当然，随着研究的深入，也有研究人员发现了一些新的思路：不通过选举产生领导者，每个副本进程都作为一个弱化的领导者，负责一部分请求的提交工作.通过其他约束来满足安全性和活性条件，使得多个进程之间达成共识.本文将这一类算法称作为弱领导者(leaderless)共识算法.

3.1 强领导者共识算法

在第3节引言中也提到，强领导者共识算法的主要思路是引入一个稳定的领导者，在一段时间内，所有的值都由这个领导者来决定.在这个过程中，需要考虑3个问题：

1) 正常情况下的日志复制；

2) 领导者失效以后选取新的领导者，系统开始时没有领导者属于这种情况的一种特例；

3) 成员更新问题，即系统内的成员发生变化，如何做配置切换.

在实际实现过程中，为了解决这3个问题，同时保证安全性条件，且尽量满足活性条件，研究人员提出了各种强领导者共识算法.在类Paxos算法发展历程中，先后出现了4种比较典型的强领导者共识算法：

1) Multi-Paxos[10-11]是将Paxos算法应用到工程实践中，通过对Paxos算法中所缺失的对于实际情况的补充来构造完成的算法；

2) VR (viewstamped replication)是Liskov等人[12-13]为了替换2阶段提交协议而设计的复制算法，主要用于数据库系统和分布式文件系统；

3) ZAB[6](ZooKeeper’s atomic broadcast)是雅虎公司为了实现分布式协同服务而设计的一种可以支持崩溃恢复的原子广播算法；

4) Raft是Ongaro等人[14]为了让技术人员更好地理解、学习以及实现副本状态机而设计的分布式共识算法，展现了副本状态机实现过程中的各个细节.

根据实际实现过程中需要考虑的问题，可以将强领导者共识算法分为3个部分：正常情况下的复制、领导者失效情况下的领导者选取以及成员更新.实际上4种算法描述基本都是围绕着这3个部分进行的.从强领导者共识算法的3个部分阐述4种算法在3个部分中采取的不同方法，以及不同方法在解决共识问题中对于安全性和活性所做的考虑.4种算法的描述中使用了一些类似的概念，但是表述不同，列举在表2中.在4种算法中，副本进程在不同时期会拥有不同状态，状态大致分为3种：正常情况下的领导者、正常情况下的追随者以及在领导者失效过程中重新选举的中间态.

Table 2 The Confrontation of Some Concepts in Leader-Based Distributed Consensus Algorithms表2 强领导者共识算法相关概念对比

3.1.1 正常情况下的复制

正常情况下，强领导者共识算法中都存在一个领导者进程，其主要的任务是接收来自客户端的请求，将其转换成为副本状态机中的一个日志项.通过复制阶段的算法约束让其他副本进程接受这个日志项，而又不违反安全性条件.4种算法在这个阶段中的差别比较小，下面将对4种算法在这一阶段的表现形式作简要描述.

3.1.1.1 Multi-Paxos算法

领导者进程接收客户端请求后，在本地形成提案，并执行基础Paxos算法的第2个阶段将提案发送给其他副本进程，如图4所示.

3.1.1.2 VR算法

领导者进程接收客户端请求，将请求添加到本地日志末端，然后向其他追随者进程发送这个请求，编号为n.追随者进程在接收这一请求之后会作一个检查，查看本地的日志中是否包含所有编号小于n的日志项，若不包含，则等到全部包含为止.满足上述条件以后，追随者进程会给领导者进程一个回复.领导者进程在收到F个追随者进程的回复以后，在本地提交并且执行这个请求，将执行结果回复给客户端.其他追随者进程想要获知这个请求是否需要提交并且执行则需要客户端发起下一个请求，领导者在下一个请求中携带提交通知一起发送给追随者进程.若没有，则领导者一段时间以后自己广播Commit消息，通知追随者进程提交相对应的请求.这个Commit消息本身也起到判断领导者进程和追随者进程之间的网络连接是否正常的心跳作用，如图5所示.

Fig. 4 Normal case in Multi-Paxos图4 Multi-Paxos 正常复制阶段

Fig. 5 Normal case in VR图5 VR算法正常复制阶段

3.1.1.3 ZAB算法

领导者进程接收到客户端请求后，本地形成1个事务，并给事务分配1个递增的事务编号 (1个64 b的整数，前32 b表示事务所在的任期，后32 b表示任期内的事务编号).然后，领导者进程向其他副本进程发送事务提案.其他副本进程接收到事务提案以后，将事务写到本地磁盘，然后向领导者进程发送确认消息.领导者进程收到F个以上副本进程的确认消息后，向所有的副本进程广播Commit消息.副本进程收到Commit消息时，提交该事务.

3.1.1.4 Raft算法

领导者进程接收客户端请求，将请求记录成日志项的形式，并把日志项发送给其他追随者进程，如图6所示.领导者将T3日志项发送给其他2个追随者完成复制过程.日志提交有2个限制条件：

1) 如果当前日志项属于领导者当前任期，那么当这个日志项发送给过半数以上的副本进程并得到正确回应以后，日志项即可标记为已提交；

2) 如果当前日志项属于之前领导者的任期，那么这个日志项是否被提交的依据是它的下一条日志项是否已经提交，也就是下一个日志项的提交会顺便将之前所有的日志项标记为已经提交.

Fig. 6 Normal case in Raft图6 Raft算法正常复制

为了追随者进程和领导者进程维护的操作日志保持一致，在新的领导者产生后，领导者需要知道追随者跟它保持一致的日志位置，然后从这个位置后的第1个位置开始执行复制操作.

追随者获知日志项是否提交的方式跟VR算法类似，也是领导者通过下一个日志项来广播提交通知，追随者进程获得通知以后更新本地日志项的状态.在没有请求到达的时候，Raft算法会定期地广播空的日志项作为心跳消息.

3.1.1.5 小结

从3个方面比较4个算法的不同点：日志项提交的判断、日志项是否连续以及追随者进程获知日志项提交的方式.

1) 日志项提交条件.4种算法对于1个日志项是否提交具有1个基本原则，即过半进程回复确认以后，即表示这个日志项可以提交；Raft算法则对于不属于当前任期的日志项，有特殊判断.

Fig. 8 View change in VR图8 VR算法的视图切换

2) 日志项是否连续.Multi-Paxos算法的日志序列是允许有空洞的，如图7所示.对于FollowerA来说没有接收到日志项x=3,不影响其接受x=4.其他3种算法则要求日志连续，VR算法在算法描述中强调了这一特征， ZAB算法和Raft算法则隐含了这个特征.

Fig. 7 The empty instance of Multi-Paxos图7 Multi-Paxos算法中的日志空洞

3) 获知日志项需要提交的方式.Multi-Paxos和ZAB算法都有独立的广播提交通知的阶段.VR和Raft算法则将提交通知隐含在下一个请求中，这个请求可以是来自客户端的请求或者领导者的心跳信息.心跳消息在VR算法中表现为Commit消息，在Raft算法中表现为空日志项.

3.1.2 领导者选取

强领导者共识算法的一个重点就是在领导者失效的时候选出新的领导者并且需要保证在选举过程中系统状态的正确性.这里需要解决2个问题： 第1问题是正确选举产生新的领导者；第2问题是选举产生新的领导者以后，如何保证新的领导者以1个正确的状态开始新的任期，对于原来已经提交的内容不再推翻.为了避免旧领导者的影响，因此有了任期这个概念，新的领导者任期编号大于旧领导者任期编号.

3.1.2.1 Multi-Paxos算法

在Multi-Paxos算法中，选举算法是相对比较灵活的.文献[11]中提到，在选举阶段，副本进程会产生一个任期编号，这个编号大于它之前见到的所有任期编号.然后，这个副本进程向所有副本进程发送这个任期编号.如果半数以上的副本进程都回复表示没有见过比这个任期编号更大的编号，那么该副本进程就作为新的领导者，这个回复消息被称为Promise消息，即发送了Promise消息的副本进程将不再回应来自旧任期的领导者的消息.与此同时，这个Promise消息中，也包含了副本进程最近见过的任期，以及这个任期内接受的最后一个日志项.至于选举的触发操作可以通过简单的超时机制实现.

领导者进程从收到的Promise消息中选择一个离自己任期最近的日志项，将这个日志项作为恢复的结束点.然后领导者进程只需要1个读阶段就能够将自己的状态和其他副本进程恢复到一致.而读阶段可以简单理解为在日志空洞位置执行基础Paxos算法的第1个阶段去发现其他进程在对应位置上的值就可以，然后把这些位置上的值重新提交即可.

3.1.2.2 VR算法

当系统中的追随者进程一段时间没有收到领导者进程的普通请求消息或者Commit消息时，追随者进程就会进入领导者选举，选举主要分为3个过程.首先追随者进程将状态转换为视图切换状态，即表示不再接受来自其他进程的请求.VR算法为领导者选取阶段定义了3种消息，如图8所示.3种消息也对应了3个过程.START-VIEW-CHANGE的主要作用是告知其他追随者自己进入新的任期，同时在此过程中选出一个最高的任期作为新的任期，拥有最高任期且得到多数派认可的副本进程出任领导者.这个过程类似于Paxos算法的第1个阶段.DO-VIEW-CHANGE作为第2个过程其主要作用是，非领导者进程向领导者进程发送自己的本地日志.领导者收集完过半进程的日志序列后，确认自己进入领导者状态，从收集的日志序列中选出一个最新日志作为新任期的初始状态.第3个过程START-VIEW的作用则是，新的领导者向所有副本进程宣布其领导者身份，并告知它们进入新的任期，将本地状态切换为新的状态，开始进入追随者状态正常工作，完成视图切换过程.VR算法的选举横跨了第1，2个过程.对于新任期正确状态的确定则主要体现在第2，3个过程.

3.1.2.3 ZAB算法

在ZAB算法中，每个进程有3种状态，即选举状态、追随状态以及领导状态.正常情况下，副本进程会向领导者进程发送心跳信息，当领导者进程一段时间没有收到多数副本进程的心跳消息时，它就进入选举状态.同时如果副本进程发现领导者进程失效或者让出了领导者的位置，它也会将自己的状态切换为选举状态.在ZooKeeper中选举算法有多种，最经典的选举算法是Fast leader election算法，思路就是每个副本进程都会维护一个投票箱，用以保存投票请求并且统计选票.进入选举阶段以后，系统经历2个过程.

1) 候选者进程向其他副本进程发送请求投票消息，请求投票消息内容主要包含2个信息：①副本进程编号；②副本进程本地最后一个事务的编号.此后的过程就是每个副本进程在接收到投票消息以后，如果它认可这个投票，它会统计这个投票，同时向外广播这个投票.对于判断是否认可的条件主要依赖于投票内容和副本进程本地状态的对比.直到有过半进程都接受了某一个投票内容，则第1个过程结束，产生了新的准领导者.

2) 准领导者将会向其他副本进程发送新任期通知，其他副本进程收到新任期通知以后会将本地状态更新，并且会向新的准领导者发送确认消息，确认消息中就包含本地最新的事务日志.准领导者收到过半副本进程的回复以后，会从回复消息中选择一个最新的事务日志作为新任期初始化的事务集合，此时领导者也就确认了自己的领导者身份.

为了提高数据同步效率，领导者为每个支持它的副本进程维护一个FIFO队列，将新的事务日志中未提交的事务放入队列，同时向队列中加入Commit消息.而通信模块则负责将各个队列里的消息顺序发送给对应的副本进程，同步过程即是恢复过程.至此完成视图切换，然后开始接收客户端的请求，提供服务.

3.1.2.4 Raft算法

Fig. 9 Leader election in Raft图9 Raft算法选取领导者

Raft算法为副本进程定义了3种不同角色：领导者、候选者和追随者，分别对应了副本进程在不同时期的状态.同时，Raft算法用一种心跳机制(heartbeat)来触发选举过程，如图9所示.当系统启动时，所有的副本进程都会被初始化为追随者，领导者会向所有追随者发送心跳信息来确保领导者和其他追随者连接正常.如果有追随者在1个周期内没有收到心跳信息，它就会认为当前系统中没有领导者，然后把自己的状态转换成候选者状态，并增加当前任期编号，发起1轮投票.如果1个候选者在1个任期内收获了半数以上的副本进程给它投票，那它就会将自己的状态转化为领导者.投票请求中的内容包含3个重要信息：候选者新的任期、候选者本地最新日志项的任期以及日志编号.判断是否投票的条件，首先投票请求中的新任期比副本进程本地任期要大，这一条件不满足则不投票；其次，对比投票请求中的日志任期和副本进程本地最后一个日志项的任期，投票请求的日志任期较小，则副本进程不投票，相同则比较日志项编号，投票请求中的日志项编号较小则不投票.总结一下就是，投票请求内容比副本进程本地状态更超前，则副本进程认可这个投票，否则就不投票.

3.1.2.5 小结

新领导者开启新的任期以后，就开始正常的日志复制工作，复制过程初始阶段不可避免地涉及到对于旧任期日志的处理，在3.1节的日志复制阶段有相关说明.

总体上，选取新的领导者是因为旧的领导者失效，出于安全性考虑，同一任期最好只有1个领导者，因为多个领导者可能造成日志序列不一致.因此，4种算法在选举阶段的目标也是相对明确的，即在1个任期内选出1个领导者，选举操作本身成功与否都不能影响系统安全性.对于领导者选举部分来说，有4个关键方面：1)选举触发条件;2)副本进程当选领导者的条件;3)确定任期内领导者的唯一性;4)新任期系统状态的确定.

1) 选举触发条件.Multi-Paxos算法和ZAB算法中副本进程和领导者进程之间会维护独立的双向心跳消息，所谓双向指的是领导者到追随者、追随者到领导者.ZAB算法选举触发是2个方面的，可以来自于领导者自身或者追随者进程.VR算法和Raft算法则主要是领导者向追随者发送心跳消息，追随者在一段时间没有收到心跳消息以后会触发选举操作.心跳消息也不一定是单独设置的.在VR算法中，心跳消息可以是普通请求消息或者提交通知.对于Raft算法来说，心跳消息是正常的日志项或者空的日志项.

2) 副本进程当选领导者的条件.4种算法判断领导者当选的条件是一致的，即该领导者进程得到了过半副本进程的认可.VR和ZAB算法对于领导者当选的判断可以是由候选者本身统计，其他副本进程也有统计.Multi-Paxos和Raft算法主要是候选者向别人征集投票，自己统计.

3) 确定任期内领导者的唯一性.4种算法本质上都限制在某一个任期内只投1次票.在这种情况下，要么形成分票的局面，即没有1个候选者获得过半进程认可;要么就选出1个领导者，而这个领导者，在这个任期内是唯一的.对于分票情况，4种算法都是通过超时，然后增加任期编号，重新选举.为了选举能够尽快成功，ZAB和VR算法通过不停广播选票信息，使得尽可能多的副本进程参与选举.Raft算法则通过随机化超时时间来降低再次分票的可能性.

4) 新任期系统状态的确定.Multi-Paxos算法新任领导者在确定日志恢复结束点之后，领导者进程会将自己的状态同步到日志恢复结束点的状态，然后开始正常工作；VR和ZAB算法则是向其他副本进程征集，在半数以上副本进程的日志序列中，选一个最新的日志作为新任期初始状态，实现上有些小的差别；Raft算法则是在选举的时候就要求候选者符合一定条件，其他副本进程才会给它投票，选出来的领导者本身就有比较全面的状态.

3.1.3 成员更新

成员更新也是分布式系统中经常会遇到的问题，涉及到系统规模的缩小和扩大.一个最简单的思路是把当前系统停掉，停止期间不接收客户端请求，然后更换配置再重启系统，等系统恢复正常以后，开始对外提供服务.然而，这样不仅仅会影响系统的可用性，同时如果手工操作失误很有可能造成无法恢复的局面.旧版本ZooKeeper就是这样做的，ZAB算法中也不包含成员更新部分.成员更新频率不高，在实际场景中也不如前面4个问题关键，因此很多算法都没有考虑这个问题.

在文献[9-10]中，提及了成员变更的方法，这一方法对于Multi-Paxos来说同样适用，具体的思路是将成员变更操作看作是状态机的一部分，可以通过操作指令去修改.当新配置出现时，将其形成一个提案通过Multi-Paxos算法去提交.提交条件还按照旧的配置，当新的配置提交并执行时，系统切换到新的配置上来.

Raft算法提出了共同共识(joint consensus)的概念，指的是在集群进行配置调整的时候，让系统先进入一个过渡状态，这个过渡状态称为共同共识，一旦共同共识被提交，系统就可以切换成新的配置.共同共识的状态可以理解为新旧配置结合的一种状态，同时也是一种特殊的日志项.领导者会广播这个日志项，让日志项提交.

实际上，以上提到的成员变更方法，基本都是将集群的配置更新作为状态机的一部分，这也是类Paxos共识算法都可以通用的思路.而为了系统具有更好的可用性，往往都会让新加入的成员与老成员的状态基本达到一致时再执行配置更新.

3.1.4 强领导者共识算法总结

在上述的4种强领导者共识算法中很容易看到，在解决共识问题过程中，解决的思路有着紧密的联系.4种算法都有类似于领导者进程这样的角色，整体上由其负责多个副本进程之间达成共识的工作.4种算法中，领导者进程都需要等待超过半数以上的副本进程正确的回应后才能够就一个提案达成共识.当然不同算法，对于提案提交条件有不同限制.Multi-Paxos 被当作是基础Paxos算法的一种具体实现形式，在文献[10]中只是简单提了一下，而实际上没有系统而完整的描述.VR算法、ZAB算法以及Raft算法是对Multi-Paxos算法作出了更加严格的限制以及更加规范的、阶段化的描述.同时，4种算法也有着不太一样的设计原则.

对于旧领导者尚未提交的日志项，Raft算法是比较消极的，只有旧领导任期内的日志项被过半复制或者日志项已经提交，才能够保证该日志项不被覆盖.Multi-Paxos，VR，ZAB算法则相对比较激进，即便是旧领导者未过半复制的日志项，只要是新的领导者能够获知这个日志项的存在，也会将这个日志项重新提交，然而处理的方式可能会存在细微的不同.对于只在旧领导者本地存在的日志项，当这个旧领导者重新回到系统中的时候：Raft算法的处理方式是新的领导者会把自己本地的日志发送给回归的旧领导者进程，覆盖掉只在旧领导者本地存在的旧的日志项；Multi-Paxos算法和VR算法则采用恢复机制尝试将旧的日志项覆盖；ZAB 算法特别地设计了TRUNC指令用以删除只在旧领导者本地存在的日志项，然后添加新的日志项.

随着强领导者共识算法在工业界的盛行，如Chubby 使用Multi-Paxos算法,ZooKeeper使用ZAB算法以及etcd 使用Raft算法，强领导者共识算法在解决共识问题上更能被工程人员接受.因为后续出现的如Raft 算法，提供了完整的副本状态机实现的描述，使得副本状态机的实现以及共识算法的理解变得相对容易.

3.2 弱领导者共识算法

强领导者共识算法会有单个领导者在处理请求上的性能瓶颈问题.尤其在广域网的情况下，客户端和领导者节点可能不在同一个区域，跨域请求的延时会相对较高.因此，也有研究人员想基于基础Paxos算法设计弱领导者共识算法.

3.2.1 Mencius算法

Mencius[15]算法就是为了解决单领导者共识算法存在的瓶颈问题而设计.在Mencius算法中，所有副本进程组成一个闭环，提前给这些副本进程分配好用以提出题案的空位编号，如图10所示.通过这种方式，所有副本进程都轮流提出自己的提案.这样做能够提高系统吞吐率，尤其是在整个系统性能限制在CPU资源上的时候.因为日志空位上的指令提案由哪个副本进程负责提出是预先商定好的，通过这种形式也就省去了基础Paxos算法中的准备提议阶段，负责对应空位的副本进程直接执行接受提议阶段即可.如果该副本进程暂时没有提案可以提出，则在对应空位填入空操作.这种做法给整个系统带来更均衡的通信模式，进而能够更好地利用闲置的网络带宽.当一个副本进程X失效或者处理速度很慢时，其余副本进程可以通过运行基础Paxos算法中的准备提议阶段，接管原本分配给X的空位，在接受提议阶段只能提交空操作.判断一个副本进程是否需要被接管可以简单通过超时机制来实现.

Fig. 10 The log of Mencius图10 Mencius算法的日志

在正常情况下，系统中所有副本进程请求负载比较均衡，系统性能跟有固定领导者的Multi-Paxos算法是比较类似的，但是Mencius算法有效解决了单领导者性能瓶颈以及请求跨地域情况下网络延时较高等问题.然而，当系统中有部分副本进程比较空闲，以及有部分副本进程很慢时，就会产生很多无效的空操作，进而使整个系统性能下降.为了解决这一问题，Mencius算法也提出了一些如租约机制等优化手段，但是依然避免不了系统性能受限于最慢的副本进程.同时如果有副本进程失效，因为系统需要花费时间去检测失效的副本进程，还需要有其他副本进程接管它负责的空位，这样的开销甚至比强领导者共识算法切换领导者更大.所以从可用性上来讲，它有可能比强领导者共识算法表现得更差.为了避免以上Mencius算法的缺陷，卡内基梅隆大学的研究人员提出了基于所有副本进程身份均等的EPaxos[16](egalitarian Paxos)算法.

3.2.2 EPaxos算法

EPaxos算法给出的设计思路是允许所有的副本进程从客户端接收请求，并让副本进程拥有只需要1个通信轮次就可以提交提案的权利.在这种情况下，系统就可以有效实现负载均摊，此外，还可以允许客户端尽量选择离自己较近的副本进程提交请求，从而解决跨地域请求延时较长的问题.基础Paxos算法能够实现副本进程最少在2个通信轮次的情况下提交提案，达到同样效果，也就是基础Paxos算法的2个阶段.EPaxos算法能够实现在1个通信轮次内提交提案，让其他副本进程接受，原因也就在于算法假设：没有关联的2个操作指令(即提案内容)在所有副本进程上提交以及执行的顺序是无关紧要的.举例来讲，有2个副本进程A和B，A提出1个提案将x变为x+1，B提出1个提案将y变为y-1.2个提案所改变的对象是不相同的，那么它们的顺序先后并不是很重要.基础Paxos算法里有1个实例的概念，1个实例就是运行1轮Paxos算法，在对应的1维日志项的空位里填上状态机操作指令，这样就形成了1个一致性操作序列.在EPaxos算法中，为了使得不同副本进程在提出提案过程中不会与其他副本进程在日志项排序上存在竞争，EPaxos算法将日志设计成了1个2维矩阵的形式.日志项编号为R.id，其中R表示的是副本进程的编号，id表示的是在副本进程R内连续递增的正整数.每个副本进程都会维护这样1个矩阵，用以记录整个系统的状态，如图11所示.

Fig. 12 The main procedure of EPaxos图12 EPaxos算法主要过程

Fig. 11 The log of EPaxos图11 EPaxos算法的日志

在实际生产环境中，对于状态机而言，操作指令之间完全不存在冲突的概率是比较低的.在操作指令存在冲突的情况下如何处理操作之间的顺序也就成为了EPaxos算法设计过程中最主要解决的问题.

简单来说，EPaxos算法主要贡献在于无冲突操作指令可以在经历1个阶段以后就可以提交并且执行.在存在操作指令冲突的情况下，退化为2个阶段的基础Paxos算法.因此，EPaxos算法适用于冲突较少，甚至是没有冲突的应用场景.

3.2.3 弱领导者共识算法总结

弱领导者共识算法在设计的过程中需要考虑2个关键问题：

1) 没有单个稳定的领导者，怎样使得请求在尽量少的通信轮次后被提交；

2) 当副本进程失效时，如何恢复.

针对问题1，弱领导者算法的解决思路是将领导者的责任均摊到每个副本进程上去.Mencius算法是将日志空位进行预分配，不选领导者而是每个副本进程轮流作为领导者主持日志项的提交.EPaxos算法则是组织了一种新的日志形式，将日志组织成为2维矩阵.每个副本进程都负责提交自己提出的日志项，作为自己提出的日志项的领导者，同时也维护其他副本进程提出的日志项的状态.

对于问题2，无论是Mencius算法还是EPaxos算法都需要通过其他副本进程接管的形式对于失效进程的日志项进行恢复.比较不同的是，EPaxos算法的性能不会像Mencius算法一样受限于集群中较慢的节点，因为算法只要能够从最快的多数派中拿到回复就可以对1个日志项进行提交.Mencius算法因为副本进程轮流当领导者角色的缘故，无法避免慢节点的影响.然而，EPaxos算法由于同时有多个领导者存在，通过将日志设计为2维矩阵的形式避免了不同领导者对于同一个日志项空位的竞争.但是为了多个进程间能够拿到1个一致性顺序，不得不做一些额外的设计.带来的开销也是多方面的，例如需要1个额外的阶段来让各个副本进程接受同一个操作指令以及依赖集合.恢复阶段的设计也比较复杂，场景局限也很显然.

3.3 2类算法对比

强领导者和弱领导者可以看作是Paxos算法2种不同的实现方向，从本质上都是Paxos算法在实际使用中的一种扩展形式.在不同的适用场景中，工程人员会有不同方面的考虑.2类算法对比如表3所示：

Table 3 Contradistinction of Two Kinds of Distributed Consensus Algorithms表3 2类分布式共识算法的对比

4 类Paxos共识算法进一步改进

4.1 算法设计上的改进

Paxos算法的作者Lamport在后续研究中，给出了一些新的改进思路.Paxos算法中假设总副本进程数为2F+1,容忍F个副本进程失效，达成共识过程中只需要F+1个副本进程参与.Cheap Paxos[17]算法为了节约资源，在算法设计过程中只使用了F+1个副本进程，另外F个副本进程在正常情况下处于闲置状态.当正常工作的F+1个副本进程出现进程失效的情况时，闲置的副本进程就会出来替换失效的进程.当然，这一过程不可避免地会造成额外的恢复开销.这一优化虽然对性能没有太大的提升，但是提出了一个更节约资源的思路.Shi等人[18]在他们的研究中设计了ThriftyPaxos算法，旨在构建低成本高可用的副本状态机.在ThriftyPaxos算法中，副本进程在处理请求的过程中，后台同时进行恢复操作.这样的设计改善了Cheap Paxos算法恢复慢、可用性差等缺陷.

在Multi-Paxos算法中，客户端将请求先提交给领导者，然后再由领导者转发给其他的接受者.Fast Paxos[19]算法则认为：从本质上，领导者只应该起到协调的作用，客户端本身更清楚提案的内容.Fast Paxos算法提出客户端应该直接将提案发送给接受者，在没有冲突的情况下通信1轮直接提交，在有冲突的情况下，交由领导者协调处理，领导者协调完毕后在下1轮通信中完成提交.Fast Paxos算法因为不容易被理解以及实现过程比较复杂，很少被使用.这些改进实质上可以看作是对于Paxos算法思想的一种延伸.

4.2 结合硬件特性的优化

当前，越来越多的研究人员开始关注共识算法结合网络环境和特定硬件的研究.随着RDMA网络技术的发展，类Paxos共识算法在设计和实现过程中出现了新的变化.Poke等人[20]基于RDMA原语设计了新的共识算法DARE.DARE算法跟Raft类似分为3个阶段：领导者选取、日志复制和集群成员更新.主要贡献在于引入了RDMA单边操作：Read和Write.因为旁路服务端的单边通信模式跟以往的双边通信模式有所区别，所以DARE重新设计了Raft共识算法.有效利用了RDMA单边操作低延时的特性，使得副本状态机的性能有了大幅度提升.

Wang等人[21]基于RDMA 原语实现了Multi-Paxos算法APUS.与DARE的不同之处在于APUS主要为通用服务器程序设计，而DARE主要是用于维护小型简单的键值存储.其次由于DARE中领导者进程负担所有的过程，完全旁路其他副本进程，因此当客户端连接数增多时，DARE会有严重的性能下降.APUS比DARE拥有更好的可扩展性，它采用了selective signaling[22]技术，领导者进程不必一直轮询完成事件队列(completion queue)获取网卡的操作完成信号.此外，DARE中为了实现超低的请求延时，把所有数据都存在内存中.APUS把日志数据都持久化到SSD硬盘中去，是一个通用型可持久化的系统.

另一方面，分布式共识算法的实现跟网络状态和性能密不可分，对网络性能和稳定性有着比较高的要求.研究人员发现在网络数据传输过程中，有很多时间花费在操作系统网络协议栈上，因此部分研究人员渐渐开始关注类Paxos共识算法在网络设备中实现的研究.Speculative Paxos[23]使用可预测的网络行为来改善Paxos算法的性能.它有效将IP多播、固定长度的网络拓扑结构以及作为消息序列器的单个顶端交换机等技术组合在一起，消除了数据中心网络中的重排现象.这个方法引入了MOM(mostly-ordered multicast)原语，可以最大程度上保证：所有接收者接收到的来自不同发送者的消息拥有一致性的顺序，这使得数据中心中的网络行为处于可预测状态，客户端的请求能够在尽可能少的通信开销内被提交并执行.

NetPaxos[24]主要提供了在SDN网络交换机中，利用网络中的消息顺序实现整个Paxos算法全部逻辑的详细设计.同时，也表明了在不更改OpenFlow[25]API接口的情况下，仅仅依赖网络交换机设备特性实现乐观控制协议的可行性.它与Speculative Paxos最大的不同之处在于交换机设备本身会作为共识算法中的角色，共识算法逻辑运行在交换机中.Speculative Paxos只是利用网络设备特性去优化Paxos算法，共识算法相关逻辑还需要运行在服务器上.

与Speculative Paxos类似，NOPaxos[26](network ordered Paxos)也是将共识问题分为2个部分：1)网络;2)共识算法.Paxos算法的基本假设是网络消息可以是乱序的、不可靠的.NOPaxos的思路是设计一个OUM (ordered unreliable multicast)原语,在网络层面上提供有序不可靠的传输，这样的原语在数据中心网络中带来的开销近乎为零.有了这个原语，NOPaxos就可以利用消息传递过程中的有序性来减少协同过程中所需要的通信操作.在应用层面只需要考虑网络丢包情况即可.解决了乱序问题以后，达成共识就变得相对简单，开销也变得更小.当然和Speculative Paxos一样，NOPaxos也依赖于数据中心固定网络拓扑结构以及可靠性网络等特性，因此不具备很好的通用性.NOPaxos和Speculative Paxos的不同之处在于，OUM保证了消息的有序性，而MOM只是最大程度上保证消息的有序性.NOPaxos只需要简单的多数派(即过半)，但是Speculative Paxos需要更大的多数派，也就意味着性能方面延时会比NOPaxos高.比较遗憾的是OUM需要更多网络技术方面的支持，需要网络设备提供可编程的数据层.MOM可以只需要设备支持OpenFlow协议即可.

除了修改交换机之外，István等人[27]认为共识算法在解决共识问题过程中所带来的协同通信的开销往往是让人无法接受的，因此在实际使用过程中不得不做一些取舍，比如容忍部分数据丢失和数据不一致，以降低协同过程带来的开销.因此，为了更高效地解决共识问题，他们把共识算法做到硬件中，用硬件的独特优势来实现高性能共识算法.为了验证这一想法的可行性，他们在FPGA中实现了ZAB算法，比原有ZooKeeper系统拥有更好更稳定的性能.同时因为不跟特定交换机设备相关，他们设计的硬件中间件可以适应不同的网络，具有良好的可移植性.

5 类Paxos共识算法的应用现状

在应用方面，Paxos算法用以解决数据一致性与可靠性被工业界普遍接受与认可.使用Paxos算法的键值存储、数据库、分布式文件系统以及分布式消息队列等系统越来越多.工程实践角度，Chandra等人[11]就如何使用Paxos 算法实现分布式共识系统给出了详细的工程细节.

1) 键值存储系统方面.开源的ZooKeeper，etcd在业界已经被广泛使用多年.ZooKeeper作为一种分布式协同服务解决了很多分布式情况下如分布式锁等问题，成为了分布式系统架构中不可缺少的一个组成部分.

2) 数据库系统方面.MySQL提出了基于Mencius算法的状态机复制MGR(MySQL group replication)技术代替了原有系统的主备架构.MGR支持多节点写入的同时保证数据一致性以及高可用性，还避免了主备系统的脑裂问题.架构上，数据库的并发控制和共识算法属于不同的层次.分层的方法带来的问题是引入2次协同操作：1)用于并发控制中确保事务的一致性;2)用于数据存储副本之间达成共识一致.由于数据库的并发控制协议与共识算法存在着相似性，MDCC[28]，TAPIR[29]，Janus[30]等协议尝试将分布式共识算法和并发控制协议融合到一起实现分布式数据库的容错.这样的方式解决了数据库事务和数据副本的一致性问题，将协同次数减少为1次.

3) 文件系统方面.Ceph分布式文件系统采用Paxos算法用以维护集群元信息并负责元信息的更新.元信息包括记录数据分布的OSDMap、记录集群监控状态的MonitorMap以及集群中其他的必要信息.由于系统可扩展性以及集群配置管理等问题，GlusterFS也决定在下一版本中采用etcd系统存储集群配置信息.

4) 分布式消息队列方面.Kafka作为分布式消息系统对比传统的消息系统性能和可靠性有大幅提升.Kafka领导者选举过程使用了ZooKeeper，同时底层的数据复制也用到共识相关技术.腾讯云基于Raft算法实现了一个高可靠、强一致性的分布式消息队列CMQ，主要服务于订单、交易类业务场景，在特定情况下保证消息的严格有序.

6 讨 论

在未来的类Paxos算法的研究和应用中，主要可以从3个方面着手.

1) 对RDMA网络的使用.RDMA网络拥有着高吞吐、低延时的特性，利用这一特性，可以有效提高算法在实用系统中的性能.尽管算法在协同通信的轮次上没有变化，但是因为网络本身的特性，通信开销变小了.如何利用好RDMA特性，需要针对具体算法进行设计.

2) 对可编程网络的使用.对于类Paxos共识算法的实现来说，网络环境的重要性毋庸置疑.网络中，数据包的可控制程度也决定了算法设计以及实现过程所需要考虑情况的多少.可编程网络使得网络行为变得可控，给类Paxos共识算法的设计实现提供了便利条件.同时也给系统设计人员提出2个要求：①对于网络环境和设备特性的了解;②需要根据可编程网络自身的特性，对类Paxos共识算法进行重新设计.

3) 特定硬件，因为多机共识问题的重要性，设计特定硬件以高效解决共识问题也是一个值得关注的方向.

同时，丰富多样的应用场景也对类Paxos算法提出了新的要求.因为应用场景的不同，对于可靠性、可用性的要求有高有低.在设计算法过程中，针对具体应用场景进行优化，也将使得类Paxos共识算法更好地发挥作用.关于强领导者和弱领导者算法的选取则依赖于在不同场景下的取舍.比如在一个数据中心内部，或者说在同一机柜上的几台机器之间做副本状态机.在这种情况下网络环境相对稳定，也不存在请求跨域的问题.如果单个领导者不会成为应用的瓶颈，可以考虑采用强领导者共识算法.当然在跨数据中心之间做副本状态机，弱领导者共识算法就显得比较有优势.因此，类Paxos算法设计和实现也渐渐地与应用场景结合更加紧密.

综上，类Paxos共识算法有两大热点方向：1)类Paxos算法在不同网络环境、网络设备以及不同硬件条件下的实现;2)针对具体应用场景如数据库系统等，设计新的类Paxos算法解决分布式可靠性和一致性等问题.

7 结 论

分布式共识算法是构建分布式服务中一个必不可少的组成部分.本文从分布式类Paxos共识算法历史发展的角度，阐述了在解决共识问题上，类Paxos共识算法在演进过程中的变化.同时，也详细介绍了在演进过程中4种关键的算法，并且对算法演进过程、分类以及适用场景、优缺点等进行了归纳和分析.在本文的后半部分，还简要介绍了类Paxos共识算法在研究与应用方面的现状.随着集群规模以及业务需求的发展，相信在不久的将来使用分布式共识算法的应用越来越广泛，也期待随着网络技术、硬件技术的发展，类Paxos共识算法的设计、实现以及应用会有越来越多新的突破.