什么是Paxos算法？
Paxos算法是莱斯利·兰伯特于1990年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法。需要注意的是，Paxos常被误称为“一致性算法”。但是“一致性（consistency）”和“共识（consensus）”并不是同一个概念，Paxos是一个共识（consensus）算法。Paxos算法在工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现致）的机制，Paxos 算法被广泛应用在 Chubby、ZooKeeper 这样的分布式系统中。
为描述Paxos算法，兰伯特虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。
Paxos算法原理
Paxos算法是第一个广泛应用的共识算法，其原理基于“两阶段提交”算法并进行泛化和扩 展，通过消息传递来逐步消除系统中的不确定状态。
算法的基本原理是将节点分为三种逻辑角色，在实现上同一个节点可以担任多个角色：
Proposer （提案者）：提出一个提案，等待大家批准（ chosen ）为结案（ value ）。系统 中提案都拥有一个自增的唯一提案号。往往由客端担任该角色；
Acceptor （接受者）：负责对提案进行投票，接受（ accept ）提案。往往由服务端担任该角色；
Learner （学习者）：获取批准结果，并可以帮忙传播，不参与投过程。可能为客户端或服务端。
算法需要满足Safety和Liveness两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的：
Safety 约束：保证决议（value ）结果是对的，无歧义的，不会出现错误情况。只有是被 Proposers 提出的提案才可能被最终批准；在一次执行中，只批准（ chosen ）一个最终决议， 被多数接受（ accept ）的结果成为决议。
Liveness 约束：保证决议过程能在有限时间内完成。决议总会产生，并且学习者能获得被批准的决议。
基本过程是多个提案者先争取到提案的权利（得到大多数接受者的支持）；得到提案权 利的提案者发送提案给所有人进行确认，得到大部分人确认的提案成为批准的结案。
Paxos 不保证系统随时处在一致的状态，但由于每次达成一致的过程中至少有超过一半 的节点参与，这样最终整个系统都会获知共识的结果。一个潜在的问题是 Proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下 ，每次新一轮提案的 Proposer 都恰好故障，又或者两个 Proposer 恰好依次提出更新的提案，则导致活锁，系统永远无法 达成一致 （实际发生概率很小）。
Paxos 能保证在超过一半的节点正常工作时，系统总能以较大概率达成共识。我们可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案，会发现在满足各种约束情 况下，算法过程会十分类似于 Paxos 的过程。
下面，由简单情况逐步推广到一般情况来探讨算法过程。
1. 单个提案者＋多接受者
如果系统中限定只有某个特定节点是提案者，那么共识结果很容易能达成（只有一个方 案，要么达成，要么失败）。提案者只要收到了来自多数接受者的投票，即可认为通过，因为系统中不存在其他的提案，但此时一旦提案者故障，则系统无法工作。
2. 多个提案者＋单个接受者
限定某个节点作为接受者，这种情况下，共识也很容易达成，接受者收到多个提案， 选第一个提案作为决议，发送给其他提案者即可。缺陷也是容易发生单点故障，包括接受者故障或首个提案者节点故障。
以上两种情形其实类似主从模式，虽然不那么可靠，但因为原理简单而被广泛采用 当提案者和接受者都推广到多个的情形，会出现一些挑战。
3. 多个提案者＋多个接受者
既然限定单提案者或单接受者都会出现故障，那么就得允许出现多个提案者和多个接受者。问题一下子变得复杂了。
一种情况是同一时间片段（如一个提案周期）内只有一个提案者，这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生，例如按照时间 、序列、或者大家猜拳（出一个参数来比较）之类。考虑到分布式系统要处理的工作量很大，这个过程要尽量高效，满足这 条件的机制非常难设计。
另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案，怎么对他们进行区分呢？这个时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的，提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个， 比如 接受其中序号较大（往往意味着是接受新提出的，因为旧提案者故障概率更大）的提案。
如何为提案分配序号呢？一种可能方案是每个节点的提案数字区间彼此隔离开，互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。同时允许多个提案意味着很可能单个提案人无法集齐足够多的投票；另一方面，提案者即便收到了多数接受者的投票，也不敢说就一定通过。因为在此过程中投票者无法获知其 他投票人的结果，也无法确认提案人是否收到了自己的投票。因此，需要实现两个阶段的提交过程。
两阶段的提交
提案者发出提案申请之后，会收到来自接受者的反馈。一种结果是提案被大多数接受者接受了，一种结果是没被接受。没被接受的话，可以过会再重试。即便收到来自大多数接 受者的答复，也不能认为就最终确认了，因为这些接受者并不知道自己刚答复的提案是否可以构成大多数的一致意见。
很自然，需要引人新的一个阶段，即提案者在第一阶段拿到所有的反馈后，需要再次判断这个提案是否得到大多数的支持，如果支持则需要对其进行最终确认。
Paxos 里面对这两个阶段分别命名为准备（Prepare ）阶段和提交（ Commit）阶段。准备阶段通过锁来解决对哪个提案内容进行确认的问题，提交阶段解决大多数确认最终值的问题。
准备阶段：
提案者发送自己计划提交的提案的编号到多个接收者，试探是否可以锁定多数接收者的支持；
接受者时刻保留收到过提案的最大编号和接受的最大提案，如果收到提案号比目前保留的最大提案号还大，则返回自己已接受的提案值（如果还未接受过任何提案，则为空）给提案者，更新当前最大提案号，并说明不再接受小于最大提案号的提案。
提交阶段：
提案者如果收到大多数（大于1/2）的回复（表示大部分人听到它的请求），则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案，说明锁定成功，则使用自己的提案内容；如果返回中有提案内容，则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复，则需要再次发出请求；
接受者收到“接受消息”后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新接受的最大提案。
一旦多数接受者接受了共同的提案值，则形成决议，成为最终确认。
