Case study: Key-value store
Design a Dynamo-style key-value store: a consistent-hash ring, N replicas per key, and R and W quorums that trade consistency for latency and availability.
40 min9 steps
By the end you can
- Size a replicated store by storage and by throughput, including the replication factor
- Explain consistent hashing, virtual nodes and preference lists, and the data moved when a node joins
- Choose N, R and W for a consistency requirement and explain why R + W greater than N gives read-your-writes
- Predict the effect of packet loss, slow replicas and a partitioned coordinator
Requirements
Operations
- put/get/delete; conditional version; typical 1 KB, max 1 MB
Targets
- Single-digit-ms regional p99; tens of TB; 1M ops/s
Availability
- Writes when quorum reachable; tune consistency per request
Estimates
Data
30 TB
10B * 1 KB * N=3
Storage nodes
15
30 TB / 2 TB usable
Throughput nodes
23 minimum
1M * (0.7*2 + 0.3*3) / 100k; plan 30
Join transfer
1 TB
New node 31: about 1/31 of data
API
Read
GET /kv/{key}?consistency=quorum or one; value/version or 404
Write
PUT /kv/{key}; optional If-Match; mismatch 409
Delete
Tombstone; 10-day grace prevents resurrection
Retry
Plain put is idempotent overwrite
Placing keys on a ring
Placement
Hash to ring; next 3 distinct nodes replicate key
Virtual nodes
64 here; spread load and failure ownership
Membership
Small key fraction moves; avoid hash modulo N
High-level design
Order the steps of a put with N = 3 and W = 2.
- 1Coordinator hashes the key to a token on the ring
- 2Coordinator finds the preference list: the next 3 distinct nodes
- 3The third replica applies the write when it arrives
- 4Coordinator sends the write to all 3 replicas
- 5Coordinator acknowledges the client after 2 replicas confirm
Deep dive: quorums
R=2 W=2 N=3
- Overlap; tolerate one failed replica; concurrent writes need versions
R=1 W=3
- Fast reads; fragile writes
R=1 W=1
- Fast; eventual consistency
Boundary
- Overlap alone does not imply linearizability
Alternatives
Weak quorum
- R=W=1 produces stale reads
Leader per shard
- Raft/Paxos linearizability; elections pause writes; minority cannot write
Round robin
- Stuck coordinators still receive half requests
Failure scenarios you can run
Inject
5% loss
Observe
30 ms timeouts; backoff retries
Recover
Idempotent puts succeed; tail grows
Inject
Latency x6
Observe
Spare workers absorb delay
Recover
p99 about x4; below 200 ms deadline
Inject
Coordinator 2 loses ring path but passes health checks
Observe
Stuck connection count rises
Recover
Least-connections steers traffic to coordinator 1
Wrap up
Repair
Hinted handoff, read repair, Merkle anti-entropy
Delete
Tombstones outlive replica outages
Watch
Compaction, hot keys, gray failures; default N=3, R=W=2
Then score each stage from 1 to 4.
Answer this step to continue.