Deep Dive
system design interviewdatabasesalgorithmsconcurrency

Design a Key-Value Store

The capstone that ties the whole series together: consistent hashing to place data, quorums to tune consistency, vector clocks to detect conflicts, and hinted handoff to stay writable through failure. This is Amazon's Dynamo, rebuilt from its four moving parts.

·23 min read
Hard
Asked atAmazonNetflixUberLinkedInMeta

This is the design that every other distributed-systems idea plugs into. Build a key-value store that never says no to a write — always available, horizontally scalable, no single coordinator — and you end up re-deriving Amazon’s Dynamo, the paper that shaped Cassandra, Riak, and DynamoDB.

Two operations, four hard problems

The API is trivial; the interview is the four problems hiding behind it:

The questions
  • Where does a key live? (placement)
  • How many copies, and where? (replication)
  • How fresh must a read be? (consistency)
  • What happens when a node is down? (failure)
Dynamo's four answers
  • Consistent hashing — a ring of nodes
  • N replicas on the next N nodes clockwise
  • Quorums: R + W > N tunes consistency
  • Hinted handoff + Merkle-tree repair

The one inequality at the heart of it

Each key is stored on N nodes. A write waits for W acknowledgements; a read gathers R responses. That’s it — and the relationship between those three numbers is the entire consistency story:

overlapput(k,v)wait for W=2 acksReplica AwrittenReplica Bwritten · readReplica Creadget(k)wait for R=2
N=3 replicas for a key. With W=2 and R=2, the write set and read set are forced to share at least one node (R + W > N), so any read sees the latest acknowledged write. Slide R or W down and the guarantee disappears — you trade consistency for lower latency and higher availability.

R + W > N guarantees the read and write sets overlap on at least one node — the pigeonhole principle doing consistency’s heavy lifting. Set R=W=1 and reads are lightning fast but may be stale; set W=N and writes are durable but block on your slowest replica.

The members-only build assembles the whole store: an interactive quorum explorer where you drag N, R, W and watch the consistency guarantee appear and vanish, the ring that places and replicates keys, vector clocks that tell a stale write from a genuine conflict, hinted handoff that keeps you writable when a node dies, Merkle trees that repair divergence cheaply, and the CAP framing that explains why Dynamo chose availability.

Members only

Keep reading with Premium

You've reached the members-only part of this deep-dive — the full implementation, the interactive ring simulator, and the step-by-step walkthrough. Unlock it with a membership.

Go PremiumAlready a member? Sign in