The big idea

What is a key-value store?

Sometimes you don’t need SQL — you need a giant, always-on dictionary: put(key, value) and get(key), spread across hundreds of machines, that never goes down even when machines do. A single database can’t offer that.

Build a distributed, replicated store with no single master. Spread keys across many nodes, keep several copies of each, and let any node serve a request. The hard part isn’t the dictionary — it’s staying available and consistent while machines fail.

How to read this: We add one piece at a time, problem then fix. This is the Dynamo lineage (DynamoDB, Cassandra, Riak). Watch it grow. Hit Begin.

Step 1 · The skeleton

Any node, one value

A client wants to put and get a key without knowing or caring which of hundreds of machines actually holds it. Routing every request through one master would just recreate the single point of failure we’re trying to avoid. So how does a request find its key?

Design decision: A client must put/get a key across hundreds of machines, and it must never go down. Routing?

The call: Let the client hit any node, which coordinates that request. — Every node runs the same code and can locate replicas and serve the request. No special master means no single failure stops the world — symmetry is the whole philosophy.

Let the client hit any node, which acts as the coordinator for that request: it finds the right home for the key and reads/writes there. Every node can coordinate, so there’s no special, fragile master.

Decentralized by design: Symmetry is the whole philosophy here: all nodes run the same code and play the same role. No master means no single thing whose failure stops the world.

Step 2 · Where does a key live?

Consistent hashing

With hash(key) % N, changing the number of nodes remaps almost every key — a catastrophic reshuffle every time you add or lose a machine. At scale, nodes change constantly.

Design decision: Nodes are added and lost constantly. How do you map keys to nodes?

The call: A consistent-hash ring; a key goes to the next node clockwise. — Adding or removing a node moves only the keys between it and its neighbor — about 1/N of the data, not all of it. Virtual nodes spread that load across many survivors.

Place nodes and keys on a hash ring. A key belongs to the first node clockwise from its hash. Add or remove a node and only the keys between it and its neighbor move — a tiny fraction, not the whole dataset.

Virtual nodes for balance: Give each physical node many points on the ring (vnodes) so load spreads evenly and a departing node’s keys scatter across many survivors instead of dumping onto one neighbor.

Step 3 · Survive a death

Replication

If a key lives on exactly one node, that node’s failure means the key is gone and unreachable. Disks and machines fail constantly at scale — single copies are not an option.

Design decision: Disks and machines fail constantly. Where do you keep each key?

The call: Replicate each key to the next N nodes on the ring. — Three consecutive ring nodes (N=3) each hold a copy, so the key survives up to two failures and reads can hit the healthiest replica. The preference list skips vnode duplicates so copies land on distinct machines.

Store each key on the N nodes following its position on the ring (its “preference list”). With N=3, three consecutive nodes each hold a copy, so the key survives failures and can be read from whichever replica is closest or healthiest.

The preference list: Replicas are just the next N distinct nodes clockwise. Skipping virtual duplicates ensures the copies sit on different physical machines (and ideally different racks).

Step 4 · Consistent or available?

Quorum reads & writes

With three copies, who’s the source of truth? Waiting for all replicas means one slow node stalls every request; trusting one risks reading stale data right after a write. CAP says you can’t have perfect consistency and availability under partitions.

Design decision: With 3 copies, how many do you wait for on a read and a write?

The call: Pick R and W with R + W > N (e.g. 2/2). — When the read set and write set must overlap, every read sees the last write. R=W=2 on N=3 gives strong consistency with one-node fault tolerance — and you can re-tune per workload.

Use a quorum: a write succeeds after W replicas ack; a read consults R. Choose R + W > N and every read set overlaps the last write set — so you always see the latest value. Tune R and W to slide between fast and strongly-consistent.

R + W > N: With N=3, (W=2, R=2) gives strong consistency with one-node fault tolerance. (W=1) favors fast writes; (R=1) favors fast reads. The knobs are yours, per workload.

Step 5 · Two truths

Resolving conflicts

During a network partition, two replicas can each accept a write to the same key. When the partition heals, they disagree — and with W < N this is expected, not a bug. Which value wins?

Design decision: A partition lets two replicas each accept a write to the same key. On heal, who wins?

The call: Version writes; use vector clocks to detect true conflicts. — Vector clocks capture causality, so the system distinguishes a newer write from genuine divergence and can surface both siblings for the app (or a merge function) to reconcile — carts merge, counters add.

Attach version metadata to every write. Last-write-wins (by timestamp) is simple but can drop data. Vector clocks capture causality, detecting true conflicts and surfacing both versions (siblings) for the application — or a merge function — to reconcile.

Make conflicts explicit: In an available system, conflicts will happen. The choice is whether to silently lose data (LWW) or to detect divergence and let the app decide (vector clocks). Carts merge; counters add.

Step 6 · Who’s alive?

Gossip membership

Coordinators need to know which nodes are up and who owns which ring range — but a central membership registry would be another single point of failure and a bottleneck.

Nodes gossip: each periodically exchanges health and ring state with a few random peers. Within seconds the whole cluster converges on a shared view of membership — fully decentralized, no coordinator required.

Epidemic protocols: Information spreads like a rumor — exponentially and resiliently. Gossip needs no central authority and degrades gracefully: a few lost messages just slow convergence slightly.

Step 7 · Heal while degraded

Hinted handoff & read repair

If a target replica is temporarily down during a write, do you reject the write (hurting availability) or accept it and risk that replica permanently missing the update?

Design decision: A target replica is down during a write. Reject the write, or accept it?

The call: Accept it; a healthy node holds a hint and replays it later. — Hinted handoff keeps writes always-succeeding: a stand-in node stores the write and forwards it when the rightful replica returns. Read repair and Merkle-tree anti-entropy converge the rest.

Accept it: a healthy node stores a hint and replays the write to the rightful replica once it returns (hinted handoff). Meanwhile, reads that notice a stale replica push the fresh value back to it (read repair), and background anti-entropy (Merkle trees) reconciles the rest.

Always writable, eventually consistent: These mechanisms let writes always succeed and let replicas quietly converge afterward. Availability now, consistency soon — the core bargain of a Dynamo-style store.

You did it

You just designed a key-value store.

• A — n
• C — o
• E — a
• Q — u
• V — e
• G — o
• H — i