大神说，世界上只有一种一致性算法，那就是Paxos。 但是大部分文章或论文的套路都差不多，先说paxos是一个完美的一致性算法，然后就给出证明等等，最后才给出实现步骤。

然而，对于我这个初学者来讲，我更希望先知道这个算法是如何工作的，然后再去研究他们的证明过程。这其实也符合学习的过程，先抛出问题，思考之后，最后看答案印证。然而大神写的Chubby并不开源，而证明过程也很数学化，很难理解在实际执行流程当某一步出现错误时，这个算法是如何保证数据的一致性的。

本文从paxos算法实际运行过程来对《Paxos Made Simple》和《The Part-Time Parliament》做一下补充。在该算法中有三种参与角色，分别用Proposer、Acceptor、Learner来表示, 下面先给出Paxos的算法执行流程（来自Paxos Made Simple)。

阶段1：（协商编号阶段)

a. Proposer选择一个提案编号为n,然后向Acceptors中的大多数人发送编号为n的Prepare请求。
b. 如果一个Acceptor收到一个编号为n的Prepare请求，且n大于它已经响应的所有Prepare请求的编号，那么他就会Promise它不会再Accept任何编号小于n的提案，同时会将它已经通过(Accept)的编号最大的的提案作为响应。（一个提案由’编号n’和’值value’组成)

阶段2：(协商提案阶段)

a. 如果Proposer收以半数以上的Acceptor对于它的Prepare请求（编号为n）的响应，那么它就会发送一个编号为n, value为v的提案的Accept请求给那些Acceptor，这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。（一个提案由(n,value)组成)

b. 如果Acceptor收到一个针对编号为n的提案Accept请求，只要它还未对编号大于n的Prepare请求作为响 应，它就可以通过这个提案。

阶段3:(选定（Choose)一个值，注：此阶段由《Paxos Made Paxos》 2.3浓缩而成)

当一个提案的Accept请求已经被大多数Acceptor接受，这个值就是被Choosen了。

下面开始分析，这个算法是如何保证一致性的。

分析1. 可能有多个Proposer同时进行, 就一定有并发问题，来看看Paxos如何解决并发问题

对于单个Acceptor, 阶段1.b可以保证提案的编号只能被用一次，而且一定是递增的。配合阶段2.b则可以保证一个ID(编号n)最终只会与一个值相对应。

这个思路有点像是无锁队列，先原子获取到队列的位置（编号n)，由于原子获取队列的位置，所以每一次获取的位置都是惟一的，这样向队列中放置值是不会有并发问题的，因为每个线程操作的其实是不一样的位置。(只不过Paxos这个队列的长度只有1个长度，永远是最大的ID（编号n)代表着这个队列的惟1位置)。而获取ID的原子性，是通过在Acceptor端保证的。

分析2. 为什么需要大多数Acceptor都同意

假设两个大多数集合分别为A和B，集合A和集合B中必然有一个公共成员(假设所有成员为X,Y,Z三个成员，集合A中成员为X,Y, 那么不管集合B如何选择，只要他的成员数大于所有成员数的一半，集合B就至少要包含集合A中的一个成员X或Y)，。由于A中成员是全部Accept了Accept请求，因此集合B中必然会有一个成员作为A中成员Accept过最新的Accept请求。

分析3. 仔细阅读论文就会发现，论文中有零星片语提到过“一个Paxos实例（instance)只能确定一个值，这个值一旦确定就永远不能更改。如果想确定多个值，需要启动多个Paxos实例（也叫MultiPaxos)”。所以下面仅仅分析一个实例如何保证这一个值是一致的。

阶段2.a保证，一旦收到的大多数Prepare的响应后（假设这个大多数为集合A)，那么发送给Acceptor的值必须为集合A中Acceptor在阶段1.b中返回的提案集合B中编号最大的提案的值。配合上面的分析2，就可以推导出阶段3的结论，因为如果一个Accept请求（携带值v)被大多数Acceptor接受，那么之后再发送任何Accept请求，其值都一定是被大多数Acceptor接受的那个提案的值。之后这个值永远不会再被变更，因此一致性得到了保证。

上面是理想情况分析，再来分析几种异常情况。

假设共有A,B,C,D,E共5个Acceptor节点，将阶段1称为
P阶段，阶段2称为A阶段, P1为第一次Prepare,P2为第二次Prepare。A1,A2同样代表第一次和第二次Accept。

1. P1（编号为n1)发送给了A,B,C三个节点，A,B节点执行并响应成功，但是节点C对P1响应失败，接着发送P2给C,D,E三个节点并且得到成功的响应。

P1的失败分为两种，一种是C节点执行P1失败了，还有一种是C节点执行P1成功了，但是对P1的响应包丢了。

如果P1执行成功了，那么C,D,E集合由于集合C的存在，就可以保证P2发出的编号n2一定是大于n1的，

如果P1执行失败了，发送给C,D,E集合的P2请求中的编号则可能与n1相同。

但是由于P1的失败导致A1并没有被请求，而是接着执行了P2。将最近一次被选定(Choosen)的提案编号称为n0，那么n2 >= n1 > n0。这并不违反Paxos协议。

2. P1（编号n1)发送给A,B,C三个节点，并且执行成功。A1发送给A,B,C三个节点后，只有C节点失败了(比如发向C节点的A1请求，在传输过程中丢失了)。

由于P1的成功，可以保证P2的编号n2一定大于n1。

A1同样有成功和失败两种可能。

当A1被执行成功，C,D,E集合在执行A2时，由于阶段2.a的存在，发送给C,D,E集合的A2请求中的值一定是节点C上在A1时被设置的值v1。

当A1被执行失败时，C,D,E集合在执行A2时，可能是一个与v1完全不同的值v2。

如果C,D,E对A2请求全部执行成功，则之后不管再发什么请求，这个值始终会为v2。

到此值v2被选定(Choosen)。

3. 继情况2之后，如果C,D,E部分成功，比如只有D和E成功了.此时A,B的值为v1,D,E的值为V2,C的值为v0（即发送P1命令之前的值)。

接下来提案的选取过程又会至少有两种情况。

如果选取了A,D,C,那么此时最终被Choosen的值为v2(因为n2>n1)。

如果选取了A,B,C,那么此时最终被Choosen的值为v1(因为n1 > n0)。

至此整个值被Choosen，整个Paxos协商过程达到稳定。

上面并没有分析多个Proposer并发请求P和A时，结果是否正确。这是因为在分析之初我们就已经确定，编号n的存在可以解决并发问题。

但是编号n只能保证并发情况下不产生错误结果，但是并不保证在并发的情况下，在有限时间内可以有某个值被Choosen这一点，也即活锁，这个可以通过选取Leader来实现。但这只是优化手段，这里就不讨论了。

比如两个Proposer按P1,P2,A1,A2这样的序列发送请求，就永远不可能最终选定一个值。

文字的描述总归是没有代码描述更具体，尤其是可以轻易运行的代码。

ps.在读两篇官方论文时，需要特别注意’accept’,’choosen’,’instance’这三个词。Accept只代表某一个Acceptor节点接受了某个提案，但是choosen代表至少大数多Acceptor都Accept了某个提案。从开始Paxos流程到最终确定一个值称一个instance,如果想确定多个值就必须通过多个Paxos Instance。