Skip to content

Distributed Key-Value Store#

Problem statement (interviewer prompt)

Design a distributed key-value store (Dynamo / Cassandra style). It must be always-writable, horizontally scalable, tunably consistent (R+W>N), and survive node + DC failures. Explain partitioning, replication, gossip, anti-entropy, and read repair.

flowchart LR
  C([Client])
  R[Coordinator / Router]
  N1[(Node 1<br/>range A-H)]
  N2[(Node 2<br/>range I-P)]
  N3[(Node 3<br/>range Q-Z)]
  C --> R
  R --> N1
  R --> N2
  R --> N3
  N1 <-. replicate .-> N2
  N2 <-. replicate .-> N3
  N3 <-. replicate .-> N1

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class C client;
    class R service;
    class N1,N2,N3 datastore;

flowchart TB
  subgraph Clients
    CL([App with smart driver])
  end

  subgraph Coordination
    GOSS[Gossip - SWIM]
    RING[Consistent hash ring<br/>tokens / vnodes]
    SEED[Seed nodes]
    REG[(Cluster meta)]
  end

  subgraph Node[Storage Node x N]
    direction TB
    COO[Coordinator]
    PART[Partitioner<br/>hash key]
    REP[Replicator<br/>N replicas, R/W quorum]
    MEM[Memtable<br/>sorted in-memory]
    WAL[[Commit log / WAL]]
    SS[(SSTable on disk<br/>LSM-tree)]
    COMP[Compaction<br/>size-tiered / leveled]
    BF[Bloom filter per SSTable]
    SUM[Index summary]
    HH[Hinted handoff]
    AE[Anti-entropy<br/>Merkle tree repair]
    RR[Read repair]
  end

  subgraph Consistency[Consistency Levels]
    ONE[ONE]
    QUO[QUORUM<br/>R+W>N]
    ALL[ALL]
    LWT[Lightweight Tx<br/>Paxos / EPaxos]
    CRDT2[CRDTs - opt]
  end

  subgraph Ops[Ops & Tooling]
    SNAP[Snapshots / Backups]
    REPAIR([Scheduled repair])
    BAL[Token rebalancer]
    MET[Metrics: read latency,<br/>pending compactions]
  end

  CL --> COO
  PART --> RING
  COO --> PART
  COO --> REP --> Node
  Node --> WAL --> MEM
  MEM -. flush .-> SS
  SS --> BF --> SUM
  SS --> COMP
  COO --> HH
  HH -.replay.-> Node
  AE --- Node
  RR --- COO
  GOSS --> RING
  SEED --> GOSS
  Consistency --- COO
  Ops --- Node

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class CL client;
    class GOSS,RING,SEED,COO,PART,REP,COMP,SUM,HH,AE,RR,ONE,QUO,ALL,LWT,CRDT2,SNAP,BAL service;
    class REG,MEM,SS,BF datastore;
    class WAL queue;
    class REPAIR compute;
    class MET obs;

Write path#

  1. Client → coordinator node (any peer).
  2. Coordinator hashes key → owners on ring, picks N replicas.
  3. Forwards write; each replica appends to WAL, applies to memtable.
  4. Acknowledged when W replicas confirm.
  5. Memtable flushes to SSTable; background compaction merges.

Read path#

  1. Client → coordinator.
  2. Coordinator queries R replicas in parallel.
  3. Compares versions (vector clock / timestamp), returns latest.
  4. On divergence → read repair.

LSM internals#

  • Memtable = skiplist / red-black tree.
  • SSTables immutable, sorted by key.
  • Bloom filter avoids disk reads for missing keys.
  • Compaction styles: size-tiered (Cassandra default), leveled (RocksDB / LevelDB).

Anti-entropy#

  • Merkle tree per range - replicas compare hashes, repair diffs.
  • Hinted handoff buffers writes destined for a down replica.

Failure handling#

  • Node down: gossip propagates "DN" state in seconds.
  • New node: streams ranges from peers; reads from old + new during bootstrap.
  • Quorum survives (N-1)/2 failures.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag Concept What it is Page
HLD Consistent hashing key placement with minimal remap consistent-hashing
HLD Raft / Paxos consensus replicated state machine via majority quorum consensus-raft-paxos
HLD Leader/follower replication sync/semi-sync/async replication, failover replication-leader-follower
HLD LSM vs B-Tree engines WAL, memtable, SSTables, compaction storage-engines-lsm-btree
HLD Probabilistic data structures Bloom, HLL, Count-Min, MinHash, t-digest probabilistic-data-structures
HLD Logical clocks Lamport, vector clocks, HLC, TrueTime logical-clocks
HLD Observability metrics, logs, traces, SLOs observability
LLD Testing strategy pyramid, doubles, TDD, contracts testing-strategy
LLD Immutability immutable types, persistent collections immutability

Quick reference#

Goals (Dynamo paper)#

  • Always writable (AP).
  • Symmetric, decentralized nodes.
  • Incremental scalability.
  • Heterogeneous hardware support.

Data model#

  • key → opaque blob (or column family).
  • Sometimes secondary indexes (materialized views in Cassandra).

Quorum tuning (N, R, W)#

  • N = replicas, R = read consensus, W = write consensus.
  • R + W > N → linearizability-like guarantee for last-writer wins.
  • Common: N=3, R=W=2 → strong-ish, tolerate 1 down.
  • Lower W=1 for fast writes (less durable).

Conflict resolution#

  • Last-writer-wins (server clock) - easy, can lose data.
  • Vector clocks (Dynamo) - keep siblings, app reconciles.
  • CRDT counters / sets - automatic merge.

Capacity#

  • 1 PB across 100 nodes ≈ 10 TB/node.
  • 100k ops/s/node common with SSD.
  • Compaction can double IO; size accordingly.

Trade-offs#

  • Tunable consistency is great but operationally complex.
  • Wide rows in Cassandra → range scans cheap but hotspot risk.
  • TTL columns → tombstones → compaction pressure.
  • LWTs (Paxos) much slower than normal write.

Refs#

  • Dynamo paper (SOSP '07), Cassandra design doc, ScyllaDB blog, Riak vs Cassandra comparisons, RocksDB tuning guide.

FAQ#

How do quorum reads and writes work?#

With N replicas, a write succeeds when W replicas ack and a read returns when R replicas respond. If R + W > N, every read sees the latest committed write.

What is gossip protocol in a key-value store?#

Each node periodically exchanges membership and health state with random peers. Information converges across the cluster without a coordinator, surviving partitions.

Eventual vs strong consistency: which to choose?#

Eventual consistency maximizes availability and write throughput. Strong consistency is needed when reads must reflect the latest write, like balances or unique usernames.

What is read repair?#

On a quorum read the coordinator notices replicas with stale data and writes back the latest version, repairing divergence opportunistically without a full anti-entropy run.

How does a key-value store handle node failures?#

Replicas on the hash ring keep serving traffic. Hinted handoff stores writes for the down node, and anti-entropy with Merkle trees reconciles data once it returns.

Further reading#

Curated, high-credibility sources for going deeper on this topic.