5 ms·

In Search of an Understandable Consensus Algorithm [pdf]

55 points by hiq 9y ago

closeparen 9y ago
I've implemented both Paxos and Raft in class projects. They were difficult and subtle, but still an order of magnitude less difficult than the standard fare of coding interviews.
- billsmithaustin 9y ago
  The standard fare of coding interviews is an order of magnitude MORE difficult than implementing Raft/Paxos? I guess my employer uses easier than standard coding problems.
- andy_ppp 9y ago
  Interesting you say this! Maybe a blog/medium post explaining the intricacies would help people? Are course notes available online?
  - ll931110 9y ago
    Check out MIT 6.824 which contains lecture notes and coding labs on Raft. (They used to teach Paxos but phased out a few years ago)
- phidot 9y ago
  I don't really think that's a sensible comparison--implementation of an algorithm (i.e. implementing Raft) and application of algorithms knowledge to a problem (i.e. a canonical coding interview) are two completely different tasks, no?
  - closeparen 9y ago
    Implementing Paxos is mentally similar to (maybe a little easier than) preparing for a coding interview, and takes drastically less time. A few hours of toil over a few days, vs. a full time job for weeks or a part time job for months. I think it's odd that HN is so blasè about the latter, and so afraid of the former. It's like people have put the problem on a pedestal and become irrationally afraid of it. It's easier than much of the other subject matter that the hive mind claims to have mastered without issue, and pretty small in scope.
    - ideal0227 9y ago
      No, it is not mentally similar I am afard. Implementing Paxos is a joy since it is a process of learning new stuff. Preparing for the coding interview is wasting time, which can put onto something much more meaningful.
- dis-sys 9y ago
  you've never fully implemented raft or paxos. it is well known that such distributed consensus libraries can be extremely easy (a couple of days coding) to start with, but it can take ages to get it polished to the extent to be production ready. a few things to ask yourself - 1. do you support membership change, checkpoint/snapshot streaming, automated consistency check, leadership transfer, witeness, etc? 2. what are the design decisions made to tolerate large latency, i.e. running your raft/paxos in geographically distributed data centres? 3. have you tried to let your "implementation" to pass any 3rd party test suite? what is that test suite? how complete it is? maybe start with the ETCD raft test suite? 4. ever tried to test your "implementation" with Japsen or at least some monkey tests? can your "implementation" survive after very high churn rate? 5. how about hardware errors? will that lead to data corruption? show me your tests please. once you feel comfortable with the answers above, think about another quick question - how can you support tens of thousands of raft/paxos groups on a 3 nodes setup? what changes are required to make it efficient? extra testing required? when further scaling to many nodes, how to manage the distribution of those large number of groups? your "class projects" is nothing else than a slightly more advanced "hello world" program - it proves one thing and one thing only - you are capable of reading a simplified paper written in English. now compare it to coding interview again, is it still "an order of magnitude less difficult"?
  - ideal0227 9y ago
    I wrote a raft implementation that is used by quite a few well known systems (etcd, cockroachdb, docker swarmkit, tikv and quite a few closed source systems). Probably it qualifies the "production ready" standard :P. With that experience, I can say that a real world raft implementation is not easy and VERY time consuming. However, preparing the coding interview is definitely a order of magnitude more difficult for me. It requires me to waste all my time on something meaningless, and makes me feel sick.
    - dis-sys 9y ago
      must be etcd then. ;) it took etcd about 2 years to become mature on its _single_ group raft implementation. the abstraction in raft.go is pretty good, the test suite is the best I can find, message passing and tick handling is correctly handled, but to be honest, everything else (entry management, transport, snapshot streaming, request handling etc) need to be rewritten/added to further scale it to support multi raft groups. that is actually what cockroachdb did. etcd raft is great, just want to give my understanding on how time consuming it is to write a production ready raft library.
alpb 9y ago
If there's a video recording of this meetup it would, in fact, be amazing, too.
- billhathaway 9y ago
  There are a couple of videos of either Diego Ongaro or John Ousterhout, his faculty advisor talking about Raft. The most recent one I saw was: https://www.youtube.com/watch?v=vYp4LYbnnW8 https://www.youtube.com/watch?v=vYp4LYbnnW8 Ben Johnson also made a cool visualization: http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/

55 points by hiq 9y ago

I've implemented both Paxos and Raft in class projects. They were difficult and subtle, but still an order of magnitude less difficult than the standard fare of coding interviews.

billsmithaustin 9y ago
The standard fare of coding interviews is an order of magnitude MORE difficult than implementing Raft/Paxos? I guess my employer uses easier than standard coding problems.
andy_ppp 9y ago
Interesting you say this! Maybe a blog/medium post explaining the intricacies would help people? Are course notes available online?
- ll931110 9y ago
  Check out MIT 6.824 which contains lecture notes and coding labs on Raft. (They used to teach Paxos but phased out a few years ago)
phidot 9y ago
I don't really think that's a sensible comparison--implementation of an algorithm (i.e. implementing Raft) and application of algorithms knowledge to a problem (i.e. a canonical coding interview) are two completely different tasks, no?
- closeparen 9y ago
  Implementing Paxos is mentally similar to (maybe a little easier than) preparing for a coding interview, and takes drastically less time. A few hours of toil over a few days, vs. a full time job for weeks or a part time job for months. I think it's odd that HN is so blasè about the latter, and so afraid of the former. It's like people have put the problem on a pedestal and become irrationally afraid of it. It's easier than much of the other subject matter that the hive mind claims to have mastered without issue, and pretty small in scope.
  - ideal0227 9y ago
    No, it is not mentally similar I am afard. Implementing Paxos is a joy since it is a process of learning new stuff. Preparing for the coding interview is wasting time, which can put onto something much more meaningful.
dis-sys 9y ago
you've never fully implemented raft or paxos. it is well known that such distributed consensus libraries can be extremely easy (a couple of days coding) to start with, but it can take ages to get it polished to the extent to be production ready. a few things to ask yourself - 1. do you support membership change, checkpoint/snapshot streaming, automated consistency check, leadership transfer, witeness, etc? 2. what are the design decisions made to tolerate large latency, i.e. running your raft/paxos in geographically distributed data centres? 3. have you tried to let your "implementation" to pass any 3rd party test suite? what is that test suite? how complete it is? maybe start with the ETCD raft test suite? 4. ever tried to test your "implementation" with Japsen or at least some monkey tests? can your "implementation" survive after very high churn rate? 5. how about hardware errors? will that lead to data corruption? show me your tests please. once you feel comfortable with the answers above, think about another quick question - how can you support tens of thousands of raft/paxos groups on a 3 nodes setup? what changes are required to make it efficient? extra testing required? when further scaling to many nodes, how to manage the distribution of those large number of groups? your "class projects" is nothing else than a slightly more advanced "hello world" program - it proves one thing and one thing only - you are capable of reading a simplified paper written in English. now compare it to coding interview again, is it still "an order of magnitude less difficult"?
- ideal0227 9y ago
  I wrote a raft implementation that is used by quite a few well known systems (etcd, cockroachdb, docker swarmkit, tikv and quite a few closed source systems). Probably it qualifies the "production ready" standard :P. With that experience, I can say that a real world raft implementation is not easy and VERY time consuming. However, preparing the coding interview is definitely a order of magnitude more difficult for me. It requires me to waste all my time on something meaningless, and makes me feel sick.
  - dis-sys 9y ago
    must be etcd then. ;) it took etcd about 2 years to become mature on its _single_ group raft implementation. the abstraction in raft.go is pretty good, the test suite is the best I can find, message passing and tick handling is correctly handled, but to be honest, everything else (entry management, transport, snapshot streaming, request handling etc) need to be rewritten/added to further scale it to support multi raft groups. that is actually what cockroachdb did. etcd raft is great, just want to give my understanding on how time consuming it is to write a production ready raft library.

alpb 9y ago

If there's a video recording of this meetup it would, in fact, be amazing, too.

billhathaway 9y ago
There are a couple of videos of either Diego Ongaro or John Ousterhout, his faculty advisor talking about Raft. The most recent one I saw was: https://www.youtube.com/watch?v=vYp4LYbnnW8 https://www.youtube.com/watch?v=vYp4LYbnnW8 Ben Johnson also made a cool visualization: http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/