pickuma.
Infrastructure

What Cloudflare's QuePaxa choice means for your clusters

Cloudflare built Meerkat on QuePaxa, a consensus algorithm whose leader is optional. Here is why that matters if you run etcd, Consul or ZooKeeper.

6 min read
Diagram: during the same network blip, Raft stops writes for a timeout and an election that outlast the blip, while QuePaxa keeps writing more slowly.

Animated diagram: a time cursor sweeps across Raft and QuePaxa during a network blip.

Cloudflare published Choosing QuePaxa, an unusual consensus algorithm. The post explains why Meerkat, its experimental consensus service for its internal global control plane, runs on QuePaxa instead of Raft or Paxos. QuePaxa is a 2023 algorithm by researchers Tennage & Băsescu et al. The detail that decides everything else is this: in QuePaxa, according to Cloudflare, “The leader is completely optional”. Any machine can propose, and nothing depends on detecting that the leader has failed. Most consensus systems you already run work the opposite way.

The background you need

A consensus algorithm lets a group of machines agree on one shared truth, even when some of them crash or disconnect. The core guarantee is that machines never decide conflicting values. Tools you may already depend on are built this way. etcd sits under the Kubernetes control plane. Consul and Apache ZooKeeper store configuration and handle service discovery. Cloudflare names all three as systems comparable to Meerkat.

These systems usually keep a replicated log. That is an ordered list of operations, such as writes to a key-value store. Every replica applies the same entries in the same order, so every replica ends up with the same data. Consensus decides what goes into each slot of the log.

To decide, the replicas need a majority, also called a quorum. With five replicas, three must agree. This is why you can lose a minority of machines and keep working.

Most real deployments use a leader-based algorithm. Raft, Multi-Paxos and Viewstamped Replication are the common ones. etcd and Consul use Raft. ZooKeeper uses its own leader-based protocol. One replica is the leader, and only it may propose new log entries. Cloudflare explains why: if several machines propose at once, they can keep blocking each other. Cloudflare calls this destructive interference. A single leader avoids it and decides in one network round trip.

The cost is that everything depends on the leader. Followers learn the leader is alive from heartbeats, which are regular I’m-alive messages. If a heartbeat doesn’t arrive within the election timeout, a follower assumes the leader is dead and starts an election. Until a new leader wins, writes stop.

Here is an analogy. Picture a team that only acts on instructions from one manager. If the manager goes quiet, the team stops and votes in a replacement. The analogy breaks in one important way. Over a network, nobody can tell whether the manager is dead or just hard to hear. Cloudflare’s point is that the two look identical from the outside.

That leads to one more term. Cloudflare calls a network asynchronous when it has no guaranteed upper bound on message delivery time. Per Cloudflare, most messages still arrive when expected. Sudden latency bursts and dropped connections still happen without warning. The Internet behaves this way.

What actually changed

QuePaxa itself is not new. It was published in 2023. What is new is that Cloudflare chose it for a real global system and explained why.

Cloudflare’s case against leader-based algorithms on wide-area networks has three parts.

Timeouts are guesses. A fault detector can only notice that an expected message hasn’t arrived. Cloudflare says any practical detector has to guess, and sometimes that guess will be wrong. When it is wrong, a healthy leader gets replaced and the system stops for the election. Cloudflare calls fault detection in asynchronous networks “fundamentally error-prone”.

Correct detection is still slow. According to Cloudflare, Raft is commonly deployed with an election timeout of five to ten times the network round-trip time. A round trip halfway around the world takes hundreds of milliseconds. So noticing a dead leader can take around a second, and the system is down for that whole time.

Elections can feed on themselves. Several replicas can become candidates at once and block each other from winning a majority. Cloudflare describes how a two-second network blip can set off elections that run much longer than the blip itself. This is a metastable failure: one that keeps going after its original cause is gone.

Cloudflare also cites a past incident. In 2020, the partial failure of a core network switch degraded a consensus-backed system. The dashboard ran 80x slower than usual for six hours. No data was lost, but writes were unavailable until the issue was fixed.

QuePaxa takes a different approach. Proposers send proposals to recorders, which pass them on to other proposers. Each proposal carries a random priority. When a proposer sees a higher-priority proposal, it adopts that proposal and starts broadcasting it. Proposers therefore converge on one proposal instead of fighting over it. A single round may not reach agreement, but the algorithm guarantees agreement given enough rounds.

A designated leader always has the top priority. It is the only proposer that can decide in a single round trip. Clients don’t have to go through it, though. If the leader goes down, clients keep sending requests to other proposers. No timeout triggers an election, because there is no election.

What it means if you deploy and run apps

The optional leader matters more than any other detail. It removes the step that makes leader-based systems fragile: a guess about whether the leader is alive, followed by a full stop.

You probably can’t use QuePaxa directly. Cloudflare describes Meerkat as experimental and built for its internal control plane. The reasoning still applies to systems you run today.

  • Know where your consensus clusters run. etcd, Consul and ZooKeeper were built for the setting Cloudflare describes as usual: smaller, more local networks with tight latency. If you stretch one cluster across regions or continents, you take on exactly the conditions Cloudflare describes.
  • Know your election timeout. Raising it reduces false elections but slows recovery from real failures. Lowering it does the opposite. Neither setting removes the trade-off, which is Cloudflare’s whole point.
  • Watch for leader changes during network trouble. If your control plane stalls while every server is healthy, look at leader-election metrics before you blame the machines. Repeated elections after a brief blip are the metastable pattern Cloudflare describes.
  • Prefer one cluster per region where you can. Multiple regional clusters avoid putting a single quorum on high-latency links.

Watch for two things next: whether Cloudflare shares more about how Meerkat behaves in production, and whether other projects start testing leaderless or optional-leader designs for wide-area deployments.

What we don’t know yet

Several questions remain open after Cloudflare’s explanation.

  • Production track record. Cloudflare calls Meerkat experimental. How it holds up through an incident like the 2020 switch failure is still to be seen.
  • Cost under contention. When the leader is unreachable, QuePaxa may need several randomized rounds to decide. How much latency that adds in real use is an open question.
  • Availability to others. Cloudflare presents Meerkat as an internal system. Whether it, or a reusable QuePaxa implementation, will ever be available for outside use is unclear.
  • Maturity. Cloudflare itself notes that Raft and Paxos have mature implementations and are well understood. QuePaxa has a much shorter history in practice.

FAQ

Does this mean Raft or etcd is broken?
No. Cloudflare says common algorithms like Raft are well understood and usually work well. Its argument is narrower: on wide-area networks with volatile latency, depending on a single leader and on timeouts leads to stalls. Inside a single region with stable links, that problem is much smaller.
What does it mean that the leader is optional?
In QuePaxa, one proposer is designated leader and can decide in a single round trip, so it is the fast path. Any other proposer can also propose. If the leader is down or slow, clients send requests elsewhere and the system keeps going, possibly over more rounds, without stopping for an election.
Can I run Meerkat or QuePaxa myself?
Cloudflare describes Meerkat as an experimental service for its own internal global control plane. For now, the practical takeaway is to understand how leader elections affect the consensus systems you already run.

Related tools

Some links above are affiliate links. We may earn a commission if you sign up. See our disclosure for details.

Related reading

See all Infrastructure articles →

Get the best tools, weekly

One email every Friday. No spam, unsubscribe anytime.