5 ms·

The Raft Consensus Algorithm (2015)

171 points by nromiun 1y ago

eatonphil 1y ago
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). https://transactional.blog/blog/2024-data-replication-design-spectrum https://transactional.blog/blog/2024-data-replication-design...
jlundberg 1y ago
I highly recommending anyone interested in high availability to read the Raft specification.
stmw 1y ago
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.
- crdrost 1y ago
  I just want to clarify that, strictly speaking, Paxos is simpler than Raft. Like Paxos is Raft plus "delete the part where the new leader has to be fully caught-up" (which causes an extra weirdness in Raft when the leader got majority adoption of a new log entry but failed to commit it due to network partition) plus "delete the part where the leader election elects the leader, you can do that and it's called multi-paxos, but if your use case isn't big enough you can instead just elect the next log entry, but it doesn't have to have the form "this is our new leader, all hail" (but in practice this is what everyone does). I think the Raft paper is more approachable for newcomers, but if you are finding Paxos hard to explain and Raft easy to explain, just use the Raft lingo to explain Paxos.
  - _benedict 1y ago
    Worth noting, not quite "everyone" does this. Cassandra uses "leaderless" (single decree) paxos, which has some advantages and some disadvantages (for instance, 1RT WAN reads from any region). I agree with you that Paxos is simpler than Raft. The problem with Paxos IMO is that Lamport's original paper is impenetrable; lots of later writing is easier to understand, including those that describe more complex protocols. The intuitions are actually pretty straightforward, and transfer to all of the extensions to Paxos (which are not as straightforwardly compatible with Raft). Raft may have helped more people get comfortable with distributed consensus, and sped its adoption, but being a sort of dangling branch of the tech tree I wonder if this may have stalled progress beyond it.
    - stmw 1y ago
      Interesting way to think about, I am not sure I quite agree, but good points and surrounding discussion for sure..
- chc4 1y ago
  It is darkly amusing to me that Paxos is still cited by people as a "good algorithm" to choose and understandable - including the cutesy island metaphor from the paper to appear approachable - and the Raft paper opens with a paragraph more or less going "ok we had a bunch of people try to understand Paxos and none of them could figure it out". Anytime I see someone recommend Paxos I silently am judging if they've actually ever read the paper or just parroting advice from when it was the only game in town.
  - jen20 1y ago
    Do you ever bother to ask whether they are recommending it for a use case other than a replicated log?
dunkelheit 1y ago
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.
- eatonphil 1y ago
  Anyone can implement Raft. There are plenty of implementations of them not by Google engineers, including a custom one in the product I work on. And developers in the Software Internals Discord are constantly in there asking questions on the road to implementing Raft or Viewstamped Replication.
  - trenchpilgrim 1y ago
    I believe the parent is referring to pre-raft consensus algorithms like Paxos. I recall the explanation of Paxos being a lengthy PDF while the explanation of Raft is a single webpage, mostly visual.
    - eatonphil 1y ago
      Could be, it was a little ambiguously worded. That said, single-decree Paxos is much simpler than Raft but I agree The Part-Time Parliament's analogy is a pain to read. But it's better if you just ignore the beginning chunk of the paper and read like the appendix; A1 The Basic Protocol being simpler to understand.
      - mananaysiempre 1y ago
        There’s also the side-by-side Paxos/Raft comparison in Howard & Mortier’s “Consensus on consensus”[1] paper, which is not enough to understand either by itself, but a great help if have a longer explanation you’re going through. [1] https://dl.acm.org/doi/10.1145/3380787.3393681 https://dl.acm.org/doi/10.1145/3380787.3393681
Vervious 1y ago
not again!
- bravesoul2 1y ago
  Hey... it is a very useful algorithm for looking smart in design interviews. And probably etcd uses it or similar.
baxter001 1y ago
I recall doing a rather large technical case for using raft and a replicated log for water industry back in 2017 it must have been. 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.
klas_segeljakt 1y ago
https://transactional.blog/talk/enough-with-all-the-raft https://transactional.blog/talk/enough-with-all-the-raft
lopatin 1y ago
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.
- chucky_z 1y ago
  It depends!!! If you do something like Consul does where you cram “events” into a radix tree that you send as one big batch it should scale quite well. I wouldn’t expect batched Redis performance but it should be within 70-80% of it in my guess.
- blast 1y ago
  > I'm working on coding a multiplayer io game for fun. I know what a multiplayer game is, but what's a multiplayer io game? (not being snarky, i loved your comment)
  - lopatin 1y ago
    It's just a browser based multi-player game with a .io TLD. Hope to make a Show HN soon :)
  - ChadNauseam 1y ago
    There's a trend of "io games" which are so named because the first one was hosted on a site called "agar.io". then was followed by slither.io and so on. They are characterized by a few distinctive qualities: they're entirely browser-based, players are instantly dropped into a big lobby with tons of other players, they typically have simplistic graphics (e.g. powered by canvas), they have no long-term progression (once you die you restart from the beginning), and they have some kind of leaderboard where you can see the players in your shard that have progressed the farthest since the last time they died.
dang 1y ago
Related. Others? Raft: Understandable Distributed Consensus (2014) - https://news.ycombinator.com/item?id=41669850 https://news.ycombinator.com/item?id=41669850 - Sept 2024 (87 comments) The Raft Consensus Algorithm (2015) - https://news.ycombinator.com/item?id=37369826 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 https://news.ycombinator.com/item?id=36070426 - May 2023 (79 comments) Strong Consistency with Raft and SQLite - https://news.ycombinator.com/item?id=35246228 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 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) 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) 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) Raft Consensus Algorithm - https://news.ycombinator.com/item?id=9613493 https://news.ycombinator.com/item?id=9613493 - May 2015 (24 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)
sathish316 1y ago
This YouTube video by the Raft creators (linked at the bottom of the page) gives a solid explanation of Raft internals - https://m.youtube.com/watch?v=YbZ3zDzDnrw https://m.youtube.com/watch?v=YbZ3zDzDnrw
brcmthrowaway 1y ago
What is used at Google?
- q3k 1y ago
  Back in my day it was all Paxos (Chubby, Borgmaster, ...).
- mrkeen 1y ago
  Probably both? Paxos is used in Spanner.
- jorangreef 1y ago
  I heard on good authority that one of the earliest implementations of consensus at Google involved Sanjay Ghemawat tangentially. Sanjay's PhD on Harp, with Barbara Liskov, had also been based on Viewstamped Replication, and so, internally, this became the first flavor at Google. Later, it would come to be referred to externally as Paxos, only because that was more well known at the time.
jorangreef 1y ago
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: 2012: http://pmg.csail.mit.edu/papers/vr-revisited.pdf http://pmg.csail.mit.edu/papers/vr-revisited.pdf [1] 2014: https://raft.github.io/raft.pdf 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.
- avinassh 1y ago
  one more difference I would add is how a leader is elected in Raft (randomized) vs VSR (deterministic succession)
  - jorangreef 1y ago
    Yes, exactly. That difference came in with '12 VSR's view change (deterministic, round-robin), which upgraded '88 VSR's view change. '14 Raft missed this upgrade, unfortunately (despite citing the '12 paper), thus preserving Oki's '88 "pick the candidate with longest log". I find the history of consensus fascinating, and was fortunate to interview both Brian Oki and James Cowling (so many anecdotes): https://www.youtube.com/watch?v=ps106zjmjhw https://www.youtube.com/watch?v=ps106zjmjhw
nurettin 1y ago
So it is a democratic vote and they are all on the same raft, is that the word play they were going for?
- nateha 1y ago
  You take a raft to get off the island of Paxos.
phtrivier 1y ago
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 ?)
- ingloriousB 1y ago
  There is only one version of the committed log. That's the definition of committed. So you won't get a committed write or read from a partitioned "zombie" leader. In good (non-buggy) Raft implementations, things are set up so there can only ever be at most one leader at a time. That is the point of the election, the pre-vote, the leader-leases, the sticky-leader, and the leader-must-step-down rules (from chapter 6 of the dissertation). Yes those optimizations are described as optional in the Raft dissertation. But really they are not. You have to read the whole dissertation to the details and full picture. You should have all of them as a part of a complete and sane implementation. Pre-vote and sticky-leader are needed for liveness. Leader leases are possible because you have pre-vote and sticky leader on; and they give you fast local-only leader reads. The leader step-down rule prevents client liveness and multiple leaders at once. Even if you do have multiple leaders at once, only one will actually be able to commit, so its not a problem with safety or consistency, just with liveness/not wasting the client's time talking to "a dead man walking".

171 points by nromiun 1y ago

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). https://transactional.blog/blog/2024-data-replication-design-spectrum https://transactional.blog/blog/2024-data-replication-design...

jlundberg 1y ago

I highly recommending anyone interested in high availability to read the Raft specification.

stmw 1y ago

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.

crdrost 1y ago
I just want to clarify that, strictly speaking, Paxos is simpler than Raft. Like Paxos is Raft plus "delete the part where the new leader has to be fully caught-up" (which causes an extra weirdness in Raft when the leader got majority adoption of a new log entry but failed to commit it due to network partition) plus "delete the part where the leader election elects the leader, you can do that and it's called multi-paxos, but if your use case isn't big enough you can instead just elect the next log entry, but it doesn't have to have the form "this is our new leader, all hail" (but in practice this is what everyone does). I think the Raft paper is more approachable for newcomers, but if you are finding Paxos hard to explain and Raft easy to explain, just use the Raft lingo to explain Paxos.
- _benedict 1y ago
  Worth noting, not quite "everyone" does this. Cassandra uses "leaderless" (single decree) paxos, which has some advantages and some disadvantages (for instance, 1RT WAN reads from any region). I agree with you that Paxos is simpler than Raft. The problem with Paxos IMO is that Lamport's original paper is impenetrable; lots of later writing is easier to understand, including those that describe more complex protocols. The intuitions are actually pretty straightforward, and transfer to all of the extensions to Paxos (which are not as straightforwardly compatible with Raft). Raft may have helped more people get comfortable with distributed consensus, and sped its adoption, but being a sort of dangling branch of the tech tree I wonder if this may have stalled progress beyond it.
  - stmw 1y ago
    Interesting way to think about, I am not sure I quite agree, but good points and surrounding discussion for sure..
chc4 1y ago
It is darkly amusing to me that Paxos is still cited by people as a "good algorithm" to choose and understandable - including the cutesy island metaphor from the paper to appear approachable - and the Raft paper opens with a paragraph more or less going "ok we had a bunch of people try to understand Paxos and none of them could figure it out". Anytime I see someone recommend Paxos I silently am judging if they've actually ever read the paper or just parroting advice from when it was the only game in town.
- jen20 1y ago
  Do you ever bother to ask whether they are recommending it for a use case other than a replicated log?

dunkelheit 1y ago

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.

eatonphil 1y ago
Anyone can implement Raft. There are plenty of implementations of them not by Google engineers, including a custom one in the product I work on. And developers in the Software Internals Discord are constantly in there asking questions on the road to implementing Raft or Viewstamped Replication.
- trenchpilgrim 1y ago
  I believe the parent is referring to pre-raft consensus algorithms like Paxos. I recall the explanation of Paxos being a lengthy PDF while the explanation of Raft is a single webpage, mostly visual.
  - eatonphil 1y ago
    Could be, it was a little ambiguously worded. That said, single-decree Paxos is much simpler than Raft but I agree The Part-Time Parliament's analogy is a pain to read. But it's better if you just ignore the beginning chunk of the paper and read like the appendix; A1 The Basic Protocol being simpler to understand.
    - mananaysiempre 1y ago
      There’s also the side-by-side Paxos/Raft comparison in Howard & Mortier’s “Consensus on consensus”[1] paper, which is not enough to understand either by itself, but a great help if have a longer explanation you’re going through. [1] https://dl.acm.org/doi/10.1145/3380787.3393681 https://dl.acm.org/doi/10.1145/3380787.3393681

Vervious 1y ago

not again!

bravesoul2 1y ago
Hey... it is a very useful algorithm for looking smart in design interviews. And probably etcd uses it or similar.

baxter001 1y ago

I recall doing a rather large technical case for using raft and a replicated log for water industry back in 2017 it must have been. 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.

klas_segeljakt 1y ago

https://transactional.blog/talk/enough-with-all-the-raft https://transactional.blog/talk/enough-with-all-the-raft

lopatin 1y ago

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.

chucky_z 1y ago
It depends!!! If you do something like Consul does where you cram “events” into a radix tree that you send as one big batch it should scale quite well. I wouldn’t expect batched Redis performance but it should be within 70-80% of it in my guess.
blast 1y ago
> I'm working on coding a multiplayer io game for fun. I know what a multiplayer game is, but what's a multiplayer io game? (not being snarky, i loved your comment)
- lopatin 1y ago
  It's just a browser based multi-player game with a .io TLD. Hope to make a Show HN soon :)
- ChadNauseam 1y ago
  There's a trend of "io games" which are so named because the first one was hosted on a site called "agar.io". then was followed by slither.io and so on. They are characterized by a few distinctive qualities: they're entirely browser-based, players are instantly dropped into a big lobby with tons of other players, they typically have simplistic graphics (e.g. powered by canvas), they have no long-term progression (once you die you restart from the beginning), and they have some kind of leaderboard where you can see the players in your shard that have progressed the farthest since the last time they died.

dang 1y ago

Related. Others? Raft: Understandable Distributed Consensus (2014) - https://news.ycombinator.com/item?id=41669850 https://news.ycombinator.com/item?id=41669850 - Sept 2024 (87 comments) The Raft Consensus Algorithm (2015) - https://news.ycombinator.com/item?id=37369826 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 https://news.ycombinator.com/item?id=36070426 - May 2023 (79 comments) Strong Consistency with Raft and SQLite - https://news.ycombinator.com/item?id=35246228 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 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) 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) 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) Raft Consensus Algorithm - https://news.ycombinator.com/item?id=9613493 https://news.ycombinator.com/item?id=9613493 - May 2015 (24 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)

sathish316 1y ago

This YouTube video by the Raft creators (linked at the bottom of the page) gives a solid explanation of Raft internals - https://m.youtube.com/watch?v=YbZ3zDzDnrw https://m.youtube.com/watch?v=YbZ3zDzDnrw

brcmthrowaway 1y ago

What is used at Google?

q3k 1y ago
Back in my day it was all Paxos (Chubby, Borgmaster, ...).
mrkeen 1y ago
Probably both? Paxos is used in Spanner.
jorangreef 1y ago
I heard on good authority that one of the earliest implementations of consensus at Google involved Sanjay Ghemawat tangentially. Sanjay's PhD on Harp, with Barbara Liskov, had also been based on Viewstamped Replication, and so, internally, this became the first flavor at Google. Later, it would come to be referred to externally as Paxos, only because that was more well known at the time.

jorangreef 1y ago

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: 2012: http://pmg.csail.mit.edu/papers/vr-revisited.pdf http://pmg.csail.mit.edu/papers/vr-revisited.pdf [1] 2014: https://raft.github.io/raft.pdf 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.

avinassh 1y ago
one more difference I would add is how a leader is elected in Raft (randomized) vs VSR (deterministic succession)
- jorangreef 1y ago
  Yes, exactly. That difference came in with '12 VSR's view change (deterministic, round-robin), which upgraded '88 VSR's view change. '14 Raft missed this upgrade, unfortunately (despite citing the '12 paper), thus preserving Oki's '88 "pick the candidate with longest log". I find the history of consensus fascinating, and was fortunate to interview both Brian Oki and James Cowling (so many anecdotes): https://www.youtube.com/watch?v=ps106zjmjhw https://www.youtube.com/watch?v=ps106zjmjhw

nurettin 1y ago

So it is a democratic vote and they are all on the same raft, is that the word play they were going for?

nateha 1y ago
You take a raft to get off the island of Paxos.

phtrivier 1y ago

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

ingloriousB 1y ago
There is only one version of the committed log. That's the definition of committed. So you won't get a committed write or read from a partitioned "zombie" leader. In good (non-buggy) Raft implementations, things are set up so there can only ever be at most one leader at a time. That is the point of the election, the pre-vote, the leader-leases, the sticky-leader, and the leader-must-step-down rules (from chapter 6 of the dissertation). Yes those optimizations are described as optional in the Raft dissertation. But really they are not. You have to read the whole dissertation to the details and full picture. You should have all of them as a part of a complete and sane implementation. Pre-vote and sticky-leader are needed for liveness. Leader leases are possible because you have pre-vote and sticky leader on; and they give you fast local-only leader reads. The leader step-down rule prevents client liveness and multiple leaders at once. Even if you do have multiple leaders at once, only one will actually be able to commit, so its not a problem with safety or consistency, just with liveness/not wasting the client's time talking to "a dead man walking".