In Search of an Understandable Consensus Algorithm [pdf]

https://github.com/papers-we-love/zurich/blob/master/2017.06.29-Raft/pwl-raft-trivedi.pdf

by hiq • 9 years ago

55 14 9 years ago

closeparen3• 9 years 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• 9 years 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• 9 years ago

Interesting you say this! Maybe a blog/medium post explaining the intricacies would help people? Are course notes available online?

ll931110• 9 years 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• 9 years 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?

closeparen3• 9 years 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.

dis-sys3• 9 years 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"?

ideal02272• 9 years 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.

closeparen3• 9 years ago

Okay, fair, we didn't do multiple Raft groups or membership changes. If I can find the code, I'll dust it off and give those test suites a try. The project's test suite had a 0MQ broker that could be programmed to selectively drop and delay messages while operating the KV store implemented by the student code. This is pretty similar to Jepsen, though Jepsen might have scenarios that the instructors didn't consider.

I didn't claim it was easy to implement tens of thousands of Raft groups among the same machines (why do you need that?) or to be resilient to Byzantine failures (if that's what you mean by hardware errors).

I don't think we are fundamentally disagreeing: you argue it's difficult to implement various extensions to Raft, we seem to agree it's not that hard to implement the core of Raft.

alpb• 9 years ago

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

billhathaway• 9 years 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

Ben Johnson also made a cool visualization:

http://thesecretlivesofdata.com/raft/

In Search of an Understandable Consensus Algorithm [pdf]

Related Stories