Raft: Understandable Distributed Consensus (2014)

I am in the minority who thinks Raft is overrated.<p>I tried teaching Raft one year instead of Paxos but ended up switching back. While it was much easier to understand how to implement Raft, I think my students gained deeper insight when focusing on single-decision Paxos. There is a lightbulb moment when they first understand that consensus is a property of the system that happens first (and they can point at the moment it happens) and then the nodes discover that it has been achieved later. Exploring various failure modes and coming to understand how Paxos is robust against them seems to work better in this setting as well.<p>I think this paper by Heidi Howard and Richard Mortier is a great way to move on to Multipaxos:<p><a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;2004.05074" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;2004.05074</a><p>They present Multipaxos in a similar style to how Raft is laid out and show that Multipaxos as it is commonly implemented and Raft are almost the same protocol.<p>Raft was a great contribution to the engineering community to make implementing consensus more approachable, but in the end I don&#x27;t think the protocol itself is actually more understandable. It was presented better for implementers, but the implementation focus obscures some of the deep insights that plain Paxos exposes.

Author here. I&#x27;m happy to answer any questions although this project was from 10+ years ago so I could be a little rusty.<p>Over the years I&#x27;ve been trying to find better ways to do this kind of visualization but for other CS topics. Moving to video is the most realistic option but using something like After Effects takes A LOT of time and energy for long-form visualizations. It also doesn&#x27;t produce a readable output file format that could be shared, diff&#x27;d, &amp; tweaked.<p>I spent some time on a project recently to build out an SVG-based video generation tool that can use a sidecar file for defining animations. It&#x27;s still a work in progress but hopefully I can get it to a place where making this style of visualizations isn&#x27;t so time intensive.

This is one of my favorite pieces of software engineering because it took something difficult and tried to design something easy to understand as a main criteria for success. The PHD Thesis has a lot more info about this if anyone is curious, it is approachable and easy to read:<p><a href="https:&#x2F;&#x2F;web.stanford.edu&#x2F;~ouster&#x2F;cgi-bin&#x2F;papers&#x2F;OngaroPhD.pdf" rel="nofollow">https:&#x2F;&#x2F;web.stanford.edu&#x2F;~ouster&#x2F;cgi-bin&#x2F;papers&#x2F;OngaroPhD.pd...</a><p>I think this was core to Raft’s success, and I strive to create systems like this with understandability as a first goal.

I&#x27;ve run a reading group for distributed systems for the last 2 years now and I do think that Raft is a better introduction to Consensus than any Paxos paper I have seen (I mean the Paxos Made Simple paper literally has bugs in it). But when I learned consensus in school, we used Paxos and Multi-Paxos and I do believe that there was a lot to be gained by learning both approaches.<p>Heidi Howard has several amazing papers about how the differences between Raft and Multi-Paxos are very surface level and that Raft&#x27;s key contribution is its presentation as well as being a more &quot;complete&quot; presentation since there are so many fragmented different presentations of Multi-Paxos.<p>As a bonus, one of my favorite papers I have read recently is Compartmentalized Paxos: <a href="https:&#x2F;&#x2F;vldb.org&#x2F;pvldb&#x2F;vol14&#x2F;p2203-whittaker.pdf" rel="nofollow">https:&#x2F;&#x2F;vldb.org&#x2F;pvldb&#x2F;vol14&#x2F;p2203-whittaker.pdf</a> which is just a brilliant piece on how to scale Multi-Paxos

In case this is of interest, MIT&#x27;s 6.5840[0], distributed systems, has a series of labs, implementing Raft in Go. Haven&#x27;t made it through the whole thing yet, but it&#x27;s quite entertaining so far.<p>The teachers provide you with some code templates, a bunch of tests, and a progressive way to implement it all.<p>[0]: <a href="https:&#x2F;&#x2F;pdos.csail.mit.edu&#x2F;6.824&#x2F;index.html" rel="nofollow">https:&#x2F;&#x2F;pdos.csail.mit.edu&#x2F;6.824&#x2F;index.html</a>

I was asked to click &quot;continue&quot; after each of the first two sentences, and the fade-in of the text took longer than reading the text.<p>This may be a great article, but I&#x27;ll never know because it&#x27;s frustrating to try and read.

Related:<p><i>Raft Consensus Animated (2014)</i> - <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=32484584">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=32484584</a> - Aug 2022 (67 comments)<p><i>Raft Visualization</i> - <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=25326645">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=25326645</a> - Dec 2020 (35 comments)<p><i>Raft: Understandable Distributed Consensus</i> - <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=8271957">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=8271957</a> - Sept 2014 (79 comments)

Ben&#x27;s visualization here is great.<p>The other biggest help to me aside from the paper and the thesis was Ongaro&#x27;s TLA+ spec: <a href="https:&#x2F;&#x2F;github.com&#x2F;ongardie&#x2F;raft.tla&#x2F;blob&#x2F;master&#x2F;raft.tla">https:&#x2F;&#x2F;github.com&#x2F;ongardie&#x2F;raft.tla&#x2F;blob&#x2F;master&#x2F;raft.tla</a>. It&#x27;s the only super concise &quot;implementation&quot; I found that is free of production-grade tricks, optimizations, and abstractions.<p>And for building an intuition, TigerBeetle&#x27;s sim.tigerbeetle.com is great. What happens to consensus when there&#x27;s high latency to disk or network? Or as processes crash more frequently? It demonstrates.

The writing and the visualizations are great. The ‘continue’ button is way too frequent.

In the log replication example, after healing the partition the uncommitted log changes in the minority group are rolled back and the leader&#x27;s log is used.<p>However it&#x27;s not clear how that log is transmitted. Until this point only heartbeats via append entry were discussed, so it&#x27;s not clear if the followers pull that information from the leader somehow via a different mechanism, or whether it&#x27;s the leader&#x27;s responsibility to detect followers that are left behind and replay everything. That would seem rather error prone and a lot of coordination effort. So how&#x27;s it actually done?

Just earlier this month I was going through <a href="https:&#x2F;&#x2F;github.com&#x2F;jepsen-io&#x2F;maelstrom">https:&#x2F;&#x2F;github.com&#x2F;jepsen-io&#x2F;maelstrom</a> and following the demo implementing (a cut-corners version of) Raft, and I found it quite elucidating. The sample (ruby) code contains some bugs, and I had to use some understanding to fix them. (The bugs were of the kind where a dummy implementation from an earlier step isn&#x27;t correctly changed)

&quot;Paxos Made Moderately Complex&quot; by Robert van Renesse and Deniz Altinbuken: <a href="http:&#x2F;&#x2F;www.cs.cornell.edu&#x2F;courses&#x2F;cs7412&#x2F;2011sp&#x2F;paxos.pdf" rel="nofollow">http:&#x2F;&#x2F;www.cs.cornell.edu&#x2F;courses&#x2F;cs7412&#x2F;2011sp&#x2F;paxos.pdf</a> is a great starting point for implementing multi-paxos. The authors also provide a working python implementation.

Here&#x27;s a visualization of Paxos and MultiPaxos that seems to be based on Ben&#x27;s work: <a href="https:&#x2F;&#x2F;visual.ofcoder.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;visual.ofcoder.com&#x2F;</a>.

DLT technology discussions are entirely incomplete without consideration of Hedera Hashgraph [0], an aBFT, leaderless, fair and <i>fast</i> DLT using a gossip-about-gossip consensus mechanism. It&#x27;s absolutely a more robust and scalable technology than Paxos or any other DLT for that matter. I&#x27;d love to know what the HN crowd thinks about Hedera as the trust layer of the internet but.... nobody around here seems to have any. It&#x27;s like ignoring Linux while comparing Mac and Windows based computing.<p>[0]: <a href="https:&#x2F;&#x2F;www.swirlds.com&#x2F;downloads&#x2F;SWIRLDS-TR-2016-01.pdf" rel="nofollow">https:&#x2F;&#x2F;www.swirlds.com&#x2F;downloads&#x2F;SWIRLDS-TR-2016-01.pdf</a>

Off topic - folks in the know, besides Paxos&#x2F;Raft what are some of the other most complex algorithm in computer sciences that are widely used or are a bedrock?

While understandable, implementing it is however far from easy.

This really teaches Raft well. Is there a good example of this but for Paxos?

Can&#x27;t proof-of-work be used as a leader election algorithm? If the proof is hard enough to generate then one node should be able to generate one and broadcast it before the other nodes can, then that node becomes the leader.