Maelstrom [1], a workbench for learning distributed systems from the creator of Jepsen, includes a simple (model-checked) implementation of Raft and an excellent tutorial on implementing it.<p>Raft is a simple algorithm, but as others have noted, the original paper includes many correctness details often brushed over in toy implementations. Furthermore, the fallibility of real-world hardware (handling memory/disk corruption and grey failures), the requirements of real-world systems with tight latency SLAs, and a need for things like flexible quorum/dynamic cluster membership make implementing it for production a long and daunting task. The commit history of etcd and hashicorp/raft, likely the two most battle-tested open source implementations of raft that still surface correctness bugs on the regular tell you all you need to know.<p>The tigerbeetle team talks in detail about the real-world aspects of distributed systems on imperfect hardware/non-abstracted system models, and why they chose viewstamp replication, which predates Paxos but looks more like Raft.<p>[1]: <a href="https://github.com/jepsen-io/maelstrom/">https://github.com/jepsen-io/maelstrom/</a><p>[2]: <a href="https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DESIGN.md">https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...</a>
I had a fun time recently implementing Raft leader election and log replication (i.e. I didn't get to snapshotting/checkpointing). One of the most challenging projects I've tried to do.<p>The Raft paper is very gentle to read, and gives you a great intuition on its own. Even if you don't want to implement it, you probably use software that uses it: like etcd or consul or cockroach or tidb, etc.<p>I collected all the resources I found useful while doing it here: <a href="https://github.com/eatonphil/goraft#references">https://github.com/eatonphil/goraft#references</a>. This includes Diego Ongaro's thesis and his TLA+ spec.<p>Some people say Figure 2 of the Raft paper has everything you need but I'm pretty sure that's just not true. It's a little bit more vague than looking at the TLA+ spec to me anyway.
If you're interested in consensus algorithms, you might be interested in this book that I used in a theoretical course on distributed system called "Reasoning about Knowledge" (<a href="https://mitpress.mit.edu/9780262562003/reasoning-about-knowledge/" rel="nofollow noreferrer">https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...</a>).<p>You have to invest a bit in learning about modal logic, but once you do get past that part, this book provides proofs of why things like Raft or Paxos work that are super intuitive and straightforward. Basically pushing the complexity of proving these algorithms into the logic structure used to form the proof (in an intuitive way). Highly recommend, changed how I think about consensus!
If anyone else doesn't understand what the visualisation is supposed to show, note that you can click on one of the nodes and make them fail. Particularly try this with the current "leader" (the thing that's sending and receiving all the packets). Press the little pause icon next to the first slider to turn it back into a clock and resume the simulation.<p>Has someone else figured out what the spreadsheet on the right is? It looks broken to me (but so I thought the rest of the simulation was before understanding that it only shows the happy flow by default), as it always remains empty. The clickable elements I discovered so far are the two sliders, the clock/pause icon, and the individual servers.
The last time I was working in a setting where a rock-solid Chubby-alike under serious load was constantly top of mind was some years ago, and at that time you used ZK if failure wasn’t an option.<p>But AFAIK people have been putting heavy, heavy work on Raft-based options like etcd and Consul and others for many years now.<p>Is one of those systems like the new best default? Certainly the conceptual clarity and elegance of Raft seem like things that would show up in performance and reliability, but I’m just dated on this.<p>What are people (who aren’t at Google or married to GCP) using as the best practices default when the stakes are high in 2023?<p>I think there’s a production-grade Rust implementation of Raft from IIRC TikV, and a rock-solid, high performance lock server seems squarely in the sweet spot for Rust. Are people using that?
Here is their answer to their own question - "What is Raft?"<p>>Raft is a consensus algorithm that is designed to be easy to understand. It's equivalent to Paxos in fault-tolerance and performance. The difference is that it's decomposed into relatively independent subproblems, and it cleanly addresses all major pieces needed for practical systems. We hope Raft will make consensus available to a wider audience, and that this wider audience will be able to develop a variety of higher quality consensus-based systems than are available today.<p>After reading that I still have no idea. They are not alone in doing this, but I think its a shame that people don't spend the extra time and effort in properly describing their work.
Consensus protocol researcher here. For what it’s worth, I think that the plethora of blockchain research in the last 10 years has made consensus much easier to understand. Raft (in particular, with all of its subtleties) reads (and implements) like Greek in comparison.<p>For a new beginner to consensus protocols, today, I would start them with Bitcoin, and then move onto Paxos/Tendermint/Simplex, and skip Raft entirely. (Simplex is my paper, a simplified version of PBFT).
I love this site. When I was learning & implementing raft in my distributed systems course, this page was invaluable. Plus the paper itself is pretty easy to read.
Are there consensus algorithms that don't require changes go through a leader? In many distributed systems, you want to distribute intake as well.
When I was studying the Raft algorithm a year and a half ago, I found this video on it by John Ousterhout to be a good complement:<p>Designing for Understandability: The Raft Consensus Algorithm<p><a href="https://www.youtube.com/watch?v=vYp4LYbnnW8">https://www.youtube.com/watch?v=vYp4LYbnnW8</a>
> Raft is a consensus algorithm that is designed to be easy to understand.<p>> Consensus typically arises in the context of replicated state machines, a general approach to building fault-tolerant systems.<p>I recognize that I'm not the intended audience but I do think I would be a lot more capable of understanding this article if it used less jargon or at least defined what it meant. I'm only mentioning this because ease of understanding is an explicit goal.<p>Can someone give a real world example of where this would be used in a production app? I'm sure it's very practical but I'm getting caught up in trying to understand what it's saying
I've written a whole SQLite replication system that works on top of RAFT ( <a href="https://github.com/maxpert/marmot">https://github.com/maxpert/marmot</a> ). Best part is RAFT has a well understood and strong library ecosystem as well. I started of with libraries and when I noticed I am reimplementing distributed streams, I just took off the shelf implementation (<a href="https://docs.nats.io/nats-concepts/jetstream" rel="nofollow noreferrer">https://docs.nats.io/nats-concepts/jetstream</a>) and embedded it in system. I love the simplicity and reasoning that comes with RAFT. However I am playing with epaxos these days (<a href="https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf" rel="nofollow noreferrer">https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf</a>), because then I can truly decentralize the implementation for truly masterless implementation. Right now I've added sharding mechanism on various streams so that in high load cases masters can be distributed across nodes too.
It's a shame many undergraduate CS curricula are allergic to distributed systems and type systems.<p>Even the grad program I was looking at is hot dog water.<p>I've been playing with raft and paxos. Employers will not care as these were learned out-of-band from degree mills.
Is Raft byzantine-fault-tolerant though? Can it be made so?<p>Paxos can: <a href="http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzant...</a>
I took a crack at finding the interesting past related threads. Any others?<p>(I've left out posts about particular implementations, extensions, and so on—there are too many. The intention is threads about the algorithm itself.)<p><i>Raft Is So Fetch: The Raft Consensus Algorithm Explained Through Mean Girls</i> - <a href="https://news.ycombinator.com/item?id=33071069">https://news.ycombinator.com/item?id=33071069</a> - Oct 2022 (53 comments)<p><i>Raft Consensus Animated (2014)</i> - <a href="https://news.ycombinator.com/item?id=32484584">https://news.ycombinator.com/item?id=32484584</a> - Aug 2022 (67 comments)<p><i>Why use Paxos instead of Raft?</i> - <a href="https://news.ycombinator.com/item?id=32467962">https://news.ycombinator.com/item?id=32467962</a> - Aug 2022 (45 comments)<p><i>In Search of an Understandable Consensus Algorithm (2014) [pdf]</i> - <a href="https://news.ycombinator.com/item?id=29837995">https://news.ycombinator.com/item?id=29837995</a> - Jan 2022 (12 comments)<p><i>Raft Consensus Protocol</i> - <a href="https://news.ycombinator.com/item?id=29079079">https://news.ycombinator.com/item?id=29079079</a> - Nov 2021 (51 comments)<p><i>Paxos vs. Raft: Have we reached consensus on distributed consensus?</i> - <a href="https://news.ycombinator.com/item?id=27831576">https://news.ycombinator.com/item?id=27831576</a> - July 2021 (48 comments)<p><i>Raft Visualization</i> - <a href="https://news.ycombinator.com/item?id=25326645">https://news.ycombinator.com/item?id=25326645</a> - Dec 2020 (35 comments)<p><i>Raft: A Fantastical and Absurd Exploration</i> - <a href="https://news.ycombinator.com/item?id=23129707">https://news.ycombinator.com/item?id=23129707</a> - May 2020 (1 comment)<p><i>Understanding Raft Consensus</i> - <a href="https://news.ycombinator.com/item?id=23128787">https://news.ycombinator.com/item?id=23128787</a> - May 2020 (3 comments)<p><i>In Search of an Understandable Consensus Algorithm (2014) [pdf]</i> - <a href="https://news.ycombinator.com/item?id=23113419">https://news.ycombinator.com/item?id=23113419</a> - May 2020 (26 comments)<p><i>Paxos vs. Raft: Have we reached consensus on distributed consensus?</i> - <a href="https://news.ycombinator.com/item?id=22994420">https://news.ycombinator.com/item?id=22994420</a> - April 2020 (65 comments)<p><i>Raft Is So Fetch: The Raft Consensus Algorithm Explained Through Mean Girls</i> - <a href="https://news.ycombinator.com/item?id=22520040">https://news.ycombinator.com/item?id=22520040</a> - March 2020 (4 comments)<p><i>Implementing Raft: Part 2: Commands and Log Replication</i> - <a href="https://news.ycombinator.com/item?id=22451959">https://news.ycombinator.com/item?id=22451959</a> - Feb 2020 (16 comments)<p><i>Building a Large-Scale Distributed Storage System Based on Raft</i> - <a href="https://news.ycombinator.com/item?id=21447528">https://news.ycombinator.com/item?id=21447528</a> - Nov 2019 (5 comments)<p><i>In Search of an Understandable Consensus Algorithm [pdf]</i> - <a href="https://news.ycombinator.com/item?id=14724883">https://news.ycombinator.com/item?id=14724883</a> - July 2017 (14 comments)<p><i>Instructors' Guide to Raft</i> - <a href="https://news.ycombinator.com/item?id=11300428">https://news.ycombinator.com/item?id=11300428</a> - March 2016 (3 comments)<p><i>Fuzzing Raft for Fun and Publication</i> - <a href="https://news.ycombinator.com/item?id=10432062">https://news.ycombinator.com/item?id=10432062</a> - Oct 2015 (10 comments)<p><i>Prove Raft Correct</i> - <a href="https://news.ycombinator.com/item?id=10017549">https://news.ycombinator.com/item?id=10017549</a> - Aug 2015 (27 comments)<p><i>Scaling Raft</i> - <a href="https://news.ycombinator.com/item?id=9725094">https://news.ycombinator.com/item?id=9725094</a> - June 2015 (12 comments)<p><i>Raft Consensus Algorithm</i> - <a href="https://news.ycombinator.com/item?id=9613493">https://news.ycombinator.com/item?id=9613493</a> - May 2015 (24 comments)<p><i>Creator of Raft is speaking at our meetup. What questions do you want answered?</i> - <a href="https://news.ycombinator.com/item?id=9351794">https://news.ycombinator.com/item?id=9351794</a> - April 2015 (6 comments)<p><i>Replicating SQLite using Raft Consensus</i> - <a href="https://news.ycombinator.com/item?id=9092110">https://news.ycombinator.com/item?id=9092110</a> - Feb 2015 (21 comments)<p><i>Raft Refloated: Do We Have Consensus? [pdf]</i> - <a href="https://news.ycombinator.com/item?id=9015085">https://news.ycombinator.com/item?id=9015085</a> - Feb 2015 (4 comments)<p><i>Analysis of Raft Consensus [pdf]</i> - <a href="https://news.ycombinator.com/item?id=8736868">https://news.ycombinator.com/item?id=8736868</a> - Dec 2014 (3 comments)<p><i>The Raft Consensus Algorithm</i> - <a href="https://news.ycombinator.com/item?id=8527440">https://news.ycombinator.com/item?id=8527440</a> - Oct 2014 (27 comments)<p><i>Raft: Understandable Distributed Consensus</i> - <a href="https://news.ycombinator.com/item?id=8271957">https://news.ycombinator.com/item?id=8271957</a> - Sept 2014 (79 comments)<p><i>Raft - The Understandable Distributed Protocol</i> - <a href="https://news.ycombinator.com/item?id=6859101">https://news.ycombinator.com/item?id=6859101</a> - Dec 2013 (10 comments)<p><i>Raft, a scrutable successor to Paxos</i> - <a href="https://news.ycombinator.com/item?id=5624627">https://news.ycombinator.com/item?id=5624627</a> - April 2013 (2 comments)
Obligatory plug: <a href="http://nil.csail.mit.edu/6.824/2022/schedule.html" rel="nofollow noreferrer">http://nil.csail.mit.edu/6.824/2022/schedule.html</a><p>MIT Distributed Systems course where Raft is implemented as a class assignment (assignment 2). The test suite around the assignment is incredibly valuable and !will! find bugs in your Raft implementation. The assignment is broken up into distinct steps to help people not get stuck when doing everything at once. It is still very challenging to implement everything, especially to get the performance tests to pass.