Design a Distributed Key-Value Store

Prompt

"Design a distributed key-value store. Clients do get, put, and delete on string keys with values up to about a megabyte. It has to scale horizontally, survive machine failures, and give predictable consistency."

Clarifying questions

• What consistency do clients need? The interviewer usually lets you choose but wants it stated. Assume the default is strongly consistent reads and writes per key, with an option for cheaper eventually consistent reads.
• Value size and key count? Values from bytes to 1 MB; billions of keys. Total data in the petabyte range.
• Access pattern? Mixed read/write, say 70/30, with skew: some keys are far hotter than others.
• Operations? get, put, delete, plus compare-and-set. No transactions across keys, no range scans in the first version.
• Durability? An acknowledged write must survive the loss of any single machine and, ideally, a single rack.
• Deployment? Within one region first; multi-region is a follow-up.
• Latency? Single-digit milliseconds at p99 for reads, low tens for writes.
• Who are the clients? Internal services, so a smart client library is acceptable.

Requirements

Functional

• get(key), put(key, value), delete(key), cas(key, expected_version, value).
• Configurable per-request read consistency: strong or eventual.

Non-functional

• Horizontal scalability: adding nodes increases capacity and throughput without downtime.
• Fault tolerance: no data loss and continued availability for reads and writes when a minority of replicas for any key are down.
• Predictable behaviour under network partitions, stated explicitly rather than discovered.

Back-of-envelope

• Data: 10B keys with an average value of 10 KB → 100 TB of logical data. With 3× replication that is 300 TB stored. On nodes with 4 TB of usable disk (leaving headroom for compaction and rebalancing), that is 75 nodes minimum; plan for 100-150 so that no node is above 60% utilisation.
• Traffic: assume 1M operations/s at peak, 700K reads and 300K writes. Per node at 100 nodes that is 10K ops/s, comfortably within a single machine's range, so the fleet size is driven by storage and replication factor, not by CPU.
• Write bandwidth: 300K writes/s × 10 KB = 3 GB/s of client data, tripled by replication to 9 GB/s of intra-cluster traffic.
• Memory for indexes: if each node holds 100M keys and an in-memory index entry costs 50 B, that is 5 GB per node for the index alone.
• Rebalancing: losing one node means re-replicating 3 TB. At a throttled 200 MB/s to avoid starving foreground traffic, that is about 4 hours, during which the affected keys have only two replicas. This number drives the decision about replication factor and rack-awareness.
• Hot keys: with skew, the hottest key might see 50K ops/s. A single leader for that key must handle it, so per-key throughput is bounded by one machine; this is a stated limitation with mitigations, not a scaling target.