Paxos 算法

1. 初识 Paxos 算法

Paxos 共识算法是 Lamport（莱斯利·兰伯特）在 1990 提出的一种分布式系统共识算法，大部分分布式一致性协议都是基于 Paxos 算法演变而来的。Paxos是基于消息传递且具有高度容错性的一致性算法，是 CAP 理论的落地者。

Paxos算法最早出现在兰伯特《The Part-Time Parliament》这篇论文里，而后续又对最初的论文做了简化，新出了一篇名为《Paxos Made Simple论文》的论文。

2. 为什么需要共识算法

单机部署方案中，由于现实中存在很多不可控因素，如网络故障、硬件故障、宕机等，这些都会导致该机器上部署的程序无法正常运行，导致不能响应外部请求，即 单点故障问题。

为了解决单点故障问题，集群模式由此诞生。对于不存储数据的业务系统来说，集群可谓是一个完美的解决方案。但是对于需要存储数据的服务（如 Redis）来说，虽然能保证可用性，但也带来了新的问题，最常见的就是一致性的问题。

• 集群中有多个节点时，如何解决多个节点写入时的冲突？

• 集群内发生网络分区问题时，如何避免集群出现脑裂问题？

• 使用读写分离时，如何保障多节点间读到的数据完全一致？

• ........

Paxos 正是为了解决上述一系列问题而诞生的。兰伯特当时提出的 Paxos 算法其实可以分为 2 类，：

• Basic Paxos 算法：论文中提到的 Paxos 算法，只具备单决策能力。

• Multi-Paxos 算法：《Paxos Made Simple》论文最后拓展提到的算法，具备多决策能力。

以下的分析也是基于 Basic Paxos 的。

3. Paxos 算法

3.1 三种角色

为了实现一致性的目标，在Paxos的定义中，存在三种角色，它们各自在系统里发挥着不同的作用，如下：

• Proposer 提案者：提案者负责接受客户端的请求并发起提案。提案信息通常包括提案编号 (Proposal ID) 和提议的值 (Value)。

• Acceptor接受者：负责对提议者的提案进行投票，同时需要记住自己的投票历史（即提案编号）。

• Learner学习者：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。

在分布式系统中，一个节点即可以是Paxos定义的提案者，也可以是接受者，又可以是学习者，即：并非一个节点只能担任一种角色，而是有可能会同时充当多种角色。

什么事提案呢？

提案其实就是一个申请，包含 提案编号（全局递增）和本地提案要达成一致的 value 值。

3.2 推导过程

客户端首先将请求发送给提案者，而集群内可能存在多个提案者，都能接受客户端请求。当不同客户端同时将请求发送到不同提案者，提案者将提案发送给接受者时，就有可能会发生冲突：

• 提案者 A 接收客户端请求将 x 的值改为 1，并发给接受者；

• 提案者 A 接收客户端请求将 x 的值改为 2，并发给接受者；

如果同时提出的方案都被接受者批准，就会出现集群内部分节点的 x 值为1，部分节点的 x 的值为2，这显然不符合 CAP 理论的一致性。那要怎么办呢？最简单的就是：

规定一：限定集群内只有一个接受者，且必须接受提出方案中的一个方案。

此时不论有多少个提案者提出方案，最终集群内也只会有一种方案，从而达到一致性。但是，这个办法是不可行的，为什么呢？还记得第二节中提到单点故障问题吗，如果这个接受者因为网络等原因不能响应提案者的请求，那岂不是整个集群服务都不能正常运行了，这是不能接受的。所以，接受者必定有多个。

多个接受者的存在又会带来新的问题，如果不同的方案，同时提交给不同的接受者，因为每个接受者之前都没接受过其他方案，所以不同的接受者一起接受，多种方案同时在集群内传播，又会因为方案冲突带来不一致。所以，需要修改一下接收的规则：一个方案必须被至少半数以上的接受者接受，才能通过。因此，一个提案者的提案需要发送给多个接受者；一个接受需要接受多个提案。所以为了让接受者区分出不同提案，需要给提案加上 编号（前面提到过的）。

规定二：一个方案必须被至少半数以上的接受者接受，才能通过。

通过这种过半机制，解决了 不同方案被被不同接受者接受的问题，但是新的问题又来了。假设现在接受者有三个，提案者有两个，那么对于一个提案者来说，它的提案只需要被两个接受者接收就会生效。提案者 A 将 x=1 的提案提交给两个接受者，提案者 B 同时也将 x=2 的提案提交给两个接受者，这样的话 A 和 B 的提案都会被接受，不一致的场景又会出现。所以，还需要加一个规定：

规定三：同一轮决策中一个接受者只允许接受一个方案，具体来说就是 同一轮决策中，所有的接受者都只能处理同一个方案。

上面仅是理想状态，但是实际存在之前说到过的不可控因素，看下面这个场景：

在 T1 时刻，接受者只有 C，提案者 A 提交了 x=1 这个方案，来看一下是否满足前面的约束：

• A 的方案对于接受者 C 来说，是收到的第一个方案，可以通过；

• T1 时刻，只有一位接受者，满足半数以上通过的条件；且只接受 A 的方案。

因此提案者 A 的提出的方案，满足约束，可以在集群内传播了。但是到了 T2 时刻，接受者 D 和 E 从网络故障、宕机中恢复了，这时提案者 B 提交了 x=2 这个方案，来看一下它的方案提交情况：

• B 的方案对于接受者 D 和 E 来说，是收到的第一个方案，D 和 E 接受并通过；

• 总共三个接受者，D 和 E 都通过，满足半数以上；

• T2 时刻，三个接受者同时对 B 的方案进行抉择。

提案者 A 的提出的方案，也满足约束，可以在集群内传播了。此时，可能由于学习者的网络延迟问题，导致这两个方案差不多一起实行，又造成了数据不一致的问题。

所以，即使已存在上述规定，也不能保证一轮决策中只通过一个提案，还需要继续完善规定：

规定四：当一个接受者通过一个提案后，在同一轮决策中，又收到了新的提案，就把前面通过的提案返回给新方案的提案者；提案者收到已经通过的提案后，就撤销新方案的提交，等待下一轮决策时重新提交。

有了这个规定后，重新看一下上面的例子：

因为接受者 C 已经通过了 A 的提案，因此收到 B 的提案时，会把 A 的提案返回给 B，根据规定四，B 收到已经通过的提案后，就知道此轮决策中已经有提案被通过了，从而撤销自己的提案，等待下一轮决策再提交。

综上所诉，根据以上的规定，Paxos 算法就能保证集群内部的一致性了。

3.3 实现过程

Paxos 有提案者、接受者、学习者三种角色，对应三个阶段，整体流程如下：

3.3.1 Prepare 阶段

Proposer 提出提案前，首先需要生成一个提案编号（全局唯一且递增），接受向至少半数以上的 Acceptor 发出 Prepare 请求，Prepare 请求仅仅携带本次生成的提案编号。

Acceptor 收到请求后，会给提案者返回响应，响应内容有以下情况：

• 如果此 Acceptor 之前确认过某个提案，则将之前的接受的提案（编号+ value）返回给 Proposer。

• 如果此 Acceptor 之前收到过其他提案但是还没确认通过，则判断两个提案的编号，如果本次请求的提案编号小于之前的提案编号，则 Acceptor 可以忽略当前的 Prepare 请求；或者直接返回错误提示。

• 如果本地请求的编号大于之前收到的提案编号，则响应此次 Prepare 请求（例如返回成功），同时不再接受小于本次提案编号的提案。

3.3.2 Accept 阶段

根据之前的规定，一个提案如果要被批准，需要半数以上的接受者接受。当一个 Proposer 发出Perpare 请求后，收到了大多数 Acceptor 的成功响应后，就可认为自己的提案通过，进入 Accept 阶段。

Accept 请求包含提案编号和 value，Proposer 在发起请求前会先判断：

• 如果之前发出的 Prepare 请求，没有 Acceptor 返回已确认的提案，则说明自己是第一个提案，本次的 Accept 请求会提交提案编号和 value；如果 Acceptor 返回了已确认的提案，本次 Accept 请求就将自己的编号+已确认的、编号最大的、提案的Value值，发送给至少大多数Acceptor。

Acceptor 接受到 Accept 请求的处理如下：

• 如果该 Accept 请求是自己收到的第一个提案，则必须确认该提案。

• 如果不是第一个 Accept 请求，则对比之前的 Accept 请求的提案编号，是否大于之前收到过的最大的 Prepare 请求编号，如果是，则确认；否则忽略本次 Accept 请求。

还是通过前面的例子来梳理一下目前的流程：

1. 提案者 A 收到客户端请求（x=1），提案者 B 也收到客户端请求（x=2）且后于 A；

2. 提案者 A 生成提案编号 1，并向 Acceptor 接受者 C、D、E 发起 Prepare 请求；

3. C、D、E 响应 A 的 Prepare 请求，并记录当前的提案编号 1；、

4. A 收到 C、D、E 响应后，发现得到了半数以上的支持，继续发起 Accept 请求；

5. C、D、E 之前都没有确认过提案，因此都会确认并记录的 A 的提案；

6. 提案者 B 后处理客户端请求，生成提案编号 2，向 C、D、E 发起 Prepare 请求；

7. 因为 C、D、E 已经确认过提案，所以返回给 B 的响应为 A的提案；

8. B 收到响应后，发现已确认的提案，并得到半数以上的响应，发起 Accept 请求，此时提案变为 提案编号 2 + value=(x=1)；

9. C、D、E 收到 B 的提案后，发现其编号最大，则会记录提案并确认。

10. 当 B 提交完 x=1 的 Accept 请求后，又会提出一个提案编号为 3的提案，对应 value 为 x=2。

3.3.3 Learn 阶段

Learn 阶段是最后的阶段，并不参与决策，只负责学习已确认过的提案，学习的前提是获取到已确认的提案，如何获取呢，有一下三种方案：

• Acceptor 确认一个提案后，就将该提案发送给所有的 Learner；

• Acceptor 确认一个提案后，将提案发送给一个 Learner，再由它通知剩余 Learner；

• Acceptor 确认一个提案后，将提案发送给多个 Learner，再由它们通知剩余 Learner。

4. Basic-Paxos 的缺陷

Basic-Paxos有个致命的缺陷，还是以前面的两个提案者 A 和 B 为例：

• A 发起提案，获取全局递增的提案编号 1，发起提案请求，获得过半通过；

• B 发起提案，获取全局递增的提案编号 2，发起提案请求，因为提案编号 2 > 1，获得过半通过；

• A发起Accept请求，因为目前接受者响应过的最大编号为2，所以提案会被拒绝；

• A 发现Accept请求被拒绝，重新获取编号 3，再发起Prepare请求，3>2，获得过半响应；

• B 发起Accept请求，可目前接受者响应过的最大编号为3，提案自然会被拒绝；

• B 发现 Accept请求被拒，重新获取编号4，……

所以，，如果两个Propser同时发起Prepare请求，然后依次提出编号递增的提案，就会陷入相互循环的过程，两个Propser提案者都能完成Prepare阶段，可始终无法完成Accept阶段，造成没有value被选定。那如何解决这个问题呢？

答案是只允许一个节点发起提案，即 集群内只允许存在一个 Proposer 角色的节点。而这种情况就对应着 Multi-Paxos 算法。

5. Multi-Paxos 算法

文章开头提到过，Basic-Paxos 是一种单决策算法，一轮决策中只能决定一个 value，且确认一个都至少要经过 Prepare、Accept 两个阶段，如果目前集群的写入并发较高，那每一次写入都需要进行一轮决策，对于现在要求高并发、高性能的系统是不能接受的。

回头看一下 Basic-Paxos 的三个阶段，其实 Prepare 阶段的作用就是 确认并发场景下，到底使用哪个 Proposer 的提案。但如果一开始就能确认使用哪个 Proposer 的提案，Prepare 阶段就是多余的了，这其实跟上一节的分析的一样，即 集群内只存在一个 Porposer，类似于 Leader。因为同一时刻永远只会有一个提案出现，自然就不会出现争议，也不会因为多提案造成不一致现象发生，外部写请求只能交给Leader处理，代表着Leader发出的提案，自然都是确定的值。