9 ms·
Implementing a distributed key-value store on top of implementing Raft in Go
- Xeoncross 3y agoThese kinds of posts are my favorite part of HN. The deep dives into LLM's, state machine theory, fourier transforms, locking data structures, and memory allocation that is miles above the basic posts around the internet you get with searching - but not quite a full book yet. The author spent 7 months tinkering and cared enough to come back and share that with us.
- beoberha 3y agoPhil rocks. Highly suggest following him on twitter. He’s pretty outspoken about writing. This is a great post of his that I need to reflect on more: https://notes.eatonphil.com/is-it-worth-writing-about.html https://notes.eatonphil.com/is-it-worth-writing-about.html
- eatonphil 3y agoGlad that post resonated! <3
- quaintdev 3y agoI wish there was a separate catalog of these posts which I could browse through.
- mptest 3y agoWe need Hacker Hacker news, with the more serious tech related posts too techie for hacker news. 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
- fredski42 3y agoHere is nice interactive and visual representation of how raft works: http://thesecretlivesofdata.com/raft/ http://thesecretlivesofdata.com/raft/
- infamousclyde 3y agoThis was really great, thank you so much for sharing.
- thinkharderdev 3y agoThat's really cool!
- yi_xuan 3y agoRecently, I have been watching the course MIT6.824. This article appeared very timely :) Here is another raft implementation in Go https://github.com/eliben/raft https://github.com/eliben/raft
- leetrout 3y agoSo kinda like "build your own consul"
- eatonphil 3y agoI'm pretty sure consul builds on top of hashicorp's Raft implementation so I'd say end result, yes, but that this post goes into the Raft implementation. And I'm sure consul does plenty my silly key-value state machine doesn't. I'm not super familiar with it.
- roncesvalles 3y agoReminded me of etcd, which is exactly this - Raft-based key-value store written in Go. https://github.com/etcd-io/etcd https://github.com/etcd-io/etcd
- restlake 3y agoCool post. Wonder if it would have helped to take a look at the MIT distributed systems course on the web and YouTube - one of the projects is exactly this (Go Raft implementation) https://pdos.csail.mit.edu/6.824/labs/lab-shard.html https://pdos.csail.mit.edu/6.824/labs/lab-shard.html
- siftrics 3y agoThis is essentially do-it-yourself etcd. https://github.com/etcd-io/etcd https://github.com/etcd-io/etcd
- esafak 3y agoAnd tidb
- moderation 3y agoTIKV [0] is closer (written in Rust). 0. https://github.com/tikv/tikv https://github.com/tikv/tikv
- didip 3y agoBig fan of Phil! A lot of us tinkered like him, but very few came back and write the findings nicely in an easy to read form.
- eatonphil 3y agoGlad to hear it! :)
- samsquire 3y agoThank you for the write up eatonphil. 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.
- qznc 3y agoI think you should try TLA+. I found it surprisingly easy: https://beza1e1.tuxen.de/tla-plus.html https://beza1e1.tuxen.de/tla-plus.html Still haven’t found an opportunity to use it professionally though.
- thdespou 3y agoIt's not easy. if it was easy, everyone would be using it. I think it's more like thought provoking.
- hintymad 3y agoA side topic: how can a company find people like the author, who can really articulate how to build a system? I've been interviewing senior engineers for years, and more than 95% of them, if not more, are really box drawers. They throw terms around confidently but fail miserably the moment I ask for specifics. No, I don't ask for details like how Raft works. That level of details probably would fail all the candidates. Just simple things like how you organize the data, how you route the traffic, how you manage metadata, or how your data path keeps metadata in sync. Really basic ones, yet most interviewers fail. Indeed, the more senior they are, the more likely they lose touch of the details -- even those who claim to work on distributed databases.
- qznc 3y agoYou find them via their blogs.
- bombela 3y agoWhere do you find the jobs where people actually care about engineering? Because real work is mostly careful plumbing without breaking what works, but in interviews you must leetcode. Real systems only work when kept reasonably simple, but system design interviews are all about drawing boxes.
- BossingAround 3y agoI recently interviewed with a company, and the interviewer asked me "how do you organize data." I wasn't sure if they wanted to talk about classes, modules, databases, k-v stores, hashing data and routing distributed requests to the same pods. I asked, and they answered "I mean in general, how do you organize data." 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.
- no_wizard 3y agoI would have halted for a moment and asked something like: organize data for what purpose? At which point I would expect there to be some amount of clarification. As it sounds to me like they're talking about organizing some set of data for lookup, as opposed to organizing data around how it flows through an application, for example
- bit_flipper 3y agoYour note about encoding/gob being inefficient is somewhat accurate for how you're using it, but I want to talk a bit about how you could improve your use. 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 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.
- eatonphil 3y agoAnother thing I glossed over (unintentionally) is that I only started limiting batch size after I switched to the custom encoder. So persist() being a function of length wouldn't be quite true anymore. 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.
- candiddevmike 3y ago> encoding/gob is intended for streams, not stateless marshals/unmarshals 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).
- bit_flipper 3y agoSorry, I should have been more precise. encoding/gob is not optimized for situations where you create an encoder or decoder, read/write a single value, then discard that encoder/decoder. As the author noted, payloads for a single call to Encode() are quite large. Additionally, re-instantiating a gob encoder for each call to Encode() is very expensive allocation-wise and benchmarks where this happens will show gob to perform poorly in these scenarios. You can certainly still use gob this way, and if the performance works for you then have at it! But it performs significantly better in situations where you make multiple calls to Encode() with the same encoder.
- cheeseprocedure 3y agoI was lucky enough to take David Beazley's "Rafting Trip," a five-day training course that guides each student through building their own Raft implementation from scratch: https://www.dabeaz.com/raft.html 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.)
- broken8ball 3y agoOut of curiosity, did you register as an individual? And if so, do recall how much the course cost you? His courses seem very interesting.
- cheeseprocedure 3y agoYes, I registered as an individual (but was reimbursed through my employer's training budget), and did so a few months in advance as the previous session seemed to fill up pretty quickly. It was USD$1500 for the week. I'm keeping an eye on his course listing too - I'd love to take more.
- powerset 3y agoI highly recommend MIT open courseware 6.824. Incredibly valuable for learning distributed systems, and one of the lab assignments is implementing raft in Go. http://nil.csail.mit.edu/6.824/2022/schedule.html http://nil.csail.mit.edu/6.824/2022/schedule.html 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.
- rochak 3y agoUnfortunately, I hit a roadblock while implementing the Raft assignment. I knew it was simply beyond my capabilities but would have made through if I had anyone I could reach out to. I second this recommendation, but make sure you know what you are signing up for. This course is as hard as they come.
- valzam 3y agoI have found the performance tests very tricky to get to pass without having any input from others. The assignment is really very unforgiving, I would wager the test suite is comparable to how commercial Raft implementations are tested (e.g. https://github.com/hashicorp/raft https://github.com/hashicorp/raft)
- geospeck 3y agoThanks for the post! 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-introduction/ https://eli.thegreenplace.net/2020/implementing-raft-part-0-...
- eatonphil 3y agoYes I definitely referred to his posts and project while working on this. I'm a big fan of his blog!
- dotnwat 3y agoepic
- sriram_malhar 3y agoI think that in the specific case of a key-value store (with just a get/put API), there is a more scaleable way to get consensus than putting a KV store on Raft. Raft (and multi-paxos) present a shared log abstraction, which is good if you want to impose a single ordering (what a replicated state machine needs). But writes to different keys are order independent, and you don't need ordering (between keys) to get a linearizable kv store. By going through raft or multi-decree paxos or VS replication, you pay a penalty for ensuring that all writes are sequentialised via the log. The penalty includes having to go through a single leader for all reads and writes, and lots of jitter when a leader fails up until the new leader becomes stable. 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.
- alexandre_m 3y ago> if you simply use the equivalent of basic (single-decree) paxos per key, the writes can be leaderless 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?
- sriram_malhar 3y agoBoth reads and writes go through the basic paxos protocol, so the answer to both is yes.
- alexandre_m 3y agoI've never taken the time to really learn paxos in depth, so forgive my ignorance. 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?
- 3y ago