Newshot 
Cloudflare 最近发布了 Meerkat，这是一个实验性的分布式共识服务，旨在管理我们的内部全局控制平面。它由研究人员 Tennage 与 Băsescu 等人发表的一种新的共识算法 QuePaxa（2023）驱动。
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 的结构——包括好的部分和不太好的部分。
文章标题：选择 QuePaxa，一种不寻常的共识算法
省略大量细节，Paxos 的工作原理如下。有两种进程：提议者（proposer）和接受者（acceptor）。抽象地说，系统的目标是让多数接受者就某个提议者提出的值达成一致。共有两个阶段：Prepare 阶段和 Accept 阶段。在 Prepare 阶段，任何提议者都可以向多数接受者发送一个选票编号。这个选票编号充当一种承诺——接受者只会接受具有该选票编号或更高编号的提案。然后，在 Accept 阶段，提议者再次将其提案连同选票编号发送给多数接受者。如果多数接受者仍然持有该提案的选票编号，多数便接受它，提议者就可以安全地决定该提案。
当两个或更多提议者同时提交提案时，挑战便出现了。具体来说，另一个提议者可以将其更高的选票编号插入两个阶段之间，从而阻塞任何更低的选票。两个提议者可以反复互相阻塞、无法推进——实际上是在争夺接受。
当提议者以这种方式竞争并互相阻塞时，我们说它们发生了破坏性干扰（destructive interference）。破坏性干扰会随着更多提议者提出各自的选票而加剧。并发提议者越多，系统陷入反复提议僵局的可能性就越大。即使没有任何副本崩溃或不可用，多个提议者和行为异常的网络也可能阻塞 Paxos。形式上，我们说 Paxos 在不假设“在某个时刻所有消息都在有界时间内到达”的情况下，不保证活性（liveness，即提案最终会被决定）——这一假设被称为部分同步（partial synchrony）。
为了避免多个提议者不断竞争，大多数已部署的共识算法，如 Raft、Multi-Paxos 和 Viewstamped Replication，都增加了一个特殊的领导者提议者。领导者是唯一可以提出提案的副本。将提议权集中到一个副本上，为并发请求强制了一个顺序，避免了相互竞争的提案，并额外带来了以最优的单次网络往返（而非两次）完成决定的优势。当领导者健康且网络行为良好时，基于领导者的协议速度很快。
代价是 leader 必须保持运行且可达。当它发生故障、变得过慢或与集群断开连接时，系统就会停滞。唯一的解决办法是让其余副本检测到 leader 已失效，并选举一个新的 leader 来替代它。
当 leader 恢复不稳定时
当 leader 失效时，系统必须通过选举新的 leader 来恢复。有趣的是，leader 恢复往往正是破坏性干扰重新潜入基于 leader 的系统的方式。
以 Raft 为例。出于安全考虑，Raft 通过多数投票选举新的 leader。怀疑 leader 已失效的副本会宣布自己为领导权候选人，并向其他副本请求投票。如果超过半数的副本同意投票给该候选人，它就成为新的 leader。如果未获多数，则会发起新的选举，候选人再次尝试。
多个副本都可能成为候选人——它们只需检测到 leader 已宕机即可。这些候选人随后可能同时尝试获取多数投票。问题在于，候选人会争夺多数投票，这意味着 Raft 的选举会遭受我们刚刚在 Paxos 中看到的破坏性干扰：两个副本可能相互阻止对方获得多数支持并成为 leader。选举失败得越多，就会有越多的副本试图让自己当选 leader。
即使 leader 不再故障，选举仍会继续干扰本可以正常运行的系统。这被称为亚稳态故障：一种即使初始故障原因被移除后仍会自我延续的故障模式。一次两秒的网络中断——或一个暂时故障的网络交换机——就可能使 leader 看起来已失效，并强制进行 leader 选举，而选举可能失败，并强制进行更多选举。中断将在两秒内结束，但选举可能持续更长时间，因为候选人会继续相互阻塞。
理想情况下，共识算法根本不需要任何恢复过程，因为它们复杂、容易受到干扰，并且会引入另一个停机来源。
当故障检测出错时
leader 选举中的破坏性干扰问题，因过于敏感的故障检测而加剧，尤其是在广域网中。为了让基于 leader 的共识算法选出新的 leader，副本必须首先检测到 leader 已失效。然而，如果副本不准确地检测 leader 失效，系统可能会花费过多时间在恢复上，而无法处理请求。
在分布式系统中，机器通过网络分隔，故障检测最终取决于预期。一个进程无法直接观察到远程进程已失效；它只能观察到预期消息是否到达。我们需要一种可预测的通信模式，例如心跳或确认，来告诉我们一台机器是健康的。如果预期消息未在预期时间内到达，我们就怀疑发生了故障。困难在于管理这些预期。
在真实网络中，尤其是广域网中，消息并不总是按预期时间到达。消息到达所需的时间没有保证的上界。这并不是说网络很慢，或者不可靠——大多数消息都在我们预期的时间内到达。相反，突发的延迟和连接中断可能会暂时地、毫无预警地增加任何消息穿越网络所需的时间。我们称这样的网络为异步网络。
异步网络的大问题在于，如果某台服务器在给定时间内没有回复，我们并不真正知道是服务器发生了故障，还是网络只是慢——这两者在网络上无法区分。任何实用的故障检测器都必须根据已等待的时间与其预期值的比较来做出猜测，而有时这个猜测会是错的。
在基于 leader 的算法中，这个猜测正是触发 leader 选举的原因。有时 leader 确实宕机了；有时它的消息迟到了，或者连接悄无声息地断了。协议在做出反应之前无法知道究竟发生了哪一种情况。如果猜测错了，某个副本认为 leader 有故障而实际上并没有，那么选举就会开始，整个系统必须停止。在 leader 被替换之前，不会取得任何进展——而正如我们刚才所见，这可能要花上一段时间。
在异步网络中，故障检测从根本上就容易出错，而当检测器犯错时，我们就会遭遇停机。
当故障检测很慢时
即使故障检测器猜对了，也存在问题。故障检测器通过观察网络上的消息来对故障做出反应，因此它们的响应时间必须随网络延迟而变化——检测器的超时时间不能低于网络延迟。这就是为什么 Raft 通常部署时选举超时设为网络往返时间的五到十倍。它必须足够高，以便给 leader 机会发出存活信号，并避免误触发选举。选举超时也可以远低于这个值，但由于 leader 选举会完全停止系统，超时通常被保守地设得很高。
粗略地说，跨越半个地球的往返时间以数百毫秒计。如果选举超时是几个往返时间，检测一个失败的协调者可能需要大约一秒。即使故障检测完全准确，它也是慢的，而且在高速迟的全球网络中是最慢的。在检测器做出反应之前，系统处于停机状态。
为什么 QuePaxa 是合适的选择
我们意识到，任何依赖严格 leader 或精确超时的算法，在运行于互联网之上的共识系统中都不可避免地会停滞。我们寻找为异步环境设计的共识算法——不依赖良好行为的网络或精确计时就能运作的协议。这引导我们找到了 QuePaxa，由 Tennage & Băsescu 等人于 2023 年发表。
QuePaxa 最引人注目的是，它能在有利的网络条件下高效地在单个往返内达成共识，同时在延迟飙升、连接问题和服务器故障期间优雅地降低性能。QuePaxa 通过三个关键设计选择解决了我们刚才讨论的 exact 问题来实现这一点：拥有一个可选的 leader、完全消除对故障检测的依赖，以及为提议者之间的建设性干扰而设计。
在 QuePaxa 中，与 Paxos 非常相似，存在两种角色：提议者和记录者。提议者提交待决定的提案，记录者充当提议者之间的中介，记录它们看到的每一个提案。
在 QuePaxa 中，提议者不是相互竞争以让自己的提案被决定，而是合作推动一个所有人都支持的提案。QuePaxa 通过为提案分配优先级来实现这一点，优先级以随机数的形式表示。可选的主节点获得一个独占的最大优先级。在执行过程中，提议者将提案提交给记录者，记录者再将提案传播给其他活跃的提议者。当提议者从记录者处收到优先级高于自己的提案时，它们会将该新提案采纳为自己的提案，即开始广播这个更高优先级的提案。总体而言，QuePaxa 中的提议者协同工作，以决定它们共同所知的最高优先级提案。这意味着提议者无法无限期地将彼此排除在决定提案之外。
需要注意的是，提案可能无法充分传播以达成一致，因此提议者必须重试，每一次尝试构成一轮。然而，随着更多提议者提交提案，它们越有可能收敛到最高优先级的提案上。这正是 QuePaxa 成为随机化算法的原因：非主节点提议者随机生成的优先级有可能——但并非保证——在一轮中促成对已知最高优先级的共识。然而，给定足够多的轮次，提议者最终达成一致是有保证的。
一个提议者被指定为主节点。主节点是唯一能够在单次往返中完成决定的提议者。主节点始终以最高优先级提出提案；如果主节点知道它在任何其他提议者之前传播了自己的提案，那么它可以立即做出决定。客户端并非必须向主节点发送请求——任何提议者都可以提出提案。如果主节点宕机，客户端可以继续向其他提议者发送请求。主节点完全是可选的。主节点只是比其他任何提议者更有可能做出决定，并且能在单次往返中更快地完成。
然而，由于主节点是唯一能在单次往返中做出决定的节点，我们希望尽可能利用它。为了利用这条快速路径而不引入单点故障，向系统发送提案的客户端会进行对冲下注：它们将提案请求发送给每一个副本，非主节点副本会等待一个较短的超时时间，以便主节点能够自行提出并决定提案。在我们自己的 QuePaxa 实现中，我们实际上偏离了论文的做法，让客户端而不是副本等待对冲超时，以减少网络上发送的消息数量，但整体结果是一样的。
这种对冲超时与 Raft 或 Multi-Paxos 中使用的超时截然不同。它不是故障检测，因此不受网络延迟约束；它由副本在本地决定，可以小到副本想要的任何值。在 Raft 中，在延迟为 100 毫秒的网络中设置 5 毫秒的超时会让系统完全冻结。但在 QuePaxa 中，5 毫秒的对冲超时只会增加活跃提议者的数量。
然而，对冲并非没有代价：提议者越多，广播的提案就越多，副本在某一轮中无法完成决定的可能也越大。相反，对冲提供了一种权衡：我们可以通过降低对冲超时来更快地响应领导者变更，但会付出额外的带宽成本，并可能花费更多时间来完成决定。这是我们非常愿意做出的权衡。
如果 QuePaxa 的领导者宕机，我们可以以任意快的速度恢复——不受网络延迟的约束。这就是 QuePaxa 绕开故障检测的方式：既然任何人都可以提议，而不仅仅是领导者，QuePaxa 就可以通过对冲主动应对领导者故障，而不是对故障做出反应。
How QuePaxa works under the hood
为了理解 QuePaxa 如何为我们提供所有这些优良特性，让我们看看 QuePaxa 实际是如何工作的。
QuePaxa 以由四个阶段组成的轮次运行。如果某个提案在最后一个阶段仍未完成决定，就会启动新一轮，QuePaxa 重新开始。在每个阶段开始时，提议者将他们当前采纳的提案广播给所有记录者。一旦提议者收到来自多数记录者的回复，他们就进入下一阶段。以下是各阶段的总体概要：
- 阶段 0（提议与采纳）：提议者随机选择一个优先级，将他们的提案发送给记录者，并采纳他们从多数记录者处收到的最高优先级提案。如果是第一轮，且领导者知道自己的提案最先到达多数记录者，领导者会立即做出决定。
- 阶段 1（传播）：提议者将他们采纳的提案传播给多数记录者。
- 阶段 2（检查与决定）：提议者向多数记录者询问上一阶段所见到的最高优先级提案。如果它与自己采纳的提案一致，他们就对其做出决定。
- 阶段 3（结转）：任何未能做出决定的提议者通过采纳他们从多数记录者处见到的最佳提案，为下一轮做准备。
让我们走查几个示例执行过程，剖析每个阶段如何促成我们期望从 QuePaxa 获得的整体行为。每个执行过程将有两个提议者（其中一个是领导者）和三个记录者。
Leader Fast Path（阶段 0）：第一阶段做三件重要的事：随机化优先级（这是规避 FLP 不可能定理所必须做的）、检查 leader 是否率先获得多数支持，以及在 leader 未能获得多数支持时帮助提议者收敛。leader 的提案不参与随机化，始终拥有可能的最高优先级。
在上面的例子中，leader 的提案比其他任何提案都更早到达多数 recorder，并收到了确认它的回复。leader 可以安全地立即做出决定。这看起来可能很危险，但得益于一个称为多数交集（majority intersection）的性质，它完全安全：任意两个 recorder 多数集合总是至少共享一个 recorder。由于 leader 已经到达多数，任何其他查询多数的提议者都必然会遇到 leader 的提案并采纳它。由于 leader 的提案具有最高优先级，任何其他提议者都会采纳 leader 的提案。不可能决定任何其他提案。
并发慢路径（阶段 0-3）：然而，当存在并发提议者时，并不能保证 leader 会立即做出决定。leader 可能未能率先到达多数 recorder，也可能收到一个支持其他提议者的回复。下面看看当另一个提议者与 leader 竞争时会发生什么。
阶段 0：如下图所示，第二个提议者（以红色显示）先到达第二个和第三个 recorder。快速路径被阻塞。提议者不会相互竞争，而是采纳它们从多数中收到的优先级最高的提案，并进入第二阶段。两个提议者在这一阶段都可能收敛到 leader 的提案。为便于说明，我们的示例将通过延迟 leader 的消息来阻止收敛。
阶段 1：proposer 将它们在阶段 0 刚刚采纳的提案传播给多数 recorder。recorder 记录它们观察到的最高优先级提案。这是一个简单但关键的步骤：它防止协议在后续决定一个优先级更低的提案。这同样要归功于多数交集：在下一阶段查询的任何多数中，必须至少包含一个在本阶段看到了被采纳提案的 recorder。为便于说明，我们在本阶段通过延迟 leader 发往第三个 recorder 的消息来阻止收敛，因此该 recorder 不会采纳 leader 的提案。
阶段 2：现在可以做出决定了。每个 proposer 向多数 recorder 询问它们在阶段 1 观察到的最高优先级提案，以此判断是否有更高优先级的提案获得了足够支持从而超越自己的提案。如果返回的最高提案仍是它们采纳的提案，它们就做出决定。在我们的图中，leader 看到多数返回的是自己的提案，于是安全地做出决定。另一个 proposer 收到相互冲突的摘要，因此它还不能做出决定。与阶段 1 一样，recorder 记录它们收到的最高优先级提案。
阶段 3：如果 proposer 在阶段 2 未能决定，则进入最后的清理阶段，为下一轮做准备。proposer 再次传播其提案，并在多数 recorder 中采纳其找到的最佳提案。在这里，剩余的 proposer 发现了已决定的提案并采纳它，进入下一轮。
这是有意为之——如果上一阶段已经做出了某个决定，那么多数 recorder 将持有该提案，任何剩余的 proposer 都保证会采纳它。我们在这里看到了 proposer 之间合作的另一个实例——即使某一轮失败，proposer 也会尝试在进入下一轮时收敛到同一个提案。
进入下一轮：在第四阶段之后，proposer 进入下一轮。此时不再有 leader 快速路径，唯一的决定方式是在第三阶段收敛。重要的是，由于提案采纳机制，随着轮次推进，做出决定的难度呈指数级下降。QuePaxa 论文预测每轮有 50% 的概率做出决定，但在实践中，由于收敛效应，这一概率要高得多。
将四个阶段放在一起，我们可以看到 QuePaxa 的韧性来自何处。第一阶段为 leader 提供了一轮往返的快速路径。如果该快速路径失败，随机优先级和提案采纳帮助 proposer 收敛而非竞争。第二和第三阶段通过多数交集使决定变得安全，而第四阶段将 proposer 学到的内容带入下一轮，以防 proposer 未能决定。
proposer 无需在取得进展之前检测 leader 是否已失败，失败的轮次也不会丢弃已完成的工作。当网络表现良好时，QuePaxa 很快。当网络表现不佳时，QuePaxa 继续前进。
QuePaxa 如何使 Meerkat 成为可能
在我们对 Meerkat 的评估中，服务器遍布几乎各大洲，我们直接体验到了 QuePaxa 对系统整体性能和可用性的影响。即使 leader 崩溃、断开连接或变慢，Meerkat 也能持续处理请求。我们从未见过它完全停滞。这正是我们想要的。
Meerkat 处理请求的速率总体上也具有可预测性。大多数决策——高达 95% 以上——由 leader 在第一阶段完成，这使我们的吞吐量保持相当稳定。在未能在第一阶段达成决策的情况下，吞吐量会短暂下降，最多降至通常速率的三分之一，这表明需要三次往返——即三个阶段——而非仅一个阶段才能完成决策。系统会变慢，但不会陷入停滞。
QuePaxa 还允许我们在集群运行期间自信地切换由哪个副本担任 leader。由于 leader 并非决策的唯一驱动者，且提议者是协作式的，一个暂时非最优的 leader 不会像在其他算法中那样成为严重限制——在其他算法中，leader 配置错误可能使系统完全停滞。我们可以动态调整哪个提议者担任 leader，而无需过多担心影响 Meerkat 集群的稳定性。
接下来我们将展示什么
为全球网络设计 Meerkat 迫使我们重新评估处理分布式共识的方式。我们没有固守那些并不完全符合我们约束的熟悉默认方案，而是求助于学术界和工业界数十年积累的研究成果。这一探索将我们引向了 QuePaxa。
选择 QuePaxa 意味着选择一条少有人走的路。它尚未像 Raft 或 Paxos 那样经过广泛的实际检验，我们还在扩展最初的 crash-stop 设计以支持崩溃恢复。这需要谨慎的工程实现，以及比通常系统更强的正确性证据。
这就是为什么我们在进行大量模拟和故障注入测试的同时，还对我们的 QuePaxa 实现以及整个 Meerkat 进行形式化验证。本系列的后续文章将解释我们如何验证 Meerkat 和 QuePaxa 的 Rust 实现、我们如何测试难以在生产环境中复现的故障、基准测试，以及我们在将学术协议转化为生产系统过程中的经验教训。
请关注 Cloudflare Blog 上更多 Meerkat 的更新，如果你想了解更多 Cloudflare 的研究工作，请查看我们在 Cloudflare Research 的工作。