Cloudflare recently introduced Meerkat, an internal globally consistent control-plane service based on the QuePaxa consensus algorithm. Unlike Raft, it allows leaderless writes while preserving strong consistency, improving availability across Cloudflare's global network.
James Larisch, senior research engineer at Cloudflare, Bob Halley, principal research engineer at Cloudflare, and João Pedro Leite, research engineer at Cloudflare, write:
Unfortunately, commonly deployed consensus algorithms like Raft suffer in wide-area networks like Cloudflare’s because they rely on leaders and timeouts. The leader is the only replica allowed to make writes, and if it fails due to a crash or network degradation, the system becomes unavailable until some other replica times out and a new leader is elected.
To avoid further incidents caused by unavailable leaders in consensus-driven systems, the team has been developing a new distributed consensus service based on the QuePaxa consensus algorithm.
Unlike Raft, QuePaxa allows all replicas to accept writes without relying on leader timeouts, avoiding the availability loss that leader-based systems experience when a leader becomes unreachable across wide-area networks. Meerkat provides a consensus log that supports services such as a transactional key-value store and a leasing system, and Cloudflare says it is expected to be the first production deployment of QuePaxa at a global scale.
After outlining the consistency and fault-tolerance requirements, the article explains how Meerkat achieves strong consistency via a globally replicated consensus log that ensures all replicas agree on the order and values of committed operations, guaranteeing linearizable reads and writes. Larisch, Halley, and Leite add:
The Meerkat log is a sequence of slots. A slot is a box that can contain an event or not. A slot that contains an event is called a decided slot. All slots in the log are decided except the last slot, which is currently being decided. One of Meerkat’s invariants is that if any two replicas decide on the value for a slot, those values are the same. In other words, no two replicas will ever disagree on the value of a decided slot.
Source: Cloudflare blog
In a popular Hacker News thread, some practitioners found the article difficult to follow, while others questioned whether the additional round trips would be worth it in typical deployments. A user comments:
What's interesting here is that this would be the first production implementation of an asynchronous consensus algorithm (QuePaxa). Paxos, Raft, etc. are all partially synchronous, meaning they rely on timeouts and only make progress if message delay is sufficiently small compared to timeout durations. QuePaxa doesn't rely on timeouts and makes progress even under wild fluctuations in message delay. The question is whether performance is competitive enough in the normal case.
Assessing Meerkat’s performance, Larisch, Halley, and Leite warn:
Meerkat has limitations. It is not designed to create general-purpose data systems like databases. All consensus algorithms come with a cost: lots of round-trips. QuePaxa in particular takes one to three round trips (usually, although it can take more) between the initial proposer and a majority of replicas to decide on a proposal and add an event to the log.
While some developers ask Cloudflare to open source the specification they used to design and verify Meerkat, Aniket Ray, software engineer at KPIT, writes:
QuePaxa's approach to the latency-consistency trade-off is sharp. Research shows consensus overhead typically adds 40-60% latency in multi-region Paxos deployments, making Meerkat's optimization critical for strongly consistent systems.
Meerkat is not yet deployed to production, but Cloudflare says it has completed multiple proofs of concept with up to 50 replicas distributed worldwide.