Design a distributed key-value store

Design a distributed key-value store like Amazon Dynamo or Cassandra: put(key, value) and get(key) on huge amounts of data, always available, and still working while servers fail.

1. Clarify the requirements

Before drawing anything, ask questions. These are the answers an interviewer would typically give:

Size of a value?

Small: under 10 KB.

How much data and traffic?

Hundreds of terabytes; 200,000 reads and 100,000 writes a second.

Consistency or availability?

Availability first: it must accept writes even during a network partition. Consistency can be tuned per request.

Latency?

Low: single-digit milliseconds inside the data centre.

Servers fail?

All the time, and the system must keep going and heal itself.

2. Estimate the scale

Assumptions: Values < 10 KB, 200K reads/s and 100K writes/s, hundreds of TB, 3 copies of every key.

• Writes per second: about 100K writes/sGiven: 100K puts/s.
• Replica writes per second (N = 3): about 300K writes/sEvery put is written to 3 replicas: 300K writes/s across the cluster.
• Storage nodes needed: about 100 nodes~300 TB with 3 copies ≈ 900 TB ÷ ~10 TB per node ≈ 90–100 nodes.

3. The high-level design

1. Clients reach coordinator nodesAny node can coordinate a request. It hashes the key onto a consistent-hash ring (with virtual nodes) to find the N = 3 replicas that own it.
2. Storage nodes own ranges of the ringEvery key is copied to 3 nodes in different racks. Writes append to a commit log, then a memtable, then SSTables on disk; vector clocks version each value.
3. Another data centreReplicating to a second data centre keeps the store available even if a whole site goes down.
4. Watch it in productionMetrics and alerts close the loop: p99 latency, hinted-handoff backlog and repair progress.

4. The components and what each one does

Clients Client (web)

A client library, or any node as coordinator.

Load balancer Load balancer

Spreads requests over coordinator nodes.

Coordinator nodes Service

Stateless: any node can coordinate, so they scale out horizontally. Hash the key onto the consistent-hash ring (virtual nodes); send it to the N = 3 replicas; wait for W acks or R replies (quorum, W + R > N when strong consistency is needed). Gossip spreads membership and detects failures.

Storage nodes NoSQL / KV store

Each owns ranges of the ring; 3 copies per key across racks. Commit log → memtable → SSTables; vector clocks for conflicts; hinted handoff while a replica is down; Merkle trees to repair.

Second data centre NoSQL / KV store

Asynchronous cross-data-centre replication.

Metrics & alerts Metrics & alerts

Dashboards and alerts on p99 latency, error rate, queue depth and cache hit ratio, so a bottleneck shows up before it becomes an outage.

5. Deep dive: partitioning, replication and consistency

How are keys spread over nodes, how many copies does each key have, and how do reads and writes agree? What happens when a node is down or the network splits?

• Consistent hashing places nodes (with virtual nodes) on a ring; a key belongs to the next N nodes clockwise.
• Quorum: a write waits for W acks and a read asks R replicas. W + R > N gives strong consistency; smaller values favour speed and availability.
• Conflicts: vector clocks detect concurrent writes. Failures: sloppy quorum + hinted handoff for temporary ones, Merkle trees for repairs, gossip to detect them.

6. What interviewers listen for

• API: get(key) and put(key, value)Simple, but say it: get(key) → value, put(key, value).
• Consistent hashing (with virtual nodes)Consistent hashing moves only a small share of keys when nodes join or leave.
• N replicas per key (e.g. 3), across racks/data centresCopy every key to the next N nodes on the ring, in different racks.
• Quorum reads and writes (W + R > N)Tunable consistency is the heart of this design.
• Conflict detection (vector clocks)With concurrent writes, versions diverge: detect it and let the client (or LWW) resolve.
• Failure detection by gossipNodes gossip heartbeats; a node unheard from for a while is marked down.
• Sloppy quorum and hinted handoff for temporary failuresKeep accepting writes while a replica is down, and hand them back when it returns.
• Anti-entropy repair with Merkle treesMerkle trees find which ranges differ between replicas, so repairs transfer little data.
• Write path: commit log, memtable, SSTablesAppend to a commit log, write to an in-memory table, flush to sorted files on disk.

7. Follow-up questions

1. One storage node dies for 10 minutes during peak traffic. Walk me through what happens to writes for its keys.
2. A product team needs read-your-writes consistency for some keys. How do you give it to them without slowing everyone down?
3. One key gets 1 million reads a second. What breaks, and what do you do?

The design in a nutshell

• Clients → coordinator (any node; or a client library that knows the ring) → the N = 3 replicas responsible for the key on the consistent-hash ring (virtual nodes, spread across racks).
• Writes: commit log → memtable → SSTables; reads check the memtable, Bloom filters and SSTables. Quorum W + R > N when strong consistency is needed.
• Vector clocks detect conflicts; gossip detects failures; sloppy quorum + hinted handoff ride out temporary outages; Merkle trees repair permanent ones.
• Replicate across data centres; monitor p99 latency, hinted-handoff backlog and repair progress.

Related lessons: Data partition and replication · Consistency: quorum consensus (N, W, R) · Inconsistency resolution: versioning and vector clocks · Handling failures: sloppy quorum, hinted handoff, data center outages