分布式一致性算法 Paxos

Paxos 是著名的分布式一致性算法，Google Chubby的作者Mike Burrows对Paxos的评价极高：

“这个世界上只有一种一致性算法，那就是 Paxos”。

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

Paxos 解决什么问题

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

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

集群内各个节点需要做数据同步，如果没有一致性算法做保证，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算法后，流程可能就是这样的：

节点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. 提案已经生效，后来的提案只能学习已生效的

节点1发起提案，编号为1，得到了3个节点的同意，提案生效。

紧接着，节点2发起提案，编号为2，发给了节点3、4、5。

节点3发现编号2大于自己的编号1，那么同意，并返回了自己已经接受的提案 (1,x) 。

节点5从所有返回值中找到提案编号最大的值 x ，作为自己的提案内容，发出  accept(2,x) 请求。

节点3、4、5收到后，发现编号大于自己的，接受了提案。

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

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

节点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. 先发起的提案失效，后来的提案生效

节点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需要接受已经生效的提案。

小结

以上是Paxos最基本的思路，如果有兴趣，可以好好看看这两篇文章：

https://segmentfault.com/a/1190000018844326

https://zh.wikipedia.org/zh-cn/Paxos算法

点击:point_down: 阅读原文 查看 文章列表