Introducing Meerkat: an experiment in global consensus

Cloudflare has developed an experimental consensus service named Meerkat, designed to manage critical control-plane state across its global network of over 330 data centers. This new system aims to provide strong consistency and high availability, even under challenging internet conditions.
Many internal Cloudflare services require access to and modification of control-plane data, which dictates how these services operate. Examples include placement information for resources like AI models and leadership assignments for replicated databases. Ensuring that different parts of the system never see conflicting data, and that the system remains accessible for writes despite potential failures, is crucial.

Traditional consensus algorithms like Raft, while effective in many scenarios, can struggle with the unpredictable nature of wide-area networks. Raft relies on a leader replica to handle all writes and uses timeouts to detect leader failures. In networks with variable latency, these timeouts can be difficult to configure, leading to system unavailability during leader elections or network disruptions. Cloudflare has experienced issues with such consensus-driven systems becoming unavailable due to leader problems.
To address these limitations, Cloudflare's Research team has been developing Meerkat, which utilizes a consensus algorithm called QuePaxa. QuePaxa, published in 2023 by researchers at EPFL, differs from Raft by allowing all replicas to perform writes concurrently and by not halting progress due to timeouts. This design makes it more suitable for Cloudflare's global infrastructure.
Meerkat is built as a consensus service, with applications like a transactional key-value store and a leasing system layered on top. The service is currently in development and is intended for internal use, initially managing small pieces of control-plane state. Cloudflare anticipates this will be the first large-scale industrial deployment of the QuePaxa algorithm.

The requirements for a global control-plane data system at Cloudflare include strong consistency, specifically linearizability, which ensures that operations appear to execute in a single, real-time order. This simplifies reasoning for developers, allowing them to treat the distributed system much like local memory on a single-threaded machine.
In terms of fault tolerance, Meerkat aims to remain available for reads and writes as long as a majority of its machines can communicate and are operational. This means that the failure of a single machine or a network link should not impact the system's availability. The system is also designed to remain correct, meaning no two up-to-date machines will disagree on data, provided no malicious actors are involved. This fault tolerance covers machine crashes, restarts, network failures, and data center outages, though it does not address Byzantine faults.
Meerkat's architecture involves clusters of replicas, where each replica is connected to all others. Developers can specify the data centers where replicas should be located, and Meerkat handles the placement. Client applications interact with any replica in a cluster by sending application-specific requests, such as key-value get or put operations. These requests are translated into log events that are distributed to all replicas via the QuePaxa consensus algorithm, ensuring all replicas maintain an identical log of events. Applications then process these log events to construct their state.





