世上只有一种一致性算法，那就是Paxos ，所有其它一致性算法都是Paxos算法的不完整版！

作者：向彪-Blockchain

前言

最近在研究Paxos算法，提到分布式算法，就不得不提 Paxos 算法，在过去几十年里，它基本上是分布式共识的代名词，因为当前最常用的一批共识算法都是基于它改进的。比如，Fast Paxos 算法、Cheap Paxos 算法、Raft 算法等等。看了许多相关的文章，概念还是比较模糊，这其实侧面说明了 Paxos 算法有一定的难度，可分布式算法本身就很复杂。这里整理一下相关的概念便于自己的理解。

概述

Paxos 算法是莱斯利·兰伯特（Leslie Lamport，现就职于微软研究院）于1990年提出的，是一种基于消息传递的一致性算法。莱斯利·兰伯特于2013年获得了图灵奖。他的分布式计算理论奠定了这门学科的基础。莱斯利·兰伯特在1978年发表了论文《分布式系统内的时间、时钟事件顺序》(Time, Clocks, and the Ordering of Events in a Distributed System)，这篇论文成为目前计算机科学史上被引用最多的文献。他的论文为并发系统的规范与验证课题的研究贡献了核心原理。Paxos算法是在莱斯利·兰伯特的论文The Part-Time Parliament中提出的。在论文中，他以故事的方式讲述了Paxos 算法。

故事如下：

   古希腊有一个叫 Paxos的岛屿，是爱琴海上的一个小岛，Paxos是一个兴盛的商业贸易中心。在这个岛屿上，法律的制定与修订通过议会表决的形式进行，而非传统的神权统治。所有法律都必须经由议会成员投票表决后才能生效实施，而且已通过的律法必须被记录在案。
   在岛上，商业繁荣，做生意赚钱才是头等大事，因此没有人愿意始终在议会大厅里从头到尾参与每一个法律表决的会议。为此，每一个议员都来维护一个法律律簿，用来记录一系列已通过的法令，每个法令带有一个唯一编号。为了保持各个议员法律律簿内容的一致性，法律律簿是用擦不掉的墨水书写而成的，所以内容一旦书写就不能改变。
   在议会中有多个角色的成员:议员和服务员。服务员的工作是在比较嘈杂的议会厅里传递信息，议员的工作是发起法律提案或将通过的法律记录在自己的法律律簿上。

    由于议员和服务员有可能并不可靠，他们可能随时会因为各种事情临时甚至是彻底离开议会大厅，服务员也有可能重复传递消息，当然也可能有新的议员在临时事务处理完毕后再回到议会大厅进行法律表决，因此议会的协议要求保证在上述情况下能够正确地修订法律并且不会产生冲突。
 

分析

Paxos算法解决的问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致。

Paxos算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

一个或多个提议进程 (Proposer) 可以发起提案 (Proposal)，Paxos算法使所有提案中的某一个提案，在所有进程中达成一致。系统中的多数派同时认可该提案，即达成了一致。最多只针对一个确定的提案达成一致。

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

• Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。

• Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。

在多副本状态机中，每个副本同时具有Proposer、Acceptor、Learner三种角色。

Paxos算法中的角色

Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：

1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。

2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。

3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

Paxos算法流程

Paxos算法流程中的每条消息描述如下：

• Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。

• Promise: Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。

两个承诺：

1. 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。

2. 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。

一个应答：

不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。

• Propose: Proposer 收到多数Acceptors的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案Value均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptors发送Propose请求。

• Accept: Acceptor收到Propose请求后，在不违背自己之前作出的承诺下，接受并持久化当前Proposal ID和提案Value。

• Learn: Proposer收到多数Acceptors的Accept后，决议形成，将形成的决议发送给所有Learners。

Paxos算法伪代码描述如下：

Paxos算法伪代码

1. 获取一个Proposal ID n，为了保证Proposal ID唯一，可采用时间戳+Server ID生成；

2. Proposer向所有Acceptors广播Prepare(n)请求；

3. Acceptor比较n和minProposal，如果n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；

4. Proposer接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，否则可以任意决定本次提案的value；

5. 到这里可以进入第二阶段，广播Accept (n,value) 到所有节点；

6. Acceptor比较n和minProposal，如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回minProposal。

7. 提议者接收到过半数请求后，如果发现有返回值result >n，表示有更新的提议，跳转到1；否则value达成一致。

下面举几个例子，实例1如下图：

Paxos算法实例1

图中P代表Prepare阶段，A代表Accept阶段。3.1代表Proposal ID为3.1，其中3为时间戳，1为Server ID。X和Y代表提议Value。

实例1中P 3.1达成多数派，其Value(X)被Accept，然后P 4.5学习到Value(X)，并Accept。

Paxos算法实例2

实例2中P 3.1没有被多数派Accept（只有S3 Accept），但是被P 4.5学习到，P 4.5将自己的Value由Y替换为X，Accept（X）。

Paxos算法实例3

实例3中P 3.1没有被多数派Accept（只有S1 Accept），同时也没有被P 4.5学习到。由于P 4.5 Propose的所有应答，均未返回Value，则P 4.5可以Accept自己的Value (Y)。后续P 3.1的Accept (X) 会失败，已经Accept的S1，会被覆盖。

Paxos算法可能形成活锁而永远不会结束，如下图实例所示：

Paxos算法形成活锁

回顾两个承诺之一，Acceptor不再应答Proposal ID小于等于当前请求的Prepare请求。意味着需要应答Proposal ID大于当前请求的Prepare请求。

两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）。

参考文章:https://zhuanlan.zhihu.com/p/31780743

总结

　　Paxos算法是保证在分布式系统中写操作能够顺利进行，保证系统中大多数状态是一致的，没有机会看到不一致，因此，Paxos算法的特点是一致性>可用性。vector clock向量时钟是另外一种保证复制的算法，其特点是可用性>一致性，但是，一旦发生冲突，不像Paxos能自行解决，需要人工干预编写代码解决。Paxos算法和Vector Clock都是由Leslie Lamport提出。