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 的工作原理。有两种进程：提议者（proposer）和接受者（acceptor）。抽象地说，系统的目标是让多数接受者就某个提议者提出的值达成一致。有两个阶段：Prepare 阶段和 Accept 阶段。在 Prepare 阶段，任何提议者都可以向多数接受者发送一个选票编号（ballot number）。这个选票编号充当一个承诺——接受者只会接受具有该选票编号或更高编号的提案。然后，在 Accept 阶段，提议者再次将其提案连同选票编号发送给多数接受者。如果多数接受者仍然持有该提案的选票编号，多数派就会接受它，提议者便可以安全地决定该提案。

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

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

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

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