分布式一致性算法 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算法