分布式确实是一个有趣的话题，只要你留心观察，分布式在生活中无处不在。

悟空哥最开始学习分布式是从一篇非常用心写的技术征文开始的，而且这篇文章获得了征文第一名，在此感谢掘金社区提供的平台。想学习的同学可以点这个文章链接：《这三年被分布式坑惨了，曝光十大坑》

前两讲主要是讲解分布式理论，涉及到了分布式的四大理论。

**拜占庭将军问题：**《用三国杀讲分布式算法，舒适了吧？》

**BASE、CAP、ACID：**《用太极拳讲分布式理论，舒服！》

从这篇开始，将会讲解分布式的八大协议/算法。本篇主要讲解 Paxos 共识算法。

本文主要内容如下：


`Paxos` 是分布式算法中的老大哥，可以说 Paxos 是分布式共识的代名词。最常用的分布式共识算法都是基于它改进。比如 Raft 算法（后面也会介绍）。所以学习分布式算法必须先学习 Paxos 算法。

Paxos 算法主要包含两个部分：

- **Basic Paxos 算法**：多个节点之间如何就某个值达成共识。（这个值我们称作`提案 Value`）

- **Multi-Paxos 算法**：执行多个 Basic Paxos 实例，就一系列值达成共识。

Basic Paxos 算法是 Multi-Paxos 思想的核心，Multi 的意思就是多次，也就是说多执行几次 Basic Paxos 算法。所以 Basic Paxos 算法是重中之重。

三国中刘备集团，有两大军师：诸葛亮和庞统，都是非常厉害的人物，当他们有不同作战计划给多名武将时，如何达成一致？

Paxos 中有三种角色：提议者、接受者、学习者。

让我们用更通俗的方式来讲解 Paxos 算法。让我们穿越回东汉末年，刘备集团的帐营中一同学习 Paxos 算法是怎么攻打曹操的。

刘备的帐营中人物介绍：

- **主公一名**：`刘备`，作为请求方或`客户端`。

- **军师两名**：`诸葛亮`、`庞统`，作为`提议者`。

- **武将三名**：`关羽`、`张飞`、`赵云`，作为`接受者`。

- **文臣两名**：`法正`、`马良`，作为`学习者`。


- 提议一个值，用于投票表决。

- 接入和协调，收到客户端的请求后，可以发起二阶段提交，进行共识协商。

- `映射`到上面的故事中，`军师`就是用来部署作战计划的。

- 对每个提议的值进行投票，并存储接受的值。

- 投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存。

- `映射`到上面的故事中，`武将`就是用来接受军师的作战计划。

- 其实，集群中所有的节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。

- 被告知投票的结果，接受达成共识的值，存储数据，

- 不参与投票的过程，即不参与共识协商。

- `映射`到上面的故事中，就是两名`文臣`作为记录作战方案的`备胎`。

为什么说节点可以扮演接受者，也可以扮演提议者呢？

上篇我在讲解 BASE 协议的时候，讲到`二阶段`提交协议。其中有一个协调者的身份，协调者既可以是接受者，也可以是提议者。

- **作为接受者**，接收客户端的消息。比如`诸葛亮`需要接收`刘备`的作战要求。

- **作为提议者**，发起二阶段提交。然后这个节点和另外其他节点作为接受者进行共识协商。比如`诸葛亮`要汇总最终的作战计划给`刘备`。

如下图所示，节点 1 作为提议者和接受者，节点 2 和节点 3 作为接受者。


三国中有刘备集团（占据西蜀）、曹操集团（占据北边）、孙权集团（占据江南）。

`诸葛亮`和`庞统`作为提议者，向三个接受者进作战计划的提案。提案中有两个属性：

- `提案编号`，每次军师进行提案，都会有个编号，这里用 n 表示。

- `提议值`，也就是作战计划，这里用 v 表示。所以提案就是 [n, v]。

`诸葛亮`的作战计划是从`北边`进攻曹操，`庞统`的作战计划是从`南边`进攻曹操，**而关羽、张飞、赵云先后收到了他们的作战计划，该听谁的呢**？这里就是一个`共识`的问题。而 Paxos 算法达成共识分两个阶段。`准备（Prepare）阶段`和`接受（Accept）阶段`。

诸葛亮和庞统作为提议者，分别向所有的接受者（关羽、张飞、赵云）发送包含作战计划编号（提案编号）的`准备请求`，但不包含作战计划（提案值）。

- 提议者`诸葛亮`先发送编号为 `1` 的作战计划的准备请求，`庞统`发送编号为 `2` 的作战计划的准备请求。

- 接受者`关羽`（节点 X）在`8 点`收到来自诸葛亮发送的作战计划准备请求，在`10 点` 收到来自庞统发送的作战计划准备请求。

- 接受者`张飞`（节点 Y）在`9 点`收到来自诸葛亮发送的作战计划准备请求，在 `11 点` 收到来自庞统发送的作战计划准备请求。

- 接受者`赵云`（节点 Z）在 `12 点` 收到来自庞统发送的作战计划准备请求，在`13 点`收到来自诸葛亮发送的作战计划准备请求。


注意：准备阶段不需要携带具体的作战计划，所以作战计划可以为空，但是提议编号必须有。

按照接受请求的时间顺序，关羽和张飞收到诸葛亮的请求` [1，空]`，赵云收到庞统的请求` [2，空]`。


因为关羽、张飞之前没有收到提案，所以返回一个`尚无提案`的响应。也就是告诉诸葛亮，不会再响应编号小于等于 `1` 的准备请求了，也不会通过编号小于 `1` 的提案。**响应的时间点是 14 点和 15 点**。

而赵云之前也没有收到提案，所以返回一个`尚无提案`的响应。也就是告诉庞统，不会再响应编号小于等于 `2` 的准备请求了，也不会通过编号小于 `2` 的提案。**响应的时间点是 16 点**。


而对于庞统的准备请求，关羽、张飞收到编号为 `2` 的准备请求，而 编号 `2` 大于之前接受到的编号 `1` ，而且关羽和张飞没有通过任何提案，所以还是会返回给庞统一个`尚无提案` 的响应。也就是告诉庞统不会再响应编号小于等于 `2` 的准备请求了，也不会通过编号小于 `2` 的提案。响应的时间点是 **14 点和 15 点**。

而赵云最后收到诸葛亮编号为 `1` 的`准备请求`后，因编号 `1`小于之前响应的准备请求的提案编号 `2`，所以直接丢弃该准备请求，不做响应，如上图的 ❌ 图示。

诸葛亮和庞统收到准备响应后，会分别发送接受请求，如下图所示：


`诸葛亮`收到大多数接受者（关羽和张飞）的`准备响应`后，根据响应中提案编号最大的提案的值，设置`接受请求`中的值。因为关羽和张飞返回的准备响应都是尚无提案，所以还是发送提案编号为 `1`，提案值为`北`的`接受请求`，`北`代表从北边进攻曹操。发送的时间点是 **15 点过 1 分、16 点**。

**为什么是 15 点过 1 分？** 因为只要满足大多数接受者的准备请求后，就可以发送`接受请求`了。关羽和张飞响应的时间点是 14 点和 15 点，所以 15 点以后就可以发送了。

而`庞统`收到大多数接受者（关羽、张飞和赵云）的`准备响应`后，根据响应中提案编号最大的提案的值，，设置`接受请求`中的值。因为关羽、张飞和赵云返回的准备响应都是尚无提案，所以还是发送提案编号为 `2`，提案值为`南`的`接受请求`，`南`代表从南边进攻曹操。发送的时间点是 **18 点、19 点、20 点**。

当关羽、张飞、赵云收到诸葛亮和庞统的`接受请求`后，会进行如下处理，如下图所示：


关羽、张飞、赵云收到诸葛亮发送的提案 [1，北]时候，因为提案编号 `1`小于他们承诺的能通过的提案的最小提案编号 `2`，所以诸葛亮的提案被拒绝了。

而当他们收到庞统的发送的提案 [2，南] 的时候，因为编号 2 不小于之前承诺的编号 2，所以通过庞统的提案 [2，南] ，所以关羽、张飞、赵云他们的作战计划是从南边进攻曹操。**达成了共识**。

当接受者通过了一个提案时，就通知所有的学习者。当学习者发现大多数的接受者都通过了某个提案，那么学习者也会通过该提案，接受该提案的值。

也就是说关羽、张飞、赵云达成了共识后，学习者`法正`和`马良`也同样通过**从南边进攻的作战计划**。

- Basic Paxos 也是通过二阶段提交协议达成共识。准备阶段、接受阶段。不知道二阶段提交协议的，可以看我前面的文章。《用太极拳讲分布式理论，舒服！》

- Basic Paxos 不仅仅实现了共识，还实现了容错。有少于一半的节点出现故障时，集群也能正常工作。文中也多次强调了大多数节点都同意的原则，而这个原则赋予了 Basic Paxos 容错的能力。

- 提案编号代表优先级，保证了三个承诺：

- 如果`准备请求`的提案编号，`小于等于`接受者已经响应的`准备请求`的提案编号，那么接受者将承诺不响应这个`准备请求`。

- 如果`接受请求`中的提案的提案编号，`小于`接受者已经响应的`准备请求`的提案，那么接受者将承诺不通过这个提案。

- 如果接受者之前有通过提案，那么接受者将承诺，会在`准备请求`的响应中，包含已经通过的最大编号的提案信息。

如果关羽和张飞已经通过了提案 `[2，南]`，而赵云还未通过任何提案，当第三名军师`简雍`提出一个提案，编号为 8，作战计划为从东边进攻曹操，也就是 `[8, 东]`的作战计划，那么最终关羽、张飞、赵云的作战计划是怎么样的？欢迎评论区留言。