Walkthrough: Designing a Distributed Key-Value Store

The problem

You’re asked to design a distributed key-value store — the system underneath DynamoDB, Cassandra, or Riak. The interviewer says something like: “Design a storage system that supports get(key) and put(key, value) across many machines. It should scale horizontally and survive machine failures.”

Sounds like a big hash map. It isn’t. The trap is treating partitioning as the whole question: candidates draw a hash ring, say “consistent hashing,” and stop. The question is really about what happens when machines fail while reads and writes are in flight — and at the scale this system runs, machines are always failing. Replication, quorum arithmetic, and conflict resolution are where the design actually lives.

Below is how I’d walk through this, start to finish.

1. Requirements

First 3–5 minutes. Questions I’d ask to pin down what we’re building:

Functional requirements

• R1. put(key, value) — write a value by key.
• R2. get(key) — read a value by key.
• R3. delete(key) — remove a key.
• R4. Scale horizontally — add and remove nodes without downtime or manual resharding.
• R5. Durability — an acknowledged write survives the permanent loss of a node.

Scope

This design covers the distributed coordination layer. Explicitly out of scope:

• Range queries and secondary indexes (a different storage-engine question — they constrain partitioning in ways point lookups don’t)
• Cross-record transactions (a consensus/2PC question; see distributed transactions)
• Multi-region active-active (named in the evolution table; a design of its own)
• Authentication, multi-tenancy, quotas (real products need them; not design drivers here)
• Storage-engine internals (LSM compaction tuning is a deep topic; I name the engine and move on)

Non-functional requirements

• Scale. How many keys, and how large are values? Total dataset size determines fleet size, and fleet size determines how often we’re handling failures.
• Read/write mix. KV stores are often closer to balanced (70/30) than the 100:1 of a read-heavy web app — caching helps less than usual, so the storage path itself must be fast.
• Latency. Single-digit-millisecond p99 for both operations?
• Availability vs consistency. During a partition, must writes always succeed? This is the contract question — it decides the architecture.
• Durability. Replication factor, and whether acknowledged writes may ever be lost.

Say the interviewer confirms: 100B keys, values average 1 KB (max 100 KB), 1M reads/sec and 300K writes/sec at peak, p99 < 10 ms, replication factor 3, single region to start — and the hard one: writes must succeed even during partial failures. Always-writable.

2. Capacity estimate

• Storage: 100B keys × 1 KB ≈ 100 TB raw. With replication factor 3 plus storage-engine overhead, ~350–400 TB on disk.
• At ~2.5 TB of usable data per node (leaving headroom for compaction and repair), that’s a ~150-node fleet.
• Throughput per node: 1M reads/sec ÷ 150 ≈ 7K reads/sec/node — comfortable for an SSD-backed store. The fleet is storage-bound, not CPU-bound.

Two conclusions worth saying out loud:

“First — at 150 nodes, hardware failure is not an event, it’s a steady state. Between disk failures, kernel patches, and network blips, something in this fleet is down or degraded every few days. Failure handling can’t involve an operator; it has to be automatic. Second — since the fleet is sized by storage, the expensive operation is moving data, not serving requests. Rebalancing and repair traffic are first-class design concerns, not afterthoughts.”

3. High-level architecture

Three logical subsystems:

1. Request coordination — receives a get/put, finds the replicas for the key, fans out, collects acknowledgments. In a leaderless design, any node can coordinate any request.
2. Partitioning and membership — decides which nodes own which keys (the hash ring) and tracks which nodes are alive (gossip). This is what makes R4 (elastic scaling) possible.
3. Replication and repair — keeps N copies of every key in sync through quorums, hinted handoff, and background anti-entropy. This is what makes R5 (durability) possible.

flowchart TD
  Client[Client] --> Router[Routing layer]
  Router --> Coord[Coordinator · node A]
  Coord --> StoreA[(Storage · A)]
  Coord -->|replicate| NodeB[Node B]
  Coord -->|replicate| NodeC[Node C]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class StoreA store

Membership decides the system’s character. A store with a central metadata master and a store where nodes gossip peer-to-peer are different systems with different failure modes — and this question is asking for the second one.

4. Architecture evolution

A key-value store in production evolves through recognizable levels:

Each level preserves the previous one as a fallback in spirit — a Level 4 ring degrades to “fewer healthy replicas, same protocol,” which is precisely its advantage over Level 3, where a primary’s death is a special case requiring election.

The design in this walkthrough is Level 4: a leaderless ring with tunable quorums — the Dynamo paper architecture that Cassandra and Riak industrialized.

I’d say out loud: “I’m designing for Level 4 — leaderless with quorums. The reason to prefer it over sharded primaries is that node failure stops being a special case: there’s no election, no failover window, just a quorum assembled from whoever’s alive.”

Target architecture (Level 4)

This is the complete system. Every section that follows explains one part of this diagram:

flowchart TD
  Client[Client] --> Router[Routing layer]
  Router --> Coord[Coordinator · node A]

  Coord --> StoreA[(Storage · A)]
  Coord -->|replicate| NodeB[Node B]
  Coord -->|replicate| NodeC[Node C]
  NodeB --> StoreB[(Storage · B)]
  NodeC --> StoreC[(Storage · C)]

  Coord --> Hints[(Hint buffer · A)]
  Coord <-.->|gossip| NodeB
  NodeB <-.->|gossip| NodeC
  StoreB <-.->|merkle repair| StoreC

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class StoreA,StoreB,StoreC,Hints store

5. Core design choice: who accepts writes

This is the question. Three options:

(a) Primary per partition. Each key range has one primary that orders all writes; replicas follow. Reads can be served from replicas (stale) or the primary (consistent). On primary failure, a failover process promotes a replica — and writes to that range block until it finishes.

(b) Consensus group per partition. Each key range is a Raft group; every write commits through a majority. Strong consistency, automatic failover — but every write pays a round of consensus, and during a partition the minority side refuses writes. This is a CP store (etcd, CockroachDB’s KV layer).

(c) Leaderless with quorums. Any of the N replicas accepts a write; the coordinator declares success after W acknowledgments. Reads ask R replicas and reconcile. No failover process exists because there’s nothing to fail over — but two replicas can accept conflicting writes during a partition, so the system must detect and resolve conflicts.

Why leaderless wins here

The justification is contract-specific: the interviewer said writes must succeed during partial failures. Options (a) and (b) both have a window — failover or minority partition — where some writes block. Option (c) has no such window by construction: as long as any W replicas (or stand-ins; see hinted handoff) are reachable, the write succeeds. The cost is real and named up front: we are choosing to handle conflicting versions rather than prevent them. Dynamo made exactly this trade for Amazon’s shopping cart — for that product, refusing a write (losing a sale) is strictly worse than merging two cart versions later.

Tradeoff matrix

Architecture decisions

Core data structures

Full schemas and access patterns are in §10. What matters now: all four structures exist to answer one question — which replicas have the latest version of this key, and how do we know?

6. Algorithm deep-dive: consistent hashing [R4]

The partitioning mechanism, step by step:

1. Hash the entire key space onto a ring — say the range 0 to 2^128 − 1, wrapping around. Consistent hashing means both keys and nodes are hashed onto the same ring.
2. Each node owns one or more tokens (positions on the ring). A key belongs to the first node found walking clockwise from hash(key).
3. The preference list for a key is the next N distinct physical nodes clockwise. With N=3, key K at position 0x6A… might map to nodes B, C, D. “Distinct physical” matters once virtual nodes exist — two adjacent tokens can belong to the same machine, and replicating to yourself twice is not replication.
4. When a node joins, it takes tokens and inherits only the key ranges those tokens carve out — roughly 1/n of the data moves, instead of nearly all of it under hash(key) mod n.

Worked example. Four nodes, one token each, at positions 0x20, 0x60, 0xA0, 0xE0. Key user:42 hashes to 0x6A → walking clockwise, its preference list is the nodes at 0xA0, 0xE0, 0x20. Now node E joins at 0x80: it takes ownership of the range (0x60, 0x80] only. Keys hashing to 0x6A now route to E first — and only that slice of data streams to E. Nothing else in the cluster moves.

Why virtual nodes. One token per node has two problems specific to this system: (1) when a node dies, its entire range lands on exactly one clockwise successor — the recovery doubles one node’s load while 148 nodes idle; (2) token placement is luck, so some nodes own 2× the keyspace of others. Giving each node ~256 virtual tokens scatters its ranges around the ring: load spreads evenly, and when a node dies, its data re-replicates from and to dozens of nodes in parallel. At our fleet size — where §2 said data movement is the expensive operation — parallel recovery is the difference between a 1-hour and a 24-hour repair window.

7. Write path [R1, R5]

The slice of the target architecture a write touches:

flowchart TD
  Client[Client] --> Router[Routing layer]
  Router --> Coord[Coordinator · node A]
  Coord --> StoreA[(Storage · A)]
  Coord -->|"replicate (parallel)"| NodeB[Node B]
  Coord -->|"replicate (parallel)"| NodeC[Node C]
  Coord --> Hints[(Hint buffer · A)]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class StoreA,Hints store

Step by step, with N=3, W=2:

1. Client sends put(key, value, context) — the context is the version it last read (more in §9).
2. The routing layer (a smart client library that gossips ring state, or a thin proxy) forwards to a coordinator — ideally a node in the key’s preference list, saving a hop.
3. Coordinator increments its entry in the key’s version vector and writes locally: append to the write-ahead log, apply to the memtable. (Each node’s storage engine is an LSM tree — justified in §10.)
4. Coordinator sends the write to the other replicas in the preference list, in parallel.
5. As soon as W=2 acknowledgments arrive (its own counts), the coordinator returns success — total latency is one parallel fan-out, no ordering round.
6. The third replica’s ack arrives late or never. Late: fine, it’s already durable on two nodes. Never — say node C is down:

Sloppy quorum and hinted handoff. Rather than fail the write (strict quorum) or silently under-replicate, the coordinator writes C’s copy to the next healthy node on the ring — node D — tagged with a hint: “this belongs to C; deliver it when C returns.” D stores it in a separate hint buffer, not its main keyspace, and replays it to C on recovery. The write met W=2 with a stand-in. This is the mechanism that makes “always-writable” literal: the cluster accepts writes as long as any W nodes are up, not any W specific nodes.

8. Read path [R2]

flowchart TD
  Client[Client] --> Router[Routing layer]
  Router --> Coord[Coordinator · node A]
  Coord --> StoreA[(Storage · A)]
  Coord -->|"read (parallel)"| NodeB[Node B]
  Coord -->|"read (parallel)"| NodeC[Node C]
  Coord -->|read repair| NodeC

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class StoreA store

Step by step, with N=3, R=2:

1. Coordinator sends the read to all N replicas (or R plus speculative extras), waits for R=2 responses.
2. Each response carries (value, version_vector). The coordinator compares vectors:
   • One version descends from the other (strictly newer) → return the newer one.
   • Versions are concurrent (neither descends from the other) → return both as siblings, with a merged context. The client resolves (§9).
3. Read repair: if any responding replica returned a stale version, the coordinator pushes the winning version back to it asynchronously. Hot keys — the ones read constantly — are thus also the ones repaired fastest, which is exactly the staleness-exposure profile you want.
4. Return (value(s), context) to the client. The context is the opaque version token the client must send back on its next put to that key.

Quorum arithmetic. The consistency knob is the pair (R, W) against N:

R+W > N guarantees the read set and write set intersect — some node in your R responses acknowledged the last write. It does not make the system linearizable (sloppy quorums and concurrent writes still produce anomalies); it makes stale reads the exception instead of the rule. I’d commit to W=2, R=2 as the default and say the API exposes per-request overrides.

9. Consistency model and conflict resolution [R1, R2, R3]

Worked conflict example. A network partition splits the cluster. A shopping-cart key has version [(A,3)] on both sides.

1. Client 1, on the left side, adds an item. Coordinator A handles it: version becomes [(A,4)].
2. Client 2, on the right side, adds a different item. Coordinator B can’t reach A; the write lands with version [(A,3),(B,1)].
3. The partition heals. A read collects both versions. Compare: is [(A,4)] ≥ [(A,3),(B,1)]? No — [(A,4)] has no B entry. Is the reverse true? No — (A,3) < (A,4). Neither descends from the other: concurrent. The coordinator returns both siblings.
4. The client merges — for a cart, set-union of items — and writes back with the merged context. The new version [(A,5),(B,1)] descends from both; the conflict is resolved and siblings collapse.

This is the vector clock mechanism from the Dynamo paper. The alternative — last-write-wins — compares wall-clock timestamps and keeps the larger. Step 4 disappears, and so does one customer’s item: whichever write carried the smaller timestamp is erased, silently, with the loser decided by which server’s clock ran faster. LWW is acceptable for genuinely overwrite-style data (a session token, a device’s latest heartbeat); it is data loss for anything merged. Name the difference and let the value type choose.

Deletes are writes (R3). A delete can’t just remove the record — a replica that missed the delete would “resurrect” the key during repair, because to repair, a missing key and a never-written key look identical. So deletes write a tombstone: a versioned “this key is deleted” marker that propagates like any write and wins version comparisons like any write. Tombstones are garbage-collected only after the repair cycle guarantees every replica has seen them — collect too early and deleted data comes back from the dead.

Anti-entropy repair. Hints cover short outages; the durable mechanism is background repair. Each node maintains a Merkle tree per key range — a hash tree where each leaf summarizes a slice of keys. Two replicas compare trees root-first: matching root, range in sync, done with one hash exchange; mismatched root, descend into children and recurse until the differing keys are found and streamed. Comparing a multi-gigabyte range costs kilobytes of hash traffic when in sync — which is the common case, which is why the cluster can afford to run repair continuously.

Failure detection. Membership rides on a gossip protocol: every second, each node exchanges its view (node, heartbeat, ring tokens) with a few random peers. Information spreads epidemically in O(log n) rounds. No node is special, which preserves the no-SPOF property — and “node C looks dead” is always a local suspicion, not a global fact. That’s fine: in this design, a false suspicion just means a few unnecessary hints, not a failover.

10. API design [R1, R2, R3]

Three operations, plus the context discipline:

GET /v1/keys/{key}?consistency=quorum|one        [R2]
  returns: { values: [...], context }            # >1 value = unresolved siblings

PUT /v1/keys/{key}                               [R1]
  body:    { value, context }                    # context from the preceding GET
  returns: { context }

DELETE /v1/keys/{key}                            [R3]
  body:    { context }
  returns: { ok }

Two non-obvious decisions:

The context round-trip. context is the version vector, opaque to clients. A client that read version X and writes with context X tells the store “this write supersedes X” — concurrent writes are detected instead of erased. A PUT with no context is a blind write that always creates siblings under concurrency.

Per-request consistency. consistency=one on a read is a deliberate “fast and possibly stale” — right for a presence indicator, wrong for a checkout. Putting the dial in the API admits what’s true: consistency requirements belong to the data, not the cluster.

The API hides everything else — ring topology, replica placement, repair. A client never knows the cluster grew from 150 to 200 nodes. That abstraction boundary is what lets the system evolve to Level 5 (multi-region) without breaking a caller.

11. Data model and storage

Requirements → components

Access frequency

Storage technology choices

Access pattern matrix

Schemas

Data record [R1, R2, R3]

data (per-node LSM):
  key:         raw bytes — ring position is hash(key)
  value:       opaque blob, ≤ 100 KB
  version:     vector clock [(node_id, counter), ...]
  tombstone:   boolean
  written_at:  wall-clock timestamp — for tombstone GC and metrics only,
               never for conflict resolution

Ring state [R4] — gossip-replicated to every node:

ring_state:
  node_id:     uuid
  tokens:      [position, ...]        # ~256 virtual nodes per physical node
  status:      joining | up | suspect | leaving | down
  heartbeat:   generation + version counter

Hints [R5] — coordinator-local:

hints:
  target_node: uuid                   # the replica that missed the write
  key, value, version:                # the write itself
  expires_at:  timestamp              # beyond this, rely on Merkle repair

12. Failure modes

I’d walk through these proactively, grouped by what they threaten. The pattern: name what fails, name what degrades, name what doesn’t.

Availability failures

A replica dies during writes

Fails: one member of the preference list. Degrades: nothing visible — sloppy quorum routes its share to the next ring node as hints; latency unchanged. Doesn’t degrade: write acceptance. The honest caveat I’d name: durability quietly runs at RF=2-plus-IOU until the node returns or repair re-replicates — this is the contract’s fine print.

Coordinator dies mid-request

Fails: the in-flight request. Degrades: the client retries against any other node — every node can coordinate, so there’s no failover wait. Doesn’t degrade: correctness. A retried put with the same context produces a version that supersedes or siblings the first attempt; it cannot half-apply.

Consistency failures

Concurrent writes during a partition

Fails: single-copy illusion — both sides accepted writes to the same key. Degrades: the next read does extra work (returns siblings; client merges, as in §9’s worked example). Doesn’t degrade: data survival — both writes exist. The contrast to name: under LWW this same scenario is silent data loss, and nobody is ever told.

Clock skew

Fails: any meaning “latest timestamp” had. With vector clocks, foreground reads and writes don’t care — causality is counters, not clocks. What’s still exposed: tombstone GC windows and TTLs, which do use wall clocks. Mitigation: NTP discipline and generous GC margins, not clock trust.

Durability and topology failures

A node is lost permanently

Fails: one replica of every range the node’s 256 vnodes owned. Degrades: those ranges run at RF=2 while Merkle repair re-streams them — from dozens of source nodes in parallel, the payoff of virtual nodes. Doesn’t degrade: reads and writes, since quorums still assemble. The operational risk to name: repair I/O competes with foreground traffic; unthrottled, the cure causes the latency outage the failure didn’t.

Gossip partition splits the ring view

Fails: membership agreement — each side suspects the other is down. Degrades: each side keeps serving with sloppy quorums and accumulates hints; conflicting writes pile up for later resolution. Doesn’t degrade: write availability — this is the AP choice, visible in its rawest form. What’s lost during the partition: any pretense of reading globally-latest data. After healing: hint replay + read repair + anti-entropy converge the sides; siblings surface to clients.

Hot key overwhelms its three replicas

Fails: latency on one preference list (a celebrity-config key, a viral object). The ring spreads keys evenly, not load — N=3 specific nodes serve every request for this key. Degrades: with mitigation, freshness — a short-TTL client-side cache or request coalescing absorbs the read storm at the cost of seconds-stale reads. Doesn’t degrade (must not): neighbors — without back-pressure, the three replicas’ overload spills into every other range they host, turning one hot key into a cluster incident.

13. What I’d skip, and say I’m skipping

Time check — five minutes left. Things I’d explicitly defer:

• Storage-engine internals. Compaction strategies, bloom filters, block caches — a full question of its own. I’ve justified why LSM; tuning it is RocksDB’s job.
• Range queries and secondary indexes. They’d force order-preserving partitioning and reopen the hot-range problem — a different design with different tradeoffs.
• Multi-region active-active. The Level 5 evolution: per-region quorums, async cross-region replication, and CRDT value types to make merges automatic. I’d name CRDTs as the direction and stop.
• Transactions. Cross-key atomicity needs consensus or 2PC — exactly the coordination this architecture exists to avoid. If the interviewer wants it, that’s a signal to switch architectures, not bolt it on.
• Security and multi-tenancy. Real products need auth, encryption, per-tenant quotas; none of it shapes this architecture.

Saying “I’d skip this, and here’s why” is a strong signal. It shows you know the full surface and are making deliberate scoping choices.

Interview flow summary

Architecture at a glance

WRITE PATH                              READ PATH

put(key, value, context)                get(key)
 ↓                                       ↓
Coordinator (any node)                  Coordinator (any node)
 ↓                                       ↓
hash(key) → preference list (N=3)       hash(key) → preference list (N=3)
 ↓                                       ↓
Parallel send to replicas               Parallel read from replicas
 ↓                                       ↓
W=2 acks → success                      R=2 responses → compare versions
 ↓                                       ↓
(replica down → hint to next node)      (stale replica → read repair)
                                         ↓
                                        (concurrent → return siblings)

The walkthrough order for your whiteboard

1. Requirements & contract  — surface "always-writable" — it decides everything
2. Capacity estimate        — 150 nodes; failure is steady state, data movement is the cost
3. Architecture evolution   — Levels 1–5; commit to Level 4 (leaderless ring)
4. Core choice              — who accepts writes; leaderless, justified by the contract
5. Consistent hashing       — ring, preference lists, virtual nodes, worked example
6. Write path               — quorum W, sloppy quorum, hinted handoff
7. Read path                — quorum R, R+W>N arithmetic, read repair
8. Conflicts                — vector clocks, worked sibling example, LWW honesty
9. API                      — context round-trip, per-request consistency dial
10. Data model              — LSM rationale, ring/hints/merkle schemas
11. Failure modes           — availability / consistency / durability groups

If the interviewer pushes deeper

14. Wrap-up

One crisp sentence before the interviewer’s next question:

This design buys always-writable availability by giving up the single-copy illusion — consistent hashing bounds what moves when topology changes, quorum overlap makes staleness the exception, and version vectors ensure that when concurrency does happen, the system surfaces both versions honestly instead of silently discarding one.

What separates levels on this question

• SDE II draws the hash ring, names N/R/W replication, and sketches get/put through a coordinator. Usually treats failure as an afterthought (“we’d detect it and rebalance”).
• SDE III runs the quorum arithmetic and says what R+W>N does not guarantee, explains hinted handoff and why hints aren’t replicas, walks a concrete conflict through vector clocks, chooses LWW vs siblings per value type, and names 4+ failure modes with what degrades in each.
• Staff/Principal frames the availability/consistency contract as a product decision and pins the interviewer down on it before designing; treats repair traffic and rebalance throttling as first-class capacity concerns (the fleet is storage-bound); knows where the metadata bites (vector-clock truncation, tombstone GC resurrection windows); and names the boundary where this architecture stops being the answer — transactions or strong ordering means consensus, not a bigger ring.

The difference isn’t knowledge. It’s honesty about guarantees — weaker candidates claim the quorum makes things consistent; stronger ones can say precisely which anomalies remain and why the contract tolerates them.

Further reading

• Dynamo: Amazon’s Highly Available Key-value Store — the paper this entire design space descends from. Consistent hashing, sloppy quorums, vector clocks, Merkle repair — all of it is here, with production war stories.
• Designing Data-Intensive Applications — Kleppmann. Chapter 5 (replication, including the leaderless section) and Chapter 6 (partitioning) are the best textbook treatment of every mechanism in this walkthrough.
• System Design Interview Vol. 1 — Alex Xu. Chapter 6 is the canonical interview-prep version of this question.
• Werner Vogels: Eventually Consistent — the consistency-model vocabulary (read-your-writes, monotonic reads) for naming exactly what a quorum configuration gives up.
• Cassandra architecture documentation — how a production system industrialized the Dynamo design: gossip, hinted handoff, and tunable consistency as shipped features.
• Riak’s vector clock documentation — the most readable practitioner’s guide to causal context and sibling resolution.