Design a Distributed Key-Value Store

Requirements

• •Partition data across nodes using consistent hashing with virtual nodes
• •Replicate each key to N nodes (configurable, default N=3)
• •Tunable consistency: allow clients to specify W (write quorum) and R (read quorum)
• •Handle node failures with hinted handoff: temporarily store writes destined for failed nodes
• •Implement anti-entropy with Merkle trees to detect and repair inconsistencies between replicas

Non-Functional Requirements

• •Read/write latency < 5ms (p99) at W=1, R=1
• •System scales linearly: adding 50% more nodes increases throughput by ~50%
• •Data remains durable with up to 2 simultaneous node failures (N=3, W=2)
• •Supports 1 million ops/second across a 20-node cluster

Constraints

• •Target: a Dynamo-style eventually consistent KV store (like Amazon DynamoDB or Apache Cassandra)
• •Values are opaque bytes, up to 1MB per key
• •No secondary indexes in v1 — primary key lookup only

Evaluation Criteria