System Design · Medium
Design a distributed key-value store
Build a linearly scalable, fault-tolerant KV store with consistent hashing, replication, and tunable consistency.
Requirements
What the system must do, and how well it must do it.
Functional
Put, get, and delete keys with byte-array values (up to 1 MB).
Support strong consistency (quorum reads/writes) and eventual consistency.
Automatically rebalance when nodes join or leave.
Provide a simple client library with retries and timeout handling.
Non-functional
99.99% availability for single-key operations.
p99 latency under 10 ms for gets, 20 ms for puts.
Linear scalability: double the nodes, double the throughput.
Survive simultaneous failure of any two nodes.
Estimation
Back of the envelope numbers that drive the design.
1 TB data, 3x replication = 3 TB raw. 10 nodes × 300 GB each.
100K ops/sec per node, 1M ops/sec cluster-wide.
Consistent hashing ring with 256 virtual nodes per physical node.
Hinted handoff + anti-entropy repair for durability.
Architecture
Design decisions
Partitioning
Consistent hashing maps keys to a ring. Each physical node owns multiple virtual nodes (vnodes) for better load distribution. The default replication factor N=3 means each key is stored on the next N nodes clockwise. The coordinator can be any node (client-side or a thin proxy); it routes the request to the primary and replicas.
Consistency levels
Write succeeds when W replicas acknowledge; read succeeds when R replicas respond. Strong consistency requires W + R > N (for example W=2, R=2, N=3). Eventual consistency uses W=1, R=1. The client chooses per request. Quorum reads also trigger read-repair to fix stale replicas.
Storage engine
Each node uses an LSM tree (like RocksDB) for write-optimised storage. Memtables flush to SSTables; background compaction merges and drops tombstones. Bloom filters avoid disk reads for missing keys. The write path: WAL → memtable → ack; the read path: memtable → block cache → SSTable.
Failure handling
Hinted handoff: if a replica is down, the coordinator writes the mutation to a local hint and replays it when the replica recovers. Anti-entropy: Merkle trees compare ranges between replicas on a schedule (daily) and repair differences. Node join: the new node streams data from its predecessors. Node leave: the node streams its data to successors before shutting down.
Questions and answers
Follow-ups an interviewer is likely to ask. Try answering before you open each one.
How do you handle hot keys?
Split the hot key's vnode range and migrate it to a less-loaded node. Or add a caching layer (Redis) in front for read-heavy hot keys.
What about range queries?
A pure KV store does not support range queries efficiently. If you need them, use a different system (Cassandra with clustering keys, or a separate search/index layer).
How do you test chaos scenarios?
Use a chaos mesh: kill nodes, partition networks, inject latency. Verify that quorum operations still succeed, hinted handoff replays, and anti-entropy repairs divergence.