江苏龙网

  1. 主页 > 生活百科 > >

Paxos算法浅析( 二 )

Paxos算法


划分角色后，就可以更精确的定义问题：
1.决议（value）只有在被 proposers 提出后才能批准（未经批准的决议称为「提案（proposal）」）；
2.在一次Paxos算法的执行实例中，只批准一个Value；
3.Learner只能获得被批准（chosen）的Value 。
Paxos一致性协议Paxos的目的是在非拜占庭条件下，当多个并行进程提出不同的倡议时，如何能够达成一致 。如果归纳Paxos协议，可以将其描述为以下两阶段过程：
阶段一:Prepare阶段
1.1【倡议者视角】倡议者选择倡议编号n，然后向大多数（即超过半数以上）接受者发送Prepare请求，请求中附带倡议编号n 。
1.2【接受者视角】对于某个接受者来说，如果接收到带有倡议编号n的Prepare请求，则做如下判断：若倡议编号n比此接受者之前响应过的任何其它Prepare请求附带的倡议编号都大，那么此接受者会给倡议者以响应，并承诺不会响应之后接收到的其它任何倡议编号小于n的请求，另外，如果接受者曾经响应过2.2阶段的Accept请求，则将所有响应的Accept请求中倡议编号最高的倡议内容发送给倡议者，倡议内容包括两项信息：Accept请求中的倡议编号以及其倡议值 。若倡议编号n不比此接受者之前响应过的任何其它Prepare请求附带的倡议编号都大，那么此接受者不会给倡议者以响应 。
阶段二:Accept阶段
2.1【倡议者视角】如果倡议者接收到大多数接受者关于带有倡议编号n的Prepare请求的响应，那么倡议者向这些接受者发送Accept请求，Accept请求附带两个信息：倡议编号n以及倡议值v 。倡议值v的选择方式如下：如果在1.2阶段接受者返回了自己曾经接受的具有最高倡议编号Accept请求倡议内容，则从这些倡议内容里面选择倡议编号最高的并将其倡议值作为倡议值v；如果1.2阶段没有收到任何接受者的Accept请求倡议内容，则可以任意赋值给倡议值v 。
2.2【接受者视角】如果接受者接收到了任意倡议编号为n的Accept请求，则接受者接受此请求，除非在此期间接受者响应过具有比n更高编号的Prepare请求 。通过以上两阶段过程即可选出唯一的倡议值，对于学习者来说，其需要从接受者那里获知到底是哪个倡议值被选出 。一个直观的方法如下：每当接受者执行完2.2步骤，即接受某个Accept请求后，由其通知所有学习者其所接受的倡议，这样，学习者很快习得是哪个倡议被最终选出 。但是这种方式会导致大量通信，因为任意一个接受者会通知任意一个学习者，如果有m个接受者，n个学习者，则需要m*n次通信 。一个替代策略是：从众多学习者中选择一个作为代表，由其从接受者那里获知最终被选出的倡议，然后再由其通知其它学习者，这样可以将通信量降为m+n 。但是这个方案中如果这个学习者代表发生故障，其它学习者无从知晓倡议值 。考虑到健壮性和通信量两个因素，可以采取折中方法：选出若干学习者作为代表，由这些代表从接受者那里获知最终倡议值，然后通知其它学习者 。
通过以上流程，如果有多个并发进程提出各自的倡议值，Paxos就可以保证从中选出且只选出一个唯一确定的倡议值，以此来达到副本状态机保持状态一致的目标 。
总结此文只是对Paxos的应用场景以及Paxos协议本身进行了介绍，而Paxos最难理解性在于是什么因素导致协议以此种方式呈现以及其正确性证明过程而非最终协议本身内容 。




推荐阅读


上一篇：普洱茶性寒 大概你是没有品尝过古树茶

下一篇：喝凉了的茶 会导致肾结石 有科学依据吗