Design a Distributed Key-Value Store — System Design Walkthrough

"Design a distributed key-value store" — often phrased as "design Dynamo" or "design Cassandra" — sounds like the caching question, and candidates often answer it as if it were. It isn't. A cache is a bounded, volatile layer in front of a system of record; if a cache node dies you lose latency, not data, which is why designing a distributed cache is mostly about eviction and hot keys. A key-value store is the system of record: writes must survive disk failures, node failures, and network partitions. That single requirement — durability — drags in replication, quorums, conflict resolution, repair, and a real storage engine. Here is the walkthrough you can mirror in a live system design interview, with the system design interview cheat sheet alongside for the shared primitives.

1. Clarify the requirements

Functional requirements

• get(key) returns the current value, or a set of conflicting versions.
• put(key, value) writes durably.
• delete(key) removes a key.
• Values are opaque blobs up to a few MB; no joins, no secondary indexes, no multi-key transactions.

Non-functional requirements

• Durability: an acknowledged write is never lost.
• High availability: writes should keep succeeding even during a network partition (the classic "always writable" shopping-cart requirement).
• Horizontal scale: add commodity nodes to grow capacity linearly, to petabytes.
• Tunable consistency: the caller chooses how many replicas must agree.
• Predictable latency: single-digit millisecond p99 for point reads and writes.

Deliberately narrowing the API this hard is the point: no range scans and no transactions is what buys you the freedom to partition arbitrarily.

2. Partitioning with consistent hashing

The data doesn't fit on one machine, so keys must be spread across a cluster. The naive node = hash(key) % N is a trap: change N and nearly every key moves, which for a durable store means shuffling the entire dataset over the network.

Consistent hashing maps both nodes and keys onto a ring (0 to 2¹²⁸ with an MD5-style hash). A key belongs to the first node clockwise from its position. Adding or removing a node only remaps the arc it owned. Virtual nodes — giving each physical machine many token positions on the ring — are essential here: they even out load, let heterogeneous hardware own proportional shares, and spread a failed node's data across many peers instead of dumping it all on one successor.

          Ring with virtual nodes; N = 3 replication

                       hash(key "cart:42")
                              |
                              v
         A1 ---- B2 ---- C1 ---- A3 ---- B1 ---- C2 ---- A2 ...
                          ^^^^^^^^^^^^^^^^^^^^^^
                          preference list = C1, A3, B1
                          (next 3 DISTINCT physical nodes
                           walking clockwise)

  Coordinator = first node in the preference list.
  Skip virtual nodes belonging to a physical node already chosen,
  so the 3 replicas live on 3 different machines (and ideally
  3 different racks / availability zones).

3. Replication and quorums

Each key is stored on N nodes — its preference list. Two more knobs make consistency tunable:

• W — replicas that must acknowledge a write before the client gets success.
• R — replicas that must respond to a read before the coordinator answers.

The central rule: if R + W > N, the read set and the write set must overlap by at least one node, so any read is guaranteed to see at least one replica carrying the latest acknowledged write. That's "strong-ish" consistency — strong enough that a stale read can be detected by version comparison, but not linearizable, because concurrent writers can still produce divergent versions and failed writes may be partially applied.

4. CAP, made concrete

CAP is only useful when you turn it into a decision. During a network partition, a coordinator that can't reach W replicas has exactly two options: reject the write (choose consistency, sacrifice availability) or accept it anyway on the reachable nodes and reconcile later (choose availability, sacrifice consistency). A Dynamo-style store picks AP: it takes the write, because refusing a customer's cart addition is worse than briefly showing two carts. A store like a strongly consistent, consensus-backed database picks CP: it refuses the write rather than diverge. Say which you're building and why — that sentence is usually what the interviewer is listening for.

5. Versioning with vector clocks

Choosing AP means concurrent writes will happen, and wall-clock timestamps can't order them reliably across machines. A vector clock is a list of (node, counter) pairs carried with each version; the coordinating node increments its own counter on every write. Comparing two clocks tells you whether one descends from the other (safe to discard the ancestor) or whether they are concurrent (a genuine conflict).

Sx writes v1            -> clock [ (Sx,1) ]
Sx writes v2            -> clock [ (Sx,2) ]        descends v1, discard v1

Partition. Two coordinators take a write against v2:

  Sy writes v3          -> clock [ (Sx,2), (Sy,1) ]
  Sz writes v4          -> clock [ (Sx,2), (Sz,1) ]

Neither clock dominates the other (Sy vs Sz counters diverge),
so v3 and v4 are CONCURRENT -> keep both as siblings.

Next read returns [v3, v4] + a merged context clock.
Client (or a merge function) resolves; the reconciled write
carries [ (Sx,2), (Sy,1), (Sz,1), (Sy,2) ] and supersedes both.

Semantic merges are application-specific — union the shopping carts, take the max counter — which is why the store pushes resolution to the client. Mention that vector clocks grow with the number of coordinating nodes, so implementations truncate the oldest entries, and that last-write-wins with synchronized clocks is the cheap alternative you'd accept only when losing a concurrent write is harmless.

6. Failure handling: gossip, hinted handoff, Merkle trees

Gossip for membership and failure detection. There is no master. Each node periodically exchanges its view of the ring and node liveness with a random peer; state converges across the cluster in logarithmic rounds. Failure detection is local and probabilistic — a node that stops responding to one peer is marked temporarily down by that peer — which avoids a coordinator becoming a single point of failure or a false positive taking a healthy node out globally.

Hinted handoff keeps writes available during transient failures. If a replica in the preference list is unreachable, the coordinator sends the write to the next healthy node on the ring with a hint recording the intended recipient. That node stores it in a separate area and replays it once the original comes back. This is the mechanism behind "always writable" — and it's why the quorum is often described as a sloppy quorum.

Merkle trees for anti-entropy. Hinted handoff covers brief outages; a node down for hours, or dropped hints, need a background repair. Each replica maintains a hash tree over its key range: leaves hash blocks of keys, parents hash their children. Two replicas compare root hashes; if equal, the ranges are identical and no data moves. If not, they descend only into subtrees whose hashes differ, so the data exchanged is proportional to the divergence, not to the dataset size.

7. Storage engine: LSM-tree vs B-tree

Everything above is cluster-level; the per-node question is how bytes hit disk. A B-tree updates pages in place, so a write is a random seek plus a page rewrite — excellent for reads and range scans, mediocre under heavy random writes. An LSM-tree never updates in place:

1. The write goes to a write-ahead log (durability) and an in-memory sorted memtable.
2. When the memtable fills, it is flushed as an immutable, sorted SSTable file — one big sequential write.
3. Compaction merges SSTables in the background, dropping superseded values and tombstoned deletes.

That turns random writes into sequential ones, which is why write-heavy stores favour LSM. The cost is read amplification: a key may live in the memtable or any of several SSTables. Mitigations to name are bloom filters per SSTable (cheaply rule out files that can't contain the key) and sparse block indexes. Compaction also causes write amplification and periodic latency spikes — a good trade-off to acknowledge rather than hide.

8. Read and write paths end to end

  WRITE put(k, v)
    client -> any node (acts as coordinator, or forwards to
                        the first node in k's preference list)
    coordinator: bump vector clock, send to N replicas
    each replica: append to commit log -> memtable
                  (memtable full -> flush SSTable)
    ack when W replicas reply; unreachable replica -> hinted handoff

  READ get(k)
    coordinator -> N replicas, wait for R responses
    compare vector clocks:
        one dominates  -> return it
        concurrent     -> return all siblings + context
    read repair: push the newest version to stale replicas inline
    background: Merkle-tree anti-entropy + gossip keep the rest sane

  Node internals:
    [ commit log ] [ memtable ] -> [ SSTable ][ SSTable ][ SSTable ]
                                     + bloom filter each
                                     + background compaction

Read repair is the cheap win worth calling out: since the coordinator already has responses from R replicas, any replica returning a stale version gets the newer one pushed to it on the spot, at no extra round trip.

9. Trade-offs to state out loud

• Availability over consistency, made concrete by what happens during a partition, plus the R+W>N knob for callers who want overlap.
• Conflict resolution is pushed to the application. That's a feature for carts and a burden for everything else — say which your workload is.
• Decentralized by design. Gossip and consistent hashing mean no master, so operational simplicity comes from symmetry, not coordination.
• Storage engine follows the workload. LSM for write-heavy, B-tree when reads and range scans dominate.
• No transactions or joins. The narrow API is what makes all of the above possible; if the requirements need them, this is the wrong data store.

FAQ

What is the difference between a distributed key-value store and a distributed cache?

A cache is a bounded, volatile layer in front of a system of record: entries are evicted when memory fills, values may expire, and losing a cache node costs latency but not data. A key-value store is the system of record itself, so it must persist writes to disk, replicate them so a node failure loses nothing, and answer questions about consistency, conflict resolution, and repair. That durability requirement is what pulls in quorums, vector clocks, anti-entropy, and a real storage engine.

How do N, R, and W quorums work?

N is the number of replicas each key is stored on, W is the number of replicas that must acknowledge a write before it is considered successful, and R is the number that must respond to a read. When R plus W is greater than N the read set and the write set must overlap by at least one replica, so a read is guaranteed to see at least one copy of the latest acknowledged write. Lowering W speeds up writes and lowering R speeds up reads, each at the cost of weaker guarantees.

What are vector clocks used for in a key-value store?

A vector clock is a list of (node, counter) pairs attached to each version of a value, incremented by whichever node coordinates a write. Comparing two vector clocks tells you whether one version descends from the other or whether the two were written concurrently. Descendant versions can be discarded safely, while genuinely concurrent versions are kept as siblings and returned together on read so the client or an application-defined merge function can resolve them.

Why do Merkle trees help with replica repair?

A Merkle tree is a hash tree built over a replica's key range, where each leaf hashes one block of keys and each parent hashes its children. Two replicas compare root hashes first; if they match, the ranges are identical and nothing is transferred. If they differ, the nodes walk down only the subtrees whose hashes disagree, so the amount of data exchanged is proportional to the differences rather than to the size of the dataset.

Why do write-heavy key-value stores prefer LSM-trees over B-trees?

A B-tree updates records in place, so each write typically means a random disk seek to the correct page. An LSM-tree buffers writes in an in-memory memtable and flushes them as immutable, sorted SSTable files, turning random writes into large sequential ones with much higher throughput. The trade-off is read amplification, because a key may live in several SSTables, which is mitigated with bloom filters and background compaction that merges files and drops superseded values.