说人话的PAXOS算法简介及证明

xman

PAXOS是很多分布式系统的基石，获得图灵奖的Lamport的成名作就是关于paxos的算法，这算法也是出了名的难理解，但实际上 只是那篇论文写的难以理解...程序员直接看代码的话一下就明白了， 这个算法的背景资料我就不讲了，下面直入正题。


　　PAXOS解决的问题是 在分布式环境中确定某一个 “不可变变量X” 的值。请多读几遍。


　　Paxos协议里有proposer,acceptor,learner三种角色，每中角色的扮演者都可以有多个，proposer提出关于X的值的proposal，acceptor对proposal进行表决 是否接受这个议案，learner负责统计acceptor的表决，若过半数acceptor接收了某个议案，那么关于X的值就被确定了。


　　Paxos算法能保证在过半数acceptor及至少一个proposer,一个learner存活的情况下，系统能正常运行。


　　不同learner获知最终X值的时间可能不一致,即最终一致性。


　　根据CAP理论，paxos算法杜绝了脑裂现象，并在C和A之间保留了较好的均衡性。


　　下面开始描述PAXOS算法的具体运行过程：


　　每一个Proposer提出的建议都会被编号，且这个编号是全局严格全序的。


　　(至于不同proposer怎么获得这个严格全序的议案编码不在本文讨论范围，如果确实想知道…那看懂这篇文章后，后续对PAXOS算法的拓展会提到)


　　一)proposer:


　　Proposer p1在向acceptor提出关于X的第n号议案前，都会先向每一个acceptor 发送 promise请求——拒绝掉所有小于编号n的promise请求及accept请求(accept请求就是真正的提议案的请求)。


　　二)acceptor:


　　1、如果某个acceptor之前已经promise过其他proposer 且其议案编号 大于n,那么将会拒绝p1的promise请求;


　　2、如果某个acceptor当前promise拒绝的议案编号小于n，那么就会接受p1的promise请求，并将当前acceptor accept的最新的议案编号及议案内容(即X的值)告诉proposer


　　三)proposer:


　　1、如果proposer p1获得了过半acceptor的承诺，则首先整合所有acceptor返回的信息，将acceptor中返回的最大编号的议案的内容作为自己的议案的内容(如果所有acceptor都没有返回议案内容，那么就自己随意设定一个)，然后向所有acceptor发出自己关于X的accept请求;


　　2、如果proposer没有获得过半数acceptor的回应，可以忽略这一次操作，申请一个新的议案编号，马上重新进行一遍整个操作


　　四)acceptor:


　　1、如果acceptor收到了proposer的accept请求时，还没有收到其他proposer更高编号的promise请求时，将会批准proposer的建议，并将自己决定告知learner;


　　2、如果acceptor收到了proposer的accept请求时，已经收到了其他proposer更高编号的promise请求时，将会拒绝本次accept


　　五)learner:


　　Learner收到了某个acceptor的accept信息后，会统计一共收到了多少个acceptor发过来的该proposal的accept信息，若该proposal的acceptor数量达到了quorum,那么就认定该proposal对应的值为 X的值。


　　一个分布式算法很明显需要包含以下特征：


　　没有确定前是未知的，一旦确定后，它是全局唯一不可变的


　　我们现在开始论证paxos算法能否在过半acceptor存活时，达到上述要求。


　　Poposer p1提出X的建议前会向所有的acceptor发出编号为n的promise请求，让acceptor不再批准编号小于n的promise和建议，当过半数acceptor答应了p1的promise后，这时编号小于n的proposal的选定情况就固定了，再也不会改变了。


　　p1获得了 “过半数acceptor的集合S1” 的promise后,如果某个编号为m(m


　　我们在程序流程里可以看到，下一次proposal的建议值必须跟当前acceptors里accept的编号最大的proposal一致，因此当 m = n – 1时，n号建议的X的值必然与m相同，依此类推后续proposal关于X的建议都必然与m相同，因此X的值必然全局唯一不可变，得证。