选择 QuePaxa:一种非比寻常的共识算法

Cloudflare 最近发布了 Meerkat,这是一项实验性的分布式共识服务,旨在管理我们内部的全局控制平面。它由研究人员 Tennage 与 Băsescu 等人发表的一种名为 QuePaxa(2023)的新共识算法驱动。
QuePaxa 是个不寻常的选择;大多数共识系统使用的是成熟的共识算法,如 Raft、(Multi-)Paxos 或 Viewstamped Replication。这些算法已被充分理解,拥有成熟的实现,通常运行良好。
遗憾的是,常见共识算法在广域网中往往表现不佳——网络连接和延迟波动剧烈,也就是像互联网这样的网络,而 Meerkat 正运行于其中。这些算法依赖于存在一个可用的领导者进程,且其延迟可预测。如果领导者宕机、延迟高于平常或断连,整个共识系统就会变慢或不可用,直到领导者被替换。这对 Meerkat 而言是不可接受的。
Meerkat 的全球部署环境促使我们转向一种更新的共识算法 QuePaxa,它承诺在波动环境下具备更好的稳定性,很大程度上是因为它不依赖领导者来取得进展。在本文中,我们将解释为什么选择 QuePaxa,以及 QuePaxa 算法是如何工作的。
Meerkat 是一个分布式系统,其中的各个副本就有序事件日志达成一致,每个事件都由共识算法决定。
共识算法使一组机器能够就单一共享事实达成一致,即使其中一些机器崩溃或断连。共识算法提供了一项重要保证:机器绝不会决定相互冲突的值。这确保 Meerkat 各副本的日志绝不会出现分歧。
Meerkat 利用其基于共识的日志来对外暴露诸如键值存储之类的应用,日志中每条条目都是一次 get 或 put 操作。由于共识算法保证各副本的日志永远不会出现分歧,因此它们都会构建出相同的键值(KV)状态。类似的基于共识的系统包括 Consul、etcd 和 Apache ZooKeeper。
不过,与类似系统不同的是,Meerkat 是为全球规模而设计的。一个 Meerkat 集群可能横跨多个大洲,其间链路往往具有高且波动大的延迟。对于共识系统而言,这是一种不寻常的部署方式——这类系统通常部署在更小、更本地化的网络中,并有着严格的延迟要求。
尽管所有共识算法都能确保各副本对同一个值达成一致,但当网络状况恶化(而机器并未崩溃)时,其中许多算法会变得异常不可用或异常缓慢。我们曾亲眼见证这种情况:2020 年,Cloudflare 一台核心网络交换机的部分故障导致一个基于共识的系统性能下降,控制面板的运行速度比平时慢 80 倍,持续了六个小时。关键在于,该系统没有丢失任何数据。但在问题解决之前,它一直无法写入,这是不可接受的。
理想情况下,共识算法应当能够在延迟飙升和连接中断的情况下继续推进,而不仅仅是在副本故障时才如此。这在全球规模下尤其成问题,因为此时故障更可能源自网络,而非我们自己的服务器。
让我们来审视共识算法在恶劣网络条件下可能导致性能退化的两个常见特性:破坏性干扰和故障检测。稍后,我们将看到 QuePaxa 如何避开这两个问题。
不妨看看 Paxos——它堪称大多数共识算法的鼻祖。许多共识算法都继承了 Paxos 的结构——既包括其中好的部分,也包括不那么好的部分。
略去大量繁琐细节,Paxos 的运作方式是这样的。系统中有两类进程:提议者和接受者。抽象地讲,该系统的目标是让多数接受者对某个提议者提出的值达成一致。整个过程分为两个阶段:Prepare 阶段和 Accept 阶段。在 Prepare 阶段,任何提议者都可以向多数接受者发送一个选票编号。这个选票编号相当于一个承诺——接受者只会接受该选票编号或更高编号的提案。随后在 Accept 阶段,提议者再次将自己的提案连同选票编号发送给多数接受者。如果多数接受者仍持有该提案的选票编号,多数便接受该提案,提议者即可安全地确定该提案。
当两个或更多提议者同时提交提案时,挑战就出现了。具体来说,另一个提议者可以在两个阶段之间插入自己更高的选票编号,从而阻断所有更低的选票。两个提议者可能反复相互阻断、无法推进——实际上就是在争夺接受。
当多个提议者这样相互竞争、相互阻塞时,我们说它们发生了破坏性干扰。提议者越多,各自提出自己的提案,破坏性干扰就越严重。并发的提议者越多,系统就越有可能陷入反复提议的僵局。即使没有任何副本崩溃或不可用,多个提议者和行为异常的网络也足以阻塞 Paxos。严格来说,如果不假设在某个时刻所有消息都能在有界时间内送达——这一假设被称为部分同步——我们就无法说 Paxos 能保证活性(即提案最终会被裁决)。
为了避免多个提议者持续竞争,大多数实际部署的共识算法,如 Raft、Multi-Paxos 和 Viewstamped Replication,都会增加一个特殊的领导者提议者。领导者是唯一可以提出提案的副本。把提议权集中到单个副本上,为并发请求强制规定了顺序,避免了相互竞争的提案,还带来一个额外好处:决策可以在最优的单次网络往返内完成,而不是两次。只要领导者健康、网络行为正常,基于领导者的协议就很快。
代价是领导者必须保持运行且可达。当它发生故障、变得过于缓慢,或与集群断开连接时,系统就会停滞。唯一的解决办法是让其余副本检测到领导者已失效,并选举出一个新的领导者取而代之。
当领导者失效时,系统必须通过选举新的领导者来恢复。有意思的是,领导者恢复往往正是破坏性干扰重新潜入基于领导者的系统的途径。
以 Raft 为例。出于安全性考虑,Raft 通过多数投票选举新的领导者。当某个副本怀疑领导者已经失效时,它会宣布自己成为领导者候选人,并向其他副本请求投票。如果有超过半数的副本同意投票给该候选人,它就成为新的领导者。如果没有,就会发起新一轮选举,候选人们再次尝试。
多个副本都可能成为候选人——它们只需检测到领导者不可用即可。这些候选人可能会同时试图争取多数投票。问题在于,候选人之间会为多数投票相互竞争,这意味着 Raft 的选举会遭遇我们刚刚在 Paxos 中看到的破坏性干扰:两个副本可能相互阻止对方获得多数支持并成为领导者。选举失败得越多,就会有越多的副本试图让自己当选领导者。
即使领导者不再故障,选举仍会持续扰乱本可以正常运行的系统。这被称为亚稳态故障:一种即使最初引发故障的原因已被消除,仍会自我延续的故障模式。一次持续两秒的网络中断——或者一台瞬时故障的网络交换机——就能让领导者看起来像是出了故障,从而强制触发领导者选举;选举可能失败,并迫使进行更多次选举。中断会在两秒内结束,但选举可能持续更长时间,因为候选人会不断相互阻碍。
理想情况下,共识算法不应需要任何恢复流程,因为这些流程复杂、容易受到干扰,还会引入另一个导致停机的原因。
领导者选举中的破坏性干扰问题,会因过于激进的故障检测而进一步加剧,尤其是在广域网中。基于领导者的共识算法要选出新的领导者,副本必须先检测到原领导者已经失效。然而,如果副本对领导者失效的检测不准确,系统可能会把过多时间花在恢复上,而无法处理请求。
在分布式系统中,机器通过网络彼此分隔,故障检测最终取决于预期。一个进程无法直接观察到远程进程已经失效;它只能观察到预期中的消息是否到达。我们需要一种可预测的通信模式,比如心跳或确认消息,来告诉我们某台机器是健康的。如果预期消息没有在预期时间内到达,我们就会怀疑出现了故障。难点在于管理这些预期。
原文较长,译文为节选;译文由英文原文机器翻译,术语按行业惯例统一,可在文末展开原文核对。
查看英文原文(Choosing QuePaxa, an unusual consensus algorithm)
Cloudflare recently announced Meerkat, an experimental distributed consensus service designed to manage our internal global control plane. It is powered by a new consensus algorithm published by researchers Tennage & Băsescu et al. called QuePaxa (2023).
QuePaxa is an unusual choice; most consensus systems use well-established consensus algorithms like Raft, (Multi-)Paxos or Viewstamped Replication. These algorithms are well understood, have mature implementations, and usually work well.
Unfortunately, common consensus algorithms often suffer in wide-area networks with volatile network connectivity and latency, i.e., networks like the Internet, which is where Meerkat runs. These algorithms rely on a single leader process being available and having predictable latency. If the leader goes down, experiences higher latency than usual, or is disconnected, the entire consensus system slows down or becomes unavailable until the leader is replaced. This is unacceptable for Meerkat.
Meerkat’s global deployment environment led us to a newer consensus algorithm, QuePaxa, which promises better stability despite volatility, in large part by not relying on a leader to make progress. In this post we’ll explain why we chose QuePaxa and how the QuePaxa algorithm works.
What we’re building and why it’s unique
Meerkat is a distributed system in which replicas agree upon an ordered log of events, where each event is decided by a consensus algorithm.
Consensus algorithms allow a group of machines to agree on a single shared truth, even if some of those machines crash or disconnect. Consensus algorithms provide an important guarantee: machines never decide conflicting values. This ensures Meerkat replicas’ logs never diverge.
Meerkat uses its consensus-powered log to expose applications like a key-value store, where each entry in the log is a get or a put. Because the consensus algorithm guarantees replicas’ logs never diverge, they all construct the same key-value (KV) state. Comparable consensus-powered systems include Consul, etcd, and Apache ZooKeeper.
Unlike similar systems, however, Meerkat was designed for global scale. A Meerkat cluster may be distributed across continents and connected by links that often exhibit high and variable latency. This is an unusual setup for consensus systems, which are usually deployed in smaller, more local networks, and have strict latency requirements.
The challenges of consensus at a global scale
While all consensus algorithms ensure that replicas agree on the same value, many of them become disproportionately unavailable or slow when network conditions degrade (but machines do not crash). We have seen this happen firsthand: in 2020, the partial failure of a core Cloudflare network switch caused a consensus-powered system to degrade and the dashboard to operate 80x slower than usual, for six hours. Critically, the system lost no data. But it became unavailable for writes until the issue was resolved, which is unacceptable.
Ideally, a consensus algorithm should be able to make progress despite latency spikes and broken connections, not just replica failures. This is particularly a problem at global scale, where faults are more likely to originate in the network, and not our own servers.
Let’s examine two common traits of consensus algorithms that can lead to degradation under hostile network conditions: destructive interference and fault detection. Later, we’ll see how QuePaxa sidesteps both of these issues.
Destructive interference and leaders
Consider Paxos, the veritable grandfather of most consensus algorithms. A lot of consensus algorithms inherit the structure of Paxos – both the good and the not-so-good bits.
Leaving an egregious amount of detail out, here’s how Paxos works. There are two kinds of processes: proposers and acceptors. Abstractly, the goal of the system is for a majority of acceptors to agree on a value proposed by some proposer. There are two phases: the Prepare phase, and the Accept phase. In the Prepare phase, any proposer can send a ballot number out to a majority of acceptors. This ballot number serves as a promise – acceptors will only accept proposals with that ballot number or higher. Then, in the Accept phase, the proposer sends its proposal along with the ballot number to a majority of acceptors again. If a majority of acceptors still hold the ballot number of the proposal, the majority accepts it, and the proposer can safely decide the proposal.
Challenges arise when two or more proposers submit proposals at the same time. Specifically, another proposer can interleave its own higher ballot number in between the two phases, blocking any lower ballots. Two proposers can repeatedly block each other from progressing – effectively competing for acceptance.
When proposers compete and block each other in this way, we say that they destructively interfere. Destructive interference gets worse as more proposers propose their own ballots. The more concurrent proposers there are, the more likely it is that the system gets stuck repeatedly proposing. Even if none of the replicas have crashed or are unavailable, multiple proposers and misbehaving networks can block Paxos. Formally, we say that Paxos does not guarantee liveness (i.e., that proposals are eventually decided) without assuming that, at some point, all messages arrive within a bounded amount of time — an assumption known as partial synchrony.
To avoid multiple proposers constantly competing, most deployed consensus algorithms, like Raft, Multi-Paxos, and Viewstamped Replication, add a special leader proposer. The leader is the only replica that can make proposals. Centralizing the proposing power in one replica forces an order on concurrent requests, avoids competing proposals, and has the added benefit of getting decisions done in an optimal single network round-trip, instead of two. While the leader is healthy and the network is well-behaved, leader-based protocols are fast.
The trade-off is that the leader must remain operational and reachable. When it fails, becomes too slow, or is disconnected from the cluster, the system stalls. The only solution is for the remaining replicas to detect that the leader has failed, and elect a new one in its place.
When leader recovery is unstable
When a leader fails, the system must recover by electing a new one. Interestingly, leader recovery is often how destructive interference sneaks right back into a leader-based system.
Consider Raft. For safety reasons, Raft elects a new leader using a majority vote. A replica that suspects that the leader has failed announces itself as a candidate for leadership and requests a vote from other replicas. If more than half of the replicas agree to vote for the candidate, it becomes the new leader. If they don’t, then a new election is called, and the candidates try again.
Multiple replicas can become candidates — all they need to do is detect that the leader is down. The candidates may then all try to acquire a majority vote simultaneously. The problem is that the candidates will compete for the majority vote, which means Raft’s elections suffer from the destructive interference we just saw in Paxos: two replicas can mutually prevent each other from getting support from a majority and becoming the leader. The more elections fail, the more replicas will try to get themselves elected leader.
Even if the leader stops being faulty, elections continue to disrupt what could have been normal system functioning. This is known as a metastable failure: a failure pattern that perpetuates itself even when the initial cause of failure is removed. A two-second network outage — or a momentarily faulty network switch — can make the leader appear to be faulty and force a leader election, which can fail, and force further elections. The outage will be over in two seconds, but the election can continue for much longer as candidates continue to block each other.
Ideally, consensus algorithms wouldn’t need any recovery process, as they are complicated, prone to interference, and introduce another source of downtime.
When fault detection goes awry
The problem of destructive interference in leader elections is compounded by trigger-happy fault-detection, especially in wide-area networks. In order for leader-based consensus algorithms to choose a new leader, replicas must first detect that the leader has failed. However, if replicas detect leader-failures inaccurately, the system may spend an inordinate amount of time in recovery, not handling requests.
In a distributed system, where machines are separated over a network, fault detection will ultimately depend on expectations. A process cannot directly observe that a remote process has failed; it can only observe that an expected message has or hasn’t arrived. We need a predictable pattern of communication, such as heartbeats or acknowledgements, to tell us that a machine is healthy. If an expected message does not arrive within the expected time, we suspect a fault. The difficulty lies in managing those expectations.
In real networks, especially wide-area networks, messages don’t always arrive when predicted. There is no guaranteed upper bound on the time that it takes for messages to arrive. That’s not to say that the network is slow, or that it is unreliable — most messages arrive within the time we expect them to. Instead, sudden bursts of latency and losses in connectivity can, momentarily, and without warning, increase the time it takes for any message to traverse the network. We call such networks asynchronous.
The big issue with asynchronous networks is that if some server doesn’t reply in a given amount of time, we don’t really know if the server has failed or if the network is just slow — the two are indistinguishable over the network. Any practical fault detector has to make a guess based on how long it has been waiting compared to its expectation, and sometimes that guess will be wrong.
In leader-based algorithms, that guess is exactly what triggers leader elections. Sometimes the leader is down; sometimes its messages are late, or the connection is silently broken. The protocol cannot know which one happened before it reacts. If the guess is wrong, and a replica thinks the leader is faulty when it actually isn’t, then an election begins and the entire system must stop. Until the leader is replaced, no progress is made — and as we just saw, that can take a while.
Fault detection is fundamentally error-prone in asynchronous networks, and when the detector makes a mistake, we get downtime.
When fault detection is slow
Even when a fault detector guesses correctly, there are issues. Fault detectors react to failures by observing messages on the network, and so their response time has to scale with network latency — the detector’s timeout can’t be below the network latency. This is why Raft is commonly deployed with an election timeout of five to ten times the network round-trip time. It has to be high enough to give a chance for the leader to signal that it is alive, and avoid falsely triggering elections. The election timeout can be much lower than that, but since leader elections completely stop the system, timeouts are usually set conservatively high.
Roughly speaking, a round trip halfway across the world is measured in hundreds of milliseconds. If an election timeout is several round trips, detecting a failed coordinator can take around a second. Even when fault detection is completely accurate, it is slow, and it is slowest in high-latency global networks. Until the detector reacts, the system is down.
Why QuePaxa is the right fit
We realized that any algorithm relying on a strict leader or accurate timeouts was inevitably going to stall in a consensus system that runs over the Internet. We searched for consensus algorithms designed for asynchronous environments — protocols that didn't rely on a well-behaved network or precise timing to function. This led us to QuePaxa, published in 2023 by Tennage & Băsescu et al.
The most notable thing about QuePaxa is how it can efficiently reach consensus in a single round trip under favorable network conditions, but also gracefully degrades performance during latency spikes, connectivity issues, and server failures. QuePaxa achieves this by solving the exact problems we just discussed through three key design choices: having an optional leader, completely removing the reliance on fault detection, and designing for constructive interference between proposers.
In QuePaxa, much like in Paxos, there are two roles: proposers and recorders. Proposers submit proposals to be decided on, and recorders serve as intermediaries between proposers, recording every proposal they see.
Instead of having proposers compete to get their own proposals decided, in QuePaxa, proposers will cooperatively work towards a proposal that everyone supports. QuePaxa does this by assigning a priority to proposals, in the form of a random number. The optional leader gets an exclusive maximum priority. During execution, proposers submit their proposals to the recorders, who propagate the proposal to other active proposers. When proposers receive a proposal from a recorder with a higher priority than theirs, they adopt the new proposal as their own, i.e., begin broadcasting the higher priority proposal instead. In general, proposers in QuePaxa work together to decide on the highest priority proposal that they collectively know. This means proposers can’t lock each other out of deciding on a proposal, indefinitely.
The caveat is that it might not be possible to spread proposals around well enough to agree on a proposal, and so proposers have to try again, with each attempt constituting a round. However, as more proposers submit proposals, the more likely they are to converge on the highest priority proposal. This is what makes QuePaxa a randomized algorithm: the randomly generated priorities of non-leader proposers are likely — but not guaranteed — to lead to consensus on the highest known priority, in a round. Yet, given enough rounds, it is guaranteed that proposers agree on a proposal.
One proposer is designated the leader. The leader is the only proposer capable of deciding in a single round trip. The leader always proposes with the highest priority; if the leader knows it spread its proposal before any other proposer, then it can decide immediately. Clients aren’t forced to make requests to the leader — any proposer can propose. If the leader goes down, then clients can keep making requests to other proposers. The leader is completely optional. The leader is simply more likely to decide, than any other proposer, and do so faster, in a single round trip.
However, because the leader is the only one that can decide in a single round trip, we want to use it whenever possible. To exploit this fast path without creating a single point of failure, clients sending proposals to the system hedge their bets: they send their requests for proposals to every replica, and the non-leader replicas will wait for a small timeout, so the leader can propose and decide on its own. In our own implementation of QuePaxa, we actually deviate from the paper and have clients wait the hedge timeout instead of the replicas, to reduce the amount of messages we send over the network, but the overall result is the same.
This hedging timeout is very different from the timeouts used in Raft or Multi-Paxos. It is not fault detection, and so isn’t constrained by network latency; it is locally determined by replicas and can be as small as they want it to be. In Raft, having a five-millisecond timeout in a network with 100-millisecond latency would completely freeze the system. But in QuePaxa, a five-millisecond hedge timeout only increases the number of active proposers.
However, hedging isn’t free: the more proposers there are, the more proposals get broadcast, and the more likely it is that replicas fail to decide in a round. Instead, hedging provides a tradeoff: we can react faster to leader changes by lowering the hedge timeout, but we incur extra bandwidth costs and may take more time to decide. That’s a tradeoff we're more than willing to make.
If the QuePaxa leader goes down, we can recover as fast as we want — we’re not bound by network latency. This is how QuePaxa gets around fault detection: since anyone can propose, not just the leader, QuePaxa can proactively deal with leader failures by hedging, rather than reacting to failures.
How QuePaxa works under the hood
To understand how QuePaxa gives us all of these nice properties, let’s look at how QuePaxa actually works.
QuePaxa works in rounds made up of four phases. If a proposal hasn’t been decided on in the last phase, a new round is started, and QuePaxa starts over. At the start of each phase, proposers broadcast their currently adopted proposal to all recorders. Once a proposer receives a reply from a majority of recorders, they advance to the next phase. Here’s the general outline of the phases:
- Phase 0 (Propose and Adopt): Proposers randomly select a priority, send their proposals to recorders, and adopt the highest-priority proposal they receive from a majority of recorders. If it’s the first round and the leader knows its proposal reached a majority of recorders first, the leader decides immediately.
- Phase 1 (Spread): Proposers spread their adopted proposal to a majority of recorders.
- Phase 2 (Check and Decide): Proposers ask a majority of recorders for the highest-priority proposal seen in the previous phase. If it matches their own adopted proposal, they decide on it.
- Phase 3 (Carry Forward): Any proposer that failed to decide prepares for the next round by adopting the best proposal they see from a majority of recorders.
Let’s walk through a couple of example executions and unpack how each phase contributes to the overall behavior we want out of QuePaxa. Each execution will have two proposers (one of which is the leader) and three recorders.
The Leader Fast Path (Phase 0): The first phase does three important things: it randomizes priorities (which it must do to circumvent the FLP impossibility theorem), checks if the leader reached a majority of support first, and helps proposers converge if the leader didn't. The leader’s proposal is not randomized, and will always have the highest possible priority.
In the example above, the leader's proposal reaches a majority of recorders before anyone else, and receives replies confirming it. The leader can safely decide right away. This might seem dangerous, but it is entirely safe thanks to a property called majority intersection: any two majorities of recorders always share at least one recorder. Because the leader reached a majority, any other proposer querying a majority will inevitably encounter the leader's proposal and adopt it. Since the leader’s proposal has the highest priority, any other proposer will adopt the leader’s proposal. It is impossible to decide on any other proposal.
Concurrent Slow Path (Phases 0-3): When there are concurrent proposers, however, it is not guaranteed that the leader will immediately decide. The leader might fail to reach a majority of recorders first, or it might receive a single reply supporting another proposer. Let's look at what happens when another proposer contests the leader.
Phase 0: Pictured below, a second proposer (shown in red) reaches the second and third recorders first. The fast path is blocked. Instead of competing, proposers adopt the highest-priority proposal they receive from a majority and move to the second phase. The two proposers could both converge to the leader’s proposal in this phase. For illustrative purposes, our example will prevent convergence by delaying the leader’s messages.
Phase 1: Proposers spread the proposal they just adopted in Phase 0 to a majority of recorders. The recorders keep track of the highest-priority proposal they observe. It is a simple but critical step: it prevents the protocol from later deciding on a lower-priority proposal. This is once again thanks to majority intersection: any majority queried in the following phase must include at least one recorder that saw the adopted proposal, in this phase. For illustrative purposes, we prevent convergence in this phase by delaying the leader’s message to the third recorder, so the recorder does not adopt the leader’s proposal.
Phase 2: Now, a decision can happen. Each proposer determines if a higher-priority proposal gained enough support to overtake its own by asking a majority of recorders for the highest-priority proposal observed during Phase 1. If the highest proposal returned is still their adopted proposal, they decide. In our diagram, the leader sees its own proposal returned by a majority and safely decides. The other proposer receives conflicting summaries, so it cannot decide yet. Like in Phase 1, recorders keep track of the highest priority proposal they received.
Phase 3: If a proposer doesn’t decide in Phase 2, it moves to the final cleanup phase to prepare for the next round. Proposers spread their proposals again and adopt the best they find among a majority of recorders. Here, the remaining proposer discovers the decided proposal and adopts it, heading into the next round.
This is deliberate — if there was some decision in the previous phase, then a majority of the recorders will have that proposal, and any remaining proposers are guaranteed to adopt it. We see here another instance of cooperation between proposers — even when a round fails, proposers try to converge on the same proposal heading into the next round.
Moving to the next round: After the fourth phase, proposers move on to the next round. At this point, there is no more leader fast path, and the only way to decide is by converging in the third phase. Importantly, due to proposal adoption, it becomes exponentially easier to decide as rounds progress. The QuePaxa paper predicts that each round has a 50% chance of deciding, but in practice, that probability is much higher, thanks to convergence.
Putting all four phases together, we can see where QuePaxa gets its resilience. The first phase gives the leader its one-round-trip fast path. If that fast path fails, random priorities and proposal adoption help proposers converge instead of compete. The second and third phases make it safe to decide, thanks to majority intersection, while the fourth carries what proposers learned into the next round, in case proposers don’t decide.
No proposer has to detect that the leader has failed before making progress, and a failed round doesn’t throw away the work already done. When the network behaves, QuePaxa is fast. When it doesn’t, QuePaxa keeps moving.
How QuePaxa makes Meerkat possible
In our own evaluations of Meerkat, where we had servers spanning nearly all continents, we’ve directly experienced the impact that QuePaxa has on the overall performance and availability of the system. Meerkat continuously processes requests, even when the leader crashes, disconnects, or just becomes slow. At no point have we ever seen it completely stall. This is exactly what we wanted.
The rate at which Meerkat handles requests has also been generally predictable. Most decisions — upwards of 95% — are made by the leader in the first phase, which keeps our throughput fairly stable. In the instances where a decision isn't reached in the first phase, the throughput drops momentarily, down to at most a third of the usual rate, signaling that three round trips — so three phases — were needed to decide instead of just one. The system slows down, but does not grind to a halt.
QuePaxa also allows us to confidently switch out which replica acts as leader while the cluster is running. Since the leader isn’t the exclusive driver behind decisions and proposers are cooperative, a temporarily non-optimal leader isn’t as limiting as in other algorithms, where a leader misconfiguration could stall the system completely. We can dynamically tune which proposer is the leader without worrying too much about impacting the stability of a Meerkat cluster.
What we’ll be showing next
Designing Meerkat for a global network forced us to re-evaluate how we approach distributed consensus. Instead of sticking to familiar defaults that didn't quite fit our constraints, we looked to the decades of research produced by academia and industry. That search led us to QuePaxa.
Choosing QuePaxa meant choosing a less-traveled path. It has not been battle-tested as extensively as Raft or Paxos, and we’re also extending the original crash-stop design to support crash recovery. This demands careful engineering and stronger evidence of correctness than usual systems.
That is why we are formally verifying our QuePaxa implementation and Meerkat as a whole, alongside extensive simulation and fault-injection testing. Future posts in this series will explain how we verify Meerkat and QuePaxa’s Rust implementation, how we test failures that are difficult to reproduce in production, benchmarks, and what we have learned while turning an academic protocol into a production system.
Stay on the lookout for further Meerkat updates on the Cloudflare Blog, and if you want to learn more about research at Cloudflare, have a look at our work at Cloudflare Research.
正文保留英文原文,标题与摘要由机器翻译。
原文发布于 Cloudflare Blog(Choosing QuePaxa, an unusual consensus algorithm),标题、摘要与正文由机器翻译,术语按行业惯例统一,未经人工逐句校订。