Choosing QuePaxa, an unusual consensus algorithm

What we’re building and why it’s unique

Cloudflare is building an experimental consensus service using a never-before-deployed consensus algorithm, QuePaxa. In this post we explain how QuePaxa works and why we chose it.

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 called QuePaxa.

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.

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
• 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:

1. The Prepare phase
2. 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 mo