Paxos 区块链

Paxos 有何必要性？

使其一个过程容错的需求是根本原因。可靠性是防止信息丢失的最简单直接的方法；它涉及通过等效的过程复制该过程，通常分布在一组机器上，以确保无论发生什么情况，即使一些副本崩溃，服务仍可继续提供。

一个明显的问题是，为了保证所有给定的信息在任何客户请求的处理方式下都保持一致，我们必须确保团队中的每个人都看到来自客户端序列的相同请求。

我们是否可以简单地指定一个特定过程作为“领导者”，这意味着它将负责接受所有客户查询并通知其他所有人？是的，这是可行的，但请考虑领导者失败并选择了一个替代者，然后“之前的”领导者又回来了。可能有多个领导者试图说服他们的支持者。出于这个原因，我们需要 Paxos 来就此顺序中的下一个客户查询达成一致。

Paxos 概述

简而言之，Paxos 是一种从一系列值中选择一个数字的方法。在此上下文中，“选择”是指确保每个成员都看到相同的结果，同时提供客户已要求的服务。基本原则是这样一个概念：压倒性的多数投票代表了整体；如果一个值被超过一半的过程选中，则构成一致。

Paxos 已经变得如此重要，以至于它几乎成为所有后续共识技术的起点，包括 Raft、ZAB（Zookeeper Atomic Broadcast）、Cheap-Paxos、Fast-Paxos，以及众多生产软件程序（例如 Apache Zookeeper，它是 Apache Hadoop 和Kafka 的基础，以及 PhxPaxos，它为拥有十亿用户的微信提供支持）。

Paxos 何时能起作用？

在互联网上传输的通信可能会丢失、延迟、复制或仅仅顺序不对；

根据故障停止模型，操作可以停止和重新启动，但它们不会表现出拜占庭故障，这意味着它们不会表现出恶意行为。这些假设是现实的，这促使 Paxos 尽管存在挑战但仍广受欢迎。

我的 Paxos 构建

让我们解释一些术语，并专注于一组过程。许多过程被称为“提议者”（proposer），它们响应每个客户的查询（值）并将其通知团队中的其余成员（此原则的通信方式称为“提议”（proposal））。每个值都有一个建议的整数，它允许卓越，这是一个特殊的数字。此外，我们还有称为“学习者”（learner）的系统，它们试图确定选择了哪个值。最后，还有称为“接受者”（acceptor）的过程，它们投票以确定批准值（接受 = 对值投票并记录建议的金额）。请记住，一个过程可以同时扮演多个角色，例如提议者、接受者和学习者。这些角色的数量可能没有严格限制；例如，可以有两个提议者、五个接受者和三个学习者。

此外，接受者和学习者的数量等于我们评估容错能力所考虑的参与者数量（我们希望每个过程都参与投票并获取值）。至少需要一个接受者，因为如果只有一个，投票就无法继续。那么，我们需要多少接受者呢？这取决于我们如何定义共识。为了让群体能够正常工作，当存在多数过程时，需要始终达到期望的结果，则接受者的总数应该为奇数且大于一，当我们希望“多数 = 共识”时（对于偶数，可能出现一半赞成一半反对）。

假设提议者接收到请求并提交。对于那些知道值的人，接受者将如何投票？由于很可能只会提出一个值，他们必须投票给他们知道的第一个值。如果他们坚持他们学习到的第一个值会发生什么？

在这种情况下，三个过程（S1、S2 和 S3）中的每一个都会发送一条名为“接受？（值）”（也称为提议）的消息，提议一个值（红色、蓝色或绿色），并且每个接受者都会批准它。

由于他们不愿意改变自己的信念，因此永远不会达成共识。这意味着 1) 接受者必须投票并批准多个估值（从不后悔投票），或者 2) 在提议者最终能够提出相同值之前，需要有一个协商期。让我们看看 1) 允许多种值。一个新的例子粉碎了我们的希望

在这里，S1 最初提议“红色”值，S1 和 S2 同意了它。鉴于总共只有三个步骤，{S1, S2} 构成了多数。然而，S3 提议“绿色”值，并在此之前成功地将此成就传达给所有学习者。此时，在对它们进行压倒性投票后，选择了两个原则！请记住，我们只想选择一个数字。

接下来，必须检查选项 2）：每个组织者都应该在提出值之前与其他提议者进行“协商”，最终允许他们提出相同价格。然后，接受者将坚持他们被通知的第一个价格。此阶段（我们将简称为“准备阶段”）的主要目的是确定当前已知的值是多少。这是通过每个提议者在提交提议之前向潜在接受者发送“准备消息”并等待返回的多数响应来完成的（少数响应可能与协议不同）。

当申请人 X 知道接收者 Y 已同意金额 V，通过这种多数，X 就知道 Y 不太可能同意高于 V 的金额；因此，建议的金额必须更改；否则，可能会出现类似于示例 1 的情况。

那么，X 应该建议哪个价值？请记住，X 可能从这些响应中发现，某些接收者收到了各种值

Paxos 已经接受了具有最高提议金额的金额；因此，提议值需要是全序的。然而，这可能会导致一个新问题，如下面的示例 4 所示

虽然颜色仍然用于表示数字，但在本例中，提议金额由括号中的数字表示，这些数字可能代表自然数以外的任何全序实体。

在“绿色”、“蓝色”或“红色”任何一个颜色被选定之前，S2 和 S4 都开始进行提议。尽管收到了大量响应，S2 认为系统应该使用“绿色”值，因为 2 > 1，而 S4 则认为因此它必须接受“红色”数字，因为 1 > 0。当 S2 和 S4 分别接受（绿色，2）和（红色，1）时，无法达成一致。

那么，我们如何处理示例 4 这样的情况呢？问题在于“协商”不足；即使提议者可能选择接受某个意见，但在另一位提议者同时提出冲突值之前，它也无法确定。为了解决这个问题，接受者需要记录提议者的准备数据，并在其准备响应中包含这些数据。

更精确地说，我们需要以下附加动作

• 每个准备好的通信都应该附带提议编号。
• 每个接受者在一个名为 max_proposal_number 的数组中跟踪它们遇到的最大提议金额。如果接受者随后收到准备或接受，会发生什么？当提议数量较低时，它会响应一个表示拒绝的查询。

让我们设想提议者 P，其提议编号是 A 的 max_proposal_number，从接受者 A 收到一个承诺。回想一下我们最初说过，接收者必须接受它被通知的第一个数字，因为它不确定这是否是唯一的建议。然而，由于有额外的准备阶段，接受者可以发现已经提出了多种选择，因此在此期间可能会拒绝建议。

如果进行以下更改，则情况 4a 将不会发生

提议者在收到大量接受者的确认后，如果提议已被选中，将随后通知所有学习者（这是可选的；其他人认为接受者组应管理此任务）。

注意

• 如果提议不成功，它会重试，直到成功为止（尽管它通常接受一个先前已批准的提议）。提议者可以通过响应 max_proposal_num 来确定其提议被拒绝的金额，这意味着它们在下一次尝试中必须选择一个大于一的提议金额。
• 为了在故障后恢复在线，接受者必须将 max_proposal_number、accepted_proposal 和 accepted_value 保存到磁盘；学习者必须将选定的金额保存到磁盘。由于客户端可能会重新发送请求，因此提议者不需要这样做。

活锁

正如任何人从示例 5 中可以看出，多个申请人很可能会争夺接受者的承诺，从而阻止任何进展。一个简单的修复方法是在每次重试前添加一个任意的暂停。选举一个管理者是越来越流行的策略，我将在我即将发表的另一篇 Paxos 文章中讨论。

结论

最终，我们得到了一种从一系列值中选择一个数字的方法，同时保证以下两个特性之一：

1. 安全性：可以选定一个原则，并且只能学习到该原则。
2. 活跃性：最终会选定一个建议值，学习者最终会获得选定的数字。

尽管如此，函数（提议者、接受者和学习者）可能会暂停和恢复。因此，消息的传输不一定总是可靠的。