Paxos算法

大神说,世界上只有一种一致性算法,那就是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。



发表评论