Paxos主要解决在一个可能发生异常的分布式系统中快速明确的在集群内部对某个数据达成一致,并且保证不论系统发生什么异常,都不会破坏整个系统的一致性。
在该一致性算法中,主要有Proposer、Acceptor和Learner三种角色。在具体的实现中,一个进程可能充当多个角色。Paxos算法的目标是保证最终有一个提案被选定,当提案被选定后,最终进程也能获取到被选定提案。Proposer负责生成提案,Acceptor负责批准提案,Learner负责学习提案。
Proposer对于每一个产生的[Mn,Vn]的提案,需要满足一下条件:存在一个超过半数的的Acceptor组成的集合S:
Paxos算法主要分为两个步骤:Proposer生成提案和Acceptor批准提案
阶段一:Proposer生成提案
Proposer在发送编号为Mn的Prepare请求时,要求Acceptor作出以下保证:
阶段二:Acceptor批准提案
上述方案在极端情况下会产生问题,举个例子如下:
Proposer1发起了编号为M0的Prepare请求并得到了正确的反馈,但此时还没有进入阶段二(也就是说Acceptor还没有批准该提案),假设此时另一个Proposer2发起了编号为M1的Prepare请求,Acceptor向Proposer2保证不再批准任何编号小于M1的提案。此时假设Proposer1的MO提案进入第二阶段,此时由于Acceptor已经不允许批准比M1编号小的提案,因此批准M0失败。然后Proposer1又发起M2的Prepare请求,Acceptor保证不再批准比M2编号小的提案,这就导致M1的提案也无法批准通过。最终提案一致在循环生成,却无法被批准。
为了解决上述问题,就必选选择一个主Proposer,并规定只有主Proposer可以生成提案,这样就避免了多个Proposer同时生成提案的问题。
上面主要讲述了如何选定提案,那么Learner如何获取选定的提案呢?主要有以下几种方案:
方案一
Acceptor一批准提案就将该提案发送给Learner,这种虽然能够让Learner尽快的获取提案,但是这种方法需要让Learner和其他的Acceptor进行通信以确保该提案是被大部分Acceptor批准的提案,通信的次数至少是Learner数量和Acceptor数量的乘积
方案二
Acceptor批准提案后向一个主Learner发送该提案,然后由该主Learner通知其他的Learner,这种方案的优点是减少了与Acceptor的通信次数,但同时也引入了主Learner的单点故障问题
方案三
为了解决主Learner的单点故障问题,这里讲主Learner替换为一个Learner的子集。Acceptor将批准的提案发送给Learner的子集,然后由这个子集发送给其他的Learner。子集中的Learner越多,系统越可靠,但通信也会越复杂。
Paxos主要有以下两个实现: