10 ms·

The Raft Consensus Algorithm (2015)

343 points by oumua_don17 3y ago

EGreg 3y ago
Is Raft byzantine-fault-tolerant though? Can it be made so? Paxos can: http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzant...
- kevdev 3y ago
  Raft is not byzantine fault tolerant.
- posix86 3y ago
  It assumes no malicious agents. If you're malicious you can take control over everything with a single message (advertise being the leader of the next term).
- dwheeler 3y ago
  Raft cannot handle Byzatune faults by itself. There are variant algorithms that can.
- u320 3y ago
  Paxos is a family of algorithms of which Raft is a member. You can change Raft in various ways but then it's not Raft anymore, but it can still be Paxos. So of course Paxos can "do more".
- intelVISA 3y ago
  No, Raft is mostly for learning the basics of distributed consensus afaik.
- sethev 3y ago
  There's a BFT version: https://www.scs.stanford.edu/17au-cs244b/labs/projects/clow_jiang.pdf https://www.scs.stanford.edu/17au-cs244b/labs/projects/clow_...
eatonphil 3y ago
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. 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. I collected all the resources I found useful while doing it here: https://github.com/eatonphil/goraft#references https://github.com/eatonphil/goraft#references. This includes Diego Ongaro's thesis and his TLA+ spec. 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.
- kevdev 3y ago
  Figure 2 is great, but I would agree the entire paper is needed if you are implementing raft. There are a few specifics in the paper that you need when implementing it. P.S. love your blog :)
  - eatonphil 3y ago
    Cheers! > Figure 2 is great, but I would agree the entire paper is needed if you are implementing raft. There are a few specifics in the paper that you need when implementing it. It was more than that. I'm blanking on what it was but there were parts where I really couldn't find anything about the intended behavior in the paper (let alone in Figure 2) except for in Diego's thesis or in the TLA+ spec. Though maybe I was just not reading the paper correctly.
- agonz253 3y ago
  This looks great. However, without a truly comprehensive test suite it’s guaranteed to have a great many subtle bugs :). I recommend trying to hook it up with the tests from MIT’s distributed systems course: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html https://pdos.csail.mit.edu/6.824/labs/lab-raft.html. It looks as though it would take only a minor refactoring at least for the leader election and log replication.
- skowalak 3y ago
kevdev 3y ago
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.
- dwheeler 3y ago
  I teach a class distributed systems, and this site is one of the references. Thanks for making Raft so clear!
candiddevmike 3y ago
Anyone using object storage like S3 for cluster coordination/election instead?
- hotpotamus 3y ago
  I want to say that jgroups has an S3 coordination method. I came across quite a few methods while trying to set up a Keycloak cluster in Docker Swarm, but ultimately the Kubernetes DNS method worked best for my case (Swarm seems close enough that I was able to use it with no problem). I'd also note that my understanding is that Swarm uses the Raft algorithm.
- ithkuil 3y ago
  Not sure about S3. Iirc they relatively recently implemented consistent writes. But this article explains how to "piggyback" on stores providing consistent writes in order to implement your own little leader election Algo on top of a foundation layer https://cloud.google.com/blog/topics/developers-practitioners/implementing-leader-election-google-cloud-storage https://cloud.google.com/blog/topics/developers-practitioner...
- cweld510 3y ago
  I think S3 is too slow to put in your control plane’s critical path; better to use something like Redis.
jmholla 3y ago
Are there consensus algorithms that don't require changes go through a leader? In many distributed systems, you want to distribute intake as well.
- dboreham 3y ago
  Blockchains
  - Rhapso 3y ago
    No, those only allow 1 leader and 1 intake at a time. They just pick the leader by proof of waste first.
    - lucb1e 3y ago
      I think you may be confusing proof of work with blockchain as a general principle. (I'm not a fan of this cryptocurrency tech anymore either, my comment is purely about the technical properties which can be interesting to study.)
      - Detrytus 3y ago
        No, GP is right. Without Proof of Work blockchains have no leader - think about Git repo with multiple branches: which one is main? Nothing in blockchain itself determines this, only we, humans chose to name one of them "main" (formerly "master").
        lucb1e 3y ago
        > Without Proof of Work blockchains have no leader But, proof of stake?
        Vervious 3y ago
        proof of stake blockchains certainly have leaders. MEV doesn't exist if there aren't designated block proposers
- 3y ago
badcarbine 3y ago
ELI5
- quest88 3y ago
  You need to at least try.
  - badcarbine 3y ago
    You need to, too.
- mrkeen 3y ago
  * 1 computer will eventually break (or one service will crash, or be replaced). To keep processing requests, you need more than 1 computer. * Two-or-more computers can be fed conflicting information. * Consensus algorithms prevent such conflicts from being accepted by the system. * Raft is one such algorithm. It operates by choosing a leader and then routing all requests via that leader, so that no observers will see a different sequence of requests.
- cweagans 3y ago
  http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/
63 3y ago
> Raft is a consensus algorithm that is designed to be easy to understand. > Consensus typically arises in the context of replicated state machines, a general approach to building fault-tolerant systems. 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. 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
- galenmarchetti 3y ago
  Consensus algorithms underly distributed databases like Cassandra, or distributed caches like Redis. (in fact Redis does use a version of Raft). Simple use case, you're running a database across three servers, so that users can ping any one of the servers and it still works (fault tolerance). User X pings server A to write something to a table. User Y pings server B to read from that table. How do you make sure that User Y reads what User X wrote, so that User X and User Y are on the same page with what happened? That's the consensus algo
  - couchand 3y ago
    Not to be too pedantic, but the step of actually shipping those changes across servers is usually outside the scope of consensus algorithms. Generally they are limited to picking a single server to act as a short-term leader. That server then is responsible for managing the data itself. Though you can conceive of a system where all data flows through the consensus algorithm, practically speaking that would introduce significant overhead at a granularity where it isn't adding value. There isn't neceasarily one dictator for the whole cluster, but rather usually they are scoped to each domain that requires serialization.
- adunk 3y ago
  Wikipedia has a nice list of software using the algorithm: https://en.wikipedia.org/wiki/Raft_(algorithm)#Production_use_of_Raft https://en.wikipedia.org/wiki/Raft_(algorithm)#Production_us...
galenmarchetti 3y ago
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" (https://mitpress.mit.edu/9780262562003/reasoning-about-knowledge/ https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...). 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!
lpage 3y ago
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. 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. 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. [1]: https://github.com/jepsen-io/maelstrom/ https://github.com/jepsen-io/maelstrom/ [2]: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DESIGN.md https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
- m00dy 3y ago
  looks like a great playground to get familiar with ds
- LAC-Tech 3y ago
  The view-stamped replication paper was surprisingly readable - I'd never looked at consensus algorithms before in my life and I found I could kind of follow it after a couple of reads. https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSAIL-TR-2012-021.pdf?sequence=1 https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
- mananaysiempre 3y ago
  > [Viewstamped replication] predates Paxos but looks more like Raft. Heidi Howard and Richard Mortier’s paper[1] on the topic of Paxos vs Raft has (multi-decree) Paxos and Raft written out in a way that makes it clear that they are very, very close. I’m very far from knowing what consequences (if any) this has for the implementation concerns you state, but the paper is lovely and I wanted to plug it. (There was also a presentation[2], but IMO the text works better when you want to refer back and forth.) [1] https://doi.org/10.1145/3380787.3393681 https://doi.org/10.1145/3380787.3393681 [2] https://www.youtube.com/watch?v=0K6kt39wyH0 https://www.youtube.com/watch?v=0K6kt39wyH0
_daor 3y ago
[flagged]
- capableweb 3y ago
  > ??? That isn't easy to understand Distributed systems aren't simple, but compared to Paxos, Raft is definitely on the simpler side. I think they're also having a specific audience in mind (distributed systems engineers) rather than the public, when they write "it's easy to understand", which makes sense.
lucb1e 3y ago
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. 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.
- sethev 3y ago
  It shows the state of each replica's log. Click on the leader and select 'request' to simulate sending a command. If you take a replica offline, you can see that it falls behind and then gets caught up when it comes back.
  - lucb1e 3y ago
    Ah, thanks, though I pushed that button a couple times (also before your comment) but it didn't/doesn't do anything that I can tell.
henrik_w 3y ago
Can't resist posting this (from Classic Programmer Paintings) “Raft Consensus Algorithm Failure”,Théodore Géricault, 1819 https://classicprogrammerpaintings.com/post/614108749635928064/raft-consensus-algorithm-failure-th%C3%A9odore https://classicprogrammerpaintings.com/post/6141087496359280...
- harryfyx 3y ago
  Raft has a TLA+ proof, which should make it "bug free". I understand your post is a joke, but I wonder if there are actually any errors.
  - henrydark 3y ago
    Actually, AFAIU the TLA+ proof is only for a few small cluster sizes - not for all sizes. And the number of nodes in the painting is definitely above that checked by TLA+...
henrik_w 3y ago
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: Designing for Understandability: The Raft Consensus Algorithm https://www.youtube.com/watch?v=vYp4LYbnnW8 https://www.youtube.com/watch?v=vYp4LYbnnW8
htowerad3242 3y ago
It's a shame many undergraduate CS curricula are allergic to distributed systems and type systems. Even the grad program I was looking at is hot dog water. I've been playing with raft and paxos. Employers will not care as these were learned out-of-band from degree mills.
bjornasm 3y ago
Here is their answer to their own question - "What is Raft?" >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. 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.
- BirdieNZ 3y ago
  Arguably it's a good description because it automatically filters out audiences who don't know what it means; if you're building a distributed system and looking at different consensus algorithms then it's a simple and clear explanation, but if you aren't then it's not a relevant algorithm for you anyway! The general class of consensus algorithms are for trying to solve the problem of what to do when you have multiple replicas of a data store across several physical devices, when one or many of the devices or their connections fail in some fashion. They are titled "consensus" because the machines need to come to a consensus for what decision to make about a piece of data when a failure event occurs. For example, you have three servers all replicating the same SQL database: (A) - (B) - (C) The network connection linking (C) to the other two drops; (A) and (B) are notified and (B) is promoted to be the primary (it receives the writes and then distributes them to the replicas). However, (C) doesn't know what's happened, and continues to receive some writes. The network connection is restored, and now (A) and (B) and (C) need to decide what to do. (B) and (C) have both independently received a different set of writes, and the servers need to come to a consensus on what to do with the data. This is what Raft, Paxos etc. are attempting to solve in a consistent and performant fashion.
  - beachy 3y ago
    > Arguably it's a good description because it automatically filters out audiences who don't know what it means; if you're building a distributed system and looking at different consensus algorithms then it's a simple and clear explanation, but if you aren't then it's not a relevant algorithm for you anyway! Somewhat discourteous to the 99% of people who don't fall into the target audience - you're leaving it to them to thrash around until they work out for themselves they're at the wrong bar.
dang 3y ago
I took a crack at finding the interesting past related threads. Any others? (I've left out posts about particular implementations, extensions, and so on—there are too many. The intention is threads about the algorithm itself.) Raft Is So Fetch: The Raft Consensus Algorithm Explained Through Mean Girls - https://news.ycombinator.com/item?id=33071069 https://news.ycombinator.com/item?id=33071069 - Oct 2022 (53 comments) Raft Consensus Animated (2014) - https://news.ycombinator.com/item?id=32484584 https://news.ycombinator.com/item?id=32484584 - Aug 2022 (67 comments) Why use Paxos instead of Raft? - https://news.ycombinator.com/item?id=32467962 https://news.ycombinator.com/item?id=32467962 - Aug 2022 (45 comments) In Search of an Understandable Consensus Algorithm (2014) [pdf] - https://news.ycombinator.com/item?id=29837995 https://news.ycombinator.com/item?id=29837995 - Jan 2022 (12 comments) Raft Consensus Protocol - https://news.ycombinator.com/item?id=29079079 https://news.ycombinator.com/item?id=29079079 - Nov 2021 (51 comments) Paxos vs. Raft: Have we reached consensus on distributed consensus? - https://news.ycombinator.com/item?id=27831576 https://news.ycombinator.com/item?id=27831576 - July 2021 (48 comments) Raft Visualization - https://news.ycombinator.com/item?id=25326645 https://news.ycombinator.com/item?id=25326645 - Dec 2020 (35 comments) Raft: A Fantastical and Absurd Exploration - https://news.ycombinator.com/item?id=23129707 https://news.ycombinator.com/item?id=23129707 - May 2020 (1 comment) Understanding Raft Consensus - https://news.ycombinator.com/item?id=23128787 https://news.ycombinator.com/item?id=23128787 - May 2020 (3 comments) In Search of an Understandable Consensus Algorithm (2014) [pdf] - https://news.ycombinator.com/item?id=23113419 https://news.ycombinator.com/item?id=23113419 - May 2020 (26 comments) Paxos vs. Raft: Have we reached consensus on distributed consensus? - https://news.ycombinator.com/item?id=22994420 https://news.ycombinator.com/item?id=22994420 - April 2020 (65 comments) Raft Is So Fetch: The Raft Consensus Algorithm Explained Through Mean Girls - https://news.ycombinator.com/item?id=22520040 https://news.ycombinator.com/item?id=22520040 - March 2020 (4 comments) Implementing Raft: Part 2: Commands and Log Replication - https://news.ycombinator.com/item?id=22451959 https://news.ycombinator.com/item?id=22451959 - Feb 2020 (16 comments) Building a Large-Scale Distributed Storage System Based on Raft - https://news.ycombinator.com/item?id=21447528 https://news.ycombinator.com/item?id=21447528 - Nov 2019 (5 comments) In Search of an Understandable Consensus Algorithm [pdf] - https://news.ycombinator.com/item?id=14724883 https://news.ycombinator.com/item?id=14724883 - July 2017 (14 comments) Instructors' Guide to Raft - https://news.ycombinator.com/item?id=11300428 https://news.ycombinator.com/item?id=11300428 - March 2016 (3 comments) Fuzzing Raft for Fun and Publication - https://news.ycombinator.com/item?id=10432062 https://news.ycombinator.com/item?id=10432062 - Oct 2015 (10 comments) Prove Raft Correct - https://news.ycombinator.com/item?id=10017549 https://news.ycombinator.com/item?id=10017549 - Aug 2015 (27 comments) Scaling Raft - https://news.ycombinator.com/item?id=9725094 https://news.ycombinator.com/item?id=9725094 - June 2015 (12 comments) Raft Consensus Algorithm - https://news.ycombinator.com/item?id=9613493 https://news.ycombinator.com/item?id=9613493 - May 2015 (24 comments) Creator of Raft is speaking at our meetup. What questions do you want answered? - https://news.ycombinator.com/item?id=9351794 https://news.ycombinator.com/item?id=9351794 - April 2015 (6 comments) Replicating SQLite using Raft Consensus - https://news.ycombinator.com/item?id=9092110 https://news.ycombinator.com/item?id=9092110 - Feb 2015 (21 comments) Raft Refloated: Do We Have Consensus? [pdf] - https://news.ycombinator.com/item?id=9015085 https://news.ycombinator.com/item?id=9015085 - Feb 2015 (4 comments) Analysis of Raft Consensus [pdf] - https://news.ycombinator.com/item?id=8736868 https://news.ycombinator.com/item?id=8736868 - Dec 2014 (3 comments) The Raft Consensus Algorithm - https://news.ycombinator.com/item?id=8527440 https://news.ycombinator.com/item?id=8527440 - Oct 2014 (27 comments) Raft: Understandable Distributed Consensus - https://news.ycombinator.com/item?id=8271957 https://news.ycombinator.com/item?id=8271957 - Sept 2014 (79 comments) Raft - The Understandable Distributed Protocol - https://news.ycombinator.com/item?id=6859101 https://news.ycombinator.com/item?id=6859101 - Dec 2013 (10 comments) Raft, a scrutable successor to Paxos - https://news.ycombinator.com/item?id=5624627 https://news.ycombinator.com/item?id=5624627 - April 2013 (2 comments)
maxpert 3y ago
I've written a whole SQLite replication system that works on top of RAFT ( https://github.com/maxpert/marmot https://github.com/maxpert/marmot ). 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 (https://docs.nats.io/nats-concepts/jetstream https://docs.nats.io/nats-concepts/jetstream) and embedded it in system. I love the simplicity and reasoning that comes with RAFT. However I am playing with epaxos these days (https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf), 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.
benreesman 3y ago
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. But AFAIK people have been putting heavy, heavy work on Raft-based options like etcd and Consul and others for many years now. 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. 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? 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?
Vervious 3y ago
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. 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).
- woooooo 3y ago
  Not a consensus protocol researcher. It seems like blockchain brings a bunch of extra stuff, complexity and cost? Raft seems comparatively simple to me. What does blockchain bring that's easier to maintain and harder to fuck up than "elect a leader and replicate a log"?
  - Vervious 3y ago
    A blockchain (without all the bells and whistles) is definitionally equivalent to a state-machine or log replication system (but handling byzantine faults). (Each log entry is just a block).
valzam 3y ago
Obligatory plug: http://nil.csail.mit.edu/6.824/2022/schedule.html http://nil.csail.mit.edu/6.824/2022/schedule.html 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.

343 points by oumua_don17 3y ago

Is Raft byzantine-fault-tolerant though? Can it be made so? Paxos can: http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzant...

kevdev 3y ago
Raft is not byzantine fault tolerant.
posix86 3y ago
It assumes no malicious agents. If you're malicious you can take control over everything with a single message (advertise being the leader of the next term).
dwheeler 3y ago
Raft cannot handle Byzatune faults by itself. There are variant algorithms that can.
u320 3y ago
Paxos is a family of algorithms of which Raft is a member. You can change Raft in various ways but then it's not Raft anymore, but it can still be Paxos. So of course Paxos can "do more".
intelVISA 3y ago
No, Raft is mostly for learning the basics of distributed consensus afaik.
sethev 3y ago
There's a BFT version: https://www.scs.stanford.edu/17au-cs244b/labs/projects/clow_jiang.pdf https://www.scs.stanford.edu/17au-cs244b/labs/projects/clow_...

eatonphil 3y ago

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. 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. I collected all the resources I found useful while doing it here: https://github.com/eatonphil/goraft#references https://github.com/eatonphil/goraft#references. This includes Diego Ongaro's thesis and his TLA+ spec. 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.

kevdev 3y ago
Figure 2 is great, but I would agree the entire paper is needed if you are implementing raft. There are a few specifics in the paper that you need when implementing it. P.S. love your blog :)
- eatonphil 3y ago
  Cheers! > Figure 2 is great, but I would agree the entire paper is needed if you are implementing raft. There are a few specifics in the paper that you need when implementing it. It was more than that. I'm blanking on what it was but there were parts where I really couldn't find anything about the intended behavior in the paper (let alone in Figure 2) except for in Diego's thesis or in the TLA+ spec. Though maybe I was just not reading the paper correctly.
agonz253 3y ago
This looks great. However, without a truly comprehensive test suite it’s guaranteed to have a great many subtle bugs :). I recommend trying to hook it up with the tests from MIT’s distributed systems course: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html https://pdos.csail.mit.edu/6.824/labs/lab-raft.html. It looks as though it would take only a minor refactoring at least for the leader election and log replication.
skowalak 3y ago

kevdev 3y ago

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.

dwheeler 3y ago
I teach a class distributed systems, and this site is one of the references. Thanks for making Raft so clear!

candiddevmike 3y ago

Anyone using object storage like S3 for cluster coordination/election instead?

hotpotamus 3y ago
I want to say that jgroups has an S3 coordination method. I came across quite a few methods while trying to set up a Keycloak cluster in Docker Swarm, but ultimately the Kubernetes DNS method worked best for my case (Swarm seems close enough that I was able to use it with no problem). I'd also note that my understanding is that Swarm uses the Raft algorithm.
ithkuil 3y ago
Not sure about S3. Iirc they relatively recently implemented consistent writes. But this article explains how to "piggyback" on stores providing consistent writes in order to implement your own little leader election Algo on top of a foundation layer https://cloud.google.com/blog/topics/developers-practitioners/implementing-leader-election-google-cloud-storage https://cloud.google.com/blog/topics/developers-practitioner...
cweld510 3y ago
I think S3 is too slow to put in your control plane’s critical path; better to use something like Redis.

jmholla 3y ago

Are there consensus algorithms that don't require changes go through a leader? In many distributed systems, you want to distribute intake as well.

dboreham 3y ago
Blockchains
- Rhapso 3y ago
  No, those only allow 1 leader and 1 intake at a time. They just pick the leader by proof of waste first.
  - lucb1e 3y ago
    I think you may be confusing proof of work with blockchain as a general principle. (I'm not a fan of this cryptocurrency tech anymore either, my comment is purely about the technical properties which can be interesting to study.)
    - Detrytus 3y ago
      No, GP is right. Without Proof of Work blockchains have no leader - think about Git repo with multiple branches: which one is main? Nothing in blockchain itself determines this, only we, humans chose to name one of them "main" (formerly "master").
      - lucb1e 3y ago
        > Without Proof of Work blockchains have no leader But, proof of stake?
      - Vervious 3y ago
        proof of stake blockchains certainly have leaders. MEV doesn't exist if there aren't designated block proposers
3y ago

badcarbine 3y ago

ELI5

quest88 3y ago
You need to at least try.
- badcarbine 3y ago
  You need to, too.
mrkeen 3y ago
* 1 computer will eventually break (or one service will crash, or be replaced). To keep processing requests, you need more than 1 computer. * Two-or-more computers can be fed conflicting information. * Consensus algorithms prevent such conflicts from being accepted by the system. * Raft is one such algorithm. It operates by choosing a leader and then routing all requests via that leader, so that no observers will see a different sequence of requests.
cweagans 3y ago
http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/

63 3y ago

> Raft is a consensus algorithm that is designed to be easy to understand. > Consensus typically arises in the context of replicated state machines, a general approach to building fault-tolerant systems. 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. 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

galenmarchetti 3y ago
Consensus algorithms underly distributed databases like Cassandra, or distributed caches like Redis. (in fact Redis does use a version of Raft). Simple use case, you're running a database across three servers, so that users can ping any one of the servers and it still works (fault tolerance). User X pings server A to write something to a table. User Y pings server B to read from that table. How do you make sure that User Y reads what User X wrote, so that User X and User Y are on the same page with what happened? That's the consensus algo
- couchand 3y ago
  Not to be too pedantic, but the step of actually shipping those changes across servers is usually outside the scope of consensus algorithms. Generally they are limited to picking a single server to act as a short-term leader. That server then is responsible for managing the data itself. Though you can conceive of a system where all data flows through the consensus algorithm, practically speaking that would introduce significant overhead at a granularity where it isn't adding value. There isn't neceasarily one dictator for the whole cluster, but rather usually they are scoped to each domain that requires serialization.
adunk 3y ago
Wikipedia has a nice list of software using the algorithm: https://en.wikipedia.org/wiki/Raft_(algorithm)#Production_use_of_Raft https://en.wikipedia.org/wiki/Raft_(algorithm)#Production_us...

galenmarchetti 3y ago

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" (https://mitpress.mit.edu/9780262562003/reasoning-about-knowledge/ https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...). 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!

lpage 3y ago

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. 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. 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. [1]: https://github.com/jepsen-io/maelstrom/ https://github.com/jepsen-io/maelstrom/ [2]: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DESIGN.md https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...

m00dy 3y ago
looks like a great playground to get familiar with ds
LAC-Tech 3y ago
The view-stamped replication paper was surprisingly readable - I'd never looked at consensus algorithms before in my life and I found I could kind of follow it after a couple of reads. https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSAIL-TR-2012-021.pdf?sequence=1 https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
mananaysiempre 3y ago
> [Viewstamped replication] predates Paxos but looks more like Raft. Heidi Howard and Richard Mortier’s paper[1] on the topic of Paxos vs Raft has (multi-decree) Paxos and Raft written out in a way that makes it clear that they are very, very close. I’m very far from knowing what consequences (if any) this has for the implementation concerns you state, but the paper is lovely and I wanted to plug it. (There was also a presentation[2], but IMO the text works better when you want to refer back and forth.) [1] https://doi.org/10.1145/3380787.3393681 https://doi.org/10.1145/3380787.3393681 [2] https://www.youtube.com/watch?v=0K6kt39wyH0 https://www.youtube.com/watch?v=0K6kt39wyH0

_daor 3y ago

[flagged]

capableweb 3y ago
> ??? That isn't easy to understand Distributed systems aren't simple, but compared to Paxos, Raft is definitely on the simpler side. I think they're also having a specific audience in mind (distributed systems engineers) rather than the public, when they write "it's easy to understand", which makes sense.

lucb1e 3y ago

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

sethev 3y ago
It shows the state of each replica's log. Click on the leader and select 'request' to simulate sending a command. If you take a replica offline, you can see that it falls behind and then gets caught up when it comes back.
- lucb1e 3y ago
  Ah, thanks, though I pushed that button a couple times (also before your comment) but it didn't/doesn't do anything that I can tell.

henrik_w 3y ago

Can't resist posting this (from Classic Programmer Paintings) “Raft Consensus Algorithm Failure”,Théodore Géricault, 1819 https://classicprogrammerpaintings.com/post/614108749635928064/raft-consensus-algorithm-failure-th%C3%A9odore https://classicprogrammerpaintings.com/post/6141087496359280...

harryfyx 3y ago
Raft has a TLA+ proof, which should make it "bug free". I understand your post is a joke, but I wonder if there are actually any errors.
- henrydark 3y ago
  Actually, AFAIU the TLA+ proof is only for a few small cluster sizes - not for all sizes. And the number of nodes in the painting is definitely above that checked by TLA+...

henrik_w 3y ago

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: Designing for Understandability: The Raft Consensus Algorithm https://www.youtube.com/watch?v=vYp4LYbnnW8 https://www.youtube.com/watch?v=vYp4LYbnnW8

htowerad3242 3y ago

It's a shame many undergraduate CS curricula are allergic to distributed systems and type systems. Even the grad program I was looking at is hot dog water. I've been playing with raft and paxos. Employers will not care as these were learned out-of-band from degree mills.

bjornasm 3y ago

Here is their answer to their own question - "What is Raft?" >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. 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.

BirdieNZ 3y ago
Arguably it's a good description because it automatically filters out audiences who don't know what it means; if you're building a distributed system and looking at different consensus algorithms then it's a simple and clear explanation, but if you aren't then it's not a relevant algorithm for you anyway! The general class of consensus algorithms are for trying to solve the problem of what to do when you have multiple replicas of a data store across several physical devices, when one or many of the devices or their connections fail in some fashion. They are titled "consensus" because the machines need to come to a consensus for what decision to make about a piece of data when a failure event occurs. For example, you have three servers all replicating the same SQL database: (A) - (B) - (C) The network connection linking (C) to the other two drops; (A) and (B) are notified and (B) is promoted to be the primary (it receives the writes and then distributes them to the replicas). However, (C) doesn't know what's happened, and continues to receive some writes. The network connection is restored, and now (A) and (B) and (C) need to decide what to do. (B) and (C) have both independently received a different set of writes, and the servers need to come to a consensus on what to do with the data. This is what Raft, Paxos etc. are attempting to solve in a consistent and performant fashion.
- beachy 3y ago
  > Arguably it's a good description because it automatically filters out audiences who don't know what it means; if you're building a distributed system and looking at different consensus algorithms then it's a simple and clear explanation, but if you aren't then it's not a relevant algorithm for you anyway! Somewhat discourteous to the 99% of people who don't fall into the target audience - you're leaving it to them to thrash around until they work out for themselves they're at the wrong bar.

dang 3y ago

I took a crack at finding the interesting past related threads. Any others? (I've left out posts about particular implementations, extensions, and so on—there are too many. The intention is threads about the algorithm itself.) Raft Is So Fetch: The Raft Consensus Algorithm Explained Through Mean Girls - https://news.ycombinator.com/item?id=33071069 https://news.ycombinator.com/item?id=33071069 - Oct 2022 (53 comments) Raft Consensus Animated (2014) - https://news.ycombinator.com/item?id=32484584 https://news.ycombinator.com/item?id=32484584 - Aug 2022 (67 comments) Why use Paxos instead of Raft? - https://news.ycombinator.com/item?id=32467962 https://news.ycombinator.com/item?id=32467962 - Aug 2022 (45 comments) In Search of an Understandable Consensus Algorithm (2014) [pdf] - https://news.ycombinator.com/item?id=29837995 https://news.ycombinator.com/item?id=29837995 - Jan 2022 (12 comments) Raft Consensus Protocol - https://news.ycombinator.com/item?id=29079079 https://news.ycombinator.com/item?id=29079079 - Nov 2021 (51 comments) Paxos vs. Raft: Have we reached consensus on distributed consensus? - https://news.ycombinator.com/item?id=27831576 https://news.ycombinator.com/item?id=27831576 - July 2021 (48 comments) Raft Visualization - https://news.ycombinator.com/item?id=25326645 https://news.ycombinator.com/item?id=25326645 - Dec 2020 (35 comments) Raft: A Fantastical and Absurd Exploration - https://news.ycombinator.com/item?id=23129707 https://news.ycombinator.com/item?id=23129707 - May 2020 (1 comment) Understanding Raft Consensus - https://news.ycombinator.com/item?id=23128787 https://news.ycombinator.com/item?id=23128787 - May 2020 (3 comments) In Search of an Understandable Consensus Algorithm (2014) [pdf] - https://news.ycombinator.com/item?id=23113419 https://news.ycombinator.com/item?id=23113419 - May 2020 (26 comments) Paxos vs. Raft: Have we reached consensus on distributed consensus? - https://news.ycombinator.com/item?id=22994420 https://news.ycombinator.com/item?id=22994420 - April 2020 (65 comments) Raft Is So Fetch: The Raft Consensus Algorithm Explained Through Mean Girls - https://news.ycombinator.com/item?id=22520040 https://news.ycombinator.com/item?id=22520040 - March 2020 (4 comments) Implementing Raft: Part 2: Commands and Log Replication - https://news.ycombinator.com/item?id=22451959 https://news.ycombinator.com/item?id=22451959 - Feb 2020 (16 comments) Building a Large-Scale Distributed Storage System Based on Raft - https://news.ycombinator.com/item?id=21447528 https://news.ycombinator.com/item?id=21447528 - Nov 2019 (5 comments) In Search of an Understandable Consensus Algorithm [pdf] - https://news.ycombinator.com/item?id=14724883 https://news.ycombinator.com/item?id=14724883 - July 2017 (14 comments) Instructors' Guide to Raft - https://news.ycombinator.com/item?id=11300428 https://news.ycombinator.com/item?id=11300428 - March 2016 (3 comments) Fuzzing Raft for Fun and Publication - https://news.ycombinator.com/item?id=10432062 https://news.ycombinator.com/item?id=10432062 - Oct 2015 (10 comments) Prove Raft Correct - https://news.ycombinator.com/item?id=10017549 https://news.ycombinator.com/item?id=10017549 - Aug 2015 (27 comments) Scaling Raft - https://news.ycombinator.com/item?id=9725094 https://news.ycombinator.com/item?id=9725094 - June 2015 (12 comments) Raft Consensus Algorithm - https://news.ycombinator.com/item?id=9613493 https://news.ycombinator.com/item?id=9613493 - May 2015 (24 comments) Creator of Raft is speaking at our meetup. What questions do you want answered? - https://news.ycombinator.com/item?id=9351794 https://news.ycombinator.com/item?id=9351794 - April 2015 (6 comments) Replicating SQLite using Raft Consensus - https://news.ycombinator.com/item?id=9092110 https://news.ycombinator.com/item?id=9092110 - Feb 2015 (21 comments) Raft Refloated: Do We Have Consensus? [pdf] - https://news.ycombinator.com/item?id=9015085 https://news.ycombinator.com/item?id=9015085 - Feb 2015 (4 comments) Analysis of Raft Consensus [pdf] - https://news.ycombinator.com/item?id=8736868 https://news.ycombinator.com/item?id=8736868 - Dec 2014 (3 comments) The Raft Consensus Algorithm - https://news.ycombinator.com/item?id=8527440 https://news.ycombinator.com/item?id=8527440 - Oct 2014 (27 comments) Raft: Understandable Distributed Consensus - https://news.ycombinator.com/item?id=8271957 https://news.ycombinator.com/item?id=8271957 - Sept 2014 (79 comments) Raft - The Understandable Distributed Protocol - https://news.ycombinator.com/item?id=6859101 https://news.ycombinator.com/item?id=6859101 - Dec 2013 (10 comments) Raft, a scrutable successor to Paxos - https://news.ycombinator.com/item?id=5624627 https://news.ycombinator.com/item?id=5624627 - April 2013 (2 comments)

maxpert 3y ago

I've written a whole SQLite replication system that works on top of RAFT ( https://github.com/maxpert/marmot https://github.com/maxpert/marmot ). 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 (https://docs.nats.io/nats-concepts/jetstream https://docs.nats.io/nats-concepts/jetstream) and embedded it in system. I love the simplicity and reasoning that comes with RAFT. However I am playing with epaxos these days (https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf), 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.

benreesman 3y ago

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. But AFAIK people have been putting heavy, heavy work on Raft-based options like etcd and Consul and others for many years now. 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. 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? 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?

Vervious 3y ago

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

woooooo 3y ago
Not a consensus protocol researcher. It seems like blockchain brings a bunch of extra stuff, complexity and cost? Raft seems comparatively simple to me. What does blockchain bring that's easier to maintain and harder to fuck up than "elect a leader and replicate a log"?
- Vervious 3y ago
  A blockchain (without all the bells and whistles) is definitionally equivalent to a state-machine or log replication system (but handling byzantine faults). (Each log entry is just a block).

valzam 3y ago

Obligatory plug: http://nil.csail.mit.edu/6.824/2022/schedule.html http://nil.csail.mit.edu/6.824/2022/schedule.html 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.