Designing a key-value store
A distributed key-value store answers single-node limits — capacity, throughput, availability, durability — with three layers stacked on top of each other.
- Quorum (N / W / R)
- N = replicas per key; W = replicas that must acknowledge a write; R = replicas consulted on a read. Tuning these trades latency against consistency.
- CAP trade-off
- Under a network partition you can keep Consistency or Availability, not both. Dynamo-style stores choose availability (AP).
Layer 1 — partition
Spread keys across nodes with consistent hashing (lessons 0003–0004), so capacity and throughput scale by adding machines and no single node holds everything.
Layer 2 — replicate
Copy each key to N nodes (the next N distinct servers clockwise on the ring). Now a node loss costs durability nothing, and reads can be served from any replica.
Layer 3 — choose a consistency model
Quorums make consistency a dial. With W + R > N the read and write sets overlap, so reads see
the latest write (strong). Lower W or R for faster, more-available operations that may return
stale data. Most large stores set this for AP: stay up during partitions, reconcile after.
Handling failure
Three primitives keep an AP store honest without a central coordinator:
- Gossip protocol — nodes swap membership and health state peer-to-peer, so there’s no single point of failure tracking who’s alive.
- Hinted handoff — if a target replica is down, a neighbor stores the write and forwards it when the node returns.
- Read repair — on a read, if a replica is found stale, the coordinator writes the current value back to it in the background.
Together these make the Dynamo/AP design the default for session caches and shopping-cart stores, where staying available matters more than a moment of staleness.
Check yourself
1During a network partition, what do DynamoDB and Cassandra choose in CAP terms?
They pick availability + partition tolerance: keep serving reads and writes and reconcile later, rather than blocking during a partition.
2With N replicas, when does W + R > N guarantee a read sees the latest write?
If the write set (W) and read set (R) must overlap (W + R > N), at least one replica in every read saw the most recent write.
3A write's target node is down. What is hinted handoff?
A neighbor holds a 'hint' for the down node and replays the write once it recovers — keeping the write available during the outage.