Hybrid Cloud Hybrid Cloud Computing Platforms

Cloudflare selects QuePaxa for its globally distributed Meerkat service

Cloudflare says its experimental distributed consensus service, Meerkat, uses QuePaxa, a consensus algorithm published in 2023 by Tennage and Băsescu and co-authors. The choice reflects the demands of running a control-plane system across a global network, where latency can vary and links may temporarily fail even when servers remain operational.

Meerkat’s replicas use consensus to maintain an ordered log of events. Applications can use that log to build a consistent key-value store: because replicas agree on the sequence of operations, they construct the same state. Cloudflare describes Consul, etcd and Apache ZooKeeper as comparable consensus-powered systems, while distinguishing Meerkat by its intended global deployment across continents.

The company’s experience with a network disruption illustrates the availability concern. In 2020, a partial failure of a core Cloudflare network switch caused a consensus-powered system to degrade, leaving its dashboard operating 80 times slower than usual for six hours. The system did not lose data, but writes were unavailable until the network issue was resolved.

Why leader-based protocols can stall

Consensus protocols such as Raft, Multi-Paxos and Viewstamped Replication commonly use a leader to coordinate proposals. A leader can order requests and, when conditions are healthy, help a system decide proposals efficiently. But if the leader becomes unreachable or slow, replicas must detect the problem and elect a replacement. During that process, the system may stop making progress.

Cloudflare identifies two related difficulties in wide-area networks. First, multiple proposers can interfere with one another. In Paxos-style protocols, competing proposals can repeatedly block progress. Leader-based designs reduce that competition during normal operation, but elections can reintroduce it: if several replicas suspect the leader has failed, they may compete for votes and prevent any candidate from winning a majority.

Second, failure detection depends on timing assumptions. A replica cannot directly tell whether a remote leader has failed or whether its messages are merely delayed. A timeout that is too short can trigger an unnecessary election; a conservative timeout avoids some false alarms but can delay recovery. Cloudflare notes that network round trips across long distances can take hundreds of milliseconds, making leader detection particularly slow in a globally distributed system.

An unnecessary election can also outlast the network disruption that prompted it. Cloudflare describes this as a metastable failure: a temporary fault may trigger repeated elections that continue to disrupt service after the original issue has passed.

QuePaxa’s optional-leader approach

QuePaxa is designed to make progress without requiring a leader to remain available. Its two roles are proposers, which submit values, and recorders, which record and relay proposals. Proposers assign priorities to proposals and adopt higher-priority proposals they learn about. Rather than permanently blocking one another, they can converge on the highest-priority proposal known to the group.

The algorithm retains a leader as a fast path, not as a requirement for progress. The leader’s proposal has the highest possible priority and can be decided in a single round trip if it reaches a majority of recorders first. If that does not happen, other proposers can continue trying to reach agreement. Clients are not required to send requests only to the leader.

Cloudflare’s implementation uses hedging to balance the fast path against continued availability. A request can be sent toward multiple replicas, while non-leader proposals are delayed briefly to give the leader an opportunity to decide first. Cloudflare says its implementation differs from the paper by having clients wait for this hedge interval rather than replicas. The interval is not a failure detector: lowering it does not trigger a system-wide pause, but can increase the number of active proposers and the volume of messages.

Rounds and agreement

QuePaxa proceeds in four phases per round. In Phase 0, proposers select priorities, submit proposals and adopt the highest-priority value supported by a majority of recorders. The leader can decide immediately if its proposal reaches a majority first. In Phase 1, proposers spread their adopted values. In Phase 2, they check the highest-priority proposal reported by a majority and decide if it matches their own. Phase 3 carries the best-known proposal into another round for those that have not decided.

The majority requirement is central to safety: any two majorities overlap, so proposals cannot be decided inconsistently. Randomized priorities help proposers converge, although a particular round is not guaranteed to produce a decision. Cloudflare says that, given enough rounds, QuePaxa guarantees agreement. Its design trades some additional messaging under contention for the ability to keep proposing without waiting for conventional leader-failure detection.