Design a Distributed Key-Value Store
The store has to stay writable while nodes fail and keep reads in single-digit milliseconds across 100 nodes. The design follows Dynamo: a hash ring for placement, quorums you can tune, and background repair that heals replicas after a failure.
1 · Requirements
The Prompt
Design a Dynamo-style key-value store that holds 100 TB, stays writable when nodes fail, and serves reads in single-digit milliseconds.
Functional
- Put, get, and delete values by key
- Choose consistency per request: one replica, a quorum, or all
- Add and remove nodes without downtime
Non-Functional
- Writes succeed while any 2 of a key's 3 replicas are up
- Reads and writes return in under 10 ms at p99
- Scales to 100 TB of data and 600,000 requests a second
2 · Estimates
Drill This Phase First
Show the Answer and Estimates
Answer
About 100 nodes
3 replicas make 300 TB on disk. Each node holds 3 TB at 75% full, and 300 divided by 3 is 100 nodes.
- Data
- About 100B keys at 1 KB each: 100 TB logical, and 300 TB on disk with 3 replicas
- Nodes
- 4 TB of SSD per node kept 75% full holds 3 TB, so about 100 nodes
- Traffic
- 500,000 reads and 100,000 writes a second at peak
- Per Node
- Writes go to all 3 replicas and reads ask 2: about 300,000 replica writes and 1M replica reads a second, or 3,000 writes and 10,000 reads per node
- Bloom Filters
- 10 bits per key on every replica: about 375 GB across the cluster, under 4 GB of memory per node
- Rebalancing
- A new node takes about 1% of the data, roughly 3 TB. Throttled to 100 MB a second, it is ready in about 8 hours
3 · API
PUT /kv/:key { value, context? } → { version } (waits for W acks)
GET /kv/:key?consistency=one|quorum|all → { value, version }, or { siblings[], context } when versions conflict
DELETE /kv/:key { context } → 204 (writes a tombstone)
GET /admin/ring → { nodes[{ id, tokens[], status }] } (this node's gossip view)Data Model
ring (gossiped to every node):
node_id : string
tokens : list<uint64> 256 virtual nodes
status : enum(up|suspect|down|joining|leaving)
record (per replica, LSM storage engine):
key : bytes, up to 1 KB
value : bytes, up to 1 MB
version : vector clock { node_id: counter }
tombstone : bool
written_at : timestamp
hints (coordinator's local disk):
target_node : string
key, value, version4 · High-Level Design
5 · Deep Dives
Partitioning and Replication
Hash each key onto a ring and store it on the next 3 distinct nodes clockwise. Give each server 256 virtual nodes, so load stays even and a new server takes a thin slice from every peer. With mod N hashing, adding one server would move almost every key.
Quorums and Conflicts
With N = 3, writing to 2 replicas and reading from 2 guarantees the read overlaps the latest write, since R + W > N. Setting W to 1 makes writes faster, and a single failure can then lose one. Concurrent writes carry vector clocks: the store returns both versions as siblings for the client to merge, or applies last-write-wins where losing an update is acceptable.
Healing Failures
Nodes learn about each other's health through gossip, with no central master. When a replica is down, the coordinator writes to the next healthy node with a hint and hands the data back when the owner returns. Reads repair stale replicas on the spot, and a background job compares Merkle trees per key range and syncs only the ranges that differ.
6 · Wrap Up
The Short Version
Consistent hashing with virtual nodes spreads keys, and each key lives on 3 replicas. Quorum reads and writes (R + W > N) set consistency, vector clocks resolve conflicts, and hinted handoff, read repair, and Merkle tree sync heal replicas.