Courses › System Design › Question Breakdowns

Design a Distributed Key-Value Store

Consistent hashing, quorums and hinted handoff, conflict resolution, gossip and anti-entropy, LSM storage.

Design a distributed key-value store like Amazon Dynamo, Cassandra or DynamoDB: put(key, value) and get(key) over hundreds of TB on many machines, staying available when machines and networks fail. Unlike a Distributed Cache, this is the source of truth — data must be durable. It's the classic question about partitioning, replication, quorums and tunable consistency, conflict resolution, failure detection and the storage engine on each node.

Requirements

Functional

  • put(key, value), get(key), delete(key); values up to ~1 MB
  • (Variant) Conditional writes (compare-and-set on a version) and optional TTLs
  • Clients can choose consistency per request (e.g. strong vs. eventual reads)

Out of scope: secondary indexes, range scans across partitions, multi-key transactions (mention as extensions).

Non-functional

  • Scale: ~100 TB, ~1M operations/second, growing by adding nodes
  • Highly available: writes succeed even when some replicas are down (AP by default; see CAP Theorem)
  • Durable: acknowledged writes survive node and disk failures
  • Low latency: p99 < 10ms within a region
  • Incremental scalability with no downtime; no single point of failure

[!TIP] Name your consistency model early "Strong or eventual?" drives everything: quorum sizes, conflict handling, and what happens during a partition. A strong default answer is tunable consistency with quorums (R + W > N for read-your-writes) plus an explicit plan for conflicts when you choose availability.

Capacity estimates

Core Entities

  • Key / value — opaque bytes, plus a version (vector clock or timestamp)
  • Partition / token range — the slice of the hash ring a node owns
  • Node — ID, token ranges, status (up / down / joining)
  • Hinted handoff entry — a write held for a replica that was down

API

PUT /v1/kv/{key}?consistency=quorum          (body: value; If-Match: <version> for compare-and-set)
→ 200 { "version": "..." }

GET /v1/kv/{key}?consistency=one|quorum|all
→ 200 value  (or several sibling values + versions if they conflict)

DELETE /v1/kv/{key}

High-Level Design

c = client "Client" @0,1
coord = service "Coordinator Node\n(any node)" @1,1
n1 = store "Replica 1" @2,0
n2 = store "Replica 2" @2,1
n3 = store "Replica 3" @2,2
gossip = note "Gossip: membership +\nfailure detection" @3,0
ring = note "Ring: hash(key) → next\nN nodes clockwise" @3,2
c -> coord : put / get
coord -> n1
coord -> n2
coord -> n3
n1 <-> n2 : anti-entropy
  • Partitioning: keys are hashed onto a consistent hashing ring with virtual nodes; a key's preference list is the next N distinct nodes clockwise.
  • Coordinator: any node can receive a request and coordinate it — clients don't need to know the ring (or smart clients route directly).
  • Writes go to all N replicas; the coordinator returns success after W acknowledge. Reads query replicas and return after R respond, resolving versions.
  • Membership spreads by gossip; background anti-entropy repairs replicas that drifted.

Deep Dives

1. Partitioning

Consistent hashing with ~256 virtual nodes per physical node spreads data evenly and lets a new node take small slices from many others (see Consistent Hashing). Heterogeneous hardware gets proportionally more virtual nodes. Place a key's N replicas in different racks / availability zones.

2. Quorums and tunable consistency

With N = 3:

Sloppy quorum + hinted handoff: if a preferred replica is down, write to the next healthy node with a hint; it forwards the data when the replica recovers. Writes stay available during failures, at the cost of strict quorum guarantees.

3. Conflicts

With availability over consistency, two clients can write the same key on different replicas during a partition.

  • Last-writer-wins by timestamp (Cassandra): simple, but silently drops one write and depends on clock sync.
  • Vector clocks (Dynamo): detect concurrent versions and return siblings for the application to merge (the shopping-cart example).
  • CRDTs for data types that merge automatically (counters, sets).
  • Conditional writes with a version (compare-and-set) give per-key linearizability when routed through a single leader per partition (DynamoDB uses a Paxos-elected leader per partition for this).

[!WARNING] LWW needs trustworthy clocks Clock skew between nodes can make an older write "win". If you choose last-writer-wins, say so explicitly, use hybrid logical clocks or server-assigned timestamps, and accept that concurrent writes lose data.

4. Repair and failure detection

  • Gossip: every second each node exchanges membership and heartbeat state with a few random peers; a node not heard from (phi-accrual detector) is suspected down.
  • Read repair: when a read sees stale replicas, the coordinator writes back the newest version.
  • Anti-entropy: replicas compare Merkle trees of their key ranges and sync only differing ranges — cheap even for TBs.
  • Permanent failures are handled by an operator (or automation) removing the node; its ranges are re-replicated.

5. Storage engine on each node

Write-heavy workloads favor an LSM tree (see Database Indexing):

Write -> (Commit log on disk) -> [Memtable in memory] -> (Flushed SSTables) -> [Compaction]
  • Writes append to a commit log (durability) and a memtable; full memtables flush to immutable sorted SSTables.
  • Reads check the memtable, then SSTables newest-first, skipping files via Bloom filters.
  • Compaction merges SSTables and drops overwritten/deleted data (tombstones expire after the repair window).

6. Adding nodes

A joining node takes ownership of some virtual-node ranges, streams that data from current owners, and only then starts serving reads for them. Gossip spreads the new ring. No downtime, and only ~1/N of the data moves.

What's expected at each level

  • Mid-level: consistent hashing, replication across nodes, a sensible get/put path.
  • Senior: quorums with R + W > N, sloppy quorum and hinted handoff, conflict resolution options, gossip-based membership.
  • Staff: vector clocks vs. LWW vs. per-partition leaders, Merkle-tree anti-entropy, LSM internals and tombstones, and what consistency each client choice really guarantees during partitions.