Check out Alex Miller's Data Replication Design Spectrum for what you might use instead of Raft (for replication specifically), or what tweaks you might make to Raft for better throughput or space efficiency (for replication).
Both the Raft algorithm and its explanation are excellent, including this little animated demo that Diego Ongaro (who is also a great guy) made to help explain his invention. While Paxos was first and still popular, I am not sure I would count against any senior engineer unable to explain it to others. With Raft, one ought to be able to do it.
Great to see this on HN.
Kudos to the raft authors for making distributed consensus accessible. Structuring the presentation in terms of RPCs and making the algorithm well-suited for implementing replicated state machines may not sound like a big deal, but those decisions really helped to make it approachable.
In a span of a decade consensus transformed from an esoteric algorithm that you can maaaaybe try implementing if you are a google engineer, to being widely deployed across many storage systems and readily accessible libraries and Raft played a big part in it.
Here's a recent Raft story from when I was trying to learn how to use it. I'm working on coding a multiplayer io game for fun. One key part was that it needs replication of game state so that live games can fail over if one of the servers crashes or is restarted.
I was like, "wait, that's what raft does, and my game state is already a state machine ... let's do this thing". I then ended up putting my entire game state into raft, and even abused it as a generic pubsub engine.
It was fun, and it worked, and was actually not hard to setup using the Rust implementation.
Then when I was done, I realized how pathological it was to put literally all game state and every single event into Raft, so decided to stop indulging myself by having fun and trying to hack Raft into an unintended use case, and just used Redis for game state and pubsub.
I never load tested the Raft implementation, but once I do have some perf testing tools, I'd be interesting to run the Raft code vs. Redis comparison to see how throughput differs. For this use case, at some point Raft should fall over while Redis would be chugging along.
Lamport's 1978 "Time, Clocks, and the Ordering of Events in a Distributed System". The Raft dissertation never really explains why using a logical clock is the critical, central thing. It just glosses over it.
And then read Lampson's 1996 "How to Build a Highly Available System Using Consensus". It will teach you how to prove equivalence of your variation back to an established, proven model. It is very clearly written.
Raft played a huge role in improving how consensus is taught, compared to Paxos.
It’s hinted at in the introduction to the Raft paper, that Raft is "most notably" similar to Viewstamped Replication from Brian Oki, Barbara Liskov and James Cowling at MIT. Reason being that Raft’s primary goal was not so much to reinvent or contribute consensus, so much as to repackage consensus to be "more understandable than Paxos". Nevertheless, it’s not widely known, and probably could be emphasized a bit more, that the protocol is otherwise pretty much ‘88 Oki VSR (same essential protocol, different terms), itself predating Paxos a year.
For example, if you compare '14 Raft (Stanford) with '12 VSR (MIT’s revision to their ‘88 original), the resemblance is striking:
Presentation aside, the only major difference is that Raft’s view change (called leader election in the Raft paper) preserves the flavor of Oki’s ‘88 Viewstamped Replication view change, electing the candidate with the longest log, and missing out on the improved round-robin view change from MIT in ‘12, that brings better stability and availability, with lower latency, and no dueling leaders.
Raft has had a tremendous impact, compared to Paxos, in helping engineers to understand consensus. But once the training wheels are there, it’s important that we also understand and preserve the history of consensus, the people who pioneered these protocols.
[1] It's an accident of history that '12 VSR wasn't promoted as much as Raft would be, two years later. Otherwise, '12 VSR from James Cowling is arguably just as understandable, if not more. For example, because of the improved view change, the paper can begin immediately with normal replication. And there's no discussion, for example, of the need for randomized timeouts, it's elegantly designed away.
Re: "It's an accident of history that '12 VSR wasn't promoted as much as Raft would be, two years later. " - more accurate to say MIT vs Stanford difference.
Probably a FAQ, but the example about network partition leaves me wondering : if two clients talk to a different leader of subnetwork, the algorithm guarantees that eventually, one of the leader will step down, and both clients will eventually see the same operation log.
Does it mean that the client should implicitly wait a bit before "trusting" their server, to be sure ? What happens if you take a wrong decision based on an outdated log that is eventually rolled back ?
(Or it simply the same thing as with any eventually consistent system - you should _not_ have irreversible side effects that depend on the value of a log in the system, at all ?)
16 comments
[ 3.0 ms ] story [ 40.7 ms ] threadhttps://transactional.blog/blog/2024-data-replication-design...
In a span of a decade consensus transformed from an esoteric algorithm that you can maaaaybe try implementing if you are a google engineer, to being widely deployed across many storage systems and readily accessible libraries and Raft played a big part in it.
That's from knowing nothing about the shape of consensus algorithms to almost getting one adopted.
To me Raft's brilliance is how easy, clear and comprehensible they made thinking about it.
I was like, "wait, that's what raft does, and my game state is already a state machine ... let's do this thing". I then ended up putting my entire game state into raft, and even abused it as a generic pubsub engine.
It was fun, and it worked, and was actually not hard to setup using the Rust implementation. Then when I was done, I realized how pathological it was to put literally all game state and every single event into Raft, so decided to stop indulging myself by having fun and trying to hack Raft into an unintended use case, and just used Redis for game state and pubsub.
I never load tested the Raft implementation, but once I do have some perf testing tools, I'd be interesting to run the Raft code vs. Redis comparison to see how throughput differs. For this use case, at some point Raft should fall over while Redis would be chugging along.
Raft: Understandable Distributed Consensus (2014) - https://news.ycombinator.com/item?id=41669850 - Sept 2024 (87 comments)
The Raft Consensus Algorithm (2015) - https://news.ycombinator.com/item?id=37369826 - Sept 2023 (76 comments)
Implementing a distributed key-value store on top of implementing Raft in Go - https://news.ycombinator.com/item?id=36070426 - May 2023 (79 comments)
Strong Consistency with Raft and SQLite - https://news.ycombinator.com/item?id=35246228 - March 2023 (42 comments)
Raft Is So Fetch: The Raft Consensus Algorithm Explained Through Mean Girls - https://news.ycombinator.com/item?id=33071069 - Oct 2022 (53 comments)
Raft Consensus Animated (2014) - https://news.ycombinator.com/item?id=32484584 - Aug 2022 (67 comments)
Why use Paxos instead of Raft? - 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 - Jan 2022 (12 comments)
Raft Consensus Protocol - 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 - July 2021 (48 comments)
In Search of an Understandable Consensus Algorithm (2014) [pdf] - 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 - April 2020 (65 comments)
Raft Is So Fetch: The Raft Consensus Algorithm Explained Through Mean Girls - https://news.ycombinator.com/item?id=22520040 - March 2020 (4 comments)
In Search of an Understandable Consensus Algorithm [pdf] - https://news.ycombinator.com/item?id=14724883 - July 2017 (14 comments)
Raft Consensus Algorithm - https://news.ycombinator.com/item?id=9613493 - May 2015 (24 comments)
The Raft Consensus Algorithm - https://news.ycombinator.com/item?id=8527440 - Oct 2014 (27 comments)
Raft: Understandable Distributed Consensus - https://news.ycombinator.com/item?id=8271957 - Sept 2014 (79 comments)
1) https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks
Lamport's 1978 "Time, Clocks, and the Ordering of Events in a Distributed System". The Raft dissertation never really explains why using a logical clock is the critical, central thing. It just glosses over it.
And then read Lampson's 1996 "How to Build a Highly Available System Using Consensus". It will teach you how to prove equivalence of your variation back to an established, proven model. It is very clearly written.
2)https://www.microsoft.com/en-us/research/wp-content/uploads/...
It’s hinted at in the introduction to the Raft paper, that Raft is "most notably" similar to Viewstamped Replication from Brian Oki, Barbara Liskov and James Cowling at MIT. Reason being that Raft’s primary goal was not so much to reinvent or contribute consensus, so much as to repackage consensus to be "more understandable than Paxos". Nevertheless, it’s not widely known, and probably could be emphasized a bit more, that the protocol is otherwise pretty much ‘88 Oki VSR (same essential protocol, different terms), itself predating Paxos a year.
For example, if you compare '14 Raft (Stanford) with '12 VSR (MIT’s revision to their ‘88 original), the resemblance is striking:
2012: http://pmg.csail.mit.edu/papers/vr-revisited.pdf [1]
2014: https://raft.github.io/raft.pdf
Presentation aside, the only major difference is that Raft’s view change (called leader election in the Raft paper) preserves the flavor of Oki’s ‘88 Viewstamped Replication view change, electing the candidate with the longest log, and missing out on the improved round-robin view change from MIT in ‘12, that brings better stability and availability, with lower latency, and no dueling leaders.
Raft has had a tremendous impact, compared to Paxos, in helping engineers to understand consensus. But once the training wheels are there, it’s important that we also understand and preserve the history of consensus, the people who pioneered these protocols.
[1] It's an accident of history that '12 VSR wasn't promoted as much as Raft would be, two years later. Otherwise, '12 VSR from James Cowling is arguably just as understandable, if not more. For example, because of the improved view change, the paper can begin immediately with normal replication. And there's no discussion, for example, of the need for randomized timeouts, it's elegantly designed away.
Does it mean that the client should implicitly wait a bit before "trusting" their server, to be sure ? What happens if you take a wrong decision based on an outdated log that is eventually rolled back ?
(Or it simply the same thing as with any eventually consistent system - you should _not_ have irreversible side effects that depend on the value of a log in the system, at all ?)