文档章节

Multi Paxos:Basic Paxos的进化

liangtee
 liangtee
发布于 2014/08/20 16:25
字数 940
阅读 2850
收藏 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
粉丝 106
博文 94
码字总数 38111
作品 0
朝阳
程序员
私信 提问
架构设计:系统存储(25)——数据一致性与Paxos算法(下)

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

yinwenjie
2017/03/20
0
0
一致性协议算法-------------Paxos算法

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

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

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

蒲聪
2017/06/19
0
0
Paxos的通俗理解及其在数据库高可用上的使用

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

蒲聪
2017/06/19
0
0
[翻译]postgres的paxos 一致性复制

题记: 这是Postgres 现有的一个paxos 复制,可能PostgreSQL的早期版本中没有完整的逻辑复制,里面的表复制使用dblink 来实现,个人以前也做过类似的组件,但是是在外部调用,没有更改postgre...

MtrS
2016/12/14
216
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊flink的Table API及SQL Programs

序 本文主要研究一下flink的Table API及SQL Programs 实例 // for batch programs use ExecutionEnvironment instead of StreamExecutionEnvironmentStreamExecutionEnvironment env = Stre......

go4it
31分钟前
1
0
mysqldump应用

备份单个库/表数据或库/表结构 命令行下具体用法如下: mysqldump -u用戶名 -p密码 -d 数据库名 表名 > 备份文件名 1、导出数据库为dbname的表结构(其中用戶名為root,密码为dbpasswd,生成的...

阿dai
39分钟前
1
0
shell脚本与Python的交互

1、Python针对shell获取传入,输出参数 传入:"$num" 例如: $0表示文件名,$1表示shell获取的第一个参数 输出:通过打印shell结果的方式,输出参数给Python。 例如: echo "{$iplist}",Python调...

一口今心
41分钟前
1
0
Euler 今日问世!国内首个工业级的图深度学习开源框架,阿里妈妈造

阿里妹导读:千呼万唤始出来!阿里妈妈正式公布重磅开源项目——图深度学习框架Euler。这是国内首个在核心业务大规模应用后开源的图深度学习框架。此次开源,Euler内置了大量的算法供用户直接...

阿里云官方博客
49分钟前
1
0
TiDB 3.0 Beta Release Notes

2019 年 1 月 19 日,TiDB 发布 3.0 Beta 版,对应 master branch 的 TiDB-Ansible。相比 2.1 版本,该版本对系统稳定性、优化器、统计信息以及执行引擎做了很多改进。 TiDB 新特性 支持 Vi...

TiDB
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部