Member-only story
Airbnb Staff Interview: Designing a Distributed Key-Value Store
This is one of those interview questions that looks simple on the surface — “design a key-value store” — and then quietly murders you with its depth. I’ve seen engineers at senior and staff level stumble on this not because they lacked knowledge, but because they didn’t connect the dots between storage internals, distributed systems theory, and the very specific constraints baked into the problem.
Let’s walk through it properly. Not as a checklist, but as a story.
Start by Respecting the Constraints
Most candidates treat constraints as footnotes. They say “we’ll shard by key” and move on. But three constraints here are load-bearing walls, not decorations.
Append-only writes mean you can never modify a file in place. Every update is a new write at the end of a log. Strong consistency means reads must always reflect the latest committed write, even during failures and even from a different server. And values up to 2GB mean you cannot buffer the full value in memory — not on writes, not on reads.
These three together eliminate a huge swath of obvious designs. No in-place hash tables. No loading everything into Redis. No hand-waving about eventual consistency.
