In Search of an Understandable Consensus Algorithm (2014) [pdf](pdos.csail.mit.edu)
pdos.csail.mit.edu
In Search of an Understandable Consensus Algorithm (2014) [pdf]
https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf
13 comments
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
[0] https://youtu.be/uXEYuDwm7e4
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 ;)
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 ;)
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!)
(Hi Jeremy!)
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.
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.
(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)
If you like a more decomposed approach you may be interested in:
https://www.usenix.org/conference/osdi20/presentation/balakr...
https://www.usenix.org/conference/osdi20/presentation/balakr...
Previous threads:
In Search of an Understandable Consensus Algorithm (2014) [pdf] - 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 - July 2017 (14 comments)
In Search of an Understandable Consensus Algorithm (2014) [pdf] - 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 - July 2017 (14 comments)
Again, if understanability is paramount, ROOT is 2000 LoC: http://root.rupy.se
Is there a high level description of the algorithm? Sorry, I just don't understand what I'm looking at.
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