Cloudflare has revealed engineering details regarding its experimental distributed consensus service, Meerkat, designed to manage the internal control plane on a global scale. The service relies on a modern consensus algorithm called QuePaxa, published by researchers Tennage & Băsescu in 2023. This choice represents a departure from the norm in the field of distributed systems, where most current infrastructures rely on established algorithms such as Raft, Paxos, or Viewstamped Replication.
Challenges of traditional consensus algorithms in global networks
Traditional consensus algorithms suffer from sharp performance drops or complete service outages when run across wide-area networks (WANs) characterized by latency jitter and potential connection drops. These protocols fundamentally rely on the presence of a leader process that ensures the ordering of operations and delivers responses within an expected time frame. When the leader experiences high latency or loses network connectivity, consensus operations stop completely until the failure is detected and a new leader is elected.
The main flaws of traditional systems manifest in two critical points:
- Destructive Interference: In the Paxos protocol, concurrent proposals from multiple nodes lead to the cancellation of mutual proposals and entry into a vortex of failed attempts that paralyze system progress. Although the Raft protocol solves the problem by designating a single leader, destructive interference reappears during leader election processes when temporary network disruption occurs.
- Fault Detectors: In asynchronous networks like the Internet, it is difficult to distinguish network slowness from a node's complete failure. Inaccurate estimations by fault detectors trigger unnecessary leader election processes, plunging the system into a failure state similar to metastable failure and stopping writes for hours.
How QuePaxa addresses failure points without a mandatory leader?
The QuePaxa algorithm overcomes these obstacles through three core design choices: making the leader an optional choice, completely eliminating fault detectors, and relying on cooperation rather than competition among proposers. The algorithm is based on dividing roles between proposers and recorders.
The algorithm relies on assigning random priorities to proposals. When a proposer receives a proposal with a higher priority than another recorder, it immediately adopts the new proposal and begins broadcasting it, causing all nodes to work cooperatively to reach the highest announced priority rather than blocking each other. In the presence of a leader, it is granted the highest possible priority, allowing it to settle consensus in a single round-trip as long as the network is stable.
Technical workflow: The four phases to achieve consensus
QuePaxa executes consensus rounds through four consecutive phases that the system goes through to approve logs:
- Phase 0 (Submission and Adoption): Proposers generate random priorities for their proposals. If the leader is operating correctly and its messages reach a majority of recorders first, consensus is immediately settled via the "Fast Path".
- Phase 1 (Propagation): Proposers broadcast the adopted proposals to a majority of recorders to prevent later regression on higher-priority proposals, based on majority intersection.
- Phase 2 (Checking and Deciding): Proposers query recorders about the highest priority seen in the previous phase, and if it matches their adopted proposal, it is officially approved.
- Phase 3 (Passing to the Next Round): In case consensus is not reached, nodes adopt the best available proposal in preparation for the next round, which heavily increases the likelihood of cumulative consensus.
Why does this technical shift matter?
The adoption of QuePaxa is a practical step that changes the design methodology of cross-continental distributed systems; it proves that systems do not need to sacrifice availability or suffer complete downtime during internet network disruptions. Meerkat's live operation results in Cloudflare's environment showed that more than 95% of decisions are settled via the leader's fast path, and when a network glitch or leader crash occurs, the system does not stop, but rather its throughput drops to a maximum of one-third while continuing to process requests.
The algorithm also enables hedging techniques, where clients can send proposals to all replicas with a short local waiting timeout without being tied to network latency, eliminating downtime periods caused by long election timeouts in Raft that reach several seconds. Cloudflare is currently working on formal verification of the algorithm's code written in Rust to ensure data safety during crash recovery recovery states.