大规模共识算法

介绍

共识算法的理论和应用的形式可以说是很难推理。通常，这些算法是偶然发现要解决的一些好问题的解决方案。不幸的是，问题正在演变。而且我认为这些解决方案不会持续更长时间。

让我们从定义他们解决的问题开始：

• 分布式持久性：万一节点出现故障，数据安全可以在别处得到保证。
• 可用性：系统在某些节点不可用时继续提供服务的能力。
• 自动化：如果出现故障，系统知道如何在没有人工干预的情况下自我修复。

严格来说，人们可能会争辩说自动化是一个不同的理论问题，因为它需要故障检测。但现实是，今天的系统期望共识系统满足上述属性。

现在让我们扭转这个局面：如果我们从这些要求开始，我们最终会得到像 Paxos 或 Raft 这样的最佳解决方案吗？在回答这个问题之前，我们需要更好地了解需求。

更重要的是，云提供商正在提出复杂的拓扑，例如 zones 和 regions 。他们鼓励特定配置的定价结构。我们构建的系统能够适应这些细微差别非常重要。这些严格的算法开始失去灵活性只是时间问题。

然而，我们需要满足怀疑者的担忧：你能用普通的 MySQL 构建这样一个系统吗？简短的回答是肯定的。

在本系列博文中，我将带您完成一段剖析共识算法的旅程。我们将把它们分解成更小的关注点，我们将使用各种可以构建的更灵活的算法来构建一组新的规则和原则。

作为免责声明，这是一种工程方法。所以，如果你期待证明，你可能会失望。相反，我将使用和分享从大规模运行存储系统中获得的直觉。因此，我们将对解决此问题的方式进行两项更改：

1. 使用工程术语。这更多是为了我自己，因为很难推理学术概念如何映射到现实世界的场景。
2. 使用基于要实现目标的方法：自上而下地解决问题，确定关注点，并将它们分开。

第二个方面很重要，因为大多数共识算法都会执行同时实现多个目标的协调行动。很难知道为什么要以某种方式做出决定，以及如果使用不同的方法会有什么权衡。

通过更好地理解这些问题，我们可以做出更好的权衡，而不会被僵化的实现所困。

共识规则

YouTube 规模

YouTube  有数万个节点提供非常高的 QPS。横向扩展是全方位的：一些分片有超过 50 个副本。由于这些节点分布在多个数据中心，拓扑结构很复杂。为了实现这一目标，我们必须在延迟、可用性和持久性之间取得平衡。为了满足这些要求，我们过去常常执行大部分自动化的常规故障转移。我很高兴地说，我们从未因硬件故障而丢失数据。

当我们第一次听说 Paxos 时，它听起来很神奇：一种动态选举领导者的算法，以确保所有请求都得到满足，没有错误、分歧或数据丢失。

但我们很快发现我们的法定人数（quorum）对于基于多数的算法来说太大了。此外，MySQL 复制机制看起来不像 Paxos 描述的持久性机制。我们唯一的选择是在两个系统之间进行差距分析。在某种程度上，这就是FlexPaxos的发现原因：an additional knob that allows you to achieve a more meaningful performance vs. safety trade-off.

我们发现了一套通用的原则，任何基于领导者的系统都可以遵循这些原则来保证正确性和安全性。我们将在这篇博文中介绍这些规则。

为什么要达成共识

我们专注于使用共识来大规模解决持久性问题。可能还有其他用例，但我们并不关心这些。

没有任何系统可以为您提供绝对的可用性保证；总是存在比预期更大的灾难性故障的可能性。您必须决定所需的容错级别。这取决于资源的可靠性和数据的重要性。换句话说， 可用性 要求取决于用例。

为了适应所有可能的用例，我们将 可用性 视为一个抽象要求。算法必须与这些要求无关，并且应该能够适应任意复杂的规则。这改变了我们处理问题的方式。

单值行为

转述 Paxos 的定义：我们希望共识系统的主要保证是它不能忘记它已经承认接受的值。一旦接受一个值，必须拒绝所有其他值。

当要求接受单个值时，该操作将产生以下三种结果之一：

1. 已接受：该值已成功接受。
2. 拒绝：该值被拒绝。
3. 失败：操作没有成功，但稍后可能会成功。

如果第一个请求被接受，则任何后续写入不同值的尝试都将被拒绝。

如果第一个请求被拒绝，则可能意味着在我们的“第一次”尝试之前接受了先前的值。在这种情况下，后续请求也将被拒绝。

如果第一个请求失败并发出第二个请求，系统可以选择将其中一个请求最终确定为“已接受”，但不能同时选择两者。由于第二个请求也可能失败，我们需要更一般地重申这一点：系统可以选择接受任何先前请求的值作为最终值。病理性故障模式可能导致系统无限期地保持在故障状态。但通常预计最终会收敛。

在实践中

一个系统只接受一个值是不太实用的。相反，让我们看看如果我们将规范更改为接受一系列值的系统会发生什么，这就是存储系统通常所做的。

如果系统首先接受值 v1，然后收到对 v2 的请求，则它必须将 v2 记录为发生在 v1 之后。更重要的属性如下：如果 v1 的请求因为系统无法满足持久性要求而失败，那么 v2 的请求需要系统做出是否应该完成或拒绝 v1 的最终决定。如果完成，它会在 v1 之后记录 v2。否则，v1 将被丢弃，而 v2 将是唯一接受的值。

Raft 明白这一点，这就是为什么他们将他们的系统描述为一种实现一致日志复制的方式。

在我们的例子中，我们将考虑请求而不是值，这可以是存储系统可能必须执行的任何操作。它可以是一个事务，或者设置一个键的值，或者任何其他原子操作。

让我们重申一下：共识系统的目的是按照严格的顺序接受一系列请求，并使它们在多个节点之间保持一致。

单一领导

为了限制复杂性和范围，我们将坚持单一领导者设计。我所知道的流行实现使用单一领导者方法。有关于无领导和多领导算法的研究，比如 epaxo，wpaxos 等。

单次领导人共识系统是相互配合两个工作流的组合：

1. 领导者接受请求并使它们持久。
2. 可以选举一个新的领导者来恢复请求而不会发散或丢失数据。

Paxos 和 Raft 也使用单一领导者方法（multi-paxos）。

规则

既然我们已经花了足够的时间来构建前提，现在是时候编写管理共识系统的规则了：

1. 领导者的工作是通过满足规定的持久性要求来满足请求。
2. 要选举新的Leader，必须执行以下操作：
   • 终止前任领导，如果有的话。
   • 为新的领导者选择必要的节点。
   • 传播先前完成的请求以满足新领导者的持久性要求。
3. Forward Progress：如果Leader选举失败，后续的重新尝试应该有一条成功之路，可以在不破坏持久性和安全性保证的情况下选举新的Leader。
4. 如果同时尝试选举领导者，则至多必须有一个领导者获胜。

规则 3 和规则 4 实际上隐含在规则 2 中。但是这些属性非常重要，值得将它们明确化。

这些规则是有意通用的，以允许在实现这些目标时发挥创造力。事实上，比这更具体将排除一些有效的实现。但是，我们将展示多种方法来满足这些规则。我们还将根据这些新规则验证现有的流行算法。

您会注意到以下差异：

• 没有提到多数法定人数。
• 没有提到节点的交集。
• 没有提案编号。

这是我们偏离传统系统的地方，因为我们认为这些并不是共识系统正确运行所严格要求的。例如，您可以构建一个具有 50 个节点的共识系统，但仍然只有 2 个法定人数。这些法定人数不需要在领导者之间交叉。至于提案编号，很少有人理解为什么甚至需要它们。最好先讨论我们要实现的目标，然后引入提案编号作为一种选择，也许还可以考虑不涉及提案编号的替代方案。我们将深入研究这些属性中的每一个，并探索多种方法之间的权衡。

回顾

• 持久性是我们想要使用共识系统的主要原因。
• 由于持久性取决于用例，我们将其作为一个抽象要求，要求共识算法对持久性要求不做任何假设。
• 我们从Paxos定义的共识系统的原始属性开始，并对其进行了修改以使其在实际场景中可用：我们将系统更改为接受一系列请求，而不是收敛于一个值。
• 我们将范围缩小到单一领导者系统。
• 我们提出了一套与耐久性无关的新规则。基本主张是遵循这些规则的系统将能够满足共识系统的要求。具体来说，我们排除了一些要求，例如以前在共识算法中用作核心构建块的多数仲裁。

共识用例

以下用例松散地源自实际生产工作负载：

• 我们有大量副本分布在许多数据中心。其中，我们有 15 个具有领导能力的节点分布在三个数据中心。我们不希望两个节点同时宕机。网络分区可能发生，但仅限于两个数据中心之间；数据中心永远不会完全孤立。可以关闭数据中心进行计划维护。
• 我们有四个区域，每个区域中有一个节点。任何节点都可能失败。一个区域可能会在没有通知的情况下关闭。分区可以发生在任何两个区域之间。
• 我们有六个节点分布在三个区域。任何节点都可能失败。一个区域可能会在没有通知的情况下关闭。分区可以发生在任何两个区域之间。
• 我们有两个区域，每个区域有两个区域。我们不希望超过一个区域下降。可以关闭一个区域进行维护，在这种情况下，我们希望主动将写入传输到另一个区域。

关于灵活共识的推理

上一节中的配置似乎无处不在。我们如何设计一个满足所有这些要求的系统，以及我们如何在未来证明自己符合新的要求？

有一种方法可以解释为什么这种灵活性是可能的。这是因为两个协作算法（请求和选举）共享持久性要求的共同视图，但可以独立运行。

例如，让我们考虑五节点系统。如果用户不希望在任何给定时间有多个节点出现故障，那么他们会将其持久性要求指定为两个节点。

领导者可以使用这个约束来使请求持久化：一旦数据到达另一个节点，它就变得持久了。我们可以将成功返还给客户。

在选举方面，如果出现故障，我们知道不会有超过一个节点出现故障。这意味着可以访问四个节点。其中至少有一个将拥有所有成功请求的数据。这将允许选举过程将该数据传播到其他节点，并在选举新领导者后继续接受新请求。

换句话说，单一的持久性约束决定了行为的双方；如果我们能找到一种正式的方式来描述需求，那么请求就必须满足这些需求。另一方面，选举需要到达足够多的节点以与相同的要求相交。

例如，如果用 2/5 个节点实现持久性，那么选举算法需要达到 4/5 个节点才能与持久性标准相交。在多数法定人数的情况下，这两个都是 3/5。但是我们的概括适用于任何任意属性。

最坏的情况

在上述五个节点的情况下，如果两个节点发生故障，则已经超出了容错能力。我们只能到达三个节点。如果我们不知道其他两个节点的状态，我们将不得不假设最坏的情况是两个无法访问的节点可能已经接受了持久请求。这将导致选举过程停滞。

如果发生这种情况，系统必须允许妥协：放弃两个节点并继续前进。否则，可用性的损失可能比数据的潜在损失代价更大。

实用平衡

双节点持久性并不总是意味着系统会停止或丢失数据。必须发生非常具体的故障序列：

• 领导接受请求
• Leader 尝试将请求发送给多个接收者
• 只有一个接收者接收并确认请求
• 领导者将成功返回给客户
• 领导者和接收者都崩溃了

如果领导者和接收者节点与集群的其余部分进行网络分区，则可能会发生这种类型的故障。我们可以通过要求 acker 跨越网络边界来缓解这种失败。

一个单元中的副本节点在确认后发生故障，而另一个单元中的主节点在返回成功后发生故障的可能性要低得多。这种故障模式非常罕见，以至于许多用户认为这种风险级别是可以接受的。

数量级命令

共识系统执行的最常见操作是请求的完成。相比之下，领导者选举通常发生在两种情况下：将节点关闭以进行维护，或在发生故障时。

即使在像 Kubernetes 这样的动态云环境中，每天看到一个集群的选举不止一次也会令人惊讶，而这样的系统每秒可以处理数百个请求。这相当于请求被满足和领导者选举之间存在许多数量级的差异。

这意味着我们必须不惜一切代价对执行请求的部分进行微调，而领导者选举可能会更加复杂和缓慢。这就是为什么我们倾向于将耐久性设置降低到最低限度的原因。扩大这个数字会对性能产生不利影响，尤其是尾部延迟。

在YouTube 上，虽然仲裁规模很大，但副本的单个 ack 足以让请求被视为完成。另一方面，领导者选举过程必须追查所有可能已经确认最后一笔交易的节点。我们确实有意识地权衡了 ackers 的数量，以避免进行彻底的疯狂追逐。