Implementing a distributed key-value store on top of implementing Raft in Go
notes.eatonphil.com
notes.eatonphil.com
The author spent 7 months tinkering and cared enough to come back and share that with us.
In all seriousness, I actually feel bad being here sometimes as a layman trying to learn what engineers and all the smarties here think about news. Imposter syndrome from commenting on an internet forum, how sad is that lol
After talking for a bit about pretty much all of the above, the interviewer asked "have you used dictionaries?"
The reason I'm telling the story is, if a lot of your candidates fail to answer your questions, the problem might be in the question.
I am most definitely not ruling out what you're saying may be common case and I am just very lucky, but I do want to act as a sort of counter point to see if others can weigh in so we can get more of an industry sense around this
Hell, even when in jobs, asking questions about projects I'm assigned has sometimes got a negative response...
If the prompt is unclear its worth getting clarity, just like if something is unclear in the job you seek clarity, I feel like people not asking questions would be a big red flag.
of course, asking too many (this is subjective but I think we can all think of a reasonable situation where there were too many questions being asked relative to their value) could be a red flag
There are a distressing number of managers / leads I have encountered who consider that if you're asking for clarity, you're impugning their powers of explanation because CLEARLY they explained it well enough (after all, they understand it!) and you're either an idiot or being sarcastic to undermine them.
By mentioning a few ways you'd show you're aware of various solutions, and you'd also provide context for why you're asking probing questions.
Then again, I haven't interviewed in quite a while (love my current job) so...
Sure but taking that as "the asker is an idiot" rather than "I may not have explained this well" is all too common (I know I've been guilty of this more than a handful of times.)
> Would it help if one prefaced with something like [...]
I think if you're having to carefully phrase your (reasonable, obvs.) questions in order to avoid upsetting the interviewer, that's a bit of a red flag, no?
Why would you only want cookie-cutter "correct" answers to your questions? That doesn't tell you shit about the candidate?
I can't read your mind, and that goes both for interview questions and determining product needs.
Hahaha classic.
I was once in an interview (which I failed) and was asked a problem related to some sort of monotonic queue. I wrote the solution and was going through it, when the interviewer asked: 'what CS concept are you using in this solution'? I didn't really understand what he was asking for and in turn I asked for more clarification like 'Are you referring to the data structures I used? Or the technique (it was some sort of greedy)?' 'no'. After a couple of back-and-forth questions and answers, he finally tells me he was looking for me to say 'a state machine'. Seriously?
You didn't fail that interview. They did.
I've seen people that can talk the talk but not walk the walk and vice versa, they can't articulate well, but their approach and work speaks for itself.
A generic question like "how do you organise data in this situation" is open-ended enough that it merits followups that the interviewee has to drive. If I was being interviewed, I'd ask "what are the operations you want on the data (random lookup vs scan, append, lifo access etc), what performance guarantees you want on those operations, what persistence and distributed fault-tolerance guarantees if any, etc.
It is no different from having to be in front of a client and teasing out what the client really wants. The interviewee has to guide the questions and answer them in a satisfactory way. Reminds of Prof. Manuel Blum (then at Berkeley), whose class project would be "think of a problem and solve it, and you'll be graded on both the quality of the problem and the solution".
The problem lies in the fact that it creates too much ambiguity in terms of how the candidate is evaluated. Some interviewers may give you credit for your approach, but like the parent, more often than not, you’re evaluated on getting to a specific question or direction, in a specific amount of time. And that just creates a bias towards you hiring people who have a chain of thought exactly like you, which may tbh be not correct chain of thought at all.
That's ok, because that's what the software engineering profession is, on the whole, for better or for worse.
But... the interview process should be clear about that, and the questions reflect that. Rather than "how would you build a high performance distributed database" the questions in those cases need to revolve around identifying problems in a design and how benchmarking, diagnostics, bug fixing, etc. would go. Even at the height of VC fever a couple years ago, being blessed with "Hey, here's some $$, go write a [database|operating system|game engine|programming language|other sexy thing]" doesn't happen really (and probably for good reasons.)
So, yeah, GP commenter is a bit disingenuous. There really are only a scant number of jobs which would involve actually being able to do these things, let alone answer how to do them in interview on demand. The jobs that are there are fixing someone else's thing where already they did this stuff.
Said interviewer would likely find a candidate who can answer all those questions... and then hire them to go write some microservices in C# for an insurance company, or join an on-call shift diagnosing production problems with an off the shelf database replication process or something.
Of course, not telling you what you don't already know, just ranting :-)
Most technical interviews are conducted in a completely inane way where the goal is to memorize pieces of information. If that was how software worked, the best engineer would just be Google. 95% of people who know enough to build this system would likely be unable to answer your questions because, more than likely, they do not currently work in a job that requires them to use this information every day. This does not mean they do not understand it or are unable to build it.
The reason why companies can't find people like this is a combination of not understanding what software development is (and not understanding people, it is really the blind leading the blind but technical people are often as bad as interviewing).
You are asking completely wrong questions. You aren't starting from the right place.
Then I'd expect the candidate could articulate her experience and knowledge in some way, no? Otherwise, how would I know the candidate has the built-up expertise? Of course, I assume we can only have interviews. Otherwise, we can have other means, like mini-project, onsite project, or a writeup. Some candidates do like the alternatives more, and some not.
> where the goal is to memorize pieces of information
I disagree. The goal is to see if a candidate does have what the candidate herself claims to know. I find it hard to imagine that a candidate claims to be an expert in a field yet couldn't articulate even one thing in depth for hours if not days, let alone 30 minutes of interview time. Note this is not about any specific details, but the general picture and insights that an expert can convey. This is like a PhD oral defense. The candidate talks about the topic that the candidate is familiar with, and the professors dive in on such topics. I don't see what's wrong with that.
> The goal is to see if a candidate does have what the candidate herself claims to know.
The process you are using does not tell you that. You will notice that your explanation is full of things that you expect, not based in an understanding of how reality actually works. And the result is, unsurprisingly, one where you do not understand the output.
Interviews are a high pressure situation where people want an immediate answer, without much of any time to think, let alone research options or run an experiment. You get people's absolute worst possible results.
https://www.dabeaz.com/raft.html
I'd recommend the course to anyone with development experience working with or near distributed systems. David is a fantastic instructor and facilitator, and the blend of student backgrounds led to some great learning and discussion.
(I have no financial or personal interest here; I just loved the course.)
I experimentally implemented Raft in Java but I am not very confident that I did it correctly.
I wish there was a way to implement stateful programs that guarantee "forward progress" and are "steady state systems". I think essentially a state machine that cannot be trapped in a state. Debugging the absence of something of forward moving progress or lack of causation is very difficult.
When there's essentially different actors in the system and they can interact with eachother by communicating, they each have a number of states they can get into. There's no guarantee that the system shall converge on a state that forward progress can be made. Maybe TLA+ is the right answer here.
YMMV but I think (my) reasoning over stateful systems is rather difficult, I think there's lots of hidden states that we cannot easily detect or reason about because they're in our blind spots. Especially related to synchronization. I think it's part of what makes multithreading and distributed systems so hard, because every component can be in a different state and if something is not where it is expected to be, the baton doesn't get passed to the correct state. If you check for something too early, you have a race condition.
If we could see in slow motion what was going on, an interaction between different actors, we could work out why something happens the way it does. But usually the logs are too numerous to get to this detail. I think animation can save us, but what does a Raft animation look like?
How often have you seen an endless spinner? It's as if a completion event was raised but didn't get detected and the system is waiting for something that shall never occur. I want this kind of error to be impossible. This is one form of hidden state that prevents progress.
I wrote an eventually consistent mesh protocol in Python and tested it with Jepsen, it is not linearizable because the consistency level is "eventually consistent".
I don't understand how Raft can scale writes or reads across multiple machines due to the round trip time talking to other nodes.
Still haven’t found an opportunity to use it professionally though.
These exist to formalize state logic (current state, computing state, transitioning state etc), you can even produce diagrams based on their definitions. Advanced libraries like xstate even have Actors are part of the core of the library
> I don't understand how Raft can scale writes or reads across multiple machines due to the round trip time talking to other nodes.
Is that at the point where that becomes a bottleneck you scale to multiple clusters, where the read/write destination cluster is determined by a key and whatever your preferred hashing mechanism is.
I started a project to implement Raft with a KV-store on top, similar to the article, meaning to use Coyote to test it; I didn't get that far before losing interest, though. It's reassuring to read that it took Phil several months to write the code in the post, it's good to know that this is a decidedly nontrivial problem.
encoding/gob is intended for streams, not stateless marshals/unmarshals. The first thing that is sent over the stream is the type information the receiver should expect, that's why your payload was so large. After the first type is received, subsequent messages are much smaller. You can see this by extending your example to do multiple writes; each write after the first is only 10 bytes: https://play.golang.com/p/Po_iaXrTUER
You have to plan differently, but you could get large improvements to transmission sizes by changing to append only files and creating the gob encoder once per file. If you find you're creating a gob encoder/decoder very often, that's a telltale sign you're not using it as intended.
However, I still keep seeing encoding/gob high up in the profiler taking a lot of time doing reflection during RPC calls.
So it does still seem like it's not ideal. Though I may still just not be understanding how to use net/rpc correctly either.
I don't understand this within the context of the rest of your comment. I use gob for marshaling stuff to storage all the time, I'm not aware of a better way to do that (serialize data to binary).
Here is another raft implementation in Go https://github.com/eliben/raft
In contrast, if you simply use the equivalent of basic (single-decree) paxos per key, the writes can be leaderless. Of course, for performance reasons, each server must batch network and disk i/o.
Is there any writes acknowledgements in what you describe when replication factor > 1?
How do you ensure that I always read the last written value to the same key?
I'm not sure that leaderless mode with basic paxos would be really better in the K/V scenario we're talking about.
There would be a lot of round-trips for each request, so there's higher latency than the raft counterpart, especially for reads. I suppose better availability in the case of node outages would be one advantage.
Anything else I miss?
Now, in many production cases, one tends to put a lease on leader election. Until the lease is valid, the leader is guaranteed that it is still the leader and no one else has a more up to date state. This allows reads to be served from the leader's state machine without having to touch Raft at all.
Another great blog post series about implementig Raft in Go that I found is this one https://eli.thegreenplace.net/2020/implementing-raft-part-0-...
There are a ton of fascinating and potentially frustrating edge cases and gotchas to implementing raft correctly. There's no better way to understand it than actually implementing it, and I probably never would have done it myself without these course materials.
A lot of us tinkered like him, but very few came back and write the findings nicely in an easy to read form.
And I'm sure consul does plenty my silly key-value state machine doesn't.
I'm not super familiar with it.