Design a Leader-Based Distributed Key-Value Store
Design a partitioned key-value service with explicit consistency modes, leader routing, failover, service discovery, repair, and online rebalancing.
Problem statement
For this exercise, assume clients put, get, and delete opaque values in a distributed key-value service. Each logical partition uses a leader and followers.
Design consistent-hash or virtual-shard placement, replication, strong and eventual read modes, leader discovery and routing, write acknowledgment, leader failure and promotion, tombstones, repair, and online membership changes.
Explain how many leaders exist, what a client does when it contacts a follower or stale leader, and how the system prevents two leaders from accepting conflicting strong writes.
The single-node storage engine may be treated as a reliable component, but its WAL, memtable, SSTable, compaction, and Bloom-filter implications should be understood.
What to build
- Put or delete one key through the current partition leader with an explicit durability and consistency result.
- Read one key using either strong-leader/quorum semantics or a labeled bounded-stale follower mode.
- Discover and route to the current partition replicas, recovering from stale membership and not-leader responses.
- Replace failed replicas and rebalance partitions online without losing acknowledged writes or resurrecting deletes.
At scale
- For this exercise, store 10 billion keys and serve 1 million requests per second with a 70/30 read-write mix within one region.
- For this exercise, use thousands of logical partitions, three replicas per partition across availability zones, and p99 under 25 ms for healthy in-region strong operations.
- For this exercise, acknowledged strong writes survive one availability-zone loss with RPO 0; eventual follower reads may lag by up to five seconds.
- For this exercise, a failed leader should be replaced within 30 seconds, while an unsafe quorum loss rejects strong writes rather than creating split brain.