4.6.1　Paxos算法

1988年，Brian M.Oki和Barbara H.Liskov在论文“Viewstamped Replication:A New Primary Copy Method to Support Highly-Available Distributed Systems”中首次提出了解决Paxos问题的算法。

1990年，Leslie Lamport在论文“The Part-time Parliament”中提出了Paxos共识算法，从工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现一致）的机制。Paxos共识算法本质上与前者相同，被广泛应用在Chubby、ZooKeeper这样的分布式系统中。Leslie Lamport作为分布式系统领域的早期研究者，因为其杰出贡献获得了2013年度图灵奖。

Leslie Lamport在论文中为了描述问题虚构了一个故事：在古代爱琴海的Paxos岛，议会用表决的方式来达成共识。议员们通过信使传递消息来对议案进行表决，但议员可能离开，信使可能走丢，甚至重复传递消息。

Paxos是首个得到证明并被广泛应用的共识算法，其原理类似于“两阶段提交”算法，但进行了泛化和扩展，并通过消息传递来逐步消除系统中的不确定状态。

作为后来很多共识算法（如Raft、ZAB等）的基础，Paxos算法基本思想并不复杂，但最初论文中的描述比较难懂，甚至发表也几经波折。2001年，Leslie Lamport还专门发表论文“Paxos Made Simple”进行重新解释。

注意

Leslie Lamport对密码学也有研究，1979年提出的多Hash签名机制，具备抗量子计算攻击特性。

1.基本原理

算法中存在三种逻辑角色的节点，在实现中同一节点可以担任多个角色。

●提案者（proposer）：提出一个提案，等待大家批准（chosen）为决议（value）。系统中提案都拥有一个自增的唯一提案号。往往由客户端担任该角色。

●接受者（acceptor）：负责对提案进行投票，接受（accept）提案。往往由服务端担任该角色。

●学习者（learner）：获取批准结果，并帮忙传播，不参与投票过程。可为客户端或服务端。

算法需要满足安全性（safety）和存活性（liveness）两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的。

●safety：保证决议（value）结果是对的，无歧义的，不会出现错误情况。

　•只有是被提案者提出的提案才可能被最终批准；

　•在一次执行中，只批准（chosen）一个最终决议。被多数接受（accept）的结果成为决议。

●liveness：保证决议过程能在有限时间内完成。

　•决议总会产生，并且学习者能获得被批准的决议。

基本思路类似于两阶段提交：多个提案者先要争取到提案的权利（得到大多数接受者的支持）；成功的提案者发送提案给所有人进行确认，得到大部分人确认的提案成为批准的决议。

Paxos并不保证系统总处在一致的状态。但由于每次达成共识至少有超过一半的节点参与，这样最终整个系统都会获知共识结果。一个潜在的问题是，提案者在提案过程中出现故障，这可以通过超时机制来缓解。在极为凑巧的情况下，每次新一轮提案的提案者都恰好故障，又或者两个提案者恰好依次提出更新的提案，则导致活锁，系统会永远无法达成共识（实际发生概率很小）。

Paxos可以保证在超过一半的节点正常工作时，系统总能以较大概率达成共识。读者可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案，会发现在满足各种约束情况下，算法过程总会十分类似于Paxos的过程。因此，Google Chubby的作者Mike Burrows说：“这个世界上只有一种一致性算法，那就是Paxos。”

下面，由简单情况逐步推广到一般情况来探讨算法过程。

2.单个提案者+多接受者

如果系统中限定只允许某个特定节点是提案者，那么共识结果很容易达成（只有一个方案，要么达成，要么失败）。提案者只要收到了来自多数接受者的投票，即可认为通过，因为系统中不存在其他的提案。

但此时一旦提案者故障，则整个系统无法工作。

3.多个提案者+单个接受者

限定某个特定节点作为接受者。这种情况下，共识也很容易达成，接受者收到多个提案，选第一个提案作为决议，发送给其他提案者即可。

缺陷是容易发生单点故障，包括接受者故障或首个提案者节点故障。

以上两种情形其实类似于主从模式，虽然不那么可靠，但因为原理简单而被广泛采用。

当提案者和接受者都推广到多个，会出现一些挑战。

4.多个提案者+多个接受者

既然限定单提案者或单接受者都会出现故障，那么就得允许出现多个提案者和多个接受者。问题一下子变得复杂了。

一种情况是同一时间片段（如一个提案周期）内只有一个提案者，这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生，例如按照时间、序列，或者大家猜拳（出一个参数来比较）之类。考虑到分布式系统要处理的工作量很大，这个过程要尽量高效，满足这一条件的机制非常难设计。

另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案，怎么对它们进行区分呢？这时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的，提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大（往往意味着是接受新提出的，因为旧提案者故障概率更大）的提案。

如何为提案分配序号呢？一种可能方案是将每个节点的提案数字区间彼此隔离，互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。

同时允许多个提案，意味着很可能单个提案人无法集齐足够多的投票；另一方面，提案者即便收到了多数接受者的投票，也不敢说就一定通过，因为在此过程中投票者无法获知其他投票人的结果，也无法确认提案人是否收到了自己的投票。因此，需要实现两个阶段的提交过程。

5.两阶段的提交

提案者发出提案申请之后，会收到来自接受者的反馈。一种结果是提案被大多数接受者接受了，一种结果是没被接受。没被接受的话，可以过一会再重试。即便收到来自大多数接受者的答复，也不能认为就最终确认了。因为这些接受者自己并不知道自己刚答复的提案可以构成大多数的一致意见。

很自然，需要引入新的一个阶段，即提案者在第一阶段拿到所有的反馈后，再次判断这个提案是否得到大多数的支持，如果支持则需要对其进行最终确认。

Paxos里对这两个阶段分别命名为“准备”（prepare）和“提交”（commit）。准备阶段通过锁来解决对哪个提案内容进行确认的问题；提交阶段解决大多数确认最终值的问题。

准备阶段

●提案者向多个接受者发送计划提交的提案编号n，试探是否可以锁定多数接受者的支持。

●接受者i检查回复过的提案的最大编号Mi。如果n>Mi，则向提案者返回接受（accept）的最大编号的提案Pi（如果还未接受过任何提案，则为空），并不再接受小于n的提案，更新Mi=n。

提交阶段

●提案者如果收到大多数的回复（表示大部分人收到了n），则准备发出带有n的接受消息。如果回复中带有提案Pi，则替换选编号最大的Pi的值为提案值；否则指定一个新提案值。如果没收到大多数回复，则再次发出请求。

●接受者i收到接受消息（带有序号n）后，如果发现n≥Pi的序号，则接受提案，并更新Pi序号为n。

一旦多数接受者接受了共同的提案值，则形成决议，成为最终确认。之后可以开始新一轮的提交确认。