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
Looking at the implementation sketches, this algorithm looks even trickier to implement than Paxos (already a notoriously tricky algorithm to implement) and on top of that, I think the failure case in this algorithm is subtle and different -- very long tail latencies. In Paxos/Raft the latencies are more likely bounded by the timeouts (not eliminated of course) so you can build other systems to expect certain delays, but in this case, you may write something, wait for an ack, then abandon and retry, then realize the old write succeeded, etc. ad infinitum.
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 what its audience is, just IMO.
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!
There's a bimodal distribution of software developers where the lower set never touches the problems that the others deal with. The attitude of "nobody has to implement X" is one set of the distribution being wholly ignorant that the other set exists.
> This article is about Cloudflare developing for their own internal control plane--I'm fairly certain their requirements preclude a single Postgres.
True, but the article claims both strong consistency (sort of) and linearizability; that is basically a serializable writer and a lock; if I read correctly (I haven't read all the details), the article conflates both; afaik it is possible to have linearizability with eventual consistency; algorithms so solve concurrent writes and having multiple writers in raft is a "solved problem". sad to see such a spotty article on such important topic by a major company, even if the underlying paper is strong. This feels like manure.
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?
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.
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).
"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"
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).
It's impossible to do it deterministically (that's the famous FLP impossibility result), but if you accept to have liveness only with probability 1 then it's possible (for example, an early randomized asynchronous protocol is Ben-Or's protocol from 1983).
This sounds like a very direct approach to linearizability - just put everything in a linear order.
But this includes READ operations too! You have to get global consensus for every read! Most distributed systems have additional complexity and latency on write paths so that reads can be completely local. If you can accept slow read operations this seems like a great trade off, but I think that is going to relegate this to niece usage.
The system seems to have no master or leader at all. Where in the article did you get that reads from a master have no consensus?
Of course, you could build database that uses meerkat to do leader election, and then neither reads nor writes need to go through the consensus algo. But then you've basically just reproduced conventional distributed db, and you're back to the timeout problems this was supposed to solve.
> 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.
Kind of a crap article that doesn't (1) link to the code (or to the golang implementation from the paper) and (2) doesn't even have the word "CAP" in it.
It doesn't mention CAP because it's obviously opting for consistency over availability, and is explicitly compared next to other systems that treat consistency as paramount. There's nothing interesting or new about it's approach to CAP.
47 comments
[ 0.23 ms ] story [ 49.4 ms ] threadI 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 what its audience is, just IMO.
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!
Who else than Cloudflare (or similar company in expertise and size) would be a better fit to implement distributed consensus?
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!
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
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.
True, but the article claims both strong consistency (sort of) and linearizability; that is basically a serializable writer and a lock; if I read correctly (I haven't read all the details), the article conflates both; afaik it is possible to have linearizability with eventual consistency; algorithms so solve concurrent writes and having multiple writers in raft is a "solved problem". sad to see such a spotty article on such important topic by a major company, even if the underlying paper is strong. This feels like manure.
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.
https://docs.cloud.google.com/kubernetes-engine/docs/concept...
https://cloud.google.com/blog/products/containers-kubernetes...
Interesting
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.
But this includes READ operations too! You have to get global consensus for every read! Most distributed systems have additional complexity and latency on write paths so that reads can be completely local. If you can accept slow read operations this seems like a great trade off, but I think that is going to relegate this to niece usage.
Of course, you could build database that uses meerkat to do leader election, and then neither reads nor writes need to go through the consensus algo. But then you've basically just reproduced conventional distributed db, and you're back to the timeout problems this was supposed to solve.