分布式之Paxos共识算法分析

写在前面

分布式共识是分布式系统中的重要内容，本文来一起看下，一种历史悠久（1998由兰伯特提出，并助其获得2003年图灵奖）的实现分布式共识的算法Paxos。Paxos主要分为两部分，Basic Paxos和Multi-Paxos,其中Basic Paxos用来使得一个值在多个副本集中达成共识，Multi-Paxos用来使得多个值在副本集中达成共识，所以Multi-Paxos可以看做是basic paxos的批量版本。下面我们就一起来看下吧！

1：paxos算法的角色和阶段

一部电影有各种角色（主角，配角，龙套），一部电视剧也一样，自然的，一个算法也是如此，paxos亦是如此，所以我们先来看下paxos都有哪些角色:

1：提议者（Proposer），负责发起某个值的修改，一般是多个副本中收到更新请求的那个副本
2：接受者（Acceptor）,对提议的值进行投票，一般是多个副本中其他副本
3：学习者（learner），被动接收达成共识的值，一般是slave

可参考下图：

2：basic paxos

假定有客户端1和客户端2（作为提议者角色），在时间1和时间2（时间1早于时间2）分别发起设置x为2和x为7的提议，接受者有节点A,节点B，节点C，如下图：

该算法一共分为两个阶段，分别是准备阶段和接受阶段。另外达成共识传递的数据是(提案编号，提案值)，提案编号可以认为是数据的版本号，时间越新，则编号越新，提案值就是要达成共识的值，首先我们按照上图进入准备阶段。假设客户端1的提案编号是1000，客户端2的提案编号是2000，则客户端1的完整消息是(1000,2),客户端2的完整消息是(2000,7)。

2.1：准备阶段

注意该阶段发送的消息，不需要提案值，因为只是确定在接受阶段使用哪个提案编号即可。

在时间1，节点A和节点B收到了客户端1的消息(1000,),节点C收到了客户端2的消息(2000,)，因为此时是各个节点收到的第一条消息，所以都会返回尚无提案，以节点A为例，返回尚无提案的意思是，当前自己还没有通过任何提案，且保证，之后如果是收到小于1000的提案，则不会做任何响应，且不会通过任何编号小于1000的提案，如下图：

在时间2，节点A和节点B收到了客户端2的消息(2000,)因为2000>1000,所以节点A和节点B会给客户端2返回尚无提案，节点C收到了客户端1的消息(1000,),因为1000<2000，所以节点C不会对客户端1做出任何的响应，而是直接丢弃，如下图：

到这里准备阶段结束，进入接受阶段。

2.2：接受阶段

此时节点A，节点B，节点C所能够接受的最小提案编号是2000，所有提案编号小于等于2000的消息都将会被丢弃，如下图，

在一段时间后，客户端1和客户端2分别将消息(1000,2),(2000,7)发送给节点A，节点B，和节点C，如下图：

因为此时节点A，节点B，节点C所能够接受的最小提案编号是2000,所以来自客户端1消息(1000,2)将会被丢弃，而最终消息(2000,7)被接受，如下图：

这样节点A，节点B，节点C就对x的值达成了共识，即x=7。

2.3：源码实现

以上准备阶段和接受阶段源码实现参考这里 ，运行截图解释如下：

3：multi paxos

首先说明，兰伯特的论文中关于multi paxos的描述很抽象，并没有给出具体的方案以及实现，只是给出了一些概念，所以准确来说multi paxos只是一种思想，而非一种具体的算法，但是可以基于这种思想来提供具体的算法实现，比如chubby（类似于zookeeper的一种分布式服务框架）对于multi paxos的实现和落地。以及raft算法也是其具体实现。

在basic paxos中，分为了准备阶段和接受阶段，其中准备阶段用于确定某个数据的最新版本的修改，接受阶段用于同步值到所有的节点。这里需要准备阶段的原因是，可能存在多个提议者提案有冲突的情况，那么如果我们能够解决提案冲突的问题，是不是就可以将准备阶段取消掉了（会直接减少一半的网络交互，性能会得到极大的提高），multi paxos解决这个问题的方式是来引入一个leader节点，此时结构可能如下：

所有提案都从这个leader发出，因为只会从一个节点发出提案，也就不存在冲突的问题了，如下图：

那么当我们有多个值需要达成共识时，只需要进行多轮优化后的basic paxos就可以了。

写在后面

小结

本文分析了paxos算法的basic paxos和multi paxos，并详细分析了basic paxos，然后给出了具体的代码实现。最后，分析了basic paxos存在的问题，以及multi paxos基于此的优化。希望本文能够帮助到你。

参考文章列表