Why leaderless consensus for a global control plane

Cloudflare’s internal services need to read and modify shared control-plane state from across its 330+ data centers. That state has to be strongly consistent — readers must never observe stale or divergent views — and writes must remain possible even when parts of the network fail.

The Internet is a hostile environment for strongly consistent distributed systems. Machines crash, links get cut, and latency is unpredictable. Consensus algorithms are the standard tool for getting replicas to agree on a shared log of operations, but the most widely deployed ones have a structural weakness in wide-area networks.

Raft-based systems, for example, rely on a single leader. Only that leader can accept writes, and if it becomes unreachable, the system stops accepting writes until another replica detects the failure via a timeout and triggers an election. In a network where round-trip times vary wildly across continents, picking timeout values is a guessing game. Set them too low and you get spurious elections; too high and outages stretch out. Cloudflare has suffered multiple incidents caused by unavailable leaders in consensus-driven systems.

For the past year, the Cloudflare Research team has been developing Meerkat, a consensus service built on QuePaxa, a 2023 algorithm by Tennage & Băsescu et al. QuePaxa has no fixed leader. Every replica can accept writes at any time, and progress never depends on a timeout firing. That makes it a better fit for Cloudflare’s network than leader-based algorithms. Meerkat layers applications — starting with a transactional key-value store and a leasing system — on top of QuePaxa’s consensus log. To Cloudflare’s knowledge, this will be the first industrial deployment of QuePaxa at global scale.

Meerkat is experimental and still in development. Its initial scope is small control-plane state, such as leadership for replicated databases, and it will remain internal-only for the foreseeable future.

Consistency and fault tolerance requirements

Control-plane data covers things like placement information (where an AI model instance is stored) and leadership information (which machine may currently write to a database). Services that depend on this data expect two properties from the system that stores it: strong consistency and tolerance for specific classes of faults.

Linearizability for everyone

A consistency level defines what behavior a system may exhibit under concurrent reads and writes. Take a single numeric key x = 6 replicated across nodes. Two writes arrive at different nodes, possibly in any order:

  1. x = x + 1
  2. x = x / 2

What value can a client read afterward? The answer depends entirely on the ordering guarantees the system provides.

Weaker consistency models allow writes to be reordered. Stronger ones serialize writes but may let reads lag. The strongest model, linearizability, orders operations exactly as they occurred in real time. A read issued after a completed write is guaranteed to observe that write.

Cloudflare services want linearizability. It lets programmers reason about a distributed system as they would about single-threaded local memory, without reasoning about stale reads or reordering edge cases. (Meerkat’s key-value store will also offer serializability, which the team plans to cover in a future post.)

Availability without a healthy leader

Fault tolerance describes which failures a system survives before it starts violating its guarantees. The relevant faults here are crashes, restarts, and network failures or delays. Cloudflare’s requirements for Meerkat are defined by two properties.

First, a client in any data center must be able to read and write as long as:

  1. A majority of the system’s machines are alive and mutually reachable (formally, tolerating f faults in a system of 2f + 1 machines).
  2. The client can reach any one machine that is connected to such a majority.

Notably, no single failed machine or degraded link may affect availability. Raft-based systems do not meet this bar near a leader failure.

Second, the system must remain correct so long as no participant is actively malicious and there are no implementation bugs. Correctness, in consensus terms, means safety: two up-to-date machines cannot hold conflicting views of the world, such as one believing key1=1 while another believes key1=2.

To summarise: Meerkat must stay correct across crashes, restarts, link degradation and data center outages. Like Raft-based systems, it is not designed to withstand Byzantine faults.

How Meerkat is built

Meerkat is a consensus service designed to run applications that need both strong consistency and fault tolerance, such as a key-value (KV) store. Developers request a cluster of Meerkat replicas, where each replica is connected to every other replica. All replicas participate in the consensus algorithm and can handle both reads and writes. Developers can also specify which data centers may host their replicas, and Meerkat places them automatically.

Clients send application-specific requests to any replica in the cluster. The simplest application is a KV store with get and put operations. Reads via get are guaranteed to return up-to-date information.

The replicated log

Internally, a replica translates each application request into a log event and distributes that event to all other replicas via the consensus algorithm, so every replica maintains the same log of events. A replica may lag behind, but it never records different entries. Meerkat’s core is agnostic to event contents; the applications hosted by each replica — such as a KV store — read the log events and construct their state from them.

For example, the KV application builds an in-memory store from the log. When a client sends put k1 v1, the receiving replica packages that write as a log event and distributes it. A later put k1 v11 sent to a different replica is likewise distributed. Because all functioning replicas share the same log, they apply the operations in sequence to build identical state. Notably, get requests also become log events, which is required for linearizability. The following shows how a replica’s KV store changes as it processes log events:

Why the log guarantees strong consistency

Meerkat ensures that if a client first executes put k1 v1, then another executes put k1 v11, and a third subsequently executes get k1, the read always returns v11 — even when each request lands on a different replica spread across the world. This is linearizability, and it follows from the structure of the log.

The log is a sequence of slots. A slot containing an event is decided; all slots are decided except the last one, which is actively being decided. A key invariant is that no two replicas ever disagree on the value of a decided slot — though one may think the last slot is empty while another does not.

To decide the value for the final empty slot, replicas run a distributed consensus algorithm, which guarantees agreement as long as a majority of replicas (more than half) are alive. If the log has two entries and a client submits put k1 v11, the receiving replica triggers consensus for slot 3. A concurrent put k1 v111 sent to a different replica also proposes slot 3. The algorithm ensures exactly one proposal wins: a majority must agree on it, and the non-majority can never decide a conflicting value — though they may miss that slot 3 was decided at all.

This design makes reads linearizable. Suppose replica Z proposes put k1 v11, and a majority decides it at slot 3 — but replica Y is not in that majority. If a reader then sends get k1 to Y, Y believes slot 3 is empty and proposes its read there. Critically, the majority that already decided slot 3 will not accept a new event in that slot. Instead, they force Y to learn the older decision (put k1 v11) and to propose the get k1 at slot 4, linearizing the read after the write. If Y cannot reach a majority, the read cannot complete.

Why not Raft

Not all consensus algorithms offer the same availability. Algorithms that depend on an authoritative leader, like Raft, introduce a single point of temporary failure. Raft forwards all writes to a leader; if the leader goes down, all writes block until a new leader is elected. If the leader stays up but becomes slow due to overload or network delays, it becomes a throughput bottleneck with no alternative path for writes.

The leader-election problem is especially acute in wide-area networks. Most leader-based algorithms rely on timeouts: a replica that hasn’t heard from the leader in a set interval declares itself leader. If the timeout is shorter than the network delay between the old leader and that replica, replicas will keep timing out and block writes; if it’s too long, the system reacts slowly to a genuine leader failure. Concurrent leadership campaigns can also interfere, causing repeated re-elections while writes are blocked. Cloudflare has seen these exact problems with Raft-based systems because wide-area network delays vary significantly, making timeout tuning extremely difficult.

Meerkat instead uses QuePaxa, a consensus protocol designed to avoid this “tyranny of timeouts.” In QuePaxa, any replica can drive consensus for the current slot. There is a leader, but it is optional — its sole benefit is deciding with one round trip instead of three or more. Clients may contact multiple replicas concurrently for the same proposal to increase the chance of success, and these concurrent proposals do not destructively interfere; replicas work together to settle on one proposed value.

QuePaxa offers three concrete advantages over Raft for Meerkat’s use case:

  1. Because there is no required leader, the system never becomes unavailable or degraded simply because one specific replica is down, unreachable, or slow. Clients can write as long as they can reach any healthy replica.
  2. There are no leader elections to disrupt operation, and concurrent proposals from different replicas interfere constructively rather than destructively — critical for a network where latencies fluctuate widely.
  3. QuePaxa is designed for asynchronous networks where connections may be attacked or dropped. Under those conditions its authors measured roughly 10x higher throughput than Raft and Multi-Paxos, which matches Cloudflare’s network reality more closely than the assumptions underlying other algorithms.

Performance trade-offs

Meerkat is not meant to power general-purpose databases. Consensus inherently incurs round trips: QuePaxa typically needs one round trip when the leader proposes, three when a non-leader proposes, and more with concurrent proposals — plus an extra broadcast to notify replicas of the decision. Fundamentally, decision latency scales with the latency between the majority of replicas, so widely dispersed replicas necessarily increase write and read latency.

Several mechanisms mitigate this cost:

  1. Developers control replica placement and can cluster replicas closer together when truly global distribution is not needed.
  2. Writes can be batched — several writes arriving close in time can be combined into a single proposal.
  3. Reads that tolerate stale (but never inconsistent) data can be served directly from any replica without triggering consensus.
  4. Multiple operations can be bundled into one consensus round, including compare-and-swap writes and general transactions within the KV application.

Even so, Meerkat’s latency profile makes it best suited in the near term for control-plane data — information that is written infrequently but must stay consistent.

Current status

Meerkat is not yet in production, but Cloudflare has run proof-of-concept clusters with up to 50 replicas distributed worldwide. In these trials, leaders fail constantly and the cluster keeps operating with no increase in error rate. Future posts will cover the internals of QuePaxa, formal verification of parts of the Rust implementation, bootstrapping and cluster management, replica placement optimization, deterministic simulation testing, and a peer-reviewed manuscript.