System Design

Distributed Key-Value Store

Design a durable, replicated key-value store like DynamoDB or Cassandra.

Functional requirements

• Clients put, get, and delete an opaque value by key (e.g., put('user:42:profile', bytes)) through a simple API.
• Every write is replicated to multiple nodes so that losing any single node's disk never loses acknowledged data.
• Clients choose per request how many replicas must acknowledge a read or write (e.g., ONE, QUORUM, ALL) to trade latency against consistency.
• The cluster keeps serving reads and writes while nodes crash, restart, or are partitioned from each other, and reconciles diverged replicas afterward.
• Operators add or remove nodes to grow or shrink capacity while the cluster stays online, with data rebalanced automatically.

Non-functional requirements

• p99 latency under 10ms for single-key reads and writes at QUORUM within one datacenter, and under 2ms at ONE.
• Availability over consistency by default: writes are accepted on both sides of a network partition as long as any replica is reachable, so replicas may diverge and must converge deterministically afterward; a client using R + W > N must always read its own acknowledged writes.
• Durability: an acknowledged write is on durable storage on at least W nodes before the ack, and the cluster survives the simultaneous loss of two nodes or one full rack with zero acknowledged writes lost.
• No single point of failure or coordination bottleneck: no master node and no central metadata service on the request path.
• Data is encrypted at rest and between nodes, and one tenant's traffic must not push another tenant past the p99 target.

Scaling & constraints

• 200 TB of unique data, 600 TB at replication factor 3, across ~300 nodes with 4 TB of local NVMe each.
• Peak of 2 million operations per second cluster-wide, ~700,000/sec average, at a 3:1 read:write ratio.
• Keys average 40 bytes; values average 4 KB with a hard cap of 400 KB; about 50 billion keys.
• A node fails about once a day (disk or host), a full rack of 30 nodes about once a quarter, and network partitions between racks last from seconds to ~10 minutes a few times a year.
• Data grows ~50% per year; capacity arrives in batches of 20-30 nodes, and a rebalance must finish within 24 hours while adding at most 20% load to any existing node.
• The hottest 1% of keys take ~30% of reads and a single key can spike to 50,000 reads per second for minutes; about 1% of writes hit a key another client wrote within the previous second.

Out of scope

• Transactions, conditional writes, and secondary indexes.
• Range scans and sort-order queries; assume single-key access only.
• Cross-region replication and geo-routing.
• Client SDKs, authentication, and per-tenant billing.