Distributed Key-Value Store

In plain words

A key-value store is the simplest database there is — put(key, value) and get(key) — spread across many machines so it survives any one of them dying. The hard part is not storing bytes; it is deciding what a reader is promised when the copies disagree. This problem is where the words "consistency", "replication" and "quorum" stop being vocabulary and become dials you set.

The shape of the problem

Every other problem in this library says "and then we store it in a distributed key-value store". This is that store. It is the hardest of the three because there is no way to answer it without taking an explicit position on consistency (what a reader is promised about how fresh the value is) — and the position you take changes the design.

Four decisions, in order:

1. Placement — which node owns a key?
2. Replication — how many copies, and where?
3. Consistency — what does a read guarantee?
4. Failure — what happens when a replica or the network is gone?

Placement: consistent hashing

The naive answer, hash(key) % N, is a trap. Change N from 10 to 11 and roughly 90% of keys move to a different node. You cannot add capacity without a full reshuffle.

Consistent hashing puts both nodes and keys on a ring. A key belongs to the first node clockwise from its hash. Adding a node steals one arc from one neighbour, so only about 1/N of keys move.

The refinement that makes it actually work is virtual nodes: each physical node is placed at 100–200 points on the ring instead of one. Without them, random placement leaves some nodes owning huge arcs and others owning slivers, and a node leaving dumps its entire load onto a single neighbour rather than spreading it.

Replication and quorums

A quorum is the minimum number of copies that must agree before an operation counts as done. The trick below is to make that number a setting.

Store each key on the next N distinct physical nodes clockwise (distinct matters — virtual nodes mean the next three ring positions could be the same machine). Then let the caller choose:

• W — replicas that must acknowledge a write.
• R — replicas that must respond to a read.

If R + W > N, the read set and the write set always overlap, so a read is guaranteed to see the newest committed write. With N=3:

• W=1, R=1 — fastest, no overlap guarantee, eventually consistent: the copies will agree, but a read right after a write may still return the old value.
• W=2, R=2 — the usual default: strong-ish consistency, survives one node down.
• W=3, R=1 — fast reads, but a single node down blocks all writes.

This is the CAP tradeoff made into two tunable dials rather than a fixed property of the system.

Conflicts

With W=2 and concurrent writes to the same key, two replicas can disagree. Three ways to settle it:

• Last-write-wins by timestamp. Simple and lossy — clock skew silently discards a real write. Fine for caches and session data.
• Vector clocks. A version stamp per replica, so the store can tell "newer" from "written at the same time". Detect that two versions are genuinely concurrent rather than ordered, and hand both to the client to merge. Correct, but pushes real complexity onto every caller.
• CRDTs (conflict-free replicated data types). Data types that merge deterministically by construction — apply the changes in any order and every copy ends up identical. Excellent when your value fits one (counters, sets); not general.

Failure handling

• Hinted handoff (in the diagram): a healthy node accepts writes destined for a down node and replays them on recovery. This is what keeps writes available during a short failure.
• Merkle trees / anti-entropy: replicas compare hash trees (a hash of each chunk, then a hash of the hashes, up to one root) of their key ranges to find divergence cheaply, without streaming the whole dataset, and repair it.
• Gossip: nodes exchange membership and health with a few random peers each second. Failure detection with no central monitor and no single point of failure.

Where this design breaks

• Hot keys. Consistent hashing distributes keys evenly, not traffic. One viral key still lands on N nodes and can saturate them.
• Large values. The design assumes small values. Multi-megabyte values make replication bandwidth, not storage, the binding constraint.
• Range scans. Hash placement destroys key ordering, so "all keys between X and Y" means asking every node. If you need ranges, you want range partitioning and its hot-spot problem instead.
• Cross-key transactions. Two keys can live on disjoint node sets, so there is no atomic multi-key write without a coordination protocol this design does not have.
• Clock skew. Two machines' clocks never agree exactly. Any last-write-wins scheme is only as trustworthy as NTP, the protocol that keeps them in sync — good to milliseconds, not microseconds.

Take this with you

• The one idea: placement, replication, consistency and failure are four separate decisions. Make each one on purpose.
• In an interview, draw the ring, say "N copies, W to write, R to read, R + W > N for fresh reads", and name one way to settle conflicts.
• At work, check what W and R your store actually runs with. The default is often the fast one, and "we read our own write back" is not guaranteed there.