Paxos算法简介
文章目录
应用场景
Paxos算法用于解决在分布式环境中,如何就某个协议达成一致的问题。
背景——拜占庭将军问题
拜占庭将军问题是由Paxos算法作者莱斯利·兰伯特提出的一个点对点通信时的基本问题:在不可靠信道上试图通过消息传递方式达到一致性是不可能的。这里简单画个草图:
拜占庭帝国有一支庞大的军队,这只军队有多个小分队(A-B-C-D-E),分别位于帝国的各个角落。一天,E分队的将军打算对某个倒霉国家发动进攻,但是必须要得到所有小分队的同意才能执行。无奈这座帝国太大,各个小分队之间的信息不得不依靠信使来传递。于是,E分队的将军分别派出a、b、c、d四个信使传递进攻任务的信息给其他各个分队。此时问题来了,没法保证信息准确可靠的传递给他们!假如d信使本就是个叛徒,亦或是a信使在路上被人劫持,再或是b信使走到一半无路可走,等等情况。这个其实非常类似于分布式系统中各节点间通信,尤其是网络问题,很容易导致通信在某两个节点间中断。该问题有没有解决办法呢?有!但不是今天的重点。那么,Paxos算法跟拜占庭将军问题之间是什么关系呢?答案就是:Paxos算法的前提,不存在拜占庭将军问题。
现实中是否存在某个环境,不存在拜占庭将军问题呢?当然有,否则Paxos算法就没有用武之地了。我们知道zookeeper解决一致性问题,就是对Paxos算法进行了实现,而类似于zookeeper这类分布式系统,本身就被部署在了一个安全的局域网环境中,尤其是生产环境,出现该问题的概率非常小,可以简单的认为不存在就行了。
Paxos算法中的角色
- 提案者Proposer
提出一个方案proposal,类比刚才提到的E将军;
- 表决者Acceptor
对别人提出的方案进行表决,类比刚才从A到E的将军(E将军自己也参与表决);
- 同步者Learner
表决通过(少数服从多数),则进入同步阶段,所有人都是同步者。同步表决通过的提案,即便是没有通过的那些表决者们。
Paxos算法基本流程
- 每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号 N, 即在整个集群中是唯一的编号 N,然后将该编号赋予其要提出的提案。
- 每个表决者在 accept 某提案后,会将该提案的编号 N 记录在本地,这样每个表决者中保存的已经被 accept 的提案中会存在一个编号最大的提案,其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案。
- 在众多提案中最终只能有一个提案被选定。
- 一旦一个提案被选定,则其它服务器会主动同步(Learn)该提案到本地。
- 没有提案被提出则不会有提案被选定。
下面照样上图:
首先看黑色部分,E向ABCD发出一个提案,该提案的编号N=1,此前BCD三者未曾accept过别的提案,因此,各自保留的最大提案编号maxN=null,所以无条件接纳,之后各自修改maxN=N=1(蓝色部分);但是A此前已经accept过编号为2的提案(这里可以认为是E在发出1号提案后,紧接着有别人发出2号提案,但是由于网络原因,1号提案没有及时发送到A,反而被2号提案抢先一步),所以A对比后来的1号提案,发现编号比自己记录的maxN=2要小,所以不予理会。这样,该提案就被BCD三者accept,根据少数服从多数原则,该提案被正式通过。之后进入同步阶段,ABCD四者都会同步1号提案的具体内容到本地。
Paxos算法具体流程
大体上分为两步:prepare阶段和accept阶段,每个阶段都是刚刚说的基本流程的实例。
prepare阶段
prepare阶段可以描述为提案者试探性的向表决者发出提案。假设有三个提案者P1(初始N=2)、P2(初始N=1)、P3(初始N=3),相对应的,有三个表决者A1(初始maxN=0)、A2(初始maxN=0)、A3(初始maxN=0)。其实跟提案者是相同的三个人,为了表述方便,将他们分开显示。
①现在P1提出一个提案(A3由于网络延迟暂未收到该提案)如下图所示:
A1和A2的maxN原先为0,现在统一改为2.
②P2提出编号为1的提案(被A2和A3收到):
由于A2的maxN=2,所以不予理会,A3的maxN变成1.
③P3提出编号为3的提案(被A2和A3收到):
A2和A3的maxN都变为3.
④只有P2的提案没有收到过半数的回应,这时他有两条路可走:放弃提案或增加N值继续提案。这里假设P2采用后者方案,系统为P2提案的编号赋值为4,继续提案:
此时A2和A3的maxN都变成4.
accept阶段
①P1提案者正式向表决者A1和A2发出提案,这时要求提案者的编号N大于等于表决者的maxN即可(不要求严格大于)。但是此时A2的maxN已经变为4,所以不予理会:
②P2向A2和A3发出提案,两者都通过:
③P3向A2和A3发出提案,两个表决者maxN=4>3,所以都不予理会。
最终,只有P2获得了超过半数的响应,也就标志着N=4号提案(原N=1号提案)正式通过。
活锁问题
死锁的概念大家都清楚,但是活锁是什么呢?处于死锁中的多个线程由于资源被对方占用,导致这些线程处于一种僵持状态(静止的);而活锁则是多个实体在两阶段提交过程中,由于时差和资源抢占,导致这些实体状态一直在发生变化,根本停不下来的一种状态(活动的)。
在本例中,假设有两个提案者P1和P2,他们的初始maxN值都是0:
此时P1进入proposal阶段,它以N=1向自己和P2发送提案编号,两者都会接受,并修改maxN=1:
紧接着P2进入proposal阶段,它以N=2向自己和P1发送提案编号,两者也都会接受,并修改maxN=2:
之后P1进入accept阶段,它向自身和P2正式发送N=1的提案,很显然,此时maxN都为2,所以就都不接受:
P1升级自己的N值为3,再次进入proposal阶段,又成功被自己和P2接受:
现在P2进入accept阶段,此时P2的N=2,自然没法通过:
所以P2升级自身的N=4,再次进入proposal阶段,又被两者都接受了:
……
大家看到这两个提案者似乎都在跟彼此较劲儿,谁也不愿放弃——这便是活锁的表现形式。
Fast Paxos算法便是用来解决活锁问题的一个方法,它只允许有一个提案者,比如zookeeper中,只有Leader有提案权一样,活锁问题不复存在。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论