System Design Lab›System Design Questions›Design Distributed Key-Value Store
Design Distributed Key-Value Store
HardDatabaseskey-valuedistributedhashingreplicationconsistency🟠 Amazon
Question Overview
Design a Dynamo-style key-value store that stays writable through node failures and network partitions. The core challenges are partitioning keys with consistent hashing, tuning quorum reads and writes, resolving concurrent updates, and repairing replicas that drift apart.…
Sign up to see the full question and AI interviewer
Requirements
- get(key) and put(key, value) for values up to 1 MB, plus delete and optional TTL
- Tunable consistency per request via replication factor N, read quorum R, and write quorum W
- Detect concurrent writes and return siblings or resolve them with a documented policy
- Always writable: accept writes when some replicas are down or partitioned away
- Add or remove nodes online, moving only a proportional share of the data
- p99 under 10 ms in-region; acknowledged writes survive the loss of any single node
Back-of-the-envelope numbers
- Logical data: 50B keys × ~1.1 KB (1 KB value plus key and version metadata) ≈ 55 TB
- Raw storage: 55 TB × 3 replicas ≈ 165 TB, × ~1.3 LSM space amplification ≈ 215 TB on disk
- Nodes: 215 TB ÷ 2.4 TB usable per node (4 TB NVMe kept 60% full for compaction headroom) ≈ 90 nodes
- Client traffic: 400K reads/s and 100K writes/s average → 1.2M reads/s and 300K writes/s at 3× peak
- Replica fan-out at peak: 300K writes × N = 3 → 900K replica writes/s; 1.2M reads × R = 2 → 2.4M replica reads/s ≈ 27K per node
- Write bandwidth at peak: 300K × 1 KB × 3 replicas ≈ 900 MB/s cluster-wide ≈ 10 MB/s per node, ~100 MB/s of disk writes after ~10× compaction amplification
- Rebalancing: a new node takes ~1/91 of the data ≈ 2.4 TB streamed from many vnode peers; at 200 MB/s that is ≈ 12,000 s ≈ 3.3 hours
Key components
- Consistent hashing ring with virtual nodes (e.g. 256 tokens per host) so load spreads evenly and rebalancing pulls data from many peers
- Preference list: the N distinct physical nodes clockwise from the key's token, spread across racks or availability zones
- Request coordinator: fans out to the N replicas, returns after W write acks or R read responses, and read-repairs stale replicas
- Sloppy quorum with hinted handoff: a healthy stand-in node stores writes for a down replica and replays them when it recovers
- Versioning: vector clocks that return siblings for the client to merge, or last-write-wins timestamps where losing a concurrent write is acceptable
- Anti-entropy and membership: per-range Merkle trees so replicas stream only differing subranges, plus gossip with a phi-accrual failure detector
- LSM storage engine: commit log, in-memory memtable, immutable SSTables with bloom filters, background compaction, and tombstones for deletes
Common mistakes
- Using hash(key) mod number_of_nodes, which remaps almost every key when a single node is added or removed
- Claiming R + W > N makes the store linearizable; sloppy quorums, hinted handoff, and concurrent writes still allow stale or conflicting reads
- Relying on wall-clock last-write-wins without admitting that clock skew silently discards one of two concurrent writes
- Physically deleting keys instead of writing tombstones, so anti-entropy resurrects deleted data from a replica that missed the delete
- Placing all N replicas on virtual nodes owned by the same physical host or rack, which defeats the replication factor
- Sizing disks from logical data alone, ignoring replication, LSM space amplification, and compaction write amplification
Likely follow-ups
- How would you support a strongly consistent compare-and-set on a single key without giving up availability for other operations?
- With N = 3 and W = 2, what happens to writes during a partition that leaves only one replica reachable?
- How would you handle a single hot key receiving 100K reads per second?
- How would you add 20 nodes without saturating the network or hurting foreground latency?
- How would you replicate across three regions, and what R and W would you choose per region?
- How do you keep vector clocks from growing without bound?
No community solutions yet
Be the first to publish your solution
Practice ‘Design Distributed Key-Value Store’ with an AI Interviewer
Get scored feedback on your diagram, scalability approach, and trade-offs. Free while we grow — up to 3 full interviews a day.