paxos算法是莱利斯·兰伯特于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。是目前公认的解决分布式一致性问题最有效的算法之一。在常见的分布式系统中，总会发生机器宕机或者网络异常等情况。paxos算法就是要解决就是如果在一个会发生上述异常的分布式系统中，快速且正确的在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

1. 历史故事

1982年，lamport与另外两人共同发表了论文The Byzantine Generals Problem，提出了一种计算机容错理论。在理论描述过程中，为了能更加形象的表达，lamport设想了下面一种场景：

拜占庭帝国有多支军队，不同军队的将军之间要指定统一的行动计划，从而选择做出进攻或者撤退的决定，同时，各个将军在地理上都是被隔离开来的，只能依靠军队的通讯员进行通信。然而在所有的通讯员中可能会存在叛徒，这些叛徒可以任意篡改消息，从而达到欺骗将军的目的。

这就是著名的拜占庭将军问题，从理论上来说，在分布式计算领域，试图在异步系统和不可靠的信道上达成一致状态是不可能的，所以在研究的过程中，往往假设信道是可靠的。实际情况中，部署在同一个局域网的集群，消息被篡改的情况是非常罕见的。另一方面，由于硬件或者网络异常导致的消息不完整性，通过一套简单的校验算法即可避免。因此在实际工程实践中，可以假设不存在拜占庭将军问题，也就是说所有消息都是完整的，没有被篡改过。那么在这种情况下需要什么样的算法来保证一致性呢？

Lamport在1990年提出了一种理论上的一致性解决方案，同时给出了严格的数学证明。这次Lamport又精心设想了一个场景来描述这种一致性算法所要解决的问题以及具体的解决过程。

在古希腊有个叫paxos的小岛，岛上采用议会的形式通过法令，议会中的议员通过信使传进行消息传递，值得注意的是，信使和议员都是兼职的，他们可能随时离开议会厅，并且信使可能会重复的传递消息，也可能一去不复还，因此，议会协议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突

这就是论文The Part-time parliament中提到的兼职议会，而paxos算法名称也取自故事中小岛的名称

2. paxos理论的诞生

先介绍一下paxos算法的作者Leslie Lamport，2013年图灵奖得主，在计算机领域具有杰出成就的传奇人物，先后多次荣获ACM和IEEE以及其他计算机重大奖项。Lamport对时间时钟、面包店算法、拜占庭将军问题以及paxos算法的创造性研究，极大的推动了计算机科学尤其是分布式计算的发展，全世界无数的工程师得益于他的理论，paxos算法的推出，正是他多年的研究成果。

Lamport早在1990就将其对paxos的研究论文The Part-Time Parliament提交给了ACM TOCS jnl. 的评审委员会了。但是Lamport使用了故事的方式来进行算法描述，导致委员会的工作人员没有一个人能够正确的理解他的算法，要求用严格的数据证明描述算法，但是Lamport认为他的描述没有问题，拒绝修改。

幸运的是，还是有人能够理解他那令人晦涩的算法描述。1996年，微软的Butler Lampson 在WDAG96上提出了重审这篇论文的建议，次年在WDAG97上，麻省理工学院的Nancy Lynch 也公布了其根据Lamport原文重新修改后的Revisiting the Paxos Algorithm，帮助Lamport以数学的形式化术语定义并证明了paxos算法。于是在1998年的ACM TOCS上，这篇论文终于被接受。也标志着paxos算法正式被计算机科学接受并影响更多的工程师解决分布式一致性问题。

后来在2001年，Lamport本人做出了让步，他放弃了故事的描述方式，使用通俗易懂的语言重新讲述了全文，并发表了Paxos Mode Simple

3. 算法详解

3.1. 问题描述

假设有一组可以提出提案的进程集合，那么对于一个一致性算法来说需要保证以下几点：

• 在这些被提出的提案中，只有一个会被选定
• 如果没有提案被提出，那么就不会有被选定的提案
• 当一个提案被选定后，进程可以获取被选定的提案信息

对于一致性来说，安全性需求如下：

• 只有被提出的提案才能被选定
• 只能由一个值被选定
• 如果某个进程认为某个提案被选定了，那么这个提案是真的被选定的那个

Paxos算法的目标就是要保证最终有一个提案会被选定，当提案被选定后，进程也能最终获取到被选定的提案。

在该一致性算法中，有三种参与角色，我们用Proposer、Accepter和Learner来表示。在具体的实现中，一个进程可能充当不止一种角色，这里我们不关心进程如何映射到角色，假设不同参与者之间通过消息传递进行通信，那么：

• 每个参与者以任意的速度执行，可能因为出错而停止，也可能会重启。即使一个提案被选定后，所有的参与者都有可能失败或者重启。因此除非那些失败或者重启的参与者可以记录某些信息，否则将无法确定最终的值
• 消息在传递过程中可能会出现无法预知的延迟，也可能会重复或丢失，但是消息不会被损坏，即消息内容不会被篡改（拜占庭式的问题）

3.2. 提案的选定

要选定一个唯一提案最简单的方式莫过于只允许一个Accepter存在，这样的话，proposer只发送提案给该Accepter，Accepter会选择它接收到的第一个提案作为被选定的提案。这种方式实现简单，但是当Accepter出现问题的时候，整个系统就无法工作了。

因此要寻找一种更好的解决方案，例如使用多个Accepter来避免单点问题。假如是这种方式，具体的方案是：
Proposer向一个Accepter集合发送提案，同样，集合中的每个Accepter都可能会批准提案，当有足够多的Accepter批准这个提案时，我们就认为该提案被选定了。

那么什么是足够多呢，我们假定足够多的Accepter是整个Accepter集合的一个子集，并且这个子集大的可以包含Accepter集合中的大部分成员。另外我们再规定，每一个Accepter最多只能批准一个提案，那么就能保证只有一个提案被选定了。

3.3. 推导过程

在没有失败和消息丢失的情况下，如果我们希望即使只有提案被提出的情况下，仍然可以选出一个提案，这就暗示了如下的需求。

P1：一个Accepter必须批准它收到的第一个提案

上面的需求引出了另一个问题：如果有多个提案被不同的Proposer同时提出，这时候虽然每个Accepter都批准了它收到的第一个提案，但是没有一个提案是被批准最多的。此时就无法确定最终的提案。

因此在P1的基础上，再加上一个提案被选定需要由半数以上的Accepter批准的需求暗示着每个Accepter能够批准不止一个提案。在这里，我们使用一个全局的编号来标识每一个被Accepter批准的提案，当一个某value的提案被半数以上的Accepter批准后，我们认为该value被选定了，此时我们也认为该提案被选定了。需要注意的是，这里的提案和value已经不是一个概念了，提案变成了一个由提案编号和value组成的组合体了。我们以【编号，value】表示一个提案。

根据上面的内容，我们虽然允许多个提案被选定，但是同时必须要保证所有选定的提案具有相同的value值--这是一个关于提案value的约定。结合提案的编号，该约定可以定义如下：

P2：如果编号为M0、Value值为V0的提案（即[M0, V0]）被选定了，那么所有编号比M0更高的，且被选定的提案，其value值也为V0。

因为提案的编号是有序的，条件P2就保证了只有一个Value值被选定这一关键安全性属性。同时，一个提案要被选定，其首先必须被至少一个Accepter批准，因此我们可以通过满足如下条件来满足P2.

P2a： 如果编号为M0，Value值为V0的提案（即【M0，V0】）被选定了，那么所有比M0编号更高的，且被Accepter批准的提案，其Value值必须也是V0

至此，我们仍然需要P1来保证提案会被选定，但是因为通信是异步的，一个提案可能会在某个Accepter还未收到任何收到任何提案时就被选定了

因此要对P2a进行强化：

P2b：如果一个提案【M0,V0】被选定后，那么之后任何Proposer产生的编号更高的提案，其Value值都是V0

因为一个提案必须在被Proposer提出后才能被Accepter批准，因此P2b包含了P2a，进而包含了P2。于是，接下去的重点就是论证P2b成立即可：

假设某个提案【M0，V0】已经被选定了，证明任何编号Mn>M0的提案，其Value值都是V0

3.4. 数学归纳法证明

我们可以通过对Mn进行数学第二归纳法证明，也就是说需要证明以下结论：

假设编号在M0到Mn-1之间的提案，其Value值都是V0，证明编号为Mn的提案的Value值也为V0。

因为编号为M0的提案已经被选定了，这就意味着肯定存在一个由半数以上的Accepter组成的集合C，C中每一个Accepter都批准了该提案。再结合归纳假设，编号为M0的提案被选定意味着：

C中每一个Accepter都批准了一个编号在M0到Mn-1范围内的提案，并且每个编号在M0到Mn-1范围内被Accepter批准的提案，其值都为V0

因为任何包含半数以上Accepter的集合S都至少包含集合C中的一个成员，因此我们可以认为保持了下面P2c的不变性，那么编号为Mn的提案的Value也为V0。

P2c:对于任意的Mn和Vn，如果提案【Mn，Vn】被提出，那么肯定存在一个由半数以上的Accepter组成的集合S，满足以下两个条件中的任意一个

• S中不存在任何批准过编号小于Mn的提案的Accepter
• 选取S中所有Accepter批准过的编号小于Mn的提案，其中编号最大的那个的提案其Value值为Vn

至此，只需要通过保持P2c，我们就能够满足P2b了，接下来我们使用第二数学归纳法证明P2c。
首先假设提案【M0，V0】被选定了，设比该提案大的编号为【Mn，Vn】，我们需要证明在P2c的前提下，对于所有的【Mn，Vn】，存在Vn=V0。

1. 当Mn=M0+1时，如果有这样一个编号为Mn的提案，首先我们知道【M0,V0】已经被选定了，那么就一定存在一个Accepter的子集S，且S中的Accepter已经批准了小于Mn的提案，于是，Vn只能是多数集合S中编号小于Mn但为最大编号的那个提案的值，而此时因为Mn=M0+1，因此理论上编号小于Mn但为最大编号的那个提案肯定是【M0，V0】，同时由于S和通过【M0，V0】的Accepter集合都是多数集，也就是说二者肯定有交集-----这样Proposer在确定Vn取值的时候，就一定会选择V0。值得注意的是，Paxos算法的证明过程使用的是第二数学归纳法，上面实际上就是数学归纳法的第一步，验证了某个初始值成立。接下去，就需要假设编号在M0+1到Mn-1区间内时成立，并在此基础上推导出当编号为Mn时也成立。

2. 根据假设,编号在M0+1到Mn-1区间内的所有提案的Value值都为V0，需要证明的是编号为Mn的提案的Value值也为V0.根据P2c，首先同样一定存在一个Accepter的自己S，且S中的Accepter已经批准了小于Mn的提案，那么编号为Mn的提案Value值只能是这个多数集S中编号小于Mn但为最大编号的那个提案值了。如果这个最大编号落在M0+1到Mn-1区间内，那么Value值肯定是V0，如果不落在M0+1到Mn-1区间内，那么它的编号不可能比M0再小了，肯定就是M0，因为S也肯定会与批准【M0，V0】这个提案的Accepter集合S有交集，而如果编号是M0，那么它的值也是V0，由此得证。

3.5. Proposer提案生成

那么在P2c的基础上如何进行提案的生成？对于一个Proposer来说，获取那些已经被通过的提案远比预测未来可能会被通过的提案简单的多。因此Proposer在产生一个编号为Mn的提案的时候，必须要知道当前某一个将要或者已经被半数以上的Accepter批准的编号小于Mn但为最大编号的提案，并且，Proposer会要求所有的Accepter都不要再批准任何编号小于Mn的提案---这就引出了如下的提案生成算法。

1. Proposer选择一个新的提案编号Mn，然后向某个Accepter集合的成员发送请求，要求该集合中的Accepter做出如下回应。

• 向Proposer承诺，保证不再批准任何编号小于Mn的提案。
• 如果Accepter已经批准过任何提案，那么其就向Proposer反馈当前该Accepter已经批准的编号小于Mn但为最大编号的那个提案的值
  我们将该请求称为编号为Mn的提案的Prepare请求

2. 如果Proposer收到来自半数以上的Accepter的响应结果，那么它就可以产生编号为Mn，value值为Vn的提案，，这里的Vn是所有响应编号最大的提案的Value值，当然还存在一种情况，就是半数以上的Accepter都没有批准过任何提案，即响应中不包含任何的提案，那么此时Vn的值就是Proposer任意选择

在确定了提案之后，Proposer就会将该提案再次发送给Accepter集合，并期望获得他们的批准，我们称为Accepter请求。

3.6. Accepter批准提案

一个Accepter可能会收到来自Proposer的两种请求，分别是Prepare请求和Accept请求，对这两类请求分别做出如下响应：

• Prepare请求：Accepter可以在任何时候响应一个Prepare请求
• Accept请求：在不违背Accept现有承诺的前提下，可以任意响应Accept请

因此，对Accept逻辑处理的约束条件，可以定义如下：

P1a：一个Acceptor只要尚未响应过任何编号大于Mn的Prepare请求，那么它就可以接受这个编号为Mn的提案。

可以看出，P1a包含了P1，同时Paxos算法允许Accepter忽略任何请求而不用担心破坏其算法的安全性

3.7. 算法优化

但是这里还有个问题：
假设一个Accepter收到了一个编号为Mn的Prepare请求，但此时该Accepter已经对编号大于Mn的Prepare请求做出了响应，因此它肯定不会再批准任何新的编号为Mn的提案，那么显然，Accepter就没有必要对这个Prepare请求做出响应

优化方案：
Accepter选择忽略这样的Prepare请求，同时Accepter也可以忽略调那些它已经批准过的提案的Prepare请求

通过这个优化，带来了两个好处

• 每个Accepter只需要记住它已经批准的提案的最大编号以及它已经做出了Prepare请求响应的提案的最大编号，以便在出现故障或节点重启的情况下，也能保证P2c的不变性
• 对于Proposer，只要它可以保证不会产生具有相同编号的提案，那么就可以丢弃任意的提案以及它所有的运行时状态信息

3.8. 提案选定过程-算法陈述

下面对Paxos算法的提案选定过程进行陈述。
阶段一：

1. Proposer选择一个提案编号Mn，然后向Accepter的某个超过半数的子集成员发送编号为Mn的Prepare请求。
2. 如果一个Accepter受到一个编号为Mn的Prepare请求，且编号Mn大于该Accepter已经响应的所有Prepare请求的编号，那么它就将会它已经批准过的最大编号的提案作为响应反馈给Proposer，同时该Accepter承诺不会再批准任何编号小于Mn的提案。

阶段二：

1. 如果Proposer收到来自半数以上的Accepter对于其发出的编号为Mn的Prepare请求的响应，那么它就会发送一个针对【Mn，Vn】提案的Accept请求给Accepter
2. 如果Acceper收到这个针对【Mn，Vn】提案的Accept请求，只要该Accepter尚未对编号大于Mn的Prepare请求做出响应，它就可以通过这个提案。

3.9. 提案的获取

接下来看一下如何让Learner获取提案。书中介绍了三种方案，这里只介绍最优的那种方案。

Accepter可以将批准的提案发送给一个特定的Learner集合，该集合中的每一个Learner都可以再一个提案被选定后通知其他所有的Learner。这个Learner集合中的Learner个数越多，可靠性就越好，但同时网络通信的复杂度就越高

3.10. 通过选取主Proposer保证算法的活性

这个算法中还存在一点问题。
有两个Proposer依次提出了一系列编号递增的议案，但是最终都无法被选定，陷入死循环，看下具体流程：

Proposer提出了一个编号为M1的提案，并完成了上述阶段一的流程。同时另一个Proposer p2提出了一个编号为M2(M2>M1)的提案，同样完成了阶段一的流程。于是Accepter已经承诺不再批准编号小于M2的提案了。因此当P1进入阶段二的时候，其发出的Accept请求将被Acceptor忽略，于是P1再次进入阶段一并提出了一个编号为M3(M3>M2)的提案，而这又导致P2在第二阶段的Accept请求被忽略，提案选定陷入死循环。

解决方案：
选择一个主Proposer，并规定只有主Proposer才能提出议案。这样一来，只要主Proposer和过半的Acceptor能够正常通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准。

4. 小结

Paxos算法引入了过半的理念，通俗的讲就是少数服从多数的原则。同时，Paxos算法支持分布式节点角色之间的轮换，这极大的避免了分布式单点的出现，因此Paxos算法既解决了无限期等待的问题，也解决了脑裂问题，是目前最优秀的分布式一致性协议之一

来自《从paxos到zookeeper 分布式一致性原理与实战》，稍微进行了归纳总结。