Introducing Meerkat- an experiment in global consensus (opens in new tab)

Cloudflare is building Meerkat, an experimental global consensus service for coordinating control-plane state across more than 330 data centers. It aims to provide linearizable reads and writes while remaining available despite machine failures, network degradation, and data-center outages. Meerkat uses QuePaxa rather than Raft because QuePaxa allows all replicas to write and does not halt progress while waiting for failure timeouts.

The Challenge of Global Control-Plane State

• Cloudflare services need to read and modify shared state from locations around the world.
• Examples include:
  • Placement information for resources such as AI model instances.
  • Leadership information identifying which machine may write to a database.
• The system must combine:
  • Strong consistency, so readers do not observe conflicting or stale state.
  • High availability, even when machines, links, queues, or data centers fail.
• Wide-area networks are unpredictable, making replica synchronization difficult.

Why Consensus Is Needed

• Consensus algorithms allow machines to agree on a single ordered sequence of operations, such as key-value-store reads and writes.
• A typical consensus system can continue safely as long as a majority of replicas remain alive and connected.
• This provides a foundation for applications such as:
  • Transactional key-value stores.
  • Distributed leases and locks.
  • Database leadership management.

Limitations of Raft in Wide-Area Networks

• Raft depends on a leader, and only the leader can accept writes.
• If the leader crashes or becomes unreachable, the system may become unavailable until a timeout triggers leader election.
• Timeout configuration is especially difficult across global networks with unpredictable latency.
• A single failed machine or degraded network link can therefore affect availability.
• Cloudflare reports having experienced incidents caused by unavailable leaders in consensus-based systems.

Strong Consistency and Linearizability

• Consistency determines how concurrent reads and writes may be ordered or observed.
• Weak consistency can allow writes to be reordered.
• Stronger models may preserve write ordering while still allowing reads to observe different states.
• Linearizability is the strongest model described:
  • Operations appear to occur in real-time order.
  • Every read after a completed write observes that write.
• Linearizability lets developers reason about distributed state similarly to local memory on a single-threaded machine.
• Meerkat’s planned key-value store also provides serializability, which Cloudflare says will be covered separately.

Fault-Tolerance Requirements

Meerkat is intended to remain available and correct under several classes of failure:

• The system should support reads and writes from any data center when:
  • A majority of machines are alive and can communicate.
  • A client can reach a machine connected to that majority.
• In a system of 2f + 1 machines, the design tolerates f faults.
• Single-machine failures and individual network-link degradations should not interrupt availability.
• The system must remain correct during:
  • Machine crashes and restarts.
  • Network failures and delays.
  • Data-center outages.
• Up-to-date machines must never disagree about committed state.
• Like Raft, Meerkat does not attempt to tolerate Byzantine faults or actively malicious participants.

Introducing Meerkat and QuePaxa

• Meerkat is being developed by Cloudflare Research as an internal, experimental consensus service.
• It is powered by QuePaxa, a consensus algorithm published by EPFL researchers in 2023.
• Unlike Raft:
  • Any replica can perform writes.
  • Progress does not stop because a timeout expires or a leader becomes unavailable.
• Applications will be layered on Meerkat’s consensus log, initially focusing on small control-plane data.
• The first use cases include database leadership and other coordination state.
• Cloudflare describes this as the first planned industrial deployment of QuePaxa at global scale.
• Meerkat will remain internal while it is still under development.