Your cart service writes on every click, and in December it cannot reject a single add-to-cart. During the peak a disk will fail, a rack switch will flap, maybe a data center will drop off the network. A single primary database turns each of those into an outage.
Amazon's 2007 Dynamo paper described a store that keeps taking writes through all of that; Cassandra and Riak KV borrowed most of its clustering ideas. This post designs a Dynamo-style store from the API to the storage engine, compares real systems and draws the result.
Requirements and API
Dynamo's interface has two operations:
get(key) -> [value, ...], context
put(key, context, value) -> ok
get can return conflicting versions plus an opaque context; the next put passes it back to say which versions it replaces. The requirements:
- Always writable, even with nodes or links down.
- Predictable tail latency. The paper's example SLA is 300 ms for 99.9% of requests at a peak of 500 requests per second.
- Small values, single keys: objects usually under 1 MB, no multi-key operations.
- Incremental scale, one node at a time.
Sizing, assuming 1 KB values and half-full disks for compaction headroom: 1 billion keys is 1 TB, 3 TB with three copies, so six 1 TB nodes, like the diagram's ring. At 30,000 writes per second, three copies mean 90,000 replica writes, or 15,000 per node.
CAP and PACELC in brief
CAP says that during a network partition a store must refuse some requests or risk stale reads; Dynamo stays available. Daniel Abadi's PACELC (2012) adds that without a partition you still trade latency for consistency; he classifies the default configurations of Dynamo, Cassandra and Riak as PA/EL.
Partitioning with a hash ring and virtual nodes
Dynamo hashes each key with MD5 to a 128-bit position on a ring, and the key belongs to the first node clockwise. When a node joins or leaves, only neighboring ranges move, instead of nearly every key as with hash(key) % N; the consistent hashing diagram shows how.
One position per node spreads data unevenly, so each node takes many, called virtual nodes or tokens. Cassandra 5.0 ships with 16 tokens per node; Riak's ring has 64 partitions by default. You give up range scans: neighboring keys land on different nodes, as the database sharding diagram explains.
Replication and preference lists
Each key lives on N nodes: the coordinator (the first node clockwise) and the next N − 1 distinct physical nodes. The key's preference list continues past them, so stand-ins exist when a replica is down. Spread replicas across failure domains: Dynamo spread each list across data centers, and Cassandra's NetworkTopologyStrategy spreads them across racks. Every replica accepts writes, unlike the leader-based setups in the database replication diagram.
Quorums: R + W > N
The coordinator sends each write to all N replicas and replies after W acknowledgments; a read replies after R answers. If R + W > N, any read set and any acknowledged write set share at least one node.
| N, R, W | R + W > N | What you get | What you pay |
|---|---|---|---|
| 3, 2, 2 | Yes | Reads see the latest acknowledged write; one replica can fail | Each request waits for the second-fastest reply |
| 3, 1, 3 | Yes | Fast reads from any replica | Writes wait for all three |
| 3, 1, 1 | No | Lowest latency, highest availability | Reads can be stale |
| 5, 3, 3 | Yes | Two replicas can fail | Five copies of every value |
The Dynamo paper's common configuration was (3, 2, 2), and read-heavy services like the product catalog used R = 1, W = N. Cassandra sets a consistency level per request, from ONE to ALL; QUORUM for reads and writes gives R + W > N.
Overlap is not linearizability. A write that reaches one replica and then fails can appear in one read and vanish from the next; Cassandra's default blocking read repair prevents that for quorum reads. Compare-and-set needs consensus, as in Cassandra's lightweight transactions or a Raft-based store.
Conflicts: last write wins, vector clocks or CRDTs
Concurrent writes through different replicas leave two versions. Three ways out:
| Strategy | How it resolves | Can it lose updates? | Used by |
|---|---|---|---|
| Last write wins | Highest timestamp wins | Yes, silently; clock skew picks the winner | Cassandra, DynamoDB global tables, Riak if configured |
| Vector clocks | Keeps concurrent versions; the client merges | No, but every client must merge | Dynamo, Riak (dotted version vectors) |
| CRDTs | Data types whose merges always converge | No, for the supported types | Riak counters, sets and maps |
A vector clock is a list of (node, counter) pairs. A version whose counters are all less than or equal to another's is an ancestor and can go; otherwise both are kept. The cart service merged conflicting carts, so added items were never lost, though deleted ones could come back. Conflicts were rare: over 24 hours, 99.94% of cart requests saw exactly one version. CRDTs move the merge into the data type itself; collaborative editors built on CRDTs apply the same idea to shared text.
Failure handling: hinted handoff, repair and gossip
Sloppy quorum and hinted handoff. Dynamo uses the first N healthy nodes on the preference list: if C is down, D takes C's copy with a hint and returns it when C recovers. Writes keep working, but a read from B and the recovered C can then miss a write that only A and D acknowledged. Cassandra keeps quorums strict: hints count toward the consistency level only at ANY and stop after a node has been down for 3 hours (max_hint_window).
Read repair and anti-entropy. When replies disagree, the coordinator writes the newest version back to stale replicas. For cold data, replicas compare Merkle trees per key range and sync only the ranges that differ. Cassandra's docs recommend running nodetool repair on every node at least every 7 days: tombstones are purged after gc_grace_seconds (10 days by default), and an unrepaired replica can bring deleted data back.
Gossip and failure detection. Every second, each node swaps membership and token state with a random peer; seed nodes known to all keep the ring from splitting. Cassandra's phi accrual detector marks a peer down when suspicion crosses phi_convict_threshold (default 8).
The write path: commit log, memtable, SSTables
Cassandra's storage engine is a write-optimized log-structured merge (LSM) tree:
- Append the write to the commit log. By default (
periodic), Cassandra acknowledges at once and syncs every 10 seconds, so a crash can lose that window. - Insert it into the memtable, a sorted in-memory structure.
- Flush a full memtable to an immutable, sorted SSTable on disk.
- Compact SSTables in the background, keeping the newest versions and dropping expired tombstones.
Reads check the memtable, then SSTables, and a Bloom filter per SSTable skips files that cannot hold the key: with 10 bits per key and 7 hash functions, the false positive rate is (1 − e^(−0.7))^7, about 0.8%. Size-tiered compaction is the default; Cassandra 5.0 recommends its unified strategy for new workloads.
Real systems versus the paper
| Dynamo (2007) | Amazon DynamoDB | Cassandra 5.0 | Riak KV | |
|---|---|---|---|---|
| Partitioning | MD5 ring, equal partitions | Ranges that split by size or traffic | Murmur3 ring, 16 tokens per node | 160-bit ring, 64 partitions |
| Replication | Leaderless, N per key | 3 replicas across AZs, Multi-Paxos leader | Leaderless, per data center | Leaderless, n_val 3 |
| Consistency | Sloppy quorum | Eventual by default; strong reads from the leader | Consistency level per request | Sloppy quorum, pr and pw |
| Conflicts | Vector clocks | Leader orders writes; last writer wins across Regions | Last write wins | Siblings or CRDTs |
| Storage | Berkeley DB, MySQL | B-tree plus write-ahead log | LSM tree | Bitcask, LevelDB |
DynamoDB shares the name, not the design: per its 2022 USENIX paper, the partition leader acknowledges a write once two of three replicas have logged it. Global tables default to last writer wins across Regions; at the time of writing (November 2026) they also offer multi-Region strong consistency in exactly three Regions.
The Dynamo-style key-value store diagram
Diagram contents
- Node B
- Node A
- Node C
- Node F
- Node D
- Node E
- Cart service
- Inside every node: LSM write path
- Commit log
- Memtable
- SSTables
- put(k, ctx, v)
- replica 2: ack
- replica 3: no reply
- hinted write for C: ack
- hand off when C recovers
- then insert
- flush when full
- gossip
How to read it:
- The ring. Walking clockwise from hash(k), the dot, gives the preference list A to F.
- The write. The cart service sends put(k, ctx, v) to coordinator A, which replicates to B and C.
- The failure. C is down, so D takes C's copy with a hint (dashed amber) and hands it back later. With W = 2, the put returns once A and B have it.
- Gossip (dotted) runs between random pairs of nodes.
- The panels list N, R, W and each node's write path.
Drawing key-value store diagrams clearly
- Follow one key. Mark its hash, write out its preference list and put N, R and W beside it; a ring with no key explains nothing.
- Draw the failure. A red node and a dashed fallback edge explain a sloppy quorum faster than prose.
- Show failure domains: color replicas by rack or zone so reviewers can check that no two copies share one.
- Leave node internals to one inset. The cluster comes first.
A common mistake: arrows from the client to every replica and no coordinator, which hides who decides that a write succeeded. The step-by-step system design method covers layout and numbers.
Build it in Archboard
- Sign in with Google or GitHub and create a diagram.
- Add a large gray Ellipse from the Core pack for the token ring.
- Place six Server nodes from the Network pack on the ring, Node A to Node F clockwise. Color A and B green, C red and D amber, and label their roles with Core Text notes.
- Add a small Ellipse on the ring just before Node A for hash(k), with a Text label.
- Add a Container from the C4 Model pack for the cart service, with a put(k, ctx, v) edge to Node A.
- Draw the edges: A to B solid green, A to C dashed red with a cross arrowhead, A to D and D to C dashed amber (hinted write, then handoff), and a dotted gossip edge between F and E with a Text note.
- Add a Markdown block from the Core pack with N, R, W and the scenario.
- Add a Frame from the Core pack with three Component nodes from the C4 Model pack, Commit log, Memtable and SSTables, linked top to bottom, and a Text note on Bloom filters.
The example uses 14 diagram nodes, within the Free plan.
FAQ
How do you design a distributed key-value store? Partition with consistent hashing, replicate each key to N nodes, tune R and W, pick a conflict strategy, add hinted handoff and anti-entropy repair, and run an LSM tree per node.
What does R + W > N mean? Of N replicas, a write waits for W and a read for R. If R + W exceeds N, every read reaches at least one replica that holds the latest acknowledged write.
Is DynamoDB based on the Dynamo paper? Only partly: each partition has three replicas with a Multi-Paxos leader and B-tree storage, not sloppy quorums and vector clocks.
What is hinted handoff? Another node stores an unreachable replica's write with a hint and delivers it when the replica returns. Cassandra stops hinting a node after 3 hours of downtime by default.
Should I use last write wins or vector clocks? Last write wins suits data where losing a concurrent update is acceptable, such as sessions. Use vector clocks or CRDTs when every update matters, like carts and counters.