Coin163

一致性 分布式一致性算法--Paxos

2016-07-23by admin, 次阅读

本篇文章主要介绍了"一致性 分布式一致性算法--Paxos",主要涉及到一致性方面的内容,对于MySql感兴趣的同学可以参考一下: Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法。Paxos算法解决的问题是...

      Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法。Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。在工程实践意义上来说,就是可以通过Paxos实现多副本一致性,分布式锁,名字管理,序列号分配等。比如,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。本文首先会讲原始的Paxos算法(Basic Paxos),主要描述二阶段提交过程,然后会着重讲Paxos算法的变种(Multi Paxos),它是对Basic Paxos的优化,而且更适合工程实践,最后我会通过Q&A的方式,给出我在学习Paxos算法中的疑问,以及我对这些疑问的理解。

概念与术语
Proposer:提议发起者,处理客户端请求,将客户端的请求发送到集群中,以便决定这个值是否可以被批准。
Acceptor:提议批准者,负责处理接收到的提议,他们的回复就是一次投票,会存储一些状态来决定是否接收一个值。
replica:节点或者副本,分布式系统中的一个server,一般是一台单独的物理机或者虚拟机,同时承担paxos中的提议者和接收者角色。
ProposalId:每个提议都有一个编号,编号高的提议优先级高。
Paxos Instance:Paxos中用来在多个节点之间对同一个值达成一致的过程,比如同一个日志序列号:logIndex,不同的logIndex属于不同的Paxos Instance。
acceptedProposal:在一个Paxos Instance内,已经接收过的提议
acceptedValue:在一个Paxos Instance内,已经接收过的提议对应的值。
minProposal:在一个Paxos Instance内,当前接收的最小提议值,会不断更新

Basic-Paxos算法
     基于Paxos协议构建的系统,只需要系统中超过半数的节点在线且相互通信正常即可正常对外提供服务。它的核心实现Paxos Instance主要包括两个阶段:准备阶段(prepare phase)和提议阶段(accept phase)。如下图所示:

 分布式一致性算法--Paxos
1.获取一个ProposalId,为了保证ProposalId递增,可以采用时间戳+serverId方式生成;
2.提议者向所有节点广播prepare(n)请求;
3.接收者比较n和minProposal,如果n>minProposal,表示有更新的提议,minProposal=n;否则将(acceptedProposal,acceptedValue)返回;
4.提议者接收到过半数请求后,如果发现有acceptedValue返回,表示有更新的提议,保存acceptedValue到本地,然后跳转1,生成一个更高的提议;
5.到这里表示在当前paxos instance内,没有优先级更高的提议,可以进入第二阶段,广播accept(n,value)到所有节点;
6.接收者比较n和minProposal,如果n>=minProposal,则acceptedProposal=minProposal=n,acceptedValue=value,本地持久化后,返回;
否则,返回minProposal
7.提议者接收到过半数请求后,如果发现有返回值>n,表示有更新的提议,跳转1;否则value达成一致。
从上述流程可知,并发情况下,可能会出现第4步或者第7步频繁重试的情况,导致性能低下,更严重者可能导致永远都无法达成一致的情况,就是所谓的“活锁”,如下图所示:

  分布式一致性算法--Paxos

1.S1作为提议者,发起prepare(3.1),并在S1,S2和S3达成多数派;
2.随后S5作为提议者 ,发起了prepare(3.5),并在S3,S4和S5达成多数派;
3.S1发起accept(3.1,value1),由于S3上提议 3.5>3.1,导致accept请求无法达成多数派,S1尝试重新生成提议
4.S1发起prepare(4.1),并在S1,S2和S3达成多数派
5.S5发起accpet(3.5,value5),由于S3上提议4.1>3.5,导致accept请求无法达成多数派,S5尝试重新生成提议
6.S5发起prepare(5.5),并在S3,S4和S5达成多数派,导致后续的S1发起的accept(4.1,value1)失败

......

prepare阶段的作用
从Basic-Paxos的描述可知,需要通过两阶段来最终确定一个值,由于轮回多,导致性能低下,至少两次网络RTT。那么prepare阶段能否省去?如下图所示:

 分布式一致性算法--Paxos
1.S1首先发起accept(1,red),并在S1,S2和S3达成多数派,red在S1,S2,S3上持久化
2.随后S5发起accept(5,blue),对于S3而言,由于接收到更新的提议,会将acceptedValue值改为blue
3.那么S3,S4和S5达成多数派,blue在S3,S4和S5持久化
4.最后的结果是,S1和S2的值是red,而S3,S4和S5的值是blue,没有达成一致。

所以两阶段必不可少,Prepare阶段的作用是阻塞旧的提议,并且返回已经接收到的acceptedProposal。同时也可以看到的是,假设只有S1提议,则不会出现问题,这就是我们下面要讲的Multi-Paxos。

Multi-paxos算法
     Paxos是对一个值达成一致,Multi-Paxos是连续多个paxos instance来对多个值达成一致,这里最核心的原因是multi-paxos协议中有一个Leader。Leader是系统中唯一的Proposal,在lease租约周期内所有提案都有相同的ProposalId,可以跳过prepare阶段,议案只有accept过程,一个ProposalId可以对应多个Value,所以称为Multi-Paxos。


MYSQL企业常用架构与调优经验分享

MYSQL企业常用架构与调优经验分享",主要涉及到Mysql,经验分享方面的内容,对于MySql感兴趣的同学可以参考一下: 一、选择Percona Server、MariaDB还是MYSQL mysql应用源码:http...

MySQL 入门(六)—— 索引 mysql官网客户端 mysql 命令 mysql安装

MySQL 入门(六)—— 索引",主要涉及到Mysql方面的内容,对于MySql感兴趣的同学可以参考一下: 索引是一种特殊的数据库结构,可用来快速查询数据库表中的特定记录。...

阿里云初始化mysql数据库安装55版本 mysql数据库下载64位 sql数据库实例下载 sql数据库补丁下载

阿里云初始化mysql数据库安装55版本",主要涉及到Mysql数据库方面的内容,对于MySql感兴趣的同学可以参考一下: 1.首先清除5.1版本的多余包(有些阿里云版本系统里有残留...

------分隔线----------------------------