用户您好!请先登录!

分布式系统中的一致性协议

分布式系统中的一致性协议

目前分布式系统中常见的一些一致性协议:两阶段提交协议,三阶段提交协议,向量时钟,RWN协议,paxos协议,Raft协议。

一. 两阶段提交协议(2PC)

两阶段提交协议,简称2PC,是比较常用的解决分布式事务问题的方式,要么所有参与进程都提交事务,要么都取消事务,即实现ACID中的原子性(A)的常用手段。

两阶段提交将提交过程划分为连续的两个阶段:表决阶段(Voting)和提交阶段(Commit)。假设在没有故障发生的情形下,两阶段提交协议由下列操作序列构成,如下图所示:

分布式系统中的一致性协议总结

协调者的有限状态机如下图:

分布式系统中的一致性协议总结

如上图所示:协调者初始处于INIT状态,当接收到系统发出的Commit消息后,向参与者多播Vote-request消息后转入WAIT状态,在此进入阻塞状态,因为要等待所有参与者发送返回的消息,当收到所有参与者的返回消息后,如果其中包含Vote-Abort消息,则多播Global-abort消息后转入ABORT状态,否则多播Global-commit消息后转入COMMIT状态。

参与者的有限状态机如下图:

分布式系统中的一致性协议总结

如上图所示:参与者初始处于INIT状态,当接收到Vote-Request消息时,发出Vote-commit会转入READY状态,告诉协调者已经准备做好提交准备,否则就返回一个VOTE-ABORT消息。等待协调者行为,如果收到Global-Abort消息,就会进入Abort状态,如果收到Global-commit消息,就会转入COMMIT状态。

从两者的有限状态机可以看出,在所有可能状态中,存在三个阻塞状态:协调者的WAIT状态,参与者的INIT状态和READY状态。

二. 三阶段提交协议(3PC)

3PC就是在2PC基础上将2PC的提交阶段细分位两个阶段:预提交阶段和提交阶段。

3PC中协调者的有限状态机如下图:

分布式系统中的一致性协议总结

3PC中参与者的有限状态机如下图:

分布式系统中的一致性协议总结

三. 向量时钟

通过向量空间祖先继承的关系比较, 使数据保持最终一致性,这就是向量时钟的基本定义。

下面给出一个场景来说明向量时钟的作用:

分布式系统中的一致性协议总结

Vector Clock就是为了解决这种问题而设计的,简单来说,就是为每个商议结果加上一个时间戳,当结果改变时,更新时间戳。所以加上时间戳之后,我们再一次描述上面的场景,如下:

分布式系统中的一致性协议总结

以上这个决策用到了向量时钟,有个图还比较清晰了说明整个过程:

分布式系统中的一致性协议总结

四. NWR协议

NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中,就应用NWR来控制一致性。

让我们先来看看这三个字母的含义:

N:在分布式存储系统中,有多少份备份数据

W:代表一次成功的更新操作要求至少有w份数据写入成功

R: 代表一次成功的读数据操作要求至少有R份数据成功读取

NWR值的不同组合会产生不同的一致性效果,当W+R>N的时候,整个系统对于客户端来讲能保证强一致性。当W+R 以常见的N=3、W=2、R=2为例:

N=3,表示,任何一个对象都必须有三个副本(Replica),W=2表示,对数据的修改操作(Write)只需要在3个Replica中的2个上面完成就返回,R=2表示,从三个对象中要读取到2个数据对象,才能返回。

在分布式系统中,数据的单点是不允许存在的。即线上正常存在的Replica数量是1的情况是非常危险的,因为一旦这个Replica再次错误,就 可能发生数据的永久性错误。假如我们把N设置成为2,那么,只要有一个存储节点发生损坏,就会有单点的存在。所以N必须大于2。N约高,系统的维护和整体 成本就越高。工业界通常把N设置为3。

当W是2、R是2的时候,W+R>N,这种情况对于客户端就是强一致性的。

分布式系统中的一致性协议总结

在上图中,如果R+W>N,则读取操作和写入操作成功的数据一定会有交集(如图中的B),这样就可以保证一定能够读取到最新版本的更新数据,数据的强一致性得到了保证。在满足数据一致性协议的前提下,R或者W设置的越大,则系统延迟越大,因为这取决于最慢的那份备份数据的响应时间。而如果R+W<=N,则无法保证数据的强一致性,因为成功写和成功读集合可能不存在交集,这样读操作无法读取到最新的更新数值,也就无法保证数据的强一致性。

在具体实现系统时,仅仅依靠NWR协议还不能完成一致性保证,因为在上述过程中,当读取到多个备份数据时,需要判断哪些数据是最新的,如何判断数据的新旧?这需要向量时钟来配合,所以对于Dynamo来说,是通过NWR协议结合向量时钟来共同完成一致性保证的。

五. paxos协议

Paxos算法的目的

Paxos算法的目的是为了解决分布式环境下一致性的问题。

多个节点并发操纵数据,如何保证在读写过程中数据的一致性,并且解决方案要能适应分布式环境下的不可靠性(系统如何就一个值达到统一)

Paxos的两个组件

  • Proposer

提议发起者,处理客户端请求,将客户端的请求发送到集群中,以便决定这个值是否可以被批准。

  • Acceptor

提议批准者,负责处理接收到的提议,他们的回复就是一次投票。会存储一些状态来决定是否接收一个值

Paxos有两个原则

1)安全原则—保证不能做错的事

a) 针对某个实例的表决只能有一个值被批准,不能出现一个被批准的值被另一个值覆盖的情况;(假设有一个值被多数Acceptor批准了,那么这个值就只能被学习)

b) 每个节点只能学习到已经被批准的值,不能学习没有被批准的值。

2)存活原则—只要有多数服务器存活并且彼此间可以通信,最终都要做到的下列事情:

a)最终会批准某个被提议的值;

b)一个值被批准了,其他服务器最终会学习到这个值。

Paxos具体流程图

分布式系统中的一致性协议总结

第一阶段(prepare)

1).获取一个proposal number, n;

2).提议者向所有节点广播prepare(n)请求;

3).接收者(Acceptors比较善变,如果还没最终认可一个值,它就会不断认同提案号最大的那个方案)比较n和minProposal,如果n>minProposal,表示有更新的提议minProposal=n;如果此时该接受者并没有认可一个最终值,那么认可这个提案,返回OK。如果此时已经有一个accptedValue, 将返回(acceptedProposal,acceptedValue);

4).提议者接收到过半数请求后,如果发现有acceptedValue返回,表示有认可的提议,保存最高acceptedProposal编号的acceptedValue到本地

第二阶段(Accept)

5)广播accept(n,value)到所有节点;

6).接收者比较n和minProposal,如果n>=minProposal,则acceptedProposal=minProposal=n,acceptedValue=value,本地持久化后,返回;

否则,拒绝并且返回minProposal

7).提议者接收到过半数请求后,如果发现有返回值>n,表示有更新的提议,跳转1(重新发起提议);否则value达成一致。

Paxos议案ID生成算法

在Google的Chubby论文中给出了这样一种方法:假设有n个proposer,每个编号为ir(0<=ir<n),proposal编号的任何值s都应该大于它已知的最大值,并且满足:

s %n = ir => s = m*n + ir

proposer已知的最大值来自两部分:proposer自己对编号自增后的值和接收到acceptor的拒绝后所得到的值。

例: 以3个proposer P1、P2、P3为例,开始m=0,编号分别为0,1,2。

1) P1提交的时候发现了P2已经提交,P2编号为1 >P1的0,因此P1重新计算编号:new P1 = 1*3+1 = 4;

2) P3以编号2提交,发现小于P1的4,因此P3重新编号:new P3 = 1*3+2 = 5。

Paxos原理

任意两个法定集合,必定存在一个公共的成员。该性质是Paxos有效的基本保障

活锁

当某一proposer提交的proposal被拒绝时,可能是因为acceptor 承诺返回了更大编号的proposal,因此proposer提高编号继续提交。 如果2个proposer都发现自己的编号过低转而提出更高编号的proposal,会导致死循环,这种情况也称为活锁。

比如说当此时的 proposer1提案是3, proposer2提案是4, 但acceptor承诺的编号是5,那么此时proposer1,proposer2 都将提高编号假设分别为6,7,并试图与accceptor连接,假设7被接受了,那么提案5和提案6就要重新编号提交,从而不断死循环。

异常情况——持久存储

在算法执行的过程中会产生很多的异常情况:proposer宕机,acceptor在接收proposal后宕机,proposer接收消息后宕机,acceptor在accept后宕机,learn宕机,存储失败,等等。

为保证paxos算法的正确性,proposer、aceptor、learn都实现持久存储,以做到server恢复后仍能正确参与paxos处理。

propose存储已提交的最大proposal编号、决议编号(instance id)。

acceptor存储已承诺(promise)的最大编号、已接受(accept)的最大编号和value、决议编号。

learn存储已学习过的决议和编号

六. Raft协议

另见其它文章分享。

行走的code
行走的code

要发表评论,您必须先登录