Tag Archives: Meerkat

Choosing QuePaxa, an unusual consensus algorithm

Post Syndicated from João Pedro Leite original https://blog.cloudflare.com/choosing-quepaxa/

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.

The trade-off is that the leader must remain operational and reachable. When it fails, becomes too slow, or is disconnected from the cluster, the system stalls. The only solution is for the remaining replicas to detect that the leader has failed, and elect a new one in its place.

When leader recovery is unstable

When a leader fails, the system must recover by electing a new one. Interestingly, leader recovery is often how destructive interference sneaks right back into a leader-based system.

Consider Raft. For safety reasons, Raft elects a new leader using a majority vote. A replica that suspects that the leader has failed announces itself as a candidate for leadership and requests a vote from other replicas. If more than half of the replicas agree to vote for the candidate, it becomes the new leader. If they don’t, then a new election is called, and the candidates try again.

Multiple replicas can become candidates — all they need to do is detect that the leader is down. The candidates may then all try to acquire a majority vote simultaneously. The problem is that the candidates will compete for the majority vote, which means Raft’s elections suffer from the destructive interference we just saw in Paxos: two replicas can mutually prevent each other from getting support from a majority and becoming the leader. The more elections fail, the more replicas will try to get themselves elected leader.

Even if the leader stops being faulty, elections continue to disrupt what could have been normal system functioning. This is known as a metastable failure: a failure pattern that perpetuates itself even when the initial cause of failure is removed. A two-second network outage — or a momentarily faulty network switch — can make the leader appear to be faulty and force a leader election, which can fail, and force further elections. The outage will be over in two seconds, but the election can continue for much longer as candidates continue to block each other.

Ideally, consensus algorithms wouldn’t need any recovery process, as they are complicated, prone to interference, and introduce another source of downtime.

When fault detection goes awry

The problem of destructive interference in leader elections is compounded by trigger-happy fault-detection, especially in wide-area networks. In order for leader-based consensus algorithms to choose a new leader, replicas must first detect that the leader has failed. However, if replicas detect leader-failures inaccurately, the system may spend an inordinate amount of time in recovery, not handling requests.

In a distributed system, where machines are separated over a network, fault detection will ultimately depend on expectations. A process cannot directly observe that a remote process has failed; it can only observe that an expected message has or hasn’t arrived. We need a predictable pattern of communication, such as heartbeats or acknowledgements, to tell us that a machine is healthy. If an expected message does not arrive within the expected time, we suspect a fault. The difficulty lies in managing those expectations.

In real networks, especially wide-area networks, messages don’t always arrive when predicted. There is no guaranteed upper bound on the time that it takes for messages to arrive. That’s not to say that the network is slow, or that it is unreliable — most messages arrive within the time we expect them to. Instead, sudden bursts of latency and losses in connectivity can, momentarily, and without warning, increase the time it takes for any message to traverse the network. We call such networks asynchronous.

The big issue with asynchronous networks is that if some server doesn’t reply in a given amount of time, we don’t really know if the server has failed or if the network is just slow — the two are indistinguishable over the network. Any practical fault detector has to make a guess based on how long it has been waiting compared to its expectation, and sometimes that guess will be wrong.

In leader-based algorithms, that guess is exactly what triggers leader elections. Sometimes the leader is down; sometimes its messages are late, or the connection is silently broken. The protocol cannot know which one happened before it reacts. If the guess is wrong, and a replica thinks the leader is faulty when it actually isn’t, then an election begins and the entire system must stop. Until the leader is replaced, no progress is made — and as we just saw, that can take a while.

Fault detection is fundamentally error-prone in asynchronous networks, and when the detector makes a mistake, we get downtime.

When fault detection is slow

Even when a fault detector guesses correctly, there are issues. Fault detectors react to failures by observing messages on the network, and so their response time has to scale with network latency — the detector’s timeout can’t be below the network latency. This is why Raft is commonly deployed with an election timeout of five to ten times the network round-trip time. It has to be high enough to give a chance for the leader to signal that it is alive, and avoid falsely triggering elections. The election timeout can be much lower than that, but since leader elections completely stop the system, timeouts are usually set conservatively high.

Roughly speaking, a round trip halfway across the world is measured in hundreds of milliseconds. If an election timeout is several round trips, detecting a failed coordinator can take around a second. Even when fault detection is completely accurate, it is slow, and it is slowest in high-latency global networks. Until the detector reacts, the system is down.

Why QuePaxa is the right fit

We realized that any algorithm relying on a strict leader or accurate timeouts was inevitably going to stall in a consensus system that runs over the Internet. We searched for consensus algorithms designed for asynchronous environments — protocols that didn't rely on a well-behaved network or precise timing to function. This led us to QuePaxa, published in 2023 by Tennage & Băsescu et al.

The most notable thing about QuePaxa is how it can efficiently reach consensus in a single round trip under favorable network conditions, but also gracefully degrades performance during latency spikes, connectivity issues, and server failures. QuePaxa achieves this by solving the exact problems we just discussed through three key design choices: having an optional leader, completely removing the reliance on fault detection, and designing for constructive interference between proposers.

In QuePaxa, much like in Paxos, there are two roles: proposers and recorders. Proposers submit proposals to be decided on, and recorders serve as intermediaries between proposers, recording every proposal they see.

Instead of having proposers compete to get their own proposals decided, in QuePaxa, proposers will cooperatively work towards a proposal that everyone supports. QuePaxa does this by assigning a priority to proposals, in the form of a random number. The optional leader gets an exclusive maximum priority. During execution, proposers submit their proposals to the recorders, who propagate the proposal to other active proposers. When proposers receive a proposal from a recorder with a higher priority than theirs, they adopt the new proposal as their own, i.e., begin broadcasting the higher priority proposal instead. In general, proposers in QuePaxa work together to decide on the highest priority proposal that they collectively know. This means proposers can’t lock each other out of deciding on a proposal, indefinitely.

The caveat is that it might not be possible to spread proposals around well enough to agree on a proposal, and so proposers have to try again, with each attempt constituting a round. However, as more proposers submit proposals, the more likely they are to converge on the highest priority proposal. This is what makes QuePaxa a randomized algorithm: the randomly generated priorities of non-leader proposers are likely — but not guaranteed — to lead to consensus on the highest known priority, in a round. Yet, given enough rounds, it is guaranteed that proposers agree on a proposal.

One proposer is designated the leader. The leader is the only proposer capable of deciding in a single round trip. The leader always proposes with the highest priority; if the leader knows it spread its proposal before any other proposer, then it can decide immediately. Clients aren’t forced to make requests to the leader — any proposer can propose. If the leader goes down, then clients can keep making requests to other proposers. The leader is completely optional. The leader is simply more likely to decide, than any other proposer, and do so faster, in a single round trip.

However, because the leader is the only one that can decide in a single round trip, we want to use it whenever possible. To exploit this fast path without creating a single point of failure, clients sending proposals to the system hedge their bets: they send their requests for proposals to every replica, and the non-leader replicas will wait for a small timeout, so the leader can propose and decide on its own. In our own implementation of QuePaxa, we actually deviate from the paper and have clients wait the hedge timeout instead of the replicas, to reduce the amount of messages we send over the network, but the overall result is the same.

This hedging timeout is very different from the timeouts used in Raft or Multi-Paxos. It is not fault detection, and so isn’t constrained by network latency; it is locally determined by replicas and can be as small as they want it to be. In Raft, having a five-millisecond timeout in a network with 100-millisecond latency would completely freeze the system. But in QuePaxa, a five-millisecond hedge timeout only increases the number of active proposers.

However, hedging isn’t free: the more proposers there are, the more proposals get broadcast, and the more likely it is that replicas fail to decide in a round. Instead, hedging provides a tradeoff: we can react faster to leader changes by lowering the hedge timeout, but we incur extra bandwidth costs and may take more time to decide. That’s a tradeoff we're more than willing to make.

If the QuePaxa leader goes down, we can recover as fast as we want — we’re not bound by network latency. This is how QuePaxa gets around fault detection: since anyone can propose, not just the leader, QuePaxa can proactively deal with leader failures by hedging, rather than reacting to failures.

How QuePaxa works under the hood

To understand how QuePaxa gives us all of these nice properties, let’s look at how QuePaxa actually works.  

QuePaxa works in rounds made up of four phases. If a proposal hasn’t been decided on in the last phase, a new round is started, and QuePaxa starts over. At the start of each phase, proposers broadcast their currently adopted proposal to all recorders. Once a proposer receives a reply from a majority of recorders, they advance to the next phase. Here’s the general outline of the phases:

  • Phase 0 (Propose and Adopt): Proposers randomly select a priority, send their proposals to recorders, and adopt the highest-priority proposal they receive from a majority of recorders. If it’s the first round and the leader knows its proposal reached a majority of recorders first, the leader decides immediately.
  • Phase 1 (Spread): Proposers spread their adopted proposal to a majority of recorders.
  • Phase 2 (Check and Decide): Proposers ask a majority of recorders for the highest-priority proposal seen in the previous phase. If it matches their own adopted proposal, they decide on it.
  • Phase 3 (Carry Forward): Any proposer that failed to decide prepares for the next round by adopting the best proposal they see from a majority of recorders.

Let’s walk through a couple of example executions and unpack how each phase contributes to the overall behavior we want out of QuePaxa. Each execution will have two proposers (one of which is the leader) and three recorders.

The Leader Fast Path (Phase 0): The first phase does three important things: it randomizes priorities (which it must do to circumvent the FLP impossibility theorem), checks if the leader reached a majority of support first, and helps proposers converge if the leader didn't. The leader’s proposal is not randomized, and will always have the highest possible priority.

In the example above, the leader's proposal reaches a majority of recorders before anyone else, and receives replies confirming it. The leader can safely decide right away. This might seem dangerous, but it is entirely safe thanks to a property called majority intersection: any two majorities of recorders always share at least one recorder. Because the leader reached a majority, any other proposer querying a majority will inevitably encounter the leader's proposal and adopt it. Since the leader’s proposal has the highest priority, any other proposer will adopt the leader’s proposal. It is impossible to decide on any other proposal.

Concurrent Slow Path (Phases 0-3): When there are concurrent proposers, however, it is not guaranteed that the leader will immediately decide. The leader might fail to reach a majority of recorders first, or it might receive a single reply supporting another proposer. Let's look at what happens when another proposer contests the leader.

Phase 0: Pictured below, a second proposer (shown in red) reaches the second and third recorders first. The fast path is blocked. Instead of competing, proposers adopt the highest-priority proposal they receive from a majority and move to the second phase. The two proposers could both converge to the leader’s proposal in this phase. For illustrative purposes, our example will prevent convergence by delaying the leader’s messages.  

Phase 1: Proposers spread the proposal they just adopted in Phase 0 to a majority of recorders. The recorders keep track of the highest-priority proposal they observe. It is a simple but critical step: it prevents the protocol from later deciding on a lower-priority proposal. This is once again thanks to majority intersection: any majority queried in the following phase must include at least one recorder that saw the adopted proposal, in this phase. For illustrative purposes, we prevent convergence in this phase by delaying the leader’s message to the third recorder, so the recorder does not adopt the leader’s proposal.

Phase 2: Now, a decision can happen. Each proposer determines if a higher-priority proposal gained enough support to overtake its own by asking a majority of recorders for the highest-priority proposal observed during Phase 1. If the highest proposal returned is still their adopted proposal, they decide. In our diagram, the leader sees its own proposal returned by a majority and safely decides. The other proposer receives conflicting summaries, so it cannot decide yet. Like in Phase 1, recorders keep track of the highest priority proposal they received.

Phase 3: If a proposer doesn’t decide in Phase 2, it moves to the final cleanup phase to prepare for the next round. Proposers spread their proposals again and adopt the best they find among a majority of recorders. Here, the remaining proposer discovers the decided proposal and adopts it, heading into the next round.

This is deliberate — if there was some decision in the previous phase, then a majority of the recorders will have that proposal, and any remaining proposers are guaranteed to adopt it. We see here another instance of cooperation between proposers — even when a round fails, proposers try to converge on the same proposal heading into the next round.

Moving to the next round:  After the fourth phase, proposers move on to the next round. At this point, there is no more leader fast path, and the only way to decide is by converging in the third phase. Importantly, due to proposal adoption, it becomes exponentially easier to decide as rounds progress. The QuePaxa paper predicts that each round has a 50% chance of deciding, but in practice, that probability is much higher, thanks to convergence.

Putting all four phases together, we can see where QuePaxa gets its resilience. The first phase gives the leader its one-round-trip fast path. If that fast path fails, random priorities and proposal adoption help proposers converge instead of compete. The second and third phases make it safe to decide, thanks to majority intersection, while the fourth carries what proposers learned into the next round, in case proposers don’t decide.

No proposer has to detect that the leader has failed before making progress, and a failed round doesn’t throw away the work already done. When the network behaves, QuePaxa is fast. When it doesn’t, QuePaxa keeps moving.

How QuePaxa makes Meerkat possible

In our own evaluations of Meerkat, where we had servers spanning nearly all continents, we’ve directly experienced the impact that QuePaxa has on the overall performance and availability of the system. Meerkat continuously processes requests, even when the leader crashes, disconnects, or just becomes slow. At no point have we ever seen it completely stall. This is exactly what we wanted.

The rate at which Meerkat handles requests has also been generally predictable. Most decisions — upwards of 95% — are made by the leader in the first phase, which keeps our throughput fairly stable. In the instances where a decision isn't reached in the first phase, the throughput drops momentarily, down to at most a third of the usual rate, signaling that three round trips — so three phases — were needed to decide instead of just one. The system slows down, but does not grind to a halt.

QuePaxa also allows us to confidently switch out which replica acts as leader while the cluster is running. Since the leader isn’t the exclusive driver behind decisions and proposers are cooperative, a temporarily non-optimal leader isn’t as limiting as in other algorithms, where a leader misconfiguration could stall the system completely. We can dynamically tune which proposer is the leader without worrying too much about impacting the stability of a Meerkat cluster.

What we’ll be showing next

Designing Meerkat for a global network forced us to re-evaluate how we approach distributed consensus. Instead of sticking to familiar defaults that didn't quite fit our constraints, we looked to the decades of research produced by academia and industry. That search led us to QuePaxa.

Choosing QuePaxa meant choosing a less-traveled path. It has not been battle-tested as extensively as Raft or Paxos, and we’re also extending the original crash-stop design to support crash recovery. This demands careful engineering and stronger evidence of correctness than usual systems.

That is why we are formally verifying our QuePaxa implementation and Meerkat as a whole, alongside extensive simulation and fault-injection testing. Future posts in this series will explain how we verify Meerkat and QuePaxa’s Rust implementation, how we test failures that are difficult to reproduce in production, benchmarks, and what we have learned while turning an academic protocol into a production system.

Stay on the lookout for further Meerkat updates on the Cloudflare Blog, and if you want to learn more about research at Cloudflare, have a look at our work at Cloudflare Research.

Introducing Meerkat: an experiment in global consensus

Post Syndicated from James Larisch original https://blog.cloudflare.com/meerkat-introduction/

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: 

  1. x = x + 1

  2. 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.

Our desired fault tolerance properties are as follows:

First, the data system should remain available for writes and reads from a client located in any of our data centers as long as the following are true:

  1. A majority of the machines in our system are alive and can communicate with one another. (Formally, we tolerate f faults in a system of 2f + 1 machines).

  2. The client can contact any machine in the system that is connected to a majority of live machines.

This means that a single failed machine, or network degradation on a single link, does not affect availability of the system. This property is not provided by Raft-based systems, as we’ll see later.

Second, the data system remains correct as long as no actor in the system is actively malicious (and, of course, there are no bugs). We define correctness in terms of consensus safety later, but loosely speaking this means no two up-to-date machines will ever disagree about the world (e.g., one thinks that key1=1 while another thinks that key1=2).

To summarize, the system must remain correct even if machines crash, machines restart, networks fail or degrade, data centers go down, and more (though we, like Raft-based systems, do not handle Byzantine faults).

Introducing Meerkat

Meerkat is a consensus service upon which we can build applications that exhibit the above properties (strong consistency and fault tolerance) like a key-value (KV) store. To understand how Meerkat works, we first outline Meerkat’s general architecture, and then describe how Meerkat’s choice of consensus algorithm helps provide strong consistency and fault tolerance.

Developers of services using Meerkat request a cluster of Meerkat replicas. Each replica is connected to every other replica. Each replica participates in the consensus algorithm and can receive both reads and writes. The developer can specify which data centers are allowed to host their replicas, and Meerkat places them automatically.

To interact with their cluster, a developer’s client sends an application-specific request to any replica in the cluster. A single replica may host many kinds of applications, but the simplest one is a key-value store, so the simplest application-specific request type is a KV get or put. The replica responds to the request with an application-specific response (e.g., the records requested with the get). Note that KV reads (gets) are guaranteed to read up-to-date information.


Meerkat’s log

Under the hood, the replica translates application requests (e.g., get and put) into log events. hat replica distributes each log event to all other replicas using a consensus algorithm such that all replicas maintain the exact same log of events (in reality, a replica may lag behind, but shall never record different entries). These events are arbitrary — Meerkat’s core doesn’t care what’s in them. Meerkat applications care about log event contents. Each Meerkat replica “hosts” many Meerkat applications (e.g., key-value store) that read the log events and construct state. (Note that each replica belongs to exactly one cluster.)

For instance, the KV Meerkat application constructs an in-memory key-value store from the log events. So when a client sends a write like put k1 v1, the receiving replica places that write into a log event and distributes it to all replicas. If someone else subsequently writes put k1 v11 to a different replica, this event is also distributed to all replicas. Since all functioning replicas have the same log, those replicas can apply the operations in the log in sequence to construct the exact same state. Note that get requests also create distributed log events (for linearizability, as explained in the next section).

Here is an example of how a replica’s KV store is updated as it receives log events:


How Meerkat’s log enables strong consistency

Meerkat guarantees that if one client executes put k1 v1, a second client subsequently executes put k1 v11, and a third client subsequently executes get k1 (with a consistent read), they will always read v11. It guarantees this even if each request is submitted to a different replica, and those replicas are distributed randomly across the world. This is linearizability. To see how Meerkat guarantees this, we must examine Meerkat’s log in more detail.

The Meerkat log is a sequence of slots. A slot is a box that can contain an event or not. A slot that contains an event is called a decided slot. All slots in the log are decided except the last slot, which is currently being decided. One of Meerkat’s invariants is that if any two replicas decide on the value for a slot, those values are the same. In other words, no two replicas will ever disagree on the value of a decided slot (though one replica may think the last slot is empty while another does not). This property helps guarantee the desired properties we described in the previous section.

To decide on the value of the last (empty) slot in the log, Meerkat replicas run a distributed consensus algorithm. A consensus algorithm allows a set of machines communicating over a network to agree on a decided slot value. Our consensus algorithm works as long as a majority of replicas (more than half) are alive.

So if the log currently contains two entries, and a client submits put k1 v11 to a replica, that replica triggers a consensus algorithm for slot 3. But another client might have submitted put k1 v111 to a different replica for slot 3. The consensus algorithm ensures that only one such proposal for slot 3 wins out. Specifically, it ensures that at least a majority of replicas agree on the same proposal, deciding it for slot 3. The non-majority can never decide a different proposal, but might miss the fact that slot 3 has been decided at all. 


To see how this provides linearizability for our key-value store, consider a write followed by a read. One replica Z proposes put k1 v11 and this proposal is decided at slot 3 by a majority of replicas, but NOT replica Y. Subsequently, a reader executes get k1 on replica Y. Replica Y believes slot 3 is empty, so proposes get k1 at slot 3. Critically, a majority of replicas will not agree to place that event at slot 3, because that slot has already been decided. They will force replica Y to decide (by receiving older decisions) put k1 v11 in slot 3, and to propose get k1 for slot 4, thus linearizing the read after the write in the log. (And if that replica can’t contact a majority, it will be unable to complete the read.)

How Meerkat’s consensus algorithm provides higher availability than Raft

Deciding on log entries requires a distributed consensus algorithm. But which one? All valid consensus algorithms would provide the required consistency and correctness guarantees, but not all provide the same availability guarantees. 

Specifically, many algorithms that rely on authoritative leaders do not provide our desired availability guarantees, because they can become unavailable when a single machine experiences issues. Consider Raft, one of the most well-known and probably the most implemented consensus algorithm. Raft relies on an authoritative leader: the only replica in the cluster that can drive consensus. As a result, all writes get forwarded to the leader. This design choice helps make Raft “understandable” and, coupled with leases, can make leader-served reads automatically linearizable (since they’re guaranteed to be up-to-date). But it also adds a single point of (temporary) failure.

In general, there are two problems with authoritative leaders. First, if the leader goes down, the system becomes unavailable (all writes block) until a new leader is elected. This is unacceptable for Meerkat. Second, if the leader stays up but slows down, either because it is overloaded or there are network delays, then performance degrades. The leader is a bottleneck because there is no alternative way to perform writes. 

The first problem is exacerbated in wide-area networks. Consider that when a leader goes down, most algorithms choose a new leader using timeouts: if a non-leader replica hasn’t heard from the leader in some amount of time, they propose themselves as the leader. At that point, the old leader has been deposed, and the system cannot accept writes until a new leader has been elected. The problem is that when the timeout is shorter than the network delay between the original leader and that replica, replicas will constantly be timing out and thus blocking writes. And when the timeout is too long, the system reacts slowly to a failed leader, during which writes are also blocked. Plus, if multiple replicas propose themselves as leader at the same time, their “campaigns” can interfere with each other, causing them to constantly re-propose themselves as leader — all the while blocking writes. We have seen these exact issues with Cloudflare’s systems that use Raft because our wide-area network delays can and do vary wildly, making tuning timeouts especially difficult.

We chose a different consensus algorithm for Meerkat, called QuePaxa, that aims to avoid the “tyranny of timeouts” imposed by protocols like Raft. QuePaxa is a subtle protocol, but here are the highlights. A client can contact any replica, and that replica can drive consensus for the latest slot. There is a leader, but it is not required — its only advantage is that it can drive consensus with fewer round trips (one) than other replicas (3+). Critically, clients are free to contact multiple replicas concurrently for the same proposal, to increase the chance of the proposal being successful. Concurrent proposals do not destructively interfere:  replicas work together to decide one of the proposed values.

In short, QuePaxa has three advantages over Raft for our purposes:

  1. Because there is no required leader, the system never becomes unavailable or degraded due to a single replica (the leader) being down, unavailable, or degraded. Clients can perform writes as long as they can contact some healthy replica (anywhere in the world). 

  2. Because there is no leader, there are no leader elections that degrade the system. And concurrent proposals made by different replicas constructively interfere, unlike Raft’s leadership elections. This is ideal for Cloudflare’s network, in which latencies can vary wildly.

  3. QuePaxa was designed for a less reliable network environment (“asynchrony”), and for networks in which an imaginary adversary can launch targeted attacks on replica connections. The authors found that it maintains much higher (~10x) throughput than Raft and Multi-Paxos during such conditions. These conditions more accurately resemble our own network than the conditions other algorithms assume.

We will save the full description of QuePaxa for another post. Major shoutout to the authors of the QuePaxa paper from EPFL for being available for feedback and questions about their work.

Assessing Meerkat’s performance 

Meerkat has limitations. It is not designed to create general-purpose data systems like databases.

All consensus algorithms come with a cost: lots of round-trips. QuePaxa in particular takes one to three round trips (usually, although it can take more) between the initial proposer and a majority of replicas to decide on a proposal and add an event to the log. The difference is with the leader. It takes one if the leader is proposing (+ an extra broadcast to notify replicas of the decision) and three if a non-leader is proposing (+ extra broadcast). If multiple replicas make proposals at the same time, it can take more. These communication costs point to the important performance limitation of consensus algorithms in general: proposal decision latency is proportional to the latency between some majority of replicas. So if your replicas are far from one another, latency will increase — there’s no getting around that.

At first glance, it seems Meerkat’s write and read latency will be quite poor. Especially if all writes and reads (for consistency) must go through the log, and thus require so many round trips.

But there are a few ways to squeeze better performance out of Meerkat: 

  1. Because developers have control over where their replicas live, they can choose to move replicas closer together, reducing round-trip latency (only applicable for services that don’t need truly global distribution).

  2. Writes can be batched. So if a replica receives 10 writes in a span of 10ms, it can place all of those in a single proposal, improving throughput.

  3. Not all reads must trigger a consensus round. If a developer is OK with reading stale (but never inconsistent) data, they can read from any replica’s local data.

  4. Multiple operations can be bundled into a single consensus round. For instance, our key-value store supports compare-and-swap-style writes in which writes execute only if a value has not changed since it was read. (In fact, it supports general transactions.)

Still, Meerkat’s fundamental latency limitations remain, especially when it is run at global scale, as it was designed to do. These limitations make it perfect, in the short term, for control plane information that is written infrequently but must remain consistent.

What’s next

Meerkat is not deployed to production, but we have run multiple proofs-of-concept with up to 50 replicas distributed around the world, to great success. Leaders in our proof-of-concept clusters constantly fail, and the cluster keeps operating with no increase in error-rate.

We have a lot more to say about Meerkat. Over the course of the next year we’ll be writing Meerkat posts that discuss how QuePaxa really works, how we’re formally verifying some of our Rust implementation, how bootstrapping and cluster management works, how we find optimal replica placement, how we use deterministic simulation testing to find bugs, and more. We’ll also be preparing a manuscript for peer-review!

Follow along on the Cloudflare Blog as Meerkat progresses, and check out more of our projects at Cloudflare Research.