Interview Case Studies
Design a Distributed Key-Value Store
A store that keeps answering when nodes fail: partitioning, replication, tunable quorums and what to do when two writes collide.
Hard18 min read
By the end of this chapter
- Partition keys with consistent hashing and virtual nodes
- Choose N, R and W and explain what R + W > N does and does not guarantee
- Resolve concurrent writes with last-writer-wins or version vectors, knowing what each loses
- Keep replicas converging with hinted handoff, read repair and anti-entropy
Clarify the requirements
- Functional: get(key), put(key, value), delete(key). Keys are strings; values are opaque blobs up to about 1 MB.
- Functional: consistency is tunable per request, from fast-and-possibly-stale to quorum.
- Out of scope: range scans, secondary indexes, multi-key transactions. Say so; each one changes the design substantially.
- Non-functional: highly available for writes, even while some nodes are down or partitioned.
- Non-functional: grows horizontally by adding nodes, without downtime.
- Non-functional: single-digit-millisecond latency for most requests inside one data centre.
Estimate
| Quantity | Assumption |
|---|
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inYou’ve reached the end
What this chapter was for:
- Consistent hashing means adding a node moves only a small share of keys, and virtual nodes keep that share even.
- R + W > N makes every read quorum overlap every write quorum. It narrows staleness; it does not by itself make the store linearizable.
- Last-writer-wins is simple and silently drops one of two concurrent writes. Version vectors detect concurrency and hand the merge to someone who understands the data.
- Leaderless replication needs background repair, because some replicas will always have missed something.