图解 Paxos 算法
Paxos 算法是一个分布式共识算法，由 Leslie Lamport 在 1989 年提出，该算法理解起来有一定的难度，本文尝试图形化解析 Paxos 算法。
Lamport 提出的 Paxos 算法包括两个部分：
- Basic Paxos 算法：多节点如何就某个值（提案Value）达成共识
- Multi-Paxos 思想：执行多个 Basic Paxos 实例，就一系列的值达成共识
Basic Paxos
思考题
假设现在有一个三节点的分布式集群，提供只读 KV 存储服务。只读 KV 服务，既创建只读变量（key）的时候，必须要对它进行赋值（value），而且这个值后续没办法修改。也就是说，只读变量在创建后就不能被修改了，所以所有节点必须要先对只读变量的值达成共识，然后再去创建这个只读变量。
那么，当有多个客户端（比如客户端 1、2）访问这个系统，试图创建同一个只读变量（比如 X），客户端 1 试图创建值为 5 的 X，客户端 2 试图创建值为 7 的 X，这样要如何达成共识，实现各节点上 X 值的一致呢？
在解决这个问题之前，先了解一下 Basic Paxos 的几个概念。
Paxos 涉及的概念
在 Basic Paxos 中，有提议者（Proposer）、接受者（Acceptor）、学习者（Learner）三种角色：
- 提议者：提议一个值，用于投票表决。为了方便演示，你可以把图 1 中的客户端 1 和 2 看作是提议者。但在绝大多数场景中，集群中收到客户端请求的节点，才是提议者（图 1 这个架构，是为了方便演示算法原理）。
- 接受者：每个提议的值进行投票，并存储接受的值，比如 A、B、C 三个节点。
- 学习者：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。
需要指出的是，一个节点，既可以是提议者，也可以是接受者；他们之间的关系如下：
其实，这三种角色，在本质上代表的是三种功能：
- 提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商
- 接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存
- 学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存
那么接下来，咱们看看如何使用 Basic Paxos 达成共识，解决开篇提到的那道思考题。
如何达成共识
在 Paxos 算法中，使用提案表示一个提议，提案包括提案编号和提议的值。接下来，我们使用 [n, v] 表示一个提案，其中，n 是提案编号，v 是提案的值。
在 Basic Paxos 中，集群中各个节点为了达成共识，需要进行 2 个阶段的协商，即准备（Prepare）阶段和接受（Accept）阶段。
准备阶段
假设客户端 1 的提案编号是 1，客户端 2 的提案编号为 5，并假设节点 A, B 先收到来自客户端 1 的准备请求，节点 C 先收到来自客户端 2 的准备请求。
客户端作为提议者，向所有的接受者发送包含提案编号的准备请求。注意在准备阶段，请求中不需要指定提议的值，只需要包含提案编号即可。
接下来，节点 A，B 接收到客户端 1 的准备请求（提案编号为1），节点 C 接收到客户端 2 的准备请求（提案编号为 5）。
集群中各个节点在接收到第一个准备请求的处理：
- 节点 A, B：由于之前没有通过任何提案，所以节点 A，B 将返回“尚无提案”的准备响应，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案
- 节点 C：由于之前没有通过任何提案，所以节点 C 将返回“尚无提案”的准备响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案
接下来，当节点 A，B 接收到提案编号为 5 的准备请求，节点 C 接收到提案编号为 1 的准备请求：
- 节点 A, B：由于提案编号 5 大于之前响应的准备请求的提案编号 1，且节点 A, B 都没有通过任何提案，故均返回“尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案
- 节点 C：由于节点 C 接收到提案编号 1 小于节点 C 之前响应的准备请求的提案编号 5 ，所以丢弃该准备请求，不作响应
接受阶段
Basic Paxos 算法第二阶段为接受阶段。当客户端 1，2 在收到大多数节点的准备响应之后会开始发送接受请求。
- 客户端 1：客户端 1 接收到大多数的接受者（节点 A, B）的准备响应后，根据响应中的提案编号最大的提案的值，设置接受请求的值。由于节点 A, B 均返回“尚无提案”，即提案值为空，故客户端 1 把自己的提议值 "5" 作为提案的值，发送接受请求 [1, "5"]
- 客户端 2：客户端 2 接收到大多数接受者的准备响应后，根据响应中的提案编号最大的提案的值，设置接受请求的值。由于节点 A, B, C 均返回“尚无提案”，即提案值为空，故客户端 2 把自己的提议值 "7" 作为提案的值，发送接受请求 [5, "7"]
当节点 A, B, C 接收到客户端 1, 2 的接受请求时，对接受请求进行处理：
- 节点 A, B, C 接收到接受请求 [1, "5"] ，由于提案编号 1 小于三个节点承诺可以通过的最小提案编号 5，所以提案 [1, "5"] 被拒绝
- 节点 A, B, C 接收到接受请求 [5, "7"]，由于提案编号 5 不小于三个节点承诺可以通过的最小提案编号 5 ，所以通过提案 [5, "7"]，即三个节点达成共识，接受 X 的值为 "7"
如果集群中还有学习者，当接受者通过一个提案，就通知学习者，当学习者发现大多数接受者都通过了某个提案，那么学习者也通过该提案，接受提案的值。
接受者存在已通过提案的情况
上面例子中，准备阶段和接受阶段均不存在接受者已经通过提案的情况。这里继续使用上面的例子，不过假设节点 A, B 已通过提案 [5, “7”]，节点 C 未通过任何提案；增加一个新的提议者客户端 3，客户端 3 的提案为 [9，”13”] 。
接下来，客户端 3 执行准备阶段和接受阶段；客户端 3 向节点 A, B, C 发送提案编号为 9 的准备请求：
- 节点 A, B 接收到客户端 3 的准备请求，由于节点 A, B 已通过提案 [5, "7"]，故在准备响应中，包含此提案信息。
- 节点 C 接收到客户端 3 的准备请求，由于节点 C 未通过任何提案，故节点 C 将返回“尚无提案”的准备响应。
- 客户端 3 接收到节点 A, B, C 的准备响应后，向节点 A, B, C 发送接受请求。这里需要特点指出，客户端 3 会根据响应中的提案编号最大的提案的值，设置接受请求的值。
- 由于在准备响应中，已包含提案 [5, "7"]，故客户端 3 将接受请求的提案编号设置为 9，提案值设置为 "7" 即接受请求的提案为 [9, "7"]
节点 A, B, C 接收到客户端 3 的接受请求，由于提案编号 9 不小于三个节点承诺可以通过的最小提案编号，故均通过提案 [9, “7”]。
概括来说，Basic Paxos 具有以下特点：
- Basic Paxos 通过二阶段方式来达成共识，即准备阶段和接受阶段
- Basic Paxos 除了达成共识功能，还实现了容错，在少于一半节点出现故障时，集群也能工作
- 提案编号大小代表优先级。对于提案编号，接受者提供三个承诺：
- 如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者承诺不响应这个准备请求
- 如果接受请求中的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者承诺不通过这个提案
- 如果按受者已通过提案，那些接受者承诺会在准备请求的响应中，包含已经通过的最大编号的提案信息
参考：
