Multi Paxos:Basic Paxos的进化

2014/08/20 16:25
阅读数 4.3K

Multi Paxos基于Basic Paxos,将原来2-Phase过程简化为了1-Phase,从而加快了提交速度。Multi Paxos要求在各个Proposer中有唯一的Leader,并由这个Leader唯一地提交value给各Acceptor进行表决,在系统中仅有一个Leader进行value提交的情况下,Prepare的过程就可以被跳过,而Leader的选举则可以由Paxos Lease来完成。

实际上,Multi Paxos并不是完全跳过了Phase-1,当系统中选举出一个新的Leader时,在最初的几次提交中必须依照2-Phase过程进行,在达到到一个“稳定”的状态,才可以跳过Phase-1,直接向各个Acceptor发送AcceptRequest进行提交。在这里就有两个比较关键的问题。

首先,新选出的Leader在初始状态下为何必须要按2-Phase过程进行提交呢?这要从Learner对value的处理说起。每一轮表决(也即一个Instance)对应一个InstanceId,InstanceId是单调连续递增的。当Learner处理value时必须严格按照InstanceId连续递增的顺序执行(用来保证数据一致性),如果因一些原因而无法得知某轮的最终表决结果,Learner就需要向各Acceptor查询该InstanceId对应的value。此时,就存在下面一种场景:当原有Leader在提交了一半突然下线了,而新当选的Leader如果直接通过AcceptRequest进行提交可能就会导致本轮表决未能通过任何最终决议(就如共4个Acceptor,原Leader刚向其中2个Acceptor提交value后下线,而新Leader上线后又给其余2个Accptor提交了不同的value,这将最终导致2:2的局面),使得Learner“卡死”在对这个Instance的处理上。

其次,如何保证新选出的Leader提交的InstanceId保持连续递增?对此,一方面可以让Leader在每次续租过程中将其当前的InstanceId告诉各个Acceptor,而新Leader当选后就可以从Acceptor那得到一个比较接近当前InstanceId的值;在新Leader当选后,先在最初的若干轮表决中使用2-Phase过程提交一些“空”操作(即Learner若发现表决结果是空操作则不做任何处理),最终追上或超过当前InstanceId,在此之后再采用1-Phase过程进行提交。到这里,又有一个问题出现了:应该执行多少轮2-Phase过程提交才能进入“稳定”状态呢?在代码实现中,为加快算法性能,可以让Proposer和Learner各自维护了一个队列,Acceptor维护了一块缓冲区,来达到一种“乱序提交-乱序表决-顺序执行”的方式,如图所示:multi_paxos-submit
按照这样,假设Proposer的队列长度为QUEUE_SIZE,那么Proposer只要得知有QUEUE_SIZE个Instance通过最终表决,就可以确定自己已达到“稳定”状态。如下图,在队列长度QUEUE_SIZE=2的情况下,原Leader在提交第5和第6个value时突然离线,新Leader被选出后需进行如下的尝试3次2-Phase提交(第4个Instace实际上是无法最终被通过的,但第5和第6个Instace能够被表决通过)后达到“稳定”状态。
multi_paxos-instance


展开阅读全文
打赏
0
7 收藏
分享
加载中
更多评论
打赏
0 评论
7 收藏
0
分享
返回顶部
顶部