C++ 中的 Paxos 算法

引言

Paxos 算法 是一种基础的共识协议，旨在允许多个系统或节点就一个单一值达成一致，即使在某些节点可能发生故障、消息可能延迟或丢失的情况下也是如此。它在分布式计算中特别有用，因为确保系统之间的一致性对于一致性至关重要。

让我们看看什么是 Paxos

Paxos 主要提供了一种分布式系统组达成共识的方法。想象一下，几个计算机（或“节点”）都在尝试就一个单一的行动方案达成一致，比如确定网络中的当前领导者、确认交易或同步共享数据。Paxos 确保即使某些计算机发生故障，其余计算机仍然可以达成一致。

该算法主要分为两个阶段（带有一些子步骤），并且通常会分解为角色和职责以简化其设计。

它主要涉及三种参与者，如下所示：

• 提议者 (Proposers) - 它们为共识提出值。
• 接受者 (Acceptors) - 它们对提出的值进行投票。
• 学习者 (Learners) - 它们在达成共识后学习被同意的值。

实施

输出

 
Learner: Value 42 chosen by consensus.   

说明

步骤 1：接受者的角色

接受者是 Paxos 中的决策者。它们响应提议者的请求，以“承诺”或“接受”提出的值。接受者有两项主要任务：

• 准备阶段 (Prepare Phase) - 承诺提案：接受者可以接收来自提议者的请求，要求考虑一个新的提案，其中包含一个唯一的 ID 来区分它与其他提案。如果提案 ID 高于它之前看到的任何提案，接受者将向提议者做出“承诺”。这个承诺意味着接受者将不会接受任何 ID 更低的未来提案。通过确保提案 ID 唯一且递增，系统可以避免提案之间的冲突，为共识奠定基础。
• 接受阶段 (Accept Phase) - 对提案进行投票：一旦提议者收集到大多数接受者的承诺，它就会要求它们接受该提案。如果提案 ID 与之前承诺的任何提案的 ID 匹配或更高，接受者就会接受该提案。这个接受代表了对所提出值的赞成投票。

通过这两项任务，接受者通过比较 ID 并仅接受或承诺满足其标准的提案，创建了一种系统地选择一个提案以达成共识的方法。

步骤 2：提议者的角色

提议者启动共识过程。它的工作是建议一个它希望所有节点都同意的值，并遵循两个步骤来实现这一目标：

• 提出并收集承诺（准备阶段）：提议者为每个新提案生成一个唯一的提案 ID。然后，它将此 ID 连同其提出的值一起发送给接受者，要求它们承诺不会接受任何先前的提案。如果提议者收到大多数承诺，它就可以自信地继续进行。这个多数要求至关重要，因为它确保了足够多的接受者支持该提案，增加了达成一致的可能性。
• 获取接受（接受阶段）：如果提议者获得了足够的承诺，它就会向接受者发送一个“接受”请求，连同同意的提案 ID 和值。接受者可以选择接受该提案，前提是它们在此期间没有收到更高的提案 ID。如果大多数接受者接受该提案，则达成共识。

这种两步法确保提议者仅在大多数接受者愿意支持提案时才继续进行，从而为单个、一致同意的值奠定了基础。

步骤 3：学习者的角色

一旦接受者就某个值达成共识，学习者的作用就是记录或“学习”这个选定的值。学习者充当日志，捕获结果，以便系统的其他部分可以依赖同意的结果。在真实的分布式系统中，学习者通过确保所有节点都知道最终决定来发挥至关重要的作用。在这里，学习者只是打印值，但在更大的系统中，它可能会更新数据库或通知其他组件。

一旦足够多的接受者接受了该提案，学习者就会从提议者那里接收最终同意的值，标志着该提案的 Paxos 过程结束。

复杂度分析

时间复杂度

基本轮次

• Paxos 需要为每个提案进行两个通信轮次才能达成共识：
• 准备阶段：提议者向所有接受者发送“准备”消息，并等待大多数响应（承诺）。
• 接受阶段：一旦收到足够的承诺，它就会发送“接受”消息，并等待大多数接受者同意。
• 总的来说，这两个轮次使得 Paxos 在轮次方面相对高效，尤其是在没有故障或冲突的情况下。

延迟影响

• 在分布式系统中，每个轮次可能需要与网络延迟成比例的时间。
• 在没有故障的理想条件下，Paxos 达成共识的时间复杂度为 O(2) 轮。
• 如果存在冲突（例如，多个提议者竞争）或节点故障，可能需要额外的轮次，从而增加延迟。

故障场景

• 如果某些节点发生故障或消息延迟，则需要进行额外的重试，这可能导致实际延迟更高。复杂性然后取决于重试次数，该次数因系统的容错能力和网络可靠性而异。

空间复杂度

接受者

• 接受者存储它们已经承诺不会接受低于此的值的最高提案 ID，以及任何被接受的提案。这通常是恒定的空间量，因此每个接受者为 O(1)。

提议者

• 提议者需要跟踪提案 ID 和一些本地状态（例如它们正在提出的值）。由于它们不需要无限期地存储响应，因此每个提议者的空间复杂度也为 O(1)。

学习者

• 一旦达成共识，学习者就会存储最终选定的值。对于它们“学习”的每个提案，每个学习者的空间复杂度保持为 O(1)。

总体空间复杂度

• 对于整个系统，每个节点仅存储每个提案的恒定数量的信息，从而导致整体空间复杂度为 O(N)，其中 N 是节点数。
• 在较大的实现或高吞吐量的系统中，日志或持久存储可能会增加有效空间，但每个节点的核心算法保持不变。

性质

1. 1. 安全性（一致性）
   • 属性： Paxos 确保如果一个值已通过共识选定，那么所有了解该选定值的所有节点都将同意相同的值。即使存在网络延迟或节点故障，此属性也成立。
   • 解释： 这种一致性是通过仔细控制提案过程来实现的。Paxos 保证，只要算法在其容错限制内运行，就不会选择两个不同的值。
2. 容错性
   • 属性： Paxos 可以容忍多达一半的节点发生故障而不会失去达成共识的能力。
   • 解释： 这种容错性是因为 Paxos 仅需要大多数节点（法定人数）同意。如果失败的节点少于多数，其余节点仍然可以组成法定人数并继续共识。
3. 提议者的非阻塞性
   • 属性： 提议者可以独立运行，并且不需要等待所有接受者的响应——只需要大多数。
   • 解释： 此属性允许提议者保持活动状态，并在检测到其他冲突的提议者时重试提案。如果一个提议者失败，其他提议者可以继续提案过程。