什么是paxos？

Paxos是用于解决分布式系统中一致性问题的共识算法（Consensus Algorithm），其最基本的功能是为了在多个进程之间对某个值达成一致。通过这个最基本功能，就可以在多个进程之间进行数据库、状态机、账本（区块链）等对象的同步。

注意，Paxos不追求值的正确性、权威性、及时性，只追求一致性。

“共识”这个词不仅仅指结果，而且还代表不同进程对于各种处理达成的协议于限制。

Paxos的推导与理解过程比较晦涩难懂，每个人学习之后都会有自己的理解角度，下文是个人经过一个礼拜学习之后自己的一些简单理解，整理记录下来。

基本概念与角色

ID：相互不冲突的提案编号，用于区分不同轮次的提案。

Value：提案的值，即最后试图达成共识的候选结果。

Proposer：提案发起者，用于提出议案，提案的内容为：令 x=value，对同一轮提案，最多提议一个value 。Proposer角度看，提案分为两个阶段：Prepare阶段、Propose阶段。一轮提案的value不一定非要是Proposer自己提议的value。

Acceptor：提案投票者，有 N 个。Proposer 提出的 x=value 提案必须获得超过半数(N/2+1)的 Acceptor接受后才能被chosen。Acceptor 之间完全对等，在独立的时间轴执行提案投票。从Acceptor角度看，投票分两阶段进行：Promise阶段、Accept阶段。

Learner：提案学习者。一个提案超过半数accpetor通过即可被chosen，其他未确定的Acceptor可以通过learner来同步结果。

协议流程

以下流程针对每个进程（多个Proposer、多个Acceptor）都是独立执行的，进程之间的处理逻辑可能是顺序执行的，也可能是交错的，这就带来了整体的不确定性。Paxos就是通过增加各种约束处理条件，降低不确定性，使得多进程之间通过多轮投票，最终能够达成一致。

Prepare阶段

---

A：Proposer选择一个提案编号n，向所有的Acceptor广播Prepare（n）请求。

B：Acceptor收到Prepare（n）请求，若提案编号n比之前接收的Prepare请求都要大，则承诺（Promise，将n记录下来）将不会接收提案编号比n小的提议，并且带上之前Accept的提议中编号小于n的最大的提案value。如果n比之前接受的提案编号小，则不予理会。

Propose阶段

---

A：Proposer收到Acceptor的Promise

如果未超过半数的accpetor回复承诺（Promise），本次提案失败；

如果超过半数的Acceptor回复承诺，又分为不同情况：

如果（回复承诺的）所有Acceptor都未接收过value（都为null），那么向所有的Acceptor发起（Propose）自己的value和提案编号n。

如果有部分Acceptor接收过value，那么从接受过的value中选择提案编号最大的value作为本次提案的value，提议编号仍然为n（即：此时Proposer不能提议自己的value，只能信任Acceptor通过的value，以达成收敛的效果。）

B：Acceptor接收到提议后，如果该提案编号不等于自身当前承诺的编号（第一阶段记录的），不接受该请求，相等则将提案的value写入本地。

如何理解？

Leslie Lamport的论文《Paxos made simple》是通过一步步的问题推导，缩写约束范围来解释并数学证明Paxos的，虽然严格但还是比较抽象，理解起来还是比较吃力。

示意图

分布式抢占锁

---

个人更愿意把Paxos理解成一个分布式抢占锁机制。

传统上在非分布式环境中，我们往往用事务来维护系统的一致性。而Lock机制是最常用的一种控制数据有序修改的手段，因此，数据的修改可以分为两个阶段：加锁阶段（多个Proposer根据在单个Acceptor️收到加锁请求的时间先后顺序占用锁，此时系统有全局时钟）、修改阶段（并释放锁）。在Paxos中，Prepare阶段可以理解为Proposer向Acceptors集合请求加锁阶段，Propose阶段相当于修改阶段，以这样的角度看，就不会对为什么Paxos设计成两阶段协议有太多疑惑了。

但对于分布式系统而言，除了缺乏全局时钟外，还有容错问题：修改者与资源都会有多个副本，并且都有可能失效。对于Paxos而言，则表现为：

（1）Acceptor有多个，因此Paxos要求提案获得大多数Acceptor的Promise，才算加锁成功；这也比较好理解：如果小于半数，则可能存在两个提案同时加锁的情况。

（2）每个Proposer都有可能失效，不能影响其他Proposer工作。传统的独占锁在获得锁定权的Proposer失效时会导致系统死锁，因此不符合要求，因此Paxos选择将独占锁改成抢占锁机制，这意味着需要引入某种可以全局有效的抢占机制。

为了全局性的对提案进行排序，Paxos引入提案编号概念，编号由每个Proposer本地产生并且递增，具有全局唯一性并且可比较排序。Paxos规定高编号的提案可以抢占编号低的提案的锁（反过来也行，但总需要一个排序规则），使得低编号提案加锁失败（无法完成大多数Acceptor的提案确认），这样就不会出现某个Proposer的失效导致的死锁情况的发生（为什么要抢占？因为Proposer之间是孤立的，而且你永远不知道某个Proposer会在何时失效）。

如何理解提案编号的概念？相当于Paxos人为的为分布式系统设定了一个非集中式的全局时钟，所有的Acceptor进程均认可这种事先安排的顺序对提案的抢占锁进行处理。即然是时钟，前面发生的提案就不能跑到后面来处理。这个时钟在不同Acceptor之间并不精确同步，只能保证每个Acceptor节点以一种有序的方式处理Proposer对锁的抢占，保证每个Accepor上每个提案不受低编号的影响，而只受高编号的影响，以最快的在Acceptor集合内达成提案的收敛。

从Proposer角度看，所有编号的提案，都在快马加鞭的试图尽快的加锁（prepare）并获得大多数Acceptors的确认（accept），以免被更高ID的提案给抢占。Proposer之间没有任何协调机制，只能通过Acceptors完成有限交流（低编号提案value向高编号提案的传播）

由于每个Paxos过程会以各种组合交叉在一起，局面会比较复杂，我们抽丝剥茧后，可以确定的是，只会有一个提案的value会最终会被加锁并被大多数Acceptors确认。原因如下：

首先，从Acceptors集合角度来看，任何时候他们只能承诺最多一个提案：因为每个Acceptor同时只能承诺一个提案，任何时刻其承诺某一个提案的大多数的集合必然只有一个。

成功的加锁是成功的确认的基础，同时拒绝了更小编号的提案成功确认的可能性，降低了来自低编号提案的不确定性。

Proposer需要在成功的加锁之后，在更大编号的提案抢占锁之前，完成大多数Acceptor的确认。

一旦该编号n的提案加锁并经过大多数Acceptor确认成功后，更大编号的提案如果能抢占锁成功，则必然能够学习到编号n提案的value，因为大多数集合之间必然有交集。如果更大编号的提案没有抢占锁成功，则不会给Acceptors集合增加任何新的可供选择的value，编号n的提案的值，仍然是编号最大的值。

更大编号的提案学习到编号n的提案后，做为自己的提案内容。依次迭代，后续提案也是如此，必然达成一致。

因此，我们需要做的就是等待某个提案的value（可能是一次确认，也可能是逐渐收敛）成功获得大多数Acceptors确认而胜出。

那么，会不会有可能永远无法有提案胜出呢？有可能，比如提案轮流抢占锁，但都在Propose前被下一个提案抢占，就永远无法有提案胜出了（活锁），解决方法就是：随机等待，重新发起提案。

（类似的活锁情况还有很多种，例如：不同提案之间永远在相同的Acceptors之间争夺承诺但都无法及时写入value。或者每次一个Acceptor确认一个value后就被隔离分区，后续提案再也接触不到，到达一半后，系统再也无法达成大多数，但只要某个分区能够有大多数Acceptor存在，都可以达成一致。）

因此，只要有足够的时间让一个提案获得大多数Acceptors确认就不会有一致性问题。

（以上是自己分析协议流程后的理解，接触时间短，水平有限，不排除有根本性理解错误。Lamport的论文没有彻底研究透，待后续补充修改。）