In Search of an Understandable Consensus Algorithm [pdf] | Hacker News Reader

In Search of an Understandable Consensus Algorithm [pdf]

github.com

55 pointshiq14 comments

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.

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.

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

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)

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?

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.

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.

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

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.

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.

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.

I'd recommend to have a look at the etcd raft tests in the link below, you probably need to port them to work with your raft library.

https://github.com/coreos/etcd/tree/master/raft

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

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/

Reply on news.ycombinator.com