Catalog My learning Blog
Distributed Systems Explained: CAP, Clocks and Replication · Phase 2 · Lesson 13 · 5 min read

Amazon Dynamo Explained: Eventual Consistency

On this page
  1. Dynamo's requirement: never refuse a cart update
  2. Dynamo's building blocks
  3. A Dynamo write: sloppy quorum and hinted handoff
  4. A Dynamo read: siblings and read repair
  5. Anti-entropy with Merkle trees
  6. Dynamo's legacy: Cassandra, Riak and DynamoDB
  7. Check yourself

Dynamo's requirement: never refuse a cart update

Amazon's shopping cart had one overriding requirement: customers must always be able to add items, even when servers or data centers fail. An unavailable cart costs sales directly; a cart that briefly shows a stale item costs little. The 2007 paper "Dynamo: Amazon's Highly Available Key-value Store" describes the design that met it, and it shaped a generation of databases.

The trade-off was explicit: choose availability during partitions (AP, Day 5) and low latency the rest of the time (EL, Day 6), and handle the resulting conflicts deliberately.

Dynamo's building blocks

ProblemDynamo's techniqueCourse day
Spread data over nodesConsistent hashing with virtual nodes11
Keep copiesEach key on the next N distinct nodes clockwise7
Balance consistency and latencyTunable N, W, R quorums9
Concurrent updatesVector clocks to detect conflicts; siblings returned to the application4, 10
Temporary node failuresSloppy quorum with hinted handoff9
Permanent divergenceAnti-entropy with Merkle treesbelow
Membership and failure detectionGossip protocol20
A write goes to N replicas on the ring with hinted handoff if one is down; reads gather versions, reconcile them and repair stale replicas; Merkle trees find differences in the background.
A write goes to N replicas on the ring with hinted handoff if one is down; reads gather versions, reconcile them and repair stale replicas; Merkle trees find differences in the background.

A Dynamo write: sloppy quorum and hinted handoff

  1. The client sends put(cart:42, ...) to any node, which becomes the coordinator.
  2. The coordinator finds the key's N = 3 replicas on the ring and sends the write with an updated vector clock.
  3. One replica is down. Instead of failing, the coordinator writes to the next healthy node, with a hint: "this belongs to node C". (That's a sloppy quorum.)
  4. Once W = 2 replicas acknowledge, the write succeeds.
  5. When C returns, the substitute hands the data over (hinted handoff).

A Dynamo read: siblings and read repair

  1. The coordinator asks R = 2 replicas.
  2. If their versions are causally ordered (vector clocks), it returns the newest.
  3. If they're concurrent, it returns all versions as siblings; the application merges them (for carts: union of items) and writes back the merged version.
  4. Replicas that returned stale data are updated: read repair.

Anti-entropy with Merkle trees

Hinted handoff and read repair miss data that's rarely read or whose hints were lost. In the background, replica pairs compare data using Merkle trees: a tree of hashes where each leaf covers a range of keys and each parent hashes its children. Comparing roots tells you instantly whether two replicas match; if not, walk down only the branches that differ. Two replicas holding millions of keys find a handful of differences after exchanging a few hashes.

Here's that walk on two replicas of 100,000 keys, where one replica missed a single update:

Python
# merkle.py: find where two replicas differ by comparing hashes from the root down
import hashlib

def sha(s): return hashlib.sha256(s.encode()).hexdigest()
def bucket(key, n): return int(sha(key), 16) % n           # which key range a key falls in

def build(data, n=1024):                                   # n leaves, a power of two
    ranges = [[] for _ in range(n)]
    for k in sorted(data):
        ranges[bucket(k, n)].append(f"{k}={data[k]}")
    tree = [[sha(";".join(r)) for r in ranges]]            # leaf: hash of one key range
    while len(tree[-1]) > 1:                               # parent: hash of its two children
        lvl = tree[-1]
        tree.append([sha(lvl[i] + lvl[i + 1]) for i in range(0, len(lvl), 2)])
    return tree                                            # tree[-1][0] is the root

def diff(t1, t2, level, i, stats):
    stats["compared"] += 1
    if t1[level][i] == t2[level][i]:
        return []                                          # identical subtree: skip it all
    if level == 0:
        return [i]
    return diff(t1, t2, level - 1, 2 * i, stats) + diff(t1, t2, level - 1, 2 * i + 1, stats)

a = {f"cart:{n}": "v1" for n in range(100_000)}
b = dict(a); b["cart:4242"] = "v2"                         # one replica missed one update
ta, tb = build(a), build(b)
stats = {"compared": 0}
ranges = diff(ta, tb, len(ta) - 1, 0, stats)
print("ranges that differ:", ranges, "| hashes compared:", stats["compared"])
print("keys to exchange:", sum(1 for k in a if bucket(k, 1024) in ranges), "of", len(a))
Code
ranges that differ: [52] | hashes compared: 21
keys to exchange: 101 of 100000

Twenty-one hash comparisons narrowed 100,000 keys down to one range of about a hundred, and only those keys are sent across. With one leaf per key range, the work grows with the number of differences times the tree's height, not with the size of the data. Cassandra builds trees like these during nodetool repair, one per token range, and streams only the ranges whose hashes differ.

Dynamo's legacy: Cassandra, Riak and DynamoDB

  • Cassandra (2008) took Dynamo's partitioning and replication (ring, tunable consistency, hinted handoff, read repair, Merkle-tree repair, gossip) and combined it with Bigtable's data model. It uses last-write-wins per column instead of vector clocks and siblings, trading correctness under concurrency for simplicity.
  • Riak followed Dynamo closely, including vector clocks (later dotted version vectors) and CRDT data types.
  • Amazon DynamoDB (2012) shares the name and lessons but is a different, managed system: it uses leader-based replication per partition with Paxos, offers strongly consistent reads on request, and later added transactions.

The enduring lessons: decide the consistency trade-off per business need, make failure normal rather than exceptional, and push conflict handling to where the domain knowledge lives.

Check yourself

When a target replica is unreachable, another node accepts its writes temporarily, storing them with a hint saying who they belong to, and delivers them once the replica returns. Writes stay available during short outages, at the cost of temporarily weaker quorum guarantees.

Vector clocks showed the versions are concurrent, so the store can't pick a winner safely; the application merges them, for example by uniting cart items.

Replicas compare hashes from the root down and only examine branches whose hashes differ, so few hashes need exchanging to find differences.

When a read finds replicas with different versions, the coordinator writes the newest version back to the stale ones, so frequently read data converges quickly.

A refused cart update loses a sale, while a merged cart with an extra or reappearing item is a minor annoyance. The business cost decided the trade-off.