Many internal services at Cloudflare need to read and modify the same control-plane state from across our 330+ global data centers. They need guarantees that different readers never see inconsistent state, and that the system remains available for writes even when some data centers or links fail. But Cloudflare’s network runs across the entire Internet, and the Internet is an unpredictable place.
Servers and data centers go down. Queues fill up. Links and cables get cut.
These conditions make it difficult to run a globally available data system that guarantees strong consistency (e. g. , that all readers are guaranteed to read all prior writes) because hostile conditions hinder distributed system replicas’ ability to reliably synchronize data with one another.
One way to synchronize data safely despite adverse network conditions is via a consensus algorithm, which allows a set of machines to agree on the same sequence of values, such as key-value store put and get operations, as long as a majority remains alive and able to communicate. 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. And these timeout values are hard to configure in networks with unpredictable latencies. We have experienced multiple incidents caused by unavailable leaders in consensus-driven systems.
And so, for the past year, Cloudflare’s Research team has been building a new distributed consensus service called Meerkat powered by a consensus algorithm called QuePaxa , published in 2023 by researchers at EPFL. QuePaxa differs from Raft in that all replicas can perform writes at all times, and progress is never halted due to a timeout, which makes it well suited for Cloudflare’s network.
We layer applications , like a transactional key-value store and leasing system, atop Meerkat’s consensus log. To our knowledge, this will be the first industrial deployment of QuePaxa at global scale. Meerkat is an experimental consensus service that is still in development.
It’s being designed initially to manage small pieces of control plane state (e. g. , leadership for replicated databases) and so it will be kept internal-only for the immediate future.
This post introduces Meerkat and lays the groundwork for the Meerkat-related blog posts to come. What we need from a global control-plane data system Many Cloudflare services read and write control-plane data , data that helps those services operate correctly, from multiple machines distributed all over the world. One example of control-plane data is placement information : where certain resources (like an AI model instance) are stored.
Another example is leadership information : which machine is currently allowed to perform writes to a database. Control-plane data must be both strongly consistent and accessible despite particular kinds of faults. In this section we precisely describe our consistency and fault tolerance requirements for a Cloudflare consensus service.
We use a key-value store for a running example of an application running atop our consensus service, though other applications (e. g. , distributed leases/locks) are possible.
Strong consistency A distributed data system’s consistency level describes what kinds of weird behavior the system is allowed to exhibit when it receives concurrent reads and writes. Consider a distributed key-value store that stores a single numeric value x = 6 across multiple nodes. Also consider the following sequence of writes.
These writes are submitted to different nodes on a best-effort basis, and could arrive in any order: x = x + 1 x = x / 2 A system’s consistency level tells you what values of x a client might see when reading x after these writes. Consider the following sequence of operations and the possible execution orders under different consistency levels: In a weak consistency level, writes can be re-ordered.
In a stronger consistency model, writes can’t be reordered, but reads can. In the strongest possible consistency level, the operations are ordered exactly as they occurred in real time. This property is called linearizability .
At Cloudflare, many services want linearizability. Unlike weaker forms of consistency, linearizability relieves programmers from thinking about all the weird behaviors the data systems might exhibit. Instead, they can reason about the distributed system like they reason about local memory on a single-threaded machine: all reads after a write will see that write.
For additional reading material on the dangers of weak consistency, check out this post by Marc Brooker. (If you’re wondering, Meerkat’s key-value store also provides serializability, which we’ll write about in a future post.) Fault tolerance A system’s level of fault tolerance describes what kinds of faults the system can handle before catastrophes happen.
Catastrophes are typically violations of properties the system aims to uphold, e. g. , that two consecutive reads without an intervening write for the same key never see different values, or that the system remains available for writes.
The faults include network failures or delays, machine crashes, and machine restarts. A system will typically explicitly handle some faults but not others (you can’t handle all faults, as the universe could always reach heat-death). For example, some key-value stores might guarantee to remain available for writes as long as two-thirds of the machines in the system can communicate and don’t crash, but make no promises if a machine is compromised and starts sending malicious messages.
Originally published at blog.cloudflare.com
