System 12.33 — Distributed Key-Value Store (Dynamo-style)
In one line
Design a highly available, horizontally scalable get/put store: consistent hashing with virtual nodes, replication with tunable quorums, versioning and conflict resolution, hinted handoff, gossip membership, and Merkle-tree repair.
Think of it like this
A chain of storage lockers across a city. Your locker number decides which branch keeps it (consistent hashing), each branch keeps copies at the next two branches (replication), and if one branch is closed a neighbour holds your parcel temporarily and returns it later (hinted handoff).
Key ideas
- 01
PARTITIONING: consistent hashing on the key (Phase 8), with many VIRTUAL NODES per physical node for even load and smooth rebalancing when nodes join or leave.
- 02
REPLICATION & QUORUMS: each key is stored on N nodes (the next N distinct nodes on the ring). Writes wait for W acknowledgements, reads for R;
W + R > Ngives read-your-latest-write in the normal case (e.g. N=3, W=2, R=2). Clients choose per request: W=1 for speed, W=N for durability (Phase 13, quorum). - 03
VERSIONS & CONFLICTS: concurrent writes on different replicas are detected with vector clocks (Phase 13B, clocks) and resolved by last-write-wins, application merge, or CRDTs. READ REPAIR fixes stale replicas found during reads.
- 04
FAILURES: SLOPPY QUORUM + HINTED HANDOFF keeps writes available when a replica is down; GOSSIP spreads membership and failure suspicion; MERKLE-TREE anti-entropy repairs divergence in the background (Phase 13B, gossip & Merkle trees). Storage per node: an LSM engine for fast writes (Phase 13B, storage engines).
Code & diagrams
Explain without notes
What does W + R > N guarantee, and what doesn't it guarantee?
Practice
Choose N, W, R for (a) a shopping cart that must never reject writes, (b) account balances.
Trade-offs
- ↔
Tunable quorums trade latency and availability against consistency per request; leaderless designs maximise availability but push conflict handling to the application.
Run it in production
You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:
Completion checklist
I can explain ring placement, quorums, hinted handoff, and anti-entropy