最近在学习zookeeper原理的时候了解到了paxos算法,看了几篇文章之后还是感觉有些迷糊,后来看了知行学社的paxos视频才对这个算法有了一定的了解,这里就做一下总结.
Paxos是Lamport于1990年提出的一种基于消息传递而具有高度容错特性的分布式一致性算法.这个算法是分布式中最为重要的算法,Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其他算法都是残次品.具体Paxos算法的详细内涵和故事背景大家可以参考知乎上的回答;
我们都知道基于消息传递通信模型的分布式系列,不可避免的会发生以下错误:进程可能会慢,被杀死或在重启,消息可能会有延迟,丢失和重复.Paxos算法解决的问题就是在一个可能发生上述异常的分布式系统中如何就某个值达成一致,保证无论发生以上任何异常,都不会破坏决议的一致性。
但是Paxos算法也有一定的使用假设。一个假设是在消息传递的过程中不会出现拜占庭将军问题:即虽然有可能一个消息被传递两次,但是绝对不会出现错误的消息。另一个假设是提议不会被反对,只能被同意或在被更新的提议替换。 Paxos协议中有三种角色,每个节点可以扮演多个角色:
Paxoso算法分为两个的阶段,我们就将其分别记为Phase1和Phase2.每个Proposer都持有一个独有的变量epoch,每个Acceptor都保存三个状态:lastest_prepared__epoch,accepted_epoch和accepted_value。
lastest_prepared_epoch是指Acceptor授予访问权的Proposer的epoch值,accepted_epoch是Acceptor接受提议的Proposer的epoch值,而accepted_value就是Acceptor接受的提议值喽,他们的初始值都为null。
Phase1过程中,Proposer向Acceptor发起Prepare(epoch)
请求来获取访问权。将自己的epoch发送给Acceptor.而Acceptor只会接受比lastest_prepared_epoch更大的epoch,并给予访问权,并将epoch记录到lastest_prepared_epoch的值中,返回当前的accepted_epoch和accepted_value的值。在初始化状态下,二者都是null,所以返回的是。如果epoch小于lastest_prepared_epoch则不授予访问权,并返回。
phase1 如上图所示,Proposer1向5个Acceptor发送了Prepare(#1)的请求,其中前三个请求顺利到达,Acceptor授予访问权,返回,并修改lastest_prepared_epoch为1。而后两个请求发生了网络延迟,一直未到达相应的Acceptor。 在阶段一中,Proposer需要获得半数以上的Acceptor的访问权和对应的一组value的取值才会进行第二阶段,这样才会确保,一个Proposer提出的确定的议案会被另外一个Proposer发现,从而在阶段二中会进行正确的操作。
第二阶段采取“后者认同前者”的原则进行。在肯定旧epoch无法生成确定性取值时,新的epoch会提交自己的取值,不会冲突;一旦旧epoch形成了确定性取值,那么该proposer一定可以获得该取值,并且会认同该取值,不会破坏。 如果Proposer在第一阶段获取的value值都是null,则旧epoch无法形成确定性取值,此时让自己的成为确定性取值:
paxos2
如上图所示,由于在阶段一中Proposer1接受到的和值都为null,所以,决定将自己的值设置为确定值,于是发送accept(1,V1)请求。
Acceptor1接受到了这个请求,检查lastest_prepared_epoch也等于1,所以将自己存储的设置为<1,V1>。而Proposer1的另外两个accept请求发生了网络延迟。
如果此时,Proposer2向Acceptor进行propose会怎么样呢?我们来模拟propose来分析一下。
paxos3
如上图所示,Proposer2向Acceptor发送了prepare(#2)的请求,Acceptor1先检测一下发现2大于现在的lastest_prepared_epoch,所以同意发送访问权,将lastest_prepared_epoch修改为2,并将自己保存的accepted_epoch和acceped_value返回给Proposer2;Acceptor3的操作也是类似,只不过因为Proposer1发送的accept请求发生了延迟,所以Acceptor3返回的是;而Acceptor5的操作和我们在文章第一张图中的Acceptor1的操作相同,他们都是第一次接收到prepare请求。
然后Proposer2进行第二阶段的操作,从所有的返回数据中,找到accepted_epoch最大的那个accepted_value.这里就是Acceptor返回的<1,V1>,所以,Proposer2会尽力让V1成为确定值,所以它向Acceptor发送accept(2,V1)的请求。然后Acceptor1,Acceptor3,Acceptor5三个Acceptor接受了这个accept请求,更新自己的。此时,已经有三个acceptor形成了一致性的值,所以V1就成了整个系统的确定性取值。
paxos7.png
那么Proposer1对Acceptor3发送的accept请求在此时达到Acceptor3会怎么样呢?Acceptor3发现当前lastest_prepared_epoch是2,所以直接拒绝了这个请求。
不清楚大家现在对Paxos算法的过程是否已经有了清楚的了解啊?那么我来问几个问题,大家可以考虑一下:
Zookeeper
关于Paxos的具体使用场景和算法,希望大家多多关注。