Design a Distributed Key-Value Store
How to design a Dynamo-style key-value store for interviews: partitioning, replication, consistency, gossip, hinted handoff, and CAP trade-offs.
“Design a key-value store” is the interview behind Redis Cluster, DynamoDB, and Cassandra. You are building put/get with huge scale, not SQL joins. It sits under almost every other design — URL shortener mappings, session caches, shopping carts. The difference from “design Redis cache” is durability and multi-node replication as first-class requirements.
Clarify with the framework: value size limits, TTL support, strong vs eventual consistency, and whether range scans are needed (usually no — pure KV).
API
| Operation | Semantics |
|---|---|
| put(key, value) | Write or overwrite |
| get(key) | Return value or not found |
| delete(key) | Remove key |
| Optional TTL | Expire after N seconds |
Requirements
- Scale to billions of keys; horizontal add/remove of nodes.
- High availability — survive node and rack failures.
- Tunable consistency (Quorum R + W > N) or declare eventual.
- Low latency gets (single-digit ms in-region).
Partitioning: consistent hashing
Hash the key onto a ring; each node owns a range. Virtual nodes (many tokens per physical machine) balance load when capacities differ. When a node joins, it takes keys from neighbors — same story as distributed cache and sharding. Mention virtual nodes unprompted — interviewers listen for it.
Hot keys
A celebrity key still hashes to one partition. Mitigate with client-side cache, key salting (`key#0..N` fan-out), or request coalescing. Same celebrity problem as news feed.
Replication
Store N replicas (commonly 3) on the next N distinct nodes on the ring (or preference list). Writes go to the coordinator (first node in preference list or any node that forwards). Coordinator sends put to replicas; waits for W acknowledgments. Reads query R replicas and return the latest by version.
- N = 3, W = 2, R = 2 → quorum; strong-ish consistency for single key.
- W = 1, R = 1 → fastest, eventual; conflict resolution needed.
- R + W > N avoids reading stale unreplicated writes in the common case.
Versioning and conflicts
Vector clocks or monotonic version numbers per key detect concurrent writes. On conflict, return both values to the client (Dynamo style) or last-write-wins with timestamp (simpler, riskier). For interviews, vector clocks show depth; LWW is acceptable if you name the data-loss risk. Tie to CAP: AP store with conflict resolution vs CP store that rejects writes on minority.
Failure handling
| Technique | Purpose |
|---|---|
| Sloppy quorum / hinted handoff | Write to another node if replica down; hand hint back when it recovers |
| Read repair | On get, fix stale replicas in background |
| Anti-entropy / Merkle trees | Periodic sync between replicas |
| Gossip membership | Nodes share ring membership and failure rumors |
You do not need to implement Merkle trees on the whiteboard — name anti-entropy and move on. Gossip for membership beats a single ZooKeeper if you are designing Dynamo-style AP; CP systems often use consensus (Raft) for membership — mention both camps.
Storage engine on one node
Each node is a local store: LSM-tree (Cassandra, RocksDB) for write-heavy workloads, or B-tree / memory + disk. WAL for durability before ack. Memory cache of hot keys. Interview level: “log-structured merge tree on SSD + memtable” is enough.
Client vs server routing
- Smart client: knows the ring, talks to the right node (lower hop).
- Dumb client: any node coordinates and proxies (simpler clients).
- Proxy tier: API gateway-like KV proxy for auth and rate limits.
Comparison table
| System | Consistency bias | Notable idea |
|---|---|---|
| Dynamo / Cassandra | AP, tunable quorum | Preference list, hinted handoff |
| etcd / ZooKeeper | CP | Raft/ZAB consensus |
| Redis Cluster | AP-ish cache | Hash slots, async replica |
| Bigtable / HBase | CP per row | Tablet servers + Chubby/ZK |
Capacity math
1 billion keys × 1 KB value ≈ 1 TB raw; with N=3 ≈ 3 TB plus LSM overhead. 100K QPS reads with R=1 is easy; R=2 doubles read fan-out. Always state N, R, W when estimating cluster size.
Worked put/get
- put("user:42", "{…}") → hash → preference list nodes A,B,C.
- Coordinator A writes WAL + memtable, forwards to B and C, waits W=2.
- Ack client after 2 acks; C may still be catching up.
- get → query A and B (R=2); compare versions; return newest; async repair C if stale.
TTL and deletion
Lazy expiry on get (check timestamp) plus a background sweeper scanning tombstones keeps disk bounded — same dual approach as Pastebin expiration. Deletes write a tombstone so replicas do not resurrect keys via anti-entropy. Compact tombstones after a grace period.
Secondary indexes are out of scope for pure KV. If the interviewer asks “query by value,” say that breaks the model — use Elasticsearch beside the store, or accept full scan. Stay disciplined about the API.
Put path deep dive
Coordinator receives put, appends to local WAL, updates memtable, then parallel RPCs to replicas. If only W−1 replicas ack before timeout, you can still ack the client under sloppy quorum and repair later — or fail the write for stricter modes. Spell out which mode you choose. Checksums on values catch bit rot during anti-entropy. Compression (LZ4) on cold SSTables saves disk at CPU cost.
Security and multi-tenancy
- Namespace keys as `tenant:key` or separate rings per tenant for noisy isolation.
- Auth at the proxy; encrypt values at rest with per-tenant keys if required.
- Rate-limit puts per API key so one writer cannot fill the cluster (rate limiter).
What to say in 45 minutes
Ring + virtual nodes, N replicas, quorum R/W, version vectors, hinted handoff, anti-entropy. Contrast with single-node Redis cache: cache can flush; KV store promises durability. That contrast is the interview.