Cloudflare 实验性共识服务 Meerkat 选用新型算法 QuePaxa

Cloudflare 最近发布了 Meerkat，这是一个实验性的分布式共识服务，旨在管理我们的内部全局控制平面。它由一种名为 QuePaxa 的新型共识算法驱动。

QuePaxa 是一个不寻常的选择；大多数共识系统使用成熟的共识算法，如 Raft、(Multi-)Paxos 或 Viewstamped Replication。这些算法已被充分理解，拥有成熟的实现，并且通常运行良好。

不幸的是，常见的共识算法在广域网中往往表现不佳，尤其是在网络连接和延迟不稳定的情况下，也就是像互联网这样的网络——而 Meerkat 正是运行在这样的环境中。这些算法依赖于单个 leader 进程的可用性和可预测的延迟。如果 leader 宕机、经历比平时更高的延迟或断连，整个共识系统就会变慢或变得不可用，直到 leader 被替换。这对 Meerkat 来说是不可接受的。

Meerkat 的全球部署环境促使我们选择了一种更新的共识算法 QuePaxa，它承诺在波动环境下具有更好的稳定性，这在很大程度上是因为它不依赖 leader 来取得进展。在本文中，我们将解释为什么选择 QuePaxa 以及 QuePaxa 算法的工作原理。

我们正在构建什么，以及它为何独特

Meerkat 是一个分布式系统，其中副本就一个有序的事件日志达成一致，每个事件由共识算法决定。

共识算法允许一组机器就单一共享事实达成一致，即使其中一些机器崩溃或断连。共识算法提供了一项重要保证：机器永远不会决定相互冲突的值。这确保了 Meerkat 副本的日志永远不会分叉。

Meerkat 使用其由共识驱动的日志来对外提供应用，例如键值存储，其中日志中的每个条目是一个 get 或 put 操作。由于共识算法保证副本的日志永远不会分叉，它们都会构建相同的键值（KV）状态。类似的由共识驱动的系统包括 Consul、etcd 和 Apache ZooKeeper。

然而，与类似系统不同，Meerkat 是为全球规模设计的。一个 Meerkat 集群可能分布在不同大洲，通过经常表现出高且可变延迟的链路连接。这对共识系统来说是一种不寻常的部署方式，因为共识系统通常部署在较小、更局部的网络中，并且有严格的延迟要求。

全球规模下共识的挑战

虽然所有共识算法都确保副本就相同的值达成一致，但许多算法在网络条件恶化（但机器未崩溃）时会变得不成比例地不可用或缓慢。我们亲眼目睹了这种情况：2020 年，Cloudflare 核心网络交换机的一次部分故障导致一个由共识驱动的系统性能下降，仪表板的运行速度比平时慢了 80 倍，持续了六个小时。关键的是，系统没有丢失任何数据。但在问题解决之前，它无法进行写入，这是不可接受的。

理想情况下，共识算法应该能够在延迟飙升和连接中断的情况下取得进展，而不仅仅是在副本故障时。这在全球规模下尤其成问题，因为故障更可能源自网络，而不是我们自己的服务器。

让我们审视共识算法的两个常见特征，它们可能在恶劣网络条件下导致性能下降：破坏性干扰和故障检测。稍后，我们将看到 QuePaxa 如何规避这两个问题。

破坏性干扰与 leader

考虑 Paxos，它是大多数共识算法的名副其实的鼻祖。许多共识算法继承了 Paxos 的结构——包括好的部分和不太好的部分。

省略大量细节，以下是 Paxos 的工作原理。有两种进程：提议者和接受者。抽象地说，系统的目标是让多数接受者就某个提议者提出的值达成一致。有两个阶段：Prepare 阶段和 Accept 阶段。在 Prepare 阶段，任何提议者都可以向多数接受者发送一个选票编号。这个选票编号充当一个承诺——接受者只接受具有该选票编号或更高编号的提案。然后，在 Accept 阶段，提议者再次将其提案连同选票编号发送给多数接受者。如果多数接受者仍然持有该提案的选票编号，多数接受者就接受它，提议者便可以安全地决定该提案。

当两个或更多提议者同时提交提案时，挑战就出现了。具体来说，另一个提议者可以在两个阶段之间插入自己更高的选票编号，从而阻断任何较低的选票。两个提议者可以反复阻止对方推进——实际上是在竞争被接受。

当提议者以这种方式竞争并相互阻断时，我们说他们发生了破坏性干扰。破坏性干扰随着更多提议者提出自己的选票而变得更糟。并发提议者越多，系统陷入反复提议僵局的可能性就越大。即使没有任何副本崩溃或不可用，多个提议者和行为异常的网络也可能阻塞 Paxos。正式地说，我们说 Paxos 在不假设在某个时刻所有消息都在有界时间内到达的情况下（这一假设被称为部分同步），不保证活性（即提案最终被决定）。

为了避免多个提议者不断竞争，大多数已部署的共识算法，如 Raft、Multi-Paxos 和 Viewstamped Replication，增加了一个特殊的 leader 提议者。Leader 是唯一可以提出提案的副本。将提议权集中在一个副本上，强制对并发请求进行排序，避免竞争性提案，并带来了额外的好处：在最优的单次网络往返中完成决策，而不是两次。当 leader 健康且网络行为良好时，基于 leader 的协议速度很快。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）