Interview Walkthrough: Design a Distributed Key-Value Store

You now know every mechanism. This section is about delivery — the order to present them, what to say at each step, and how to fit it in 45 minutes without either rushing or rambling.

Step 0 — Scope it before you design

• What are we storing, and how big are the values?
• What scale — number of keys, request rate, number of servers?
• Is this single-region or global?
• Do we need to always accept writes, or is it acceptable to reject during a partition? — the question that decides the whole design.
• Do clients tolerate reading stale or conflicting data?
• Is the hardware fleet uniform?

Then commit:

"I'll design an always-writable store — availability over consistency — with values in the kilobyte range, tens of thousands of servers, and a heterogeneous fleet where machines have different capacities. Clients can tolerate occasional conflicting reads if we give them a way to reconcile. Let me size it and then build up from partitioning."

Step 1 — A quick BOTEC

Keys                = 100 billion
Average value size  = 1 KB
Replication factor  = 3

Raw data     = 100B * 1 KB          = 100 TB
Replicated   = 100 TB * 3           = 300 TB
Per node at 16 TB usable            = ~19 nodes minimum for storage

Request rate = 1M ops/sec
Per node     = ~10,000 ops/sec      -> ~100 nodes for throughput

"Throughput needs about 100 nodes, storage about 19 — so this is request-bound, not storage-bound. That tells me partitioning is about spreading load, not just data, which makes even distribution the thing to get right."

Step 2 — Requirements

Functional: configurable consistency · always writable · hardware heterogeneity. Non-functional: scale to tens of thousands of servers with incremental growth · fault tolerance.

Say the consequence out loud:

"'Always writable' means choosing A over C in CAP. That's not a detail — it means I'll be accepting conflicting writes and I'll owe you a reconciliation story later. Let me flag that now so it doesn't look like an afterthought."

Step 3 — API

get(key)                    -> value(s) + context
put(key, context, value)    -> success

"Two operations. The interesting part is that get can return multiple values — under an always-write requirement, two clients can write concurrently to different nodes and both have to survive. The context carries version metadata so the client can hand it back on the next write."

Introducing context here, before you have explained vector clocks, is deliberate — it tells the interviewer you already know where this is going.

Step 4 — Partitioning, built up in three moves

This is the narrative core. Do not jump to the answer.

(a) The naive attempt.

"Simplest partitioning is hash(key) % m. It distributes evenly — and it fails our incremental-scalability requirement, because changing m changes the mapping for nearly every key. Adding one node triggers a cluster-wide reshuffle."

(b) Consistent hashing.

"So: a hash ring. Nodes and keys both hash onto positions from 0 to n-1, and a key belongs to the first node clockwise. Adding a node now only takes keys from its immediate successor — everyone else is untouched."

(c) Virtual nodes.

"But random ring positions leave uneven gaps, and a node owning a large arc becomes a hotspot. So each physical machine takes many positions via different hash functions. Three wins at once: distribution smooths out, a failed node's load spreads across many successors instead of doubling one neighbor, and I can give a bigger machine more virtual nodes — which satisfies the heterogeneity requirement."

Step 5 — Replication

"Peer-to-peer, not primary-secondary — a primary failing would block writes, and we said always writable. The coordinator for a key replicates to the next n-1 successors on the ring; that list is the preference list. One subtlety: because of virtual nodes, consecutive ring positions can map to the same physical box, so the preference list has to skip duplicates or all three replicas land on one machine."

Step 6 — Versioning

"Now the bill for always-writable. During a partition both sides accept writes and diverge. I can't order them by timestamp because clocks drift — so I track causality with vector clocks: a list of (node, counter) pairs per version. If every counter in one clock is at most the other's, it's an ancestor and I discard it. Otherwise they're concurrent, and I return both to the client to reconcile — same model as a Git merge conflict."

Step 7 — Configurability

"r + w > n so the read and write sets overlap. With n=3, 2/2 is a sensible default; a cart would run w=1 to never reject a write and pay with r=3. Read latency is the slowest of the r replicas, not the average — so raising r is expensive at the tail."

Step 8 — Fault tolerance

"Two cases, two mechanisms. Temporary: sloppy quorum takes the first n healthy nodes, and hinted handoff parks the write with a note saying who it belongs to, forwarding it when the owner returns. Permanent: Merkle trees — exchange root hashes, and if they match, gigabytes are proven identical in one comparison; if not, recurse to find exactly which keys differ. And gossip for membership, so there's no coordinator to be a special node."

The finished picture

Deep Dives & Follow-up Questions

"Two clients write the same key at the same instant. What does a subsequent read return?"

Both versions, with their vector clocks. Neither clock dominates the other — each has a counter the other lacks — so they're concurrent, which is the definition of a conflict. The store can't decide which is right because it doesn't know what the value means, so it hands both to the client with the context. The client reconciles and writes back a merged version whose clock subsumes both. For a shopping cart that merge is a union, which loses nothing; for a counter it's genuinely ambiguous, which is a good reason not to store counters this way.

"Vector clocks grow forever. Doesn't that break?"

They can grow when writes land outside the top n nodes, which happens during partitions or multiple failures — you end up with a dozen (node, counter) pairs. The fix is truncation: attach a physical timestamp to each entry and drop the oldest once you exceed a threshold, say ten. The honest cost is that truncation removes causal history, so the system can misjudge ancestry and report a false conflict. That's the safe direction to err — a spurious conflict is annoying; missing a real one loses data.

"A node is down. Walk me through a write."

Sloppy quorum: instead of insisting on the designated owners, I take the first n healthy nodes from the preference list. If A is down, D takes the write and stores a hint recording that it belongs to A. When A recovers, D forwards the data and deletes its copy. The cost is that during the outage the read and write sets may not overlap, so r + w > n doesn't actually hold — I've traded the consistency guarantee for staying writable, which is what the requirement asked for.

"How do you know a node is down rather than slow?"

I don't, and I've designed so I don't have to decide quickly. Peers infer death from silence past a threshold, but the system deliberately doesn't rebalance on that signal, because most outages are transient and rebalancing means recomputing Merkle trees and moving data — expensive work to redo when the node reboots. Hinted handoff keeps us writable in the meantime, which buys the patience. Ring membership only changes on a confirmed sustained failure or a planned change.

"A node was replaced after a week. How does the new one catch up?"

Anti-entropy with Merkle trees. Each node keeps a hash tree per key range: leaves are hashes of individual values, parents hash their children. Two nodes exchange root hashes — if they match, the ranges are identical and we're done in one comparison regardless of data size. If they differ, we recurse down only the differing subtrees, so locating divergence is logarithmic rather than a full scan. Then we transfer only the keys that actually differ.

"Where does this design lose data?"

Three places, and I'd name them unprompted. With w = 1, an acked write on a node that dies before replicating is gone. Vector clock truncation can lose causal history and cause a bad merge. And a sloppy-quorum write held as a hint on a substitute node is lost if that substitute dies before handing off. All three are consequences of choosing availability — a CP design would trade them for rejected writes instead. Which is right depends entirely on whether a lost cart item or a rejected checkout is worse for the business.

"How would you make this strongly consistent?"

I'd stop building this. Strong consistency means a single writer per key with consensus — Raft or Paxos on the write path — so writes are ordered and conflicts can't arise. That removes vector clocks, reconciliation, and sloppy quorums entirely, and costs a consensus round trip per write plus write unavailability during leader election. It's a genuinely different system, not a configuration of this one, which is why "is this always-writable?" belongs in the first two minutes.

Now do it live

The next section drills these as standalone probes.