用户您好!请先登录!

看得懂的分布式协调算法Paxos图解

看得懂的分布式协调算法Paxos图解

Google Chubby的作者Mike Burrows对Paxos的评价极高:“这个世界上只有一种一致性算法,那就是 Paxos”。

其实也不为过,像非常有名的 Raft 算法、Zab 算法等都是基于 Paxos 的简化和改进。

Paxos 解决什么问题

Paxos 是解决分布式环境下多节点的数据一致性问题,先看下一致性问题。

例如一个cache集群有3个节点,每个节点都可以写入。

深度原理学习之–让人看得懂的分布式协调算法Paxos图解

集群内各个节点需要做数据同步,如果没有一致性算法做保证,3个节点内数据就可能混乱,例如:

  • 节点1收到请求后,同步给节点2、3,节点2立即收到了,但因为网络原因,节点3没有立即同步。
  • 在节点3同步之前,节点2也发起了同步请求,因为2、3间的网络状况好,节点3立即同步了。
  • 所以,节点1、2的同步顺序是x=1,x=2,而节点3的同步顺序是x=2,x=1,造成了节点间数据不一致。

Paxos 就是用来解决这个问题,保证各节点数据的绝对一致,不会混乱。

Paxos 的基本思路

Paxos把每次对数据的更改称为一个提案,就像一个委员会,其中一人发起一个提案,委员会成员对这个提案投票,票数过半的通过。

有3个角色:

  1. Proposer,提出提案
  2. Acceptor,对提案进行投票
  3. Learner,获取投票结果

Proposer 和 Acceptor 是委员会的,Learner 不参与投票过程,只接受通过的提案,所以可先忽略这个角色。

一次Paxos算法的执行实例中,只批准一个value,过程分为2个阶段:

(1)Prepare 准备阶段

Proposer 想发起提案,问各个 Acceptor :我是否可以发起?

(2)Accept 接受阶段

如果多数 Acceptor 都同意,那么 Proposer 就真正发出自己的提案,请求大家接受。 如果多数 Acceptor 都同意了,提案生效。

Acceptor 如何判断是否同意提案呢?下面是整个流程。

首先需要知道,Acceptor 持有3个变量:

  1. minProposal,自己目前持有的最小提案编号
  2. acceptedProposal,已经接受的提案编号
  3. acceptedValue,已经接受的提案内容

然后看流程图:

深度原理学习之–让人看得懂的分布式协调算法Paxos图解

对照上面那个示例,使用Paxos算法后,流程可能就是这样的:

深度原理学习之–让人看得懂的分布式协调算法Paxos图解
  • 节点1收到x=1的请求,节点1成为Proposer,拿到提案编号1,发起提案,得到了其他节点的同意,然后发送accept(1,1)请求,请求大家接受。
  • 节点1顺利同意,但由于网络问题,节点2、3暂时没有收到,由于此提案没有得到超过半数的同意,所以现在没有生效。
  • 这时节点2提出x=2的提案,顺利得到大家的同意,因为节点1已经接受了(1,1),会将其返回给节点2。
  • 节点2收到大家的同意确认,发现节点1的返回信息中含有已经接受的提案,就将其提案内容作为自己的提案,发送accept(2,1)。
  • 大家收到后,记录提案内容,返回确认信息,节点2的提案生效了。
  • 在此之后节点2、3才收accept(1,1)请求,由于这个请求的提案编号1小于自己已经接受的提案编号2,所以不会同意,直接拒绝。
  • 最终,3个节点都是x=1,保持一致。

Paxos 的3中典型情况

为了方便理解,下面以5个节点为例。

1. 提案已经生效,后来的提案只能学习已生效的

深度原理学习之–让人看得懂的分布式协调算法Paxos图解
  • 节点1发起提案,编号为1,得到了3个节点的同意,提案生效。
  • 紧接着,节点2发起提案,编号为2,发给了节点3、4、5。
  • 节点3发现编号2大于自己的编号1,那么同意,并返回了自己已经接受的提案(1,x)。
  • 节点5从所有返回值中找到提案编号最大的值x,作为自己的提案内容,发出accept(2,x)请求。
  • 节点3、4、5收到后,发现编号大于自己的,接受了提案。

结果是所有节点的数据一致为x。

2. 提案未生效,但已经被某节点接受,后来的提案只能学习已经接受的

深度原理学习之–让人看得懂的分布式协调算法Paxos图解
  • 节点1发起提案,因为网络问题,节点3最先接受,节点1、2没有接受。
  • 然后节点5发起提案,发给节点3、4、5。
  • 节点3一看编号比自己的大,表示同意,同时返回自己已经接受的(1,x)。
  • 节点5收到回复后,从所有返回值中找到编号最大的值x,作为自己的提案内容,发起接受请求accept(2,x)。
  • 节点3、4、5接到后,记录提案,提案生效。
  • 同时,节点1、2也收到了节点1的accept请求,记录提案。

结果是所有节点的数据一致为x。

3. 先发起的提案失效,后来的提案生效

深度原理学习之–让人看得懂的分布式协调算法Paxos图解
  • 节点1发起提案,节点1、2、3同意,但因为网络问题,节点1最先接受。
  • 在节点2、3还未接受时,节点5发起提案,发给了3、4、5。
  • 节点3、4、5一看编号比自己的大,同意。
  • 此时,节点3收到了节点1的accept请求,因为此时节点3自己记录的编号是2,大于节点1的编号,所以,节点3决绝了节点1的accept请求。
  • 节点5收到大家的确认后,从返回值中没有找到已接受的提案,所以使用自己的提案内容y作为提案内容,发起accept(2,y)请求。
  • 节点3、4、5接受,提案y生效。
  • 节点1的提案没有得到多数同意,所以失效,节点1、2需要接受已经生效的提案。
X-Eyes Admin
X-Eyes Admin

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