No leader required!? Cloudflare's new consensus service "Meerkat"

Hi everyone, it's me! Today's story is a bit technical but really interesting, it's about distributed systems. Let's take our time with this one!

Cloudflare Blog blog.cloudflare.com

What was announced?

On Cloudflare's Engineering blog, the Cloudflare Research team introduced "Meerkat," a global consensus service they're building. Meerkat is designed to keep control-plane state consistent across Cloudflare's 330+ data centers worldwide, with strong consistency and fault tolerance as top priorities. Down the line, the plan is to build applications on top of it, like a strongly consistent key-value store.

Why it matters

Raft is a go-to algorithm for reaching consensus in distributed systems, but it has a weak spot. Raft requires an authoritative leader, and if that leader goes down, all writes block until a new leader is elected. Leader election relies on timeouts, and tuning those timeouts is hard on a wide-area network like the Internet, where latency is unpredictable.

To address this, Meerkat uses "QuePaxa" instead of Raft, an algorithm published by EPFL researchers in 2023. QuePaxa doesn't require an authoritative leader; any replica can drive consensus. A leader exists purely as a performance optimization (it needs just one round trip), while going through a non-leader still works, just with three or more round trips. That means a single replica (the leader) going down never makes the service unavailable or degraded!

What changes

According to the post, under unreliable network conditions, QuePaxa achieved roughly 10x higher throughput than Raft and Multi-Paxos. In a proof-of-concept with up to 50 replicas deployed globally, the cluster kept running with no increase in error rate even while leaders kept failing constantly. This is described as the first industrial-scale deployment of QuePaxa.

Meerkat itself is still experimental and not yet in production. It's designed for control-plane data that's written infrequently but absolutely needs strong consistency.

Dive Deep

Let's look a little closer at how Meerkat works.

• Log structure: Meerkat keeps a distributed consensus log made up of units called "slots," with every replica holding an identical sequence of events. All slots except the last one are "decided," and once a slot is decided, its value is guaranteed to never disagree across replicas
• Strong consistency (linearizability): Reads and writes are guaranteed to appear in an order consistent with real time. If a read lands on a replica that's behind on a slot, that replica's proposal fails because the majority has already decided it, so the replica first catches up on the write and then re-proposes the read for the next slot
• Availability conditions: The service stays up as long as a majority of replicas are alive and communicating, and a client can reach any replica connected to that majority. It's designed to tolerate a single machine failure or a degraded link
• Performance trade-off: Decision latency is proportional to the communication latency between a majority of replicas, an unavoidable constraint once you're distributed globally. To ease this, Meerkat uses techniques like careful replica placement, batching writes (say, 10 writes arriving within 10ms get folded into one proposal), allowing slightly stale reads from a local replica, and supporting transactional operations like compare-and-swap

Looking ahead, the team plans deep dives into how QuePaxa itself works, formal verification of the Rust implementation, replica placement optimization, deterministic simulation testing, and a peer-reviewed manuscript. There's clearly more to come from this research!

Wrap-up

• Cloudflare Research is building "Meerkat," a global consensus service spanning 330+ data centers
• Instead of a Raft-style "leader required" design, it uses "QuePaxa," a leaderless algorithm published by EPFL in 2023
• It demonstrated roughly 10x the throughput of Raft and Multi-Paxos under unreliable network conditions
• It guarantees linearizability (strong consistency) while staying resilient to replica failures
• It's still experimental, with more technical write-ups and a paper planned

If you get excited about distributed systems and consensus algorithms, this is one worth reading slowly!