分布式Paxos算法详解

Paxos算法的业务场景就好比是在一个大公司的董事会选举中心选出新董事长，但这个过程是在乌云密布的风雨天进行，通信极度不稳定，董事们时不时被困在电梯里或是在高尔夫球场打不了电话。

在Paxos算法中，每个董事（参与者）都是独立操作的，而这个算法就是确保即便在通信可能失败，董事们也能达成一致。

它通过一系列的提议（proposal）和承诺（promise）来保证最终的一致性。

业务场景

假设，现在有 3 个董事候选人在争夺董事长职位，用 Paxos 算法来表示这个过程，可分为三个阶段：

1. 准备阶段（Prepare）:
   • 候选董事 A 向所有董事会成员（不包含其它候选人）发送一个带有特定提议编号的请求。
   • 其他董事会成员在确保该提议编号高于任何之前收到的提案编号的情况下，会承诺不会接受编号更低的提议，它们响应说：“好的，你是编号最高的候选人，我听听你的是啥提案”。
2. 批准阶段（Accept）:
   • 当候选董事 A 收到了多数董事会成员的承诺后，它会向那些承诺过的成员发送详细的提案内容。
   • 如果这些董事会成员没有对更高编号的提案做出过承诺，它们就会接受这个提案。
3. 学习阶段（Learn）:
   • 一旦提案被多数董事会成员批准，这个候选人就被选为新董事，每个董事会成员会记录下来这个结果。
   • 此时，所有其他员工或股东都需要知道这个结果，这样新董事的确立就在全公司范围内达到了一致。

在这过程中，Paxos 算法又将系统中的节点分为三类：

• 提议者（Proposer）：提议者负责创建提案，并向 Acceptor（接受者） 发送提案。提案包括一个序号和提议值，假设为 [n, v]，提议者需要确保它提出的提案编号 n 是独一无二的，例如董事候选人和他的候选编号。
• 接受者（Aceeptor）：接受或拒绝提案，当接受提案后，接受者会作出 承诺（Promise）不再接受比当前提案接受者编号更低的提案，并继续接受具有更高编号的提案，就像例子中的董事会成员那样。
• 告知者（Learner）：被告知投票的结果，不参与投票过程，公司股东或者其他员工。

提议的时候，包含俩字段：[n, v]，其中 n 为序号，v 为提议值。每个 Aceeptor 在接收提议请求的时候，会比对其中的序号 n：

• 当前序号小于已存在的 n 时，则不予理会；
• 当前序号大于 n 时，会返回响应，表示接受了这个序号为 n 的提议，并承诺（Promise）不再接受比当前提案编号更低的提案。

当一个 Proposer 接收到超过半数的 Aceeptor 响应时，说明该提议值被 Paxos 选择了出来，这时候，由 Acceptor 负责通知给所有的 Learner。