PAXOS的初次学习

参考:
http://dsdoc.net/paxosmadesimple/index.html#id49
http://my.oschina.net/linlifeng/blog/78918
http://www.open-open.com/lib/view/open1420635646984.html

可以参考小秦我的这篇文章,在链接中的文章中对PAXOS有了更加深入的体会。

1.P1 + P2如何保证一致性?
P1:一个Acceptor必须通过(accept)它收到的第一个提案。

P2:如果具有value值v的提案被选定(chosen)了,那么所有比它编号更高的被选定的提案的value值也必须是 v。
一致性的保证依赖于严格的数学证明,具体的可以参见《The Part-Time Parliament》。

首先说说一致性的含义:
a.只有被提出的提案才能被选定。
b.只能有一个值被选定(chosen),同时
c.如果某个提出者认为某个提案被选定了,那么这个提案必须是真的被选定的那个。

假设编号是不会重复的递增序列。按照P2的要求,a是肯定成立的。当某个v被选定的时候,如果满足P2,那么后续的提案肯定也是v,这也就保证了b和c。

但是P1和P2并没有告诉我们如何保证v被第一次选定。通常的做法是保证acceptor中大多数都接受了v,则表明v被选定。那么如果要事先知道“大多数”这个概念,就需要分两阶段提交提案,首先需要先做prepare工作,知道大多数acceptor满足接收提案的条件。在两阶段的情况下,作者想到了一个思路,这个思路能保证P2:
P2c:对于任意的n和v,如果编号为n和value值为v的提案被提出,那么肯定存在一个由半数以上的Acceptor组成的集合S,可以满足条件a或者b中的一个:
a.S中不存在任何的Acceptor通过过编号小于n的提案
b.v是S中所有Acceptor通过的编号小于n的具有最大编号的提案的value值。

为此,P1也就变成了:
P1a.一个Acceptor可以接受一个编号为n的提案,只要它还未响应任何编号大于n的prepare请求。

P2c的a保证我们的算法可以开始,P2c的a和b保证在算法的计算期间算法可以正常继续下去。

P1a + P2c能保证一致性(因为P1a => P1, P2c => P2),并且是可行的。不过其不保证一定能选出最终的结果。

根据上面的要求,算法在某一时刻某个或某些acceptors中大半都接受了同一个v,那么从此时的编号n开始往后我们的v就确定下来了。这个可以通过归纳法证明出来。

2.learner如何学习新的值
最简单的方法:
为了获取被选定的值,一个Learner必须确定一个提案已经被半数以上的Acceptor通过。最明显的算法是,让每个Acceptor,只要它通过了一个提案,就通知所有的Learners,将它通过的提案告知它们。这可以让Learners尽快的找出被选定的值,但是它需要每个Acceptor都要与每个Learner通信—所需通信的次数等于二者个数的乘积。

3.唯一编号如何得到
最简单的方法:
每个propersor启动的时候都给一个唯一编号x以及Proposer的总数n,则每次提出请求的时候的id为x + n*m

4.应用
a.选主
选主就是大家通过PAXOS选出master的value,value可以是主机名。

b.HA
HA可以通过选主得到,比如对外提供服务的时候先由选举出的master提供,如果master宕机了(比如心跳超时了),那么通过PAXOS继续选举出唯一的新master提供服务

总的来说对于PAXOS的算法实现目前比较清楚,但是对于作者思考这一算法的思路以及具体的数学证明还有很大的疑问。之后学习的时候会继续完善这部分内容。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*