This article is a bit hard for me to grasp the main ideas of because, given Cloudflare's requirements (e.g. no strong leaders), it immediately seems like they should be comparing to leaderless protocols like Paxos-class algorithms. Comparing to Raft and saying it's better because Meerkat is leaderless is confusing, because Raft is an adjustment to Paxos to specifically have strong leaders. So I'm 3/4 the way into the article and I don't see what's unique here.
I think the unique idea here is supposed to be QuePaxa's idea of avoiding timeouts for ensuring liveness. The actual discussion of QuePaxa is limited to one paragraph at the end, and tbh only a couple sentences of that paragraph.
I feel like the article could've been titled "Consensus protocols and linearizability: a brief explainer", or "Paxos vs Raft", or similar. It just doesn't feel like it communicates what it claims to communicate, and is a bit confused on who its audience is, just IMO.
Worth noting if it wasn't obvious from the article that Cloudflare did not develop QuePaxa. It's from an SOSP paper back in 2023[0]. The article is discussing what is the first known large-scale public deployment of the protocol.
Right. But given that the entire point revolves around QuePaxa, it's strange to see no discussion on it. If that weren't the point, the article would be "Why Cloudflare implemented and deployed Paxos".
Which would also be a good read, but this article also isn't that. It doesn't discuss their experience deploying the protocol, aside from the following statement:
> 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.
I think it would've been more interesting to read why Cloudflare chose the specific algorithm they did, see an example of a pathological but common situation Cloudflare sees at their scale that makes other protocols unsuitable for them, therefore they made X choice and this led to Y gains in production (or on dummy workloads, or whatever). As it stands, there's nothing here actually specific to Cloudflare's workload or deployment. It doesn't even state their use-case beyond "small pieces of control plane state (e.g., leadership for replicated databases)"
But it's not a large-scale public deployment yet either. The article says towards the end that they just ran a proof of concept.
Maybe the blog post is just premature. It would be much more valuable if they posted it after actually having run it in production and validated the strengths and weaknesses with real world data.
Agreed on - it took a long time to get to the “so what is new here” vs the broader topic of distributed consensus. Stylistically would prefer more upfront “here is what is novel here”
The article lets itself down when it reveals it's had some marketing "polish" added: "where certain resources (like an AI model instance) are stored"
They could have picked something far more concrete (for Cloudflare's business and the type of services they deploy) than "AI model" there, which is clearly picked just to make it seem 'current' and on-trend.
That, or the model writing it already had "You are an AI model instance" sitting at the beginning of its context ready to pull from. Telling it it's an AI pushes it to make text about AI.
What's interesting here is that this would be the first production implementation of an asynchronous consensus algorithm (QuePaxa). Paxos, Raft, etc. are all partially synchronous, meaning they rely on timeouts and only make progress if message delay is sufficiently small compared to timeout durations. QuePaxa doesn't rely on timeouts and makes progress even under wild fluctuations in message delay. The question is whether performance is competitive enough in the normal case, when message delay is small and doesn't vary much, and historically the answer has been "no" and that's why asynchronous protocols weren't used.
Wasn't there an impossibility proof for consensus without timeouts? At the boundary between a consensus failure and success, there must be a certain message that, if you delay it enough, causes a consensus failure, and that implies either you wait forever for that message (deadlock) or you eventually give up waiting (timeout).
"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"
if youve ever fought a raft cluster on a bad network with leaders flapping, elections storming and latency spiking this genuinely doesnt seem that bad. i believe this will be very useful to those dealing with messy networks
This is really interesting. I wonder if etcd can benefit from this as it uses Raft for consensus and split-brain can be a problem depending on how its setup (usually when a Kubernetes control plane is initialized).
TBH I’m doubtful of most people building their own crypto libs and distributed consensus implementations. But maybe cloudflare can pull it off. Good to see them pushing the state of distributed consensus.
Take aways:
* it’s not in prod yet. I suspect those many round trips are going to get expensive on median aka typical redistributed deployments. Curious to see how it goes once in the wild.
* they say it isn’t likely suitable for eg databases.
* they talk about formal verification, which is good and feels appropriate.
There’s a weird yet common attitude that nobody has to implement operating systems, databases, compilers, cryptography, consensus algorithms, etc because you should use off the shelf solutions.
This is obviously true, and there are surely more web devs than, say, compiler engineers.
But then the logic seems to go as far as to imply nobody does or should be doing these things. Where do they think the “off the shelf” solutions came from?
I worked at <big internet tech company>, and many critical systems written in the 90’s and early 2000s used bespoke compilers, caches, and consensus protocols that were hand rolled by the original developers.
Back then, most of these ideas were already present in academia. But the industry tech wasn’t quite there yet to run these huge services at scale without running into problems (paying a vendor, licensing, the open source solution not quite there or tunable enough to easily integrate it at the needed scale, no company wide consensus on a shared approach yet).
A lot of these handwritten implementations eventually informed the “off the shelf industry solutions” we have today.
I think that’s what gets me down about tech these days. There’s a weird almost anti innovation attitude, which is the opposite of what made me fall in love with this profession. I’m not saying to hand roll a consensus algorithm at your next start up. But there’s definitely a vibe these days that any sort of theoretical, creative, or innovative thinking is suspect. Get back to selling ads!
I feel like it would be much better if the article focused on QuePaxa because IMHO it's an algorithm that finally brings some novel ideas to concensus (e.g. not relying on timeouts) by kinda coming at it from a gossip protocol angle and is not getting the attention it deserves. The post shouldn't have focused and introduced Meerkat which hasn't been fully developed and tried in production. If they clearly presented the pros and cons vs not just Raft (which is popular but doesn't even play in the same league because it is relies on a leader) but other leaderless or multi-leader concensus protocols that would have been of greater value. The Paxos family of algorithms are a much closer fit here and there's a reason why some serious large planet scale systems choose it over Raft.
E.g. 1. Intro about issues with concensus 2. Intro to QuePaxa 3. Comparison to other algos that are close to it 4. Mentioning active work on implementation via Meerkat and intent to bring to production with followup posts.
As always when it comes to concensus it's all about trade-offs. And with QuePaxa that might be the increase in messages (note: I don't mean message round-trips). We'll see how it goes but it will definitely be interesting.
Consensus is one of those areas where the interesting engineering and the number of
people who actually need it are inversely correlated. Most "we need distributed
coordination" turns out to be "we need one writer and a lock," which a single
Postgres hands you for free: advisory locks, SELECT ... FOR UPDATE, SKIP LOCKED for
work distribution. Linearizability without running Raft..
The real threshold is multi-region writes on a hard latency budget, and even then a
single-region primary plus accepting cross-region read latency beats eating a
consensus round-trip on every write for a lot of teams. Curious what workload pushed
you past single-primary - usually a better story than the impl itself.
Are you arguing that most teams that recognise a need for a distributed system chicken-out and use a single node instead, and if so, is that a good thing?
This article is a bit hard for me to grasp the main ideas of because, given Cloudflare's requirements (e.g. no strong leaders), it immediately seems like they should be comparing to leaderless protocols like Paxos-class algorithms. Comparing to Raft and saying it's better because Meerkat is leaderless is confusing, because Raft is an adjustment to Paxos to specifically have strong leaders. So I'm 3/4 the way into the article and I don't see what's unique here.
I think the unique idea here is supposed to be QuePaxa's idea of avoiding timeouts for ensuring liveness. The actual discussion of QuePaxa is limited to one paragraph at the end, and tbh only a couple sentences of that paragraph.
I feel like the article could've been titled "Consensus protocols and linearizability: a brief explainer", or "Paxos vs Raft", or similar. It just doesn't feel like it communicates what it claims to communicate, and is a bit confused on who its audience is, just IMO.
Worth noting if it wasn't obvious from the article that Cloudflare did not develop QuePaxa. It's from an SOSP paper back in 2023[0]. The article is discussing what is the first known large-scale public deployment of the protocol.
[0] https://dl.acm.org/doi/10.1145/3600006.3613150
Right. But given that the entire point revolves around QuePaxa, it's strange to see no discussion on it. If that weren't the point, the article would be "Why Cloudflare implemented and deployed Paxos".
Which would also be a good read, but this article also isn't that. It doesn't discuss their experience deploying the protocol, aside from the following statement:
> 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.
I think it would've been more interesting to read why Cloudflare chose the specific algorithm they did, see an example of a pathological but common situation Cloudflare sees at their scale that makes other protocols unsuitable for them, therefore they made X choice and this led to Y gains in production (or on dummy workloads, or whatever). As it stands, there's nothing here actually specific to Cloudflare's workload or deployment. It doesn't even state their use-case beyond "small pieces of control plane state (e.g., leadership for replicated databases)"
But it's not a large-scale public deployment yet either. The article says towards the end that they just ran a proof of concept.
Maybe the blog post is just premature. It would be much more valuable if they posted it after actually having run it in production and validated the strengths and weaknesses with real world data.
Agreed. When they describe the advantages over Raft, I can't help but read 'this is Paxos'.
Agreed on - it took a long time to get to the “so what is new here” vs the broader topic of distributed consensus. Stylistically would prefer more upfront “here is what is novel here”
It feels like somebody prompted an AI agent at CF "why Meerkat is better than Raft" when drafting this blog post.
Everyone cloudflare blog post that gets posted on here shares that quality now
The article lets itself down when it reveals it's had some marketing "polish" added: "where certain resources (like an AI model instance) are stored"
They could have picked something far more concrete (for Cloudflare's business and the type of services they deploy) than "AI model" there, which is clearly picked just to make it seem 'current' and on-trend.
That, or the model writing it already had "You are an AI model instance" sitting at the beginning of its context ready to pull from. Telling it it's an AI pushes it to make text about AI.
What's interesting here is that this would be the first production implementation of an asynchronous consensus algorithm (QuePaxa). Paxos, Raft, etc. are all partially synchronous, meaning they rely on timeouts and only make progress if message delay is sufficiently small compared to timeout durations. QuePaxa doesn't rely on timeouts and makes progress even under wild fluctuations in message delay. The question is whether performance is competitive enough in the normal case, when message delay is small and doesn't vary much, and historically the answer has been "no" and that's why asynchronous protocols weren't used.
Wasn't there an impossibility proof for consensus without timeouts? At the boundary between a consensus failure and success, there must be a certain message that, if you delay it enough, causes a consensus failure, and that implies either you wait forever for that message (deadlock) or you eventually give up waiting (timeout).
"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"
Interesting
This seems like something that would be great to open source; I can see it being a good building block for other globally distributed services.
if youve ever fought a raft cluster on a bad network with leaders flapping, elections storming and latency spiking this genuinely doesnt seem that bad. i believe this will be very useful to those dealing with messy networks
dumb guesses
1. I'd bet they either already do log-routed config, or simulation testing finds this race before production does.
2. The first part of Meerkat that will need clocks for correctness will probably be stale local reads, not the core consensus protocol.
I imagine something akin to a bat signal that alerts Aphyr to these types of posts. Looking forward to the Jepsen write-up.
This is really interesting. I wonder if etcd can benefit from this as it uses Raft for consensus and split-brain can be a problem depending on how its setup (usually when a Kubernetes control plane is initialized).
Yeah, for real. etcd is one of the biggest limitations to Kubernetes in my opinion. I would love to have a region-agnostic Kubernetes cluster.
TBH I’m doubtful of most people building their own crypto libs and distributed consensus implementations. But maybe cloudflare can pull it off. Good to see them pushing the state of distributed consensus.
Take aways:
* it’s not in prod yet. I suspect those many round trips are going to get expensive on median aka typical redistributed deployments. Curious to see how it goes once in the wild.
* they say it isn’t likely suitable for eg databases.
* they talk about formal verification, which is good and feels appropriate.
Looking forward to seeing more!
> I’m doubtful of most people building their own crypto libs and distributed consensus implementations. But maybe cloudflare can pull it off.
Who else than Cloudflare (or similar company in expertise and size) would be a better fit to implement distributed consensus?
There’s a weird yet common attitude that nobody has to implement operating systems, databases, compilers, cryptography, consensus algorithms, etc because you should use off the shelf solutions.
This is obviously true, and there are surely more web devs than, say, compiler engineers.
But then the logic seems to go as far as to imply nobody does or should be doing these things. Where do they think the “off the shelf” solutions came from?
I worked at <big internet tech company>, and many critical systems written in the 90’s and early 2000s used bespoke compilers, caches, and consensus protocols that were hand rolled by the original developers.
Back then, most of these ideas were already present in academia. But the industry tech wasn’t quite there yet to run these huge services at scale without running into problems (paying a vendor, licensing, the open source solution not quite there or tunable enough to easily integrate it at the needed scale, no company wide consensus on a shared approach yet).
A lot of these handwritten implementations eventually informed the “off the shelf industry solutions” we have today.
I think that’s what gets me down about tech these days. There’s a weird almost anti innovation attitude, which is the opposite of what made me fall in love with this profession. I’m not saying to hand roll a consensus algorithm at your next start up. But there’s definitely a vibe these days that any sort of theoretical, creative, or innovative thinking is suspect. Get back to selling ads!
I predict we may be heading back to self implementations based off of papers since it is now cheaper to do so with AI coding agents.
Yeah they kinda suck and make mistakes right now, but tech only gets better.
It’s no different than 3D printing. Instead of cutting and joining a bunch of stock parts, you just print the desired part.
In the same way printing with plastic kinda sucks, the tech will improve. Now you can print in metal or in resin without supports.
The future will be take all the ideas from various off the shelf products but tightly integrate them together for my specific use case
Cloudflare did not develop QuePaxa, although I'm sure they did a lot of work to operationalize it. The original protocol is from a SOSP 2023 paper.
https://dl.acm.org/doi/10.1145/3600006.3613150
The parent's claim was that Cloudflare is _implementing_ QuePaxa, not developing it, for whatever it's worth.
I feel like it would be much better if the article focused on QuePaxa because IMHO it's an algorithm that finally brings some novel ideas to concensus (e.g. not relying on timeouts) by kinda coming at it from a gossip protocol angle and is not getting the attention it deserves. The post shouldn't have focused and introduced Meerkat which hasn't been fully developed and tried in production. If they clearly presented the pros and cons vs not just Raft (which is popular but doesn't even play in the same league because it is relies on a leader) but other leaderless or multi-leader concensus protocols that would have been of greater value. The Paxos family of algorithms are a much closer fit here and there's a reason why some serious large planet scale systems choose it over Raft.
E.g. 1. Intro about issues with concensus 2. Intro to QuePaxa 3. Comparison to other algos that are close to it 4. Mentioning active work on implementation via Meerkat and intent to bring to production with followup posts.
As always when it comes to concensus it's all about trade-offs. And with QuePaxa that might be the increase in messages (note: I don't mean message round-trips). We'll see how it goes but it will definitely be interesting.
Illustrated with meercats looking in different directions.
2 out of 3 meerkats look in the same direction. Enough for consensus.
Can I run up some memecoins on it?
Consensus is one of those areas where the interesting engineering and the number of people who actually need it are inversely correlated. Most "we need distributed coordination" turns out to be "we need one writer and a lock," which a single Postgres hands you for free: advisory locks, SELECT ... FOR UPDATE, SKIP LOCKED for work distribution. Linearizability without running Raft..
The real threshold is multi-region writes on a hard latency budget, and even then a single-region primary plus accepting cross-region read latency beats eating a consensus round-trip on every write for a lot of teams. Curious what workload pushed you past single-primary - usually a better story than the impl itself.
Are you arguing that most teams that recognise a need for a distributed system chicken-out and use a single node instead, and if so, is that a good thing?
> Most "we need distributed coordination" turns out to be "we need one writer and a lock," which a single Postgres hands you for free
1. This article is about Cloudflare developing for their own internal control plane--I'm fairly certain their requirements preclude a single Postgres
2. Even if you're not Cloudflare, you may not want to be limited by the availability of a single Postgres instance.