Cloudflare recently announced Meerkat , an experimental distributed consensus service designed to manage our internal global control plane. It is powered by a new consensus algorithm called QuePaxa . QuePaxa is an unusual choice; most consensus systems use well-established consensus algorithms like Raft, (Multi-)Paxos or Viewstamped Replication.
These algorithms are well understood, have mature implementations, and usually work well. Unfortunately, common consensus algorithms often suffer in wide-area networks with volatile network connectivity and latency, i. e.
, networks like the Internet, which is where Meerkat runs. These algorithms rely on a single leader process being available and having predictable latency. If the leader goes down, experiences higher latency than usual, or is disconnected, the entire consensus system slows down or becomes unavailable until the leader is replaced.
This is unacceptable for Meerkat. Meerkat’s global deployment environment led us to a newer consensus algorithm, QuePaxa, which promises better stability despite volatility, in large part by not relying on a leader to make progress. In this post we’ll explain why we chose QuePaxa and how the QuePaxa algorithm works.
What we’re building and why it’s unique Meerkat is a distributed system in which replicas agree upon an ordered log of events, where each event is decided by a consensus algorithm. Consensus algorithms allow a group of machines to agree on a single shared truth, even if some of those machines crash or disconnect. Consensus algorithms provide an important guarantee: machines never decide conflicting values.
This ensures Meerkat replicas’ logs never diverge. Meerkat uses its consensus-powered log to expose applications like a key-value store, where each entry in the log is a get or a put . Because the consensus algorithm guarantees replicas’ logs never diverge, they all construct the same key-value (KV) state.
Comparable consensus-powered systems include Consul, etcd, and Apache ZooKeeper. Unlike similar systems, however, Meerkat was designed for global scale . A Meerkat cluster may be distributed across continents and connected by links that often exhibit high and variable latency.
This is an unusual setup for consensus systems, which are usually deployed in smaller, more local networks, and have strict latency requirements . The challenges of consensus at a global scale While all consensus algorithms ensure that replicas agree on the same value, many of them become disproportionately unavailable or slow when network conditions degrade (but machines do not crash).
We have seen this happen firsthand: in 2020, the partial failure of a core Cloudflare network switch caused a consensus-powered system to degrade and the dashboard to operate 80x slower than usual, for six hours. Critically, the system lost no data. But it became unavailable for writes until the issue was resolved, which is unacceptable.
Ideally, a consensus algorithm should be able to make progress despite latency spikes and broken connections, not just replica failures. This is particularly a problem at global scale, where faults are more likely to originate in the network, and not our own servers. Let’s examine two common traits of consensus algorithms that can lead to degradation under hostile network conditions: destructive interference and fault detection.
Later, we’ll see how QuePaxa sidesteps both of these issues. Destructive interference and leaders Consider Paxos, the veritable grandfather of most consensus algorithms. A lot of consensus algorithms inherit the structure of Paxos – both the good and the not-so-good bits.
Leaving an egregious amount of detail out, here’s how Paxos works. There are two kinds of processes: proposers and acceptors. Abstractly, the goal of the system is for a majority of acceptors to agree on a value proposed by some proposer.
There are two phases: the Prepare phase, and the Accept phase. In the Prepare phase, any proposer can send a ballot number out to a majority of acceptors. This ballot number serves as a promise – acceptors will only accept proposals with that ballot number or higher.
Then, in the Accept phase, the proposer sends its proposal along with the ballot number to a majority of acceptors again. If a majority of acceptors still hold the ballot number of the proposal, the majority accepts it, and the proposer can safely decide the proposal. Challenges arise when two or more proposers submit proposals at the same time.
Specifically, another proposer can interleave its own higher ballot number in between the two phases, blocking any lower ballots. Two proposers can repeatedly block each other from progressing – effectively competing for acceptance. When proposers compete and block each other in this way, we say that they destructively interfere.
Destructive interference gets worse as more proposers propose their own ballots. The more concurrent proposers there are, the more likely it is that the system gets stuck repeatedly proposing. Even if none of the replicas have crashed or are unavailable, multiple proposers and misbehaving networks can block Paxos.
Formally, we say that Paxos does not guarantee liveness (i. e. , that proposals are eventually decided) without assuming that, at some point, all messages arrive within a bounded amount of time — an assumption known as partial synchrony.
To avoid multiple proposers constantly competing, most deployed consensus algorithms, like Raft, Multi-Paxos, and Viewstamped Replication, add a special leader proposer. The leader is the only replica that can make proposals. Centralizing the proposing power in one replica forces an order on concurrent requests, avoids competing proposals, and has the added benefit of getting decisions done in an optimal single network round-trip, instead of two.
While the leader is healthy and the network is well-behaved, leader-based protocols are fast.
Originally published at blog.cloudflare.com
