4 ms·

In Search of an Understandable Consensus Algorithm (2014) [pdf]

73 points by kkwteh 5y ago

nayuki 5y ago
I really like this animated visualization of the Raft consensus algorithm: http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/ ; https://news.ycombinator.com/item?id=25326645 https://news.ycombinator.com/item?id=25326645
- deleted 5y ago
  [deleted]
- superasn 5y ago
  This was an amazing presentation. Thanks so much for sharing.
lnsp 5y ago
Martin Kleppmann (known for the Building Data-Intensive Applications book) gave a lecture on Raft a year ago [0], it remains my absolute favorite explanation of the algorithm. [0] https://youtu.be/uXEYuDwm7e4 https://youtu.be/uXEYuDwm7e4
jlrubin 5y ago
I dont like raft personally. I think it does way too much "all in one shot" v.s. a layered abstraction approach you have to do with Paxos where you build up from the basics of consensus. The evidence that raft is more "understandable" rest on IIRC a multiple choice question test not on actually implementing the thing working correctly. But (without having seen the test, but being familiar with both algorithms) it is easier to answer questions about what raft is supposed to be doing than paxos, but paxos actually confronts you with the edge cases more explicitly that are still present in raft. Granted, both are hard to implement correctly! I just think that learning Paxos does lead to a more detailed understanding of consensus than raft. just my 2¢ and no one asked ;)
- lokar 5y ago
  If you like a more decomposed approach you may be interested in: https://www.usenix.org/conference/osdi20/presentation/balakrishnan https://www.usenix.org/conference/osdi20/presentation/balakr...
- ziedaniel1 5y ago
  As someone who TA'd 6.824 (Distributed Systems) twice, I 100% agree. It's easier to halfway understand Raft than to halfway understand Paxos, but implementing a consensus algorithm correctly requires understanding it fully. Once you start talking about e.g. the "election restriction", Raft becomes a bit hairy. (Hi Jeremy!)
  - jlrubin 5y ago
    Hi back atcha! I took 6.824 under Paxos (I think we took it at the same time maybe? not sure if you were TA at that point) and then helped a friend when it switched to raft and good lord that seemed to be a worse for them.
    - ziedaniel1 5y ago
      (Yeah, I was not a TA then -- I took it under Paxos in Spring 2014 but only TA'd it after the switch to Raft)
dang 5y ago
Previous threads: 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) 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)
bullen 5y ago
Again, if understanability is paramount, ROOT is 2000 LoC: http://root.rupy.se http://root.rupy.se
- asimpletune 5y ago
  Is there a high level description of the algorithm? Sorry, I just don't understand what I'm looking at.
  - bullen 5y ago
    It replicates all data everywhere in real-time asynchronously over HTTP. The id of each node is a hash of the key each node uses as privilege to edit. A user node can edit child nodes with it's key. link is used for 1-to-many and word search. meta is used for 3-way many-to-many x-ref values, so for example user-type-item etc. The user management uses this for security: https://datatracker.ietf.org/doc/html/rfc2289 https://datatracker.ietf.org/doc/html/rfc2289

73 points by kkwteh 5y ago

I really like this animated visualization of the Raft consensus algorithm: http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/ ; https://news.ycombinator.com/item?id=25326645 https://news.ycombinator.com/item?id=25326645

deleted 5y ago
[deleted]
superasn 5y ago
This was an amazing presentation. Thanks so much for sharing.

lnsp 5y ago

Martin Kleppmann (known for the Building Data-Intensive Applications book) gave a lecture on Raft a year ago [0], it remains my absolute favorite explanation of the algorithm. [0] https://youtu.be/uXEYuDwm7e4 https://youtu.be/uXEYuDwm7e4

jlrubin 5y ago

I dont like raft personally. I think it does way too much "all in one shot" v.s. a layered abstraction approach you have to do with Paxos where you build up from the basics of consensus. The evidence that raft is more "understandable" rest on IIRC a multiple choice question test not on actually implementing the thing working correctly. But (without having seen the test, but being familiar with both algorithms) it is easier to answer questions about what raft is supposed to be doing than paxos, but paxos actually confronts you with the edge cases more explicitly that are still present in raft. Granted, both are hard to implement correctly! I just think that learning Paxos does lead to a more detailed understanding of consensus than raft. just my 2¢ and no one asked ;)

lokar 5y ago
If you like a more decomposed approach you may be interested in: https://www.usenix.org/conference/osdi20/presentation/balakrishnan https://www.usenix.org/conference/osdi20/presentation/balakr...
ziedaniel1 5y ago
As someone who TA'd 6.824 (Distributed Systems) twice, I 100% agree. It's easier to halfway understand Raft than to halfway understand Paxos, but implementing a consensus algorithm correctly requires understanding it fully. Once you start talking about e.g. the "election restriction", Raft becomes a bit hairy. (Hi Jeremy!)
- jlrubin 5y ago
  Hi back atcha! I took 6.824 under Paxos (I think we took it at the same time maybe? not sure if you were TA at that point) and then helped a friend when it switched to raft and good lord that seemed to be a worse for them.
  - ziedaniel1 5y ago
    (Yeah, I was not a TA then -- I took it under Paxos in Spring 2014 but only TA'd it after the switch to Raft)

dang 5y ago

Previous threads: 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) 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)

bullen 5y ago

Again, if understanability is paramount, ROOT is 2000 LoC: http://root.rupy.se http://root.rupy.se

asimpletune 5y ago
Is there a high level description of the algorithm? Sorry, I just don't understand what I'm looking at.
- bullen 5y ago
  It replicates all data everywhere in real-time asynchronously over HTTP. The id of each node is a hash of the key each node uses as privilege to edit. A user node can edit child nodes with it's key. link is used for 1-to-many and word search. meta is used for 3-way many-to-many x-ref values, so for example user-type-item etc. The user management uses this for security: https://datatracker.ietf.org/doc/html/rfc2289 https://datatracker.ietf.org/doc/html/rfc2289