Distributed Key-Value Store

Design a Dynamo-style key-value store. Each key is stored on several nodes. Clients choose how many replicas must acknowledge a write and answer a read, trading consistency, latency and availability.

A single database is a single point of failure. Replicating it raises the question of how many copies must agree before an operation counts, and that choice sets consistency, latency and availability together.

Primary-replica replication is simple but makes the primary a write bottleneck and a failover risk. Leaderless quorums remove the primary at the cost of conflict handling and repair.

1. Partition keys across nodes with consistent hashing.
2. Replicate each key to N nodes.
3. Let writes and reads succeed with W and R acknowledgements.
4. Stay available for reads and writes when one replica is down.

Workload: 6,000 reads/s, 3,000 writes/s, 1000 B records, 200 ms read p99 target. These are exercise assumptions; the Solution includes capacity formulas.

With N = 3, any two sets of two replicas share at least one member. That shared replica is how a read with R = 2 is guaranteed to see a write that W = 2 acknowledged. Sloppy quorums relax this during failures by writing to substitute nodes.

If each replica is up with probability p, a write needing W of N succeeds with the probability that at least W are up. With p = 0.99, W = 2 of 3 succeeds 99.97% of the time, while W = 3 of 3 succeeds only 97% of the time.