Design a distributed key-value store

Build the storage layer itself: a store that keeps key → value pairs across hundreds of machines, keeps working when machines and whole zones fail, and lets each application choose how consistent it needs to be. This is the design behind Amazon's Dynamo paper and, in spirit, Cassandra, ScyllaDB and Riak. It ties together almost all of Level 3, and it follows the interview framework phase by phase.

1. The prompt

"Design a distributed key-value store like DynamoDB or Cassandra. Clients put and get values by key; the store must scale out by adding machines and keep working when machines fail."

There are no product features to discuss, so the interview is about mechanisms: how keys are spread over machines, how copies are kept, what "consistent" means when copies disagree, and how a cluster of hundreds of nodes heals itself every week without anyone touching it.

2. Frame the problem

3. What it must do

1. A client can put a value under a key, choosing how many copies must confirm.
2. A client can get the value for a key, choosing how many copies to consult.
3. A client can delete a key.

Not now:

• Range queries and secondary indexes: they need ordered partitioning and a different design.
• Multi-key transactions: they need consensus per range (the CP alternative in section 12).
• A query language: belongs in a layer above.

4. How well it must do it

5. Numbers that change the design

6. The nouns

• Key and value.
• Version: a timestamp or a vector clock.
• Node.
• Token range: the part of the hash ring a node owns.
• Replica set: the N nodes holding one key.
• Hint: a write held for a node that was down.
• Tombstone: a delete marker.

on each node   LSM tree: commit log → memtable → SSTables (+ Bloom filters), compaction
per key        key → [(value, version)]           (several versions only if writes were concurrent)
cluster state  ring: token → node, node → zone, node → status   (spread by gossip)

7. The contract

A client library (or any node, acting as coordinator) exposes three calls. The consistency level and a version context travel with them.

put(key, value, consistency = QUORUM, context?) → ok
get(key, consistency = QUORUM) → [value(s)], context      // more than one value = concurrent versions
delete(key) → ok                                          // writes a tombstone

The context carries version information (for example a vector clock), so the client can say which version its write is based on. Consistency levels: ONE (fastest), QUORUM (a majority of the N replicas), ALL.

8. First working version

Start with the simplest store that spreads data: a client library that hashes each key to one of the nodes, and nodes that store values in a local engine.

8.1 Putting a value

The client computes hash(key) mod N to pick the node and sends the write there. That node appends it to its commit log, updates its in-memory table, and acknowledges.

8.2 Getting a value

The same hash finds the same node, which reads its memtable, then its on-disk files (using Bloom filters to skip files that can't contain the key), and returns the value.

8.3 Deleting a key

The node removes the key from its engine. With one copy, that's all.

9. Make it hold up

9.1 Spreading keys so nodes can come and go scale out

9.2 Copies and quorums always writable · durable · fast

• Replication: each key lives on the next N = 3 distinct nodes clockwise, chosen in 3 different zones, so a zone failure leaves two copies.
• Any node coordinates: a client sends a request to any node (or computes the replicas itself); the coordinator forwards it to the N replicas.
• Quorums: a write is acknowledged after W replicas confirm; a read waits for R replies. If W + R > N (say 2 + 2 > 3), every read overlaps every acknowledged write on at least one replica, so it sees the latest version (Module 14).
• Hinted handoff: if a replica is down, the coordinator still needs W confirmations, so another healthy node stores the write with a hint ("this belongs to node C") and replays it when C returns. This "sloppy quorum" keeps the store writable; the price is that a read right afterwards may miss the write unless R + W > N on the proper replicas.

9.3 Concurrent writes to the same key always writable · durable

9.4 Finding and fixing divergence cheaply self-healing · durable

9.5 Membership and failure detection without a coordinator self-healing

There's no central coordinator to fail. Each node periodically gossips its view of the cluster (who's alive, which tokens they own) with a few random peers; the information reaches every node in a few rounds. An accrual failure detector marks a node "suspected down" by how late its heartbeats are, instead of a fixed timeout. A node marked down keeps its tokens (no data moves); replicas and hints cover for it. Data moves only for planned changes: adding or removing capacity.

9.6 Deletes, and the storage engine durable · fast

• Tombstones: a delete can't simply remove the value, because a replica that missed it would bring it back during repair. Write a tombstone (a delete marker with a version) that's replicated like a write and removed by compaction only after a grace period long enough for every replica to have seen it.
• An LSM engine on each node (Module 12): writes go to a commit log and an in-memory table, flushed as sorted immutable files and merged by compaction. Writes are sequential, so they're fast; Bloom filters keep reads from opening files that can't hold the key.
• The cost: compaction uses disk bandwidth in the background and must be throttled, and many tombstones slow down reads until they're compacted away.

9.7 The whole design after the deep dives

A write while one replica is down, then a read that repairs the stale copy, through the final design.

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Availability over consistency (AP), with tunable quorums per request.
• Leaderless replication with hinted handoff instead of leaders per range.
• Last-write-wins by default, with siblings or CRDTs where data matters.
• LSM storage (fast writes, compaction cost).

The CP alternative is a consensus group per range: linearizable, but a range without a majority stops accepting writes.

What we'd watch:

• p99 latency per consistency level.
• Hints pending.
• Read-repair rate.
• Pending compactions.
• Disk use per node.
• Nodes suspected down.

At 10×:

• More nodes and more tokens per node.
• Multi-region with LOCAL_QUORUM.
• Smart clients.

Common mistakes:

• hash mod N.
• Replicas in one zone.
• Last-write-wins with node clocks.
• Deletes without tombstones.
• Moving data whenever a node is briefly down.
• Claiming strong consistency without consensus.

13. Try it, check yourself, read more

Two replicas each hold 8 keys, hashed into a Merkle tree. Click keys to make replica B's copy differ, then compare: matching hashes (green) are skipped entirely; only branches with a difference (red) are explored.