月度归档:2016年06月

Paxos算法的核心

这里默认大家对paxos算法已经有了基础的了解,本文主要根据自己的理解,描述paxos算法的核心所在。

先表述一下已知条件:

角色Proposer:负责提出提案;
角色Acceptor:负责批准提案。
提案的格式:[M,V],其中M表示提案的编号,V即Value值。
M:提案编号,全局唯一。
Value值:可以理解为提案的具体内容,如:A/B/C三人投票选班长,A/B/C共有三票,每人都有一个唯一的编号M0-M2,但是其Value值可以相同,例如A和B选B当班长,C选C当班长,这是Value值便是B和C。
选定条件:一个提案,只有被超过半数的Acceptor批准,才能被选定。

A:目的:如果某个提案[M,V]被选定了,之后选定的提案Value值都和这个提案相同

A是我们的原始目的,我们要通过设计一套提案的协议,最后达到这个目的A。
我们通过逐步缩小限制条件,来进一步明确目标A,推导步骤如下:

B:如果某个提案[M,V]被选定了,之后Acceptor批准的提案,Value值必须和选定的提案相同。

C:如果某个提案[M0,V0]被选定了,之后Acceptor批准的提案[Mn,Vn],必须满足Mn>M0,且Vn=V0。

D:按照如下方式产生和批准方案
D-1:方案产生。产生的方案必须满足以下两个条件中的一个。
(1)产生的方案的编号Mn小于已产生的所有编号
(2)产生的方案的编号不小于已产生的所有编号,则Vn要等于已选定的最大编号的Value,或者如果没有选定过任何方案,则Value值可以任意。
D-2:方案批准。被批准的方案的编号Mn大于或等于所有已产生的编号。

从A到B到C,都是在一步步缩小条件范围,所以比较容易可以看出,如果C成立,那么C–>B–>A,A肯定也成立,接下来最主要的是如何证明D成立时,C成立,如下:

(1)方案要先产生才能被批准然后被选定,如果方案M0是被选定了,则M0肯定是一个已经产生了得编号,则之后被批准的方案Mn要满足“被批准的方案的编号Mn大于或等于所有已产生的编号”,所以一定有Mn>M0。

(2)假如第一个被选定的方案为[M0,V0],第二个被选定的方案为[Mn,Vn],则问题变成了,证明:如果按照上述方式产生和批准方案,则Vn=V0。
由于Mn是第二个被选定的方案,按照上面的方式D-2批准方案,则一定有Mn>M0。
我们用P表示提案的产生,A表示提案的选定,Time(P)和Time(A)表示提案产生和选定的时间。
可以明显得出:
Time(A0)<Time(An)
Time(P0)<Time(A0)
Time(Pn)<Time(An)
接下来,判断Time(Pn)和Time(A0)以及Time(P0)的关系,通过条件“被批准的方案的编号Mn大于或等于所有已产生的编号”,说明方案M0被批准的时候,方案Mn还没产生,所以有
Time(A0)<Time(Pn)
再根据条件“产生的方案的编号不小于已产生的所有编号,则Vn要等于已批准的最大编号的Value,或者如果没有批准过任何方案,则Value值可以任意”,所以Mn方案对应的Value值Vn必须等于已经批准的V0.
依此类推,之后第3到第m个被批准的方案,其Value值也都必须等于V0。
所以,第2个到第n个被批准的方案,都满足Mn>M0,并且Vn=V0。
综上所述,D成立时,C也成立。

另外,在一开始还没有提案被选定时,根据条件D-1和D-2,提案编号大的将被首先选定。

到此,我们已经将目的A细化到了具体产生和批准提案的方式D,现在让我们来看一下如何将方式D表述为具体的算法:

Prepare阶段
1.1 Proposer选择一个提案编号Mn ,然后向半数以上的Acceptors发送编号为 Mn 的prepare请求。
1.2 如果一个Acceptor收到一个编号为Mn 的prepare请求,且 Mn 大于它已经响应的所有prepare请求的编号,那么它就会保证不会再批准(accept)任何编号小于Mn的提案,同时将它已经通过的最大编号的提案(如果存在的话)作为响应。
2. Accept阶段
2.1 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求(编号为Mn )的响应,那么它就会发送一个针对编号为 Mn ,value值为Vn 的提案的accept请求给Acceptors,在这里 Vn是收到的响应中编号最大的提案的值,如果响应中不包含提案,那么它就是任意值。
2.2 如果Acceptor收到一个针对编号Vn 的提案的accept请求,只要它还未对编号大于 Vn 的prepare请求作出响应,它就可以通过这个提案。
一个Acceptor可以响应任何一个Prepare请求,但是Accept(批准)请求,必须满足上述条件。

可以看出:
(1)阶段1.1到2.1模拟了提案的产生:提案的编号先通过1.1广播给Acceptors,然后通过1.2获取已选定的最大编号的Value,先证明一下,1.2获得的超半数Acceptors一定已经包含了已选定的最大编号的Value:由于Accept阶段和Prepare阶段都需要超半数Acceptors响应,所以这两个阶段一定有共同的Acceptors,因此1.2可以获得已选最大编号的Value。
(2)阶段1.2到2.2模拟了提案的批准。

让我们来换个角度理解一下:
假如方案1和2是两个都被选定了的方案,P1和P2,A1和A2分别表示方案1和2的prepare和accept阶段,由于每个操作都会涉及超过半数的acceptor,因此P1/P2/A1/A2任何两个操作之间都有公共acceptor,尽管这些公共acceptor不一定相同,但是“任何两个操作都有公共acceptor”所表述的含义其实是”任何两个操作都会相互影响“,因此我们可以把这些操作类似集中到一个acceptor上做一个类似的分析,则这些操作之间的可能顺序关系为:
P1 P2 A2 A1
P1 P2 A1 A2
P1 A1 P2 A2
P2 P1 A2 A1
P2 P1 A1 A2
P2 A2 P1 A1
由于1和2都是最终被选定了的方案,结合上面prepare阶段和accept阶段的要求,只有以下两种情况是存在的:
P1 A1 P2 A2
P2 A2 P1 A1
而且前一种情况下,编号2大于编号1,后一种情况编号1大于编号2(此处的1和2只代表编号的ID,不代表大小),可以看到,实际上通过”超过半数“和“只批准最大的prepare编号”以及“value值为accept最大编号的value”这三个条件,让这种并发的分布式操作,变成了串行的原子操作(P和A中间不能有其他P和A),这便是paxos算法的核心所在。

参考资料:
1. 《从Paxos到Zookeeper分布式一致性原理与实践》
2. http://blog.csdn.net/anderscloud/article/details/7175209