朴素Paxos算法简介

简介:

        Paxos算法是莱斯利·兰伯特于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。Paxos协议于1989年首次出版，并以在希腊Paxos岛使用的虚构的立法协商一致制度命名。Paxos通常用于需要持久性的地方(例如，复制一个文件或数据库)，其中持久状态的数量可能很大。因为Paxos算法的强大,很多网络上文章有介绍,也有很多成熟的项目使用该算法,如zookeeper.

       本篇文章只用一个国会法案的提出通过过程,介绍朴素Paxos算法, 更加严谨的数学证明请参考:https://zhuanlan.zhihu.com/p/21438357?refer=lynncui

       网络上paxos过程被分别隔离描述成法官和律师,但是功能与法官和律师有所区别,而且将准备阶段描述成贿选让我第一次接触时候觉得很难理解.所以我会换个场景介绍paxos.

       我们可以把paxos一致性算法的实现,想象成一次在国会中一次提案的提出与审议,这样其实更简单.

算法中角色:

       在该算法*有两个角色,一个是提案者(Proposer),一个是审议者(Acceptor 接受者,但其并不是无条件接收所有信息,所以译为审议者).提案者负责提出表决的议案(一个需要达成一致的事情),而审议者根据规则判断是否通过.每一个server既可以是提案者,又同时是审议者,这也是为什么我觉得paxos算法中每一个server更像一个*.因为*既有提案权,又有表决权.

算法过程:

提案准备:

        一个*想要提出议案需要经过半数其余*同意才能通过提案准备阶段.所以,每个*在提案准备阶段会产生一个本地提案Id.提案的*会将这个提案号告知其余所有*,表明他要提出议案了.

       而收到议案请求的*会对比一下自己之前是否接收到过提案Id更高的提案请求,如果没有则回复ok,承诺自己将不再接收比该Id更小的请求;如果有就拒绝该*的提案准备. 

                                                                        图1:发起准备提案求情过程

       由图中可以看出*B接收了*A的提案,返回OK的同时也返回了自己的V和Max.

       那么收到回执的*A,会有两种情况:一种回执中的Max小于自己的Max,那么*A会坚持自己之前的提案值V(如图2);

                                                                         图2,*B的Max值为小于A的Max值

另一种是回执中的Max大于自己的Max,那么*A会更改自己的V以及Max(如图3):

                                                                        图3,*B的Max值小于A的

       更改提案值这一步非常重要,它保证了每一次取得的共识均不会与之前达成的共识产生冲突,比如这个议案讨论的是谁将是master,B*显然在前一轮成功的讨论过程中认同了之前收到的议案,即β为master,*A可能因为网络原因并没有收到.现在*A网络恢复后继续讨论该议案,与*B通信后发现原来之前其余*已经取得过共识V=β,那么现在他就将自己V也设为β.这样就不会与之前达成过的共识冲突,保证了一致性.而且这种类似信息的洪范有有利于整个系统加速收敛为一致状态.

        所以总结出规则,对于接收准备提议请求的*,只有提议Id大于Pb时候,*才会接受发过来的准备提议请求.并且把Pb置为该Id.之后返回自己的V以及max值.

       最后,发起提议请求的*A会对返回的ok计数,如果超过半数则完成了第一阶段的提案准备;反之,*A会将Id+1后再重复提案准备过程.

提案发布:

       在前一个阶段中,假设*A获得了过半数票(回执中的OK数大于总人数的一半),则*A可以进入提案发布过程.

       这一步与图1类似,比较简单.*A就是将提案Id与V值发布出去,其余*对比Id,发现与本地Pb一致,那么就接收该V值,反之则拒绝,如下图.

                                                                                              图4,提案发