Ref: https://pdai.tech/md/algorithm/alg-domain-distribute-x-paxos.html

Paxos 算法简介

Paxos 算法是 Lamport 宗师提出的一种基于消息传递的分布式一致性算法，使其获得 2013 年图灵奖。
Paxos 由 Lamport 于 1998 年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛 Paxos 作为比喻，描述了 Paxos 小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在 2001 年，Lamport 觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made Simple》。

自 Paxos 问世以来就持续垄断了分布式一致性算法，Paxos 这个名词几乎等同于分布式一致性。Google 的很多大型分布式系统都采用了 Paxos 算法来解决分布式一致性问题，如 Chubby、Megastore 以及 Spanner 等。开源的 ZooKeeper，以及 MySQL 5.7 推出的用来取代传统的主从复制的 MySQL Group Replication 等纷纷采用 Paxos 算法解决分布式一致性问题。

Basic Paxos 算法实现

Paxos 算法解决的问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值 (决议) 达成一致。
Paxos 算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了 2F+1 的容错能力，即 2F+1 个节点的系统最多允许 F 个节点同时出现故障。
一个或多个提议进程 (Proposer) 可以发起提案 (Proposal)，Paxos 算法使所有提案中的某一个提案，在所有进程中达成一致。系统中的多数派同时认可该提案，即达成了一致。最多只针对一个确定的提案达成一致。

角色

Paxos 将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner):

  • Proposer: 提出提案 (Proposal)。Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
  • Acceptor: 参与决策，回应 Proposers 的提案。收到 Proposal 后可以接受提案，若 Proposal 获得多数 Acceptors 的接受，则称该 Proposal 被批准。
  • Learner: 不参与决策，从 Proposers/Acceptors 学习最新达成一致的提案 (Value)。

在多副本状态机中，每个副本同时具有 Proposer、Acceptor、Learner 三种角色。
image.png
可以理解为人大代表 (Proposer) 在人大向其它代表 (Acceptors) 提案，通过后让老百姓 (Learner) 落实。

3 个阶段

image.png

第一阶段: Prepare 阶段

Proposer 向 Acceptors 发出 Prepare 请求，Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。

  • Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID)，向所有 Acceptors 发送 Prepare 请求，这里无需携带提案内容，只携带 Proposal ID 即可。

  • Promise: Acceptors 收到 Prepare 请求后，做出 “两个承诺，一个应答”。

    • 承诺 1: 不再接受 Proposal ID 小于等于 (注意：这里是 <=) 当前请求的 Prepare 请求；
    • 承诺 2: 不再接受 Proposal ID 小于 (注意：这里是 <) 当前请求的 Propose 请求；
    • 应答：不违背以前作出的承诺下，回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID，没有则返回空值。

      第二阶段: Accept 阶段

      Proposer 收到多数 Acceptors 承诺的 Promise 后，向 Acceptors 发出 Propose 请求，Acceptors 针对收到的 Propose 请求进行 Accept 处理。

  • Propose: Proposer 收到多数 Acceptors 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value，作为本次要发起的提案。如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value。然后携带当前 Proposal ID，向所有 Acceptors 发送 Propose 请求。

  • Accept: Acceptor 收到 Propose 请求后，在不违背自己之前作出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。

    第三阶段: Learn 阶段

    Proposer 在收到多数 Acceptors 的 Accept 之后，标志着本次 Accept 成功，决议形成，将形成的决议发送给所有 Learners。

    伪代码

    image.png

  • 获取一个 Proposal ID n，为了保证 Proposal ID 唯一，可采用时间戳 + Server ID 生成；

  • Proposer 向所有 Acceptors 广播 Prepare (n) 请求；
  • Acceptor 比较 n 和 minProposal，如果 n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；
  • Proposer 接收到过半数回复后，如果发现有 acceptedValue 返回，将所有回复中 acceptedProposal 最大的 acceptedValue 作为本次提案的 value，否则可以任意决定本次提案的 value；
  • 到这里可以进入第二阶段，广播 Accept (n,value) 到所有节点；
  • Acceptor 比较 n 和 minProposal，如果 n>=minProposal，则 acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回 minProposal。
  • 提议者接收到过半数请求后，如果发现有返回值 result >n，表示有更新的提议，跳转到 1；否则 value 达成一致。

    实现举例

    下面举几个例子，实例 1 如下图:
    image.png
    图中 P 代表 Prepare 阶段，A 代表 Accept 阶段。3.1 代表 Proposal ID 为 3.1，其中 3 为时间戳，1 为 Server ID。X 和 Y 代表提议 Value。
    实例 1 中 P 3.1 达成多数派，其 Value (X) 被 Accept，然后 P 4.5 学习到 Value (X)，并 Accept。
    image.png
    实例 2 中 P 3.1 没有被多数派 Accept (只有 S3 Accept)，但是被 P 4.5 学习到，P 4.5 将自己的 Value 由 Y 替换为 X，Accept (X)。
    image.png
    实例 3 中 P 3.1 没有被多数派 Accept (只有 S1 Accept)，同时也没有被 P 4.5 学习到。由于 P 4.5 Propose 的所有应答，均未返回 Value，则 P 4.5 可以 Accept 自己的 Value (Y)。后续 P 3.1 的 Accept (X) 会失败，已经 Accept 的 S1，会被覆盖。
    Paxos 算法可能形成活锁而永远不会结束，如下图实例所示:
    image.png
    回顾两个承诺之一，Acceptor 不再应答 Proposal ID 小于等于当前请求的 Prepare 请求。意味着需要应答 Proposal ID 大于当前请求的 Prepare 请求。
    两个 Proposers 交替 Prepare 成功，而 Accept 失败，形成活锁 (Livelock)。

    Paxos 算法推导

    通常说 Paxos 算法是复杂算法难以理解是指其推导过程复杂。理论证明一个 Paxos 的实现，比实现这个 Paxos 还要难。一个成熟的 Paxos 实现很难独立产生，往往需要和一个系统结合在一起，通过一个或者多个系统来验证其可靠性和完备性。

https://blog.csdn.net/yeqiuzs/article/details/76862026

Paxos 算法拓展

Multi-Paxos 算法

原始的 Paxos 算法 (Basic Paxos) 只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos 搞不定了。因此 Basic Paxos 几乎只是用来做理论研究，并不直接应用在实际工程中。

实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos 正是为解决此问题而提出。Multi-Paxos 基于 Basic Paxos 做了两点改进:

  • 针对每一个要确定的值，运行一次 Paxos 算法实例 (Instance)，形成决议。每一个 Paxos 实例使用唯一的 Instance ID 标识。
  • 在所有 Proposers 中选举一个 Leader，由 Leader 唯一地提交 Proposal 给 Acceptors 进行表决。这样没有 Proposer 竞争，解决了活锁问题。在系统中仅有一个 Leader 进行 Value 提交的情况下，Prepare 阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

image.png
Multi-Paxos 首先需要选举 Leader，Leader 的确定也是一次决议的形成，所以可执行一次 Basic Paxos 实例来选举出一个 Leader。选出 Leader 之后只能由 Leader 提交 Proposal，在 Leader 宕机之后服务临时不可用，需要重新选举 Leader 继续服务。在系统中仅有一个 Leader 进行 Proposal 提交的情况下，Prepare 阶段可以跳过。
Multi-Paxos 通过改变 Prepare 阶段的作用范围至后面 Leader 提交的所有实例，从而使得 Leader 的连续提交只需要执行一次 Prepare 阶段，后续只需要执行 Accept 阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个 Instance ID 标识，Instance ID 由 Leader 本地递增生成即可。
Multi-Paxos 允许有多个自认为是 Leader 的节点并发提交 Proposal 而不影响其安全性，这样的场景即退化为 Basic Paxos。

Chubby 和 Boxwood 均使用 Multi-Paxos。ZooKeeper 使用的 Zab 也是 Multi-Paxos 的变形。