Design a Distributed Key-Value Store (Dynamo-style)

hard

Scale: Linear scale with nodes; ms-level p99 Storage: PB-scale across cluster; replication factor × dataset Amazon, Netflix, Apple

Case StudyKV StoreQuorum

A Dynamo-style distributed KV store provides scale-out and high availability for simple put/get. Amazon's Dynamo paper defined the pattern; production systems include DynamoDB, Cassandra, Riak, ScyllaDB, FoundationDB. Philosophy: every node equal, AP by default, tunable consistency.

ScaleLinear scale with nodes; ms-level p99

StoragePB-scale across cluster; replication factor × dataset

Key Concepts

1. Partitioning + replication. Consistent hashing with virtual nodes (ID 162). Each key's N replicas live on the next N distinct physical nodes clockwise. Coordinator (any node) takes the request, fans out to replicas. Membership and health tracked via gossip (SWIM, phi-accrual failure detector).

1. Partitioning + replication.

2. Tunable quorums. put(k, v) waits for W of N writes; get(k) queries R of N. R + W > N gives strong consistency. R = W = 1 gives eventual with lowest latency. R = N, W = 1 optimizes for writes. R = 1, W = N optimizes for reads. Cassandra exposes per-query (ONE / QUORUM / ALL); DynamoDB exposes eventual vs strong reads.

2. Tunable quorums.put(k, v)get(k)

3. Sloppy quorum + hinted handoff. During a partition, an intended replica is unreachable. Coordinator writes to the next live node with a hint: 'this was meant for X'. When X returns, the neighbor replays the hint and deletes it. Writes stay available even under partition — at the cost of brief inconsistency.

3. Sloppy quorum + hinted handoff.

4. Conflict resolution. Concurrent writes from different clients can diverge. LWW (Last-Write-Wins): timestamp on each write; latest wins. Simple but loses concurrent updates and needs synchronized clocks. Vector clocks: tag writes with [node_id → counter]; reads return siblings, app resolves (Riak's approach). CRDTs: data types with commutative + associative merges (G-counters, OR-sets) — automatic, no siblings, restricted data model.

4. Conflict resolution.[node_id → counter]

5. Anti-entropy and operations. Replicas periodically exchange Merkle trees of key ranges, identify mismatches, synchronize. Read repair fixes mismatches noticed during reads. Storage engine is typically LSM-tree (RocksDB, Cassandra SSTables) — high write throughput, read amplification, background compaction. Wide rows allow time-series and log-style access. No multi-key transactions (or limited) — design schema as single-key updates.

5. Anti-entropy and operations.

High-level design

Ring: consistent hashing with vnodes (256 per physical node typical).
Replicas: next N distinct physical nodes clockwise from primary.
Coordinator: any node receives request, fans out to replicas.
Quorum: wait for W writes / R reads; respond.
Failure: sloppy quorum + hinted handoff during partition; anti-entropy reconciles.
Conflict: LWW (simple) or vector clocks (precise) or CRDTs (automatic merge).

Components

Coordinator service (any node).
Local storage engine — LSM-tree (RocksDB, Cassandra's SSTable) for write-heavy.
Gossip / failure detector (SWIM, phi-accrual).
Hinted handoff queue.
Anti-entropy worker (Merkle tree compare).
Read repair on detected mismatch.
Compaction (LSM background).
Client SDK with smart routing (knows the ring; sends directly to coordinator).

Consistency tuning

R + W > N: strongly consistent (every read sees latest committed write).

R = N, W = 1: write-optimized; read all to find latest.

R = 1, W = N: read-optimized; write to all.

R = W = QUORUM = ceil(N/2)+1: balanced default.

R = W = 1: eventual; lowest latency.

Per-query knob in Cassandra / DynamoDB (eventual vs strong reads).

Sloppy quorum + hinted handoff

During partition, replica A is unreachable.
Coordinator writes to A's clockwise neighbor with a hint: 'this was meant for A'.
When A returns, neighbor replays the hint and deletes it.
Keeps writes available but introduces brief inconsistency.
Reads from A may not see the hint until replay.

Conflict resolution

LWW (timestamps): every write tagged with timestamp; later wins. Simple but loses concurrent updates and needs synchronized clocks.

Vector clocks: tag each write with [node_id → counter] vector. Concurrent updates produce divergent vectors; coordinator returns siblings; app resolves.

CRDTs: data types with commutative + associative merge. G-counter (increment-only), OR-set, RGA (text), maps. Merge is automatic; no siblings.

Tombstones: deletes need explicit markers (gravestones) that persist long enough for all replicas to learn.

Trade-offs

Higher N: more durable, more storage, slower writes.

LWW: simple, lossy.

Vector clocks: precise, app complexity.

CRDTs: clean merge, restricted data model.

LSM storage: high write throughput, read amplification, compaction CPU.

Wide rows: time-series, log-style access patterns shine.

No multi-key transactions (or limited): keep schema as single-key updates.