文档章节

Multi Paxos:Basic Paxos的进化

liangtee
 liangtee
发布于 2014/08/20 16:25
字数 940
阅读 3.3K
收藏 7

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


本文转载自:http://weihaoyang.com/archives/92#respond

liangtee
粉丝 107
博文 94
码字总数 38111
作品 0
朝阳
程序员
私信 提问
加载中

评论(0)

架构设计:系统存储(25)——数据一致性与Paxos算法(下)

(接上文《架构设计:系统存储(24)——数据一致性与Paxos算法(中)》) 2-3. Paxos算法变种 上文(架构设计:系统存储(24)——数据一致性与Paxos算法(中))我们提到,Paxos算法的设计...

yinwenjie
2017/03/20
0
0
TIDB 架构及分布式协议Paxos和Raft对比

近来newsql大热,尤以TIDB最火,pingcap不断打磨TiDB,现如今版本已经迭代到3.0,产品已经基本趋于成熟。 对于TiDB,整体架构图如下图所示 是由四个模块组成,TiDB Server,PD Server,TiKV ...

liuminkun
2019/04/11
0
0
专题二:RDS 5.7三节点企业版时代的数据一致性解决方案

  上篇我们看到了在MySQL主备模式下,我们在数据一致性上做了不少事情,但解决方案都有一定的局限性,适合部分场景或者解决不彻底的问题。随着以Google Spanner以及Amazon Aruora 为代表的...

jixiang_zy
2019/07/12
0
0
一致性协议算法-------------Paxos算法

基本算法(basic paxos) 算法(决议的提出与批准)主要分为两个阶段: 1. prepare阶段: (1). 当Proposer希望提出方案V1,首先发出prepare请求至大多数Acceptor。Prepare请求内容为序列号<SN1>; ...

满小茂
2016/02/24
360
0
Paxos的通俗理解及其在数据库高可用上的使用

本文转自【Qunar技术沙龙】,经平台同意授权转载。 近期大家都在讨论Paxos算法,我看了很多网上的文章,总觉得有些晦涩难懂,经过一段时间研究,对Paxos有了一些理解,在这里总结一下,希望能...

蒲聪
2017/06/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

根据坐标和数据库记录坐标对比 按距离分页排序

$EARTH=6378.137; //地球半径 $PI=3.1415926535898; //PI值 //将要和数据库经纬度对比的坐标 $lng=34.15; $lat=36.073516; SELECT y.id, y.title, y.lat, y.lng, y.address, y.c......

sing-wa
30分钟前
43
0
Java 位运算符

https://java-er.com/blog/java-shit-operation/ Java位运算符(bitwise operators),应用于整数类型(int),长整型(long),短整型(short),字符型(char),和字节型(byte)。 位运算符作用在所有...

月小升
30分钟前
70
0
聚类索引与非聚类索引

聚集索引的叶节点就是最终的数据节点,而非聚集索引的叶节仍然是索引节点,但它有一个指向最终数据的指针。

无名氏的程序员
35分钟前
74
0
Quick BI 新版地图来袭,报表展现分分钟变高级!

在BI产品的所有图表组件中,地图图表组件,由于其展示效果直观且生动,一直是报表中必不可少的部分。地图图表的插入,也可以立马让报表变得高大上,分分钟吸引老板的注意! 在这个风和日丽的好...

阿里云官方博客
35分钟前
58
0
在线办公第二周,还有哪些安全威胁待解决?

上周,为保障员工健康安全,大量企业开启在线办公模式。“云复工”第一周,在经历VPN接入需求暴增、视频会议因洪峰爆发出现卡顿掉线等“新状况”后,各类安全威胁也正在凸显。 疫情无情,安全...

baishancloud
39分钟前
71
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部