Meerkat, Cloudflare's QuePaxa consensus service

Cloudflare Research has spent a year building Meerkat, a consensus service for control-plane state shared across 330+ data centers. The motivating complaint is specific: they have had multiple incidents caused by unavailable Raft leaders, and wide-area latencies that vary wildly make the timeouts Raft depends on impossible to tune. Meerkat runs QuePaxa instead, the 2023 algorithm by Tennage, Băsescu et al., which has no required leader and never blocks on a timeout. Cloudflare says this will be the first industrial deployment of QuePaxa at global scale.

The state in question is small and written rarely — where an AI model instance lives, which machine currently holds write leadership for a replicated database. It is not a general-purpose database and isn't meant to become one.

What they need

Linearizability, first. Not because it's the strongest option on the menu but because anything weaker forces every service author to reason about which reorderings their code can survive; linearizable reads let them think about the cluster the way they think about local memory on a single thread.

Fault tolerance, second, in a specific shape. The system stays available for reads and writes from a client in any data center as long as a majority of machines are alive and mutually reachable (f faults out of 2f + 1), and the client can reach any machine connected to that majority. A single dead machine or one degraded link must not affect availability anywhere. Raft-based systems do not provide this. Like Raft, Meerkat does not handle Byzantine faults — correctness assumes no actor is actively malicious.

The log

A developer requests a cluster of replicas, optionally constraining which data centers may host them, and Meerkat places them. Every replica connects to every other and accepts both reads and writes. A client sends an application-specific request to whichever replica it likes.

The replica turns that request into a log event and runs consensus to place it in the next slot. Meerkat's core does not interpret events; applications hosted on each replica do. The key-value store application, for instance, replays the log into an in-memory map. The invariant that makes this work is that no two replicas ever decide different values for the same slot — a replica may lag, and may believe the last slot is still empty when it isn't, but it can never record something different.

Reads go through the log too, and the mechanism for why is the clearest part of the post. Replica Z gets put k1 v11 decided at slot 3 by a majority that excludes replica Y. A client then sends get k1 to Y. Y thinks slot 3 is free and proposes the read there. The majority refuses, because slot 3 is decided; they force Y to learn put k1 v11 for slot 3 and to re-propose its read at slot 4. The read is thereby linearized after the write it must observe. If Y cannot reach a majority, the read simply fails rather than returning stale data.

Why not Raft

Raft's authoritative leader is the single replica allowed to drive consensus, which buys understandability and, with leases, linearizable leader-served reads. It also buys a single point of temporary failure. If the leader dies, writes block until an election completes. If it merely slows down, whether overloaded or sitting behind a degraded link, everything degrades with it, because there is no other way to write.

Wide-area networks make the election worse. Failure detection is a timeout, and a timeout shorter than the real network delay means replicas time out constantly and block writes for no reason, while a timeout longer than that means slow reaction to a genuinely dead leader, blocking writes the whole time. Simultaneous candidates interfere: campaigns collide, replicas re-propose themselves, and writes stay blocked through all of it. Cloudflare says they have hit exactly these failures in production.

QuePaxa's differences, as summarized in the post: any replica can drive consensus for the current slot, so no single machine's health gates availability. A leader exists but is only an optimization — it decides in one round trip, a non-leader needs three or more. Concurrent proposals from different replicas interfere constructively: replicas cooperate to decide one of the proposed values rather than knocking each other down, which means a client is free to contact several replicas at once to raise its odds. And the algorithm was designed for asynchrony and for an adversary targeting specific replica links, conditions under which its authors measured roughly 10x the throughput of Raft and Multi-Paxos.

The cost

Round trips, and no way around them. One if the leader proposes, three if a non-leader does, plus a broadcast to announce the decision, and more when proposals collide. Decision latency is bounded below by the latency to some majority of replicas, so replicas spread across the planet are slow by construction.

Four mitigations, none of which change that floor. Developers control replica placement, so clusters that don't need global reach can be packed tighter. Writes arriving close together get batched into one proposal. Reads that tolerate staleness (stale but never inconsistent) can be served from any replica's local state without a consensus round. And multiple operations can ride one round, including compare-and-swap writes and general transactions.

This is the argument for the scope: infrequently-written, must-be-correct control-plane data, where a few wide-area round trips per write is an acceptable price.

Status

Not in production. Proofs of concept have run with up to 50 replicas worldwide, and the headline result is that leaders in those clusters fail constantly with no increase in error rate — which is the whole point, since under Raft that would be an outage each time. Future posts are promised on how QuePaxa actually works, formal verification of parts of the Rust implementation, bootstrapping and cluster management, optimal replica placement, and deterministic simulation testing. A peer-reviewed manuscript is planned.

distributed-consensus for Paxos, Raft, and the tradeoff space Meerkat is picking a corner of; flp-impossibility for why timeout-based failure detection is a synchrony assumption rather than an implementation detail — QuePaxa's claim is not that it escapes FLP but that it doesn't convert asynchrony into unavailability. lee-holloway, Cloudflare's co-founder and first lead engineer, built the company's first prototype.