跳转至

Paxos

Paxos 分为 3 种角色，在具体的实现中，一个进程可能同时充当多种角色： - 提议者 (Proposer): 提出提案 (Proposal)。Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。 - 决策者 (Acceptor)：参与决策，回应 Proposers 的提案。收到 Proposal 后可以接受提案，若 Proposal 获得多数 Acceptors 的接受，则称该 Proposal 被批准。 - 学习者 (Learner)：不参与决策，从 Proposers/Acceptors 学习最新达成一致的提案（Value）。

Paxos 算法的核心是一个两阶段提交协议。 - 在第一阶段 Prepare，提议者向所有参与者发送一个编号为 n 的提案，请求他们批准或拒绝该提案。 - 在第二阶段Accept，如果提案获得了多数参与者的批准，则提议者将该提案提交给所有参与者。

当提议者向所有参与者发送一个编号为 n 的提案时，如果一个参与者没有收到编号大于 n 的提案，则它批准该提案。否则，它将拒绝该提案。如果提案获得了多数参与者的批准，则提议者将该提案提交给所有参与者。如果一个参与者已经批准了一个编号为 n 的提案，则它不会批准任何编号小于 n 的提案。

在第二阶段，如果提案获得了多数参与者的批准，则提议者将该提案提交给所有参与者。如果一个参与者已经批准了一个编号为 n 的提案，则它不会批准任何编号小于 n 的提案。

paxos 流程

1 paxos 活锁问题

很容易构建一个场景，在这个场景中，两个 proposers 各自不断发布数量不断增加的一系列提案，但从未有过被选中的。提案人 p 完成编号为 n1 的提案的第一阶段。然后另一个提议者 q 针对编号为 n2＞n1 的提议完成阶段 1。提案人 p 的第 2 阶段接受编号为 n1 的提案请求被忽略，因为接受者都承诺不会接受任何编号为小于 n2。因此，提案人 p 开始并完成新的第一阶段提案编号 n3>n2，导致第二阶段 2 接受提案人 q 被忽略。以此就导致了一条无止尽的死链。

为解决此问题，需要在 proposers 中选出一个 leader，由 leader 发送提案，这就是 multi-paxos。

2 multi-paxos

multi-paxos 在 paxos 基础上改造，把二阶段提交改为一个阶段。通过在多个 proposers 中选出主 leader 后，由 leader 来发起提案，并且直接发送提案值；当半数以上的 acceptors 批准时，提案就成功。

Multi Paxos 对 Basic Paxos 的核心改进是增加了“选主”的过程，提案节点会通过定时轮询（心跳），确定当前网络中的所有节点里是否存在有一个主提案节点，一旦没有发现主节点存在，节点就会在心跳超时后使用 Basic Paxos 中定义的准备、批准的两轮网络交互过程，向所有其他节点广播自己希望竞选主节点的请求，希望整个分布式系统对“由我作为主节点”这件事情协商达成一致共识，如果得到了决策节点中多数派的批准，便宣告竞选成功。当选主完成之后，除非主节点失联之后发起重新竞选，否则从此往后，就只有主节点本身才能够提出提案。此时，无论哪个提案节点接收到客户端的操作请求，都会将请求转发给主节点来完成提案，而主节点提案的时候，也就无需再次经过准备过程，因为可以视作是经过选举时的那一次准备之后，后续的提案都是对相同提案 ID 的一连串的批准过程。也可以通俗理解为选主过后，就不会再有其他节点与它竞争，相当于是处于无并发的环境当中进行的有序操作，所以此时系统中要对某个值达成一致，只需要进行一次批准的交互即可。