03.分布式一致性协议——paxos算法

paxos目的

Paxos算法是基于消息传递且具有高度容错特性的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一,其解决的问题就是在分布式系统中如何就某个值(决议)达成一致

Paxos算法的前提假设是不存在拜占庭将军问题,即: 信道是安全的(信道可靠),发出的信号不会被篡改,因为Paxos算法是基于消息传递的。:如下图所示

03.分布式一致性协议——paxos算法

paxos算法角色划分:三种类型

  • 提议者(Proposer):提出提案;

  • 接受者(Acceptor):对提案作出裁决;

  • 告知者(Learner):被告知投票的结果,不参与投票过程

    提案(Proposal)。最终要达成一致的value就在提案里。只要Proposer发的提案被Acceptor接受(半数以上的Acceptor同意才行),Proposer就认为该提案里的value被选定了。Acceptor告诉Learner哪个value被选定,Learner就认为那个value被选定。只要Acceptor接受了某个提案,Acceptor就任务该提案里的value被选定了。

    03.分布式一致性协议——paxos算法

优势:为了避免单点问题:会有一个acceptor集合,proposer向该集合发送提案,acceptor集合中所有成员都有可能接受提案,并且只能批准一个提案,当有半数以上的成员同意,那么就同意批准该提案

paxos算法过程

  • 阶段一(prepare阶段):

(a) Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求。Pareper(N)

(b) 如果一个Acceptor收到一个编号为N的Prepare请求,如果小于它已经响应过的请求,则拒绝,不回应或回复error。若N大于该Acceptor已经响应过的所有Prepare请求的编号(maxN),那么它就会将它已经接受过(已经经过第二阶段accept的提案)的编号最大的提案(如果有的话,如果还没有的accept提案的话返回{pok,null,null})作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案

  • 阶段二(accept阶段):

(a) 如果一个Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意:V就是收到的响应中编号最大的提案的value(某个acceptor响应的它已经通过的{acceptN,acceptV}),如果响应中不包含任何提案,那么V就由Proposer自己决定。

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求做出过响应,它就接受该提案。如果N小于Acceptor以及响应的prepare请求,则拒绝,不回应或回复error(当proposer没有收到过半的回应,那么他会重新进入第一阶段,递增提案号,重新提出prepare请求)。

03.分布式一致性协议——paxos算法

paxos优缺点

优点:paxos算法的优点很明显,按照此方法可以对多个数据值达到一致,收敛较好。

缺点:paxos算法的缺点是会出现活锁问题:考虑到一种极端的情况下,有两个proposer依次提出了一系列编号递增的议案,但是最终paxos无法形成最终的议案。具体场景如下:

03.分布式一致性协议——paxos算法

03.分布式一致性协议——paxos算法解决办法

通过选取主Proposer,就可以保证Paxos算法的活性。选择一个主Proposer,并规定只有主Proposer才能提出议案。这样一来,只要主Proposer和过半的Acceptor能够正常进行网络通信,那么肯定会有一个提案被批准(第二阶段的accept),则可以解决死循环导致的活锁问题

总结:

通过选择一个主Proposer,并规定只能由主Proposer才能提出议案,整个paxos算法就可以保持活性。

Paxos算法的过半依据

在Paxos算法中,采用了“过半”理念,也就是少数服从多数,这使Paxos算法具有很好的容错性

Paxos基于的过半数学原理

大多数(过半)进程组成的集合为法定集合, 两个法定(过半)集合必然存在非空交集,即至少有一个公共进程,称为法定集合性质。 例如A,B,C,D,F进程组成的全集,法定集合Q1包括进程A,B,C,Q2包括进程B,C,D,那么Q1和Q2的交集必然不在空,C就是Q1,Q2的公共进程。如果要说Paxos最根本的原理是什么,那么就是这个简单性质。也就是说:两个过半的集合必然存在交集,也就是肯定是相等的,也就是肯定达成了一致

Paxos是基于消息传递的具有高度容错性的分布式一致性算法。Paxos算法引入了过半的概念,解决了2PC,3PC的太过保守的缺点,且使算法具有了很好的容错性,另外Paxos算法支持分布式节点角色之间的轮换,这极大避免了分布式单点的出现,因此Paxos算法既解决了无限等待问题,也解决了脑裂问题,是目前来说最优秀的分布式一致性算法。其中,Zookeeper的ZAB算法和Raft一致性算法都是基于Paxos的

参考文档:

  1. 如何浅显易懂地解说 Paxos 的算法?
  2. paxos算法
上一篇:分布式一致性协议介绍(Paxos、Raft)


下一篇:一致性算法(一):Paxos