Cheat Sheet
Key takeaway
A key-value store is a distributed hash table: a key's hash is both its identity and its address. Every mechanism below exists because one requirement — always writable — forces the system to accept conflicting writes and reconcile them later.
Key terms
| Term | One line |
|---|---|
| DHT | Distributed hash table — key's hash determines its node |
| Coordinator | The node handling a get/put; first of the top n in the preference list |
| Preference list | The n successor virtual nodes holding a key's replicas |
| Virtual node | One physical server occupying many ring positions |
| Vector clock | List of (node, counter) pairs per object version |
| Context | Opaque version metadata returned by get, passed back on put |
| Sloppy quorum | Use the first n healthy nodes, not the designated owners |
| Hinted handoff | Substitute stores data + a note naming the real owner |
| Anti-entropy | Background replica repair via Merkle trees |
| Gossip | Peers randomly exchange membership info; eventually consistent |
Requirements
Functional: configurable consistency · ability to always write (A over C) · hardware heterogeneity. Non-functional: tens of thousands of servers, incremental scalability with minimal disruption · fault tolerance.
Assumptions: trusted data centers (crash faults, not Byzantine) · authn/authz external · HTTPS.
API
get(key) -> value(s) + context put(key, context, value) -> success
get can return MULTIPLE versions. That single fact generates vector clocks, reconciliation, and the context parameter. Dynamo uses MD5 to produce a 128-bit key identifier.
Partitioning — built in three moves
| Step | Problem | Fix |
|---|---|---|
hash(key) % m | Changing m remaps nearly every key | Rejected |
| Consistent hashing | — | Ring 0..n-1; key goes to first node clockwise; only the successor's keys move |
| Virtual nodes | Random gaps are uneven → hotspots | One server, many ring positions via multiple hash functions |
Virtual nodes give three wins:
- Even distribution — many small arcs average better than one large one
- Fault tolerance — a failed node's load spreads over many successors, not one neighbor
- Capacity management — bigger machine, more virtual nodes, more load
Replication
Peer-to-peer, not primary-secondary — a primary failing blocks writes, violating always-write.
Coordinator owns key K -> replicates to the next n-1 successors clockwise = preference list Typical n = 3 or 5
Preference list must skip virtual nodes whose physical machine is already listed — otherwise all replicas land on one box. Extend across data centers for catastrophic failures.
CAP posture: AP. During a partition nodes keep accepting requests, then reconcile on reconnect.
Vector clocks
Physical timestamps are unusable — clocks drift, so they can't order writes.
Vector clock = list of (node, counter) pairs per version Every counter in X <= matching counter in Y -> X is an ANCESTOR, discard it Each has a counter the other lacks -> CONCURRENT = conflict, keep both
Worked sequence:
A writes -> [A,1] A writes again -> [A,2] (supersedes [A,1]) --- partition --- B writes -> ([A,2], [B,1]) C writes -> ([A,2], [C,1]) concurrent -> conflict --- reconcile --- A coordinates -> ([A,3], [B,1], [C,1])
Client reconciles, not the store — only the application knows what the value means (Git merge model).
Truncation: clocks grow when writes land outside the top n. Attach a physical timestamp per entry, drop oldest past a threshold (~10). Cost: lost causal history → false conflicts (the safe direction to be wrong).
Configurability
r + w > n read and write sets must overlap
| n | r | w | Behavior |
|---|---|---|---|
| 3 | 2 | 1 | Illegal — violates the constraint |
| 3 | 2 | 2 | Allowed — balanced default |
| 3 | 3 | 1 | Fast writes, slow reads |
| 3 | 1 | 3 | Fast reads, slow writes |
Write path: coordinator generates the vector clock, writes locally, sends to top n; success at w-1 acks (its own write makes w); remainder replicated asynchronously.
Read path: query top n reachable, wait for r responses; return all unrelated versions; merged result written back (read repair).
Latency = slowest of the r replicas, not the average. Raising r costs tail latency and availability.
Client routing: generic load balancer (simple client) vs partition-aware library (lower latency, fewer hops).
Fault tolerance
| Failure | Mechanism | How it works |
|---|---|---|
| Temporary | Sloppy quorum + hinted handoff | First n healthy nodes take the write; substitute stores a hint; forwards on recovery |
| Permanent | Merkle trees (anti-entropy) | Exchange root hashes; match = identical; differ = recurse to find diverging leaves |
| Membership | Gossip | Peers randomly exchange token sets; eventually consistent; no coordinator |
Merkle tree: leaves hash values, parents hash children. Root match proves gigabytes identical in one comparison; locating divergence is logarithmic. Cost: ring membership changes force tree recomputation.
Failure detection is deliberately conservative — most outages are transient, hinted handoff keeps the system writable, and rebalancing is expensive. Ring changes only on confirmed sustained failure or planned change. Nodes announce joins/leaves; death is inferred from silence past a threshold.
Quick decision cues
- Access is lookup by identity → key-value store
- Must never reject a write → peer-to-peer + sloppy quorum, not primary-secondary
- Heterogeneous fleet → virtual nodes proportional to capacity
- Concurrent writes possible → vector clocks + client reconciliation
- Cart-like data → w = 1 (never reject), pay with high
r - Read-dominated catalog → r = 1, pay with
w = n - Node briefly down → hinted handoff
- Node replaced/long outage → Merkle anti-entropy
- Need strong consistency → this is the wrong design; use single-leader + consensus
Work the Interview Walkthrough for the full design under time pressure, and the Concept Drills for rapid-fire practice.