In 2007, Amazon published a paper titled "Dynamo: Amazon's Highly Available Key-value Store". This paper didn't just describe a database—it laid out a comprehensive architecture for building highly available distributed systems. Its influence cannot be overstated.

Dynamo's innovations addressed real operational pain at Amazon's scale: the company's e-commerce infrastructure needed to survive datacenter failures, handle holiday traffic spikes, and provide millisecond latencies to millions of concurrent shoppers. Traditional databases couldn't meet these requirements.

The resulting "Dynamo-style" architecture became a template, inspiring databases like Cassandra, Riak, Voldemort, and influencing countless proprietary systems. Understanding Dynamo's approach is essential knowledge for any engineer working with distributed systems.

Before diving into Dynamo's architecture, we must understand the operational context that drove its design. Amazon's requirements were specific and demanding, shaped by years of running large-scale e-commerce infrastructure.

The core requirement: "Always writeable"

"Even if disks are failing, network routes are flapping, or entire datacenters are being destroyed, the shopping cart should remain available."

This single requirement shaped every design decision. Availability wasn't just important—it was the primary constraint. Temporary inconsistency was acceptable; losing customer actions was not.

Service Level Agreements (SLAs) at Amazon:

Amazon's internal SLAs specified latency requirements in percentiles, not averages:

• p99.9 latency < 300ms for reads and writes
• Targets applied even during peak traffic (holiday shopping)
• Individual slow requests were tracked and investigated

This focus on tail latency influenced Dynamo's design significantly. Techniques that improved average latency but worsened p99 were rejected. Every design decision had to be evaluated at the tail.

Dynamo's data distribution strategy builds on consistent hashing, but with crucial enhancements that address the limitations of the basic algorithm.

Basic consistent hashing recap:

1. Nodes and keys are mapped to positions on a conceptual ring (0 to 2^128-1 or similar)
2. Each key is stored on the first node clockwise from its position
3. When nodes join/leave, only keys in the affected segment need to move

The problem with basic consistent hashing:

With random node placement, the distribution is rarely uniform:

• Some nodes get much larger ring segments than others
• Node additions/removals cause uneven load redistribution
• Doesn't account for heterogeneous hardware (faster nodes should handle more)

Dynamo's solution: Virtual nodes (vnodes)

Instead of each physical node having one position on the ring, Dynamo assigns multiple "virtual nodes" to each physical node:

Physical Node A → Virtual nodes: v1, v5, v9, v12, v18
Physical Node B → Virtual nodes: v2, v6, v10, v14, v21
Physical Node C → Virtual nodes: v3, v7, v11, v15, v19
Physical Node D → Virtual nodes: v4, v8, v13, v16, v20

Ring with 21 positions, evenly distributed

Benefits of virtual nodes:

For each key, Dynamo maintains a preference list: an ordered list of nodes that should store replicas of that key. The preference list determines which nodes participate in reads and writes, and in what order they're preferred.

Constructing the preference list:

1. Hash the key to find its position on the ring
2. Walk clockwise, collecting nodes that should store replicas
3. Skip virtual nodes belonging to physical nodes already in the list (to ensure replicas are on different physical machines)
4. Continue until N distinct physical nodes are collected (where N = replication factor)

Example with N=3:

Key K hashes to position 50
Walking clockwise:
  - Position 52: vnode owned by Physical Node A → Add A
  - Position 55: vnode owned by Physical Node A → Skip (A already included)
  - Position 58: vnode owned by Physical Node B → Add B  
  - Position 61: vnode owned by Physical Node C → Add C
  - Preference list complete: [A, B, C]

Coordinator selection from preference list:

The first node in the preference list is called the coordinator for that key. When a client wants to read or write, it should contact the coordinator first. However, if the coordinator is unavailable, the client can contact any node in the preference list.

Why ordering matters:

The preference list order has implications:

1. Read repair is more efficient — When the coordinator processes a read, it can easily compare with other nodes in the known list
2. Hinted handoff is targeted — If a node is down, hints are stored for specific list positions
3. Consistency operations know the authoritative set — Anti-entropy and repair know which nodes should have the data

Dynamo's "always writeable" requirement led to two interconnected innovations: sloppy quorums and hinted handoff. These mechanisms allow writes to succeed even when the preferred replica nodes are unavailable.

Traditional (strict) quorums:

With strict quorums, a write to a key must reach nodes in that key's preference list:

Preference list for key K: [A, B, C]
Write requires 2 of 3 (quorum)

If A and B are available → Write succeeds
If only A is available → Write FAILS (can't reach quorum)

Sloppy quorums:

Dynamo extends the concept: if preferred nodes are unavailable, the system can write to other nodes outside the preference list:

Preference list for key K: [A, B, C]
Write requires 2 of 3

If only A is available:
  → Write to A (preferred)
  → Write to D (next healthy node on ring, outside preference list)
  → Write succeeds! (sloppy quorum met)

The key insight: durability is preserved (data exists on 2 nodes) even though it's not on the "correct" nodes temporarily.

Hinted handoff mechanics:

When data is written to a non-preferred node (like D in the example above), the write includes a hint—metadata indicating the intended recipient:

Data stored on Node D:
{
  key: K,
  value: V,
  timestamp: T,
  hint: {
    intended_for: "Node B",
    reason: "B unreachable during write"
  }
}

Node D periodically checks if Node B has recovered. Once B is healthy:

1. D sends the hinted data to B
2. B acknowledges receipt
3. D deletes the hinted copy

The handoff process:

[During failure]
Client → A (primary) ✓
Client → B (primary) ✗ (down)
Client → D (handoff) ✓ with hint for B

[After B recovers]
D → B: "Here's data that was for you"
B: Stores data, ACKs
D: Deletes hinted copy

Hinted handoff handles transient failures, but what about durable replica divergence? Long failures, disk corruption, or missed updates can cause replicas to drift apart. Dynamo uses anti-entropy with Merkle trees to detect and repair these inconsistencies.

The anti-entropy concept:

Anti-entropy is a background process that periodically compares replicas and synchronizes differences. The challenge is efficiency: comparing every key between replicas would be prohibitively expensive.

Merkle trees for efficient comparison:

A Merkle tree (hash tree) enables comparison of large datasets by comparing only hashes:

Merkle tree structure:

           [Root Hash]
              /    \
         [Hash1]  [Hash2]
          /  \      /  \
       [H1] [H2] [H3] [H4]   ← Hash of key ranges
        |    |    |    |
      keys keys keys keys    ← Actual data

Anti-entropy comparison process:

1. Each replica maintains a Merkle tree of its data, grouped by key range
2. Replicas exchange root hashes
3. If roots match → data is synchronized, done
4. If roots differ → exchange child hashes to narrow down
5. Continue recursively until differing key ranges are identified
6. Exchange only the keys in differing ranges

Merkle tree challenges in Dynamo:

Challenge 1: Tree maintenance

• Each data modification requires tree updates up to the root
• With virtual nodes, each physical node maintains multiple trees (one per range)

Challenge 2: Key range stability

• Merkle trees are built over key ranges
• When nodes join/leave, ranges change, requiring tree rebuilds

Challenge 3: Comparison frequency

• Too frequent: excessive background load
• Too infrequent: longer inconsistency windows

Modern implementations (like Cassandra):

• Use "repair" operations that can be scheduled or triggered
• Merkle trees are built on-demand during repair, not continuously maintained
• Incremental repair allows repairing only recently-modified data

When multiple replicas can accept writes independently, concurrent modifications can create conflicting versions. Dynamo uses vector clocks (a form of version vectors) to track causality and detect conflicts.

Why simple timestamps fail:

Consider two concurrent writes at physical time T:

Client 1 @ Node A: SET key=X, value="apple", time=1000
Client 2 @ Node B: SET key=X, value="banana", time=1000

Which write happened first? We can't know—the timestamps are identical.
Even if different by milliseconds, clock skew means we can't trust ordering.

Vector clocks solution:

Instead of a single timestamp, track a vector of per-node counters:

Initial state: X = {value: null, vclock: []}

Client 1 writes via Node A:
  X = {value: "apple", vclock: [{A: 1}]}

Node B receives, client 2 writes:
  X = {value: "banana", vclock: [{A: 1}, {B: 1}]}  // Builds on A:1

OR if client 2 hadn't seen A's update:
  X = {value: "banana", vclock: [{B: 1}]}  // Independent

Comparing vector clocks:

Given two vector clocks V1 and V2:

V1 < V2 (V1 happened before V2)

• Every counter in V1 is ≤ the corresponding counter in V2
• At least one counter in V1 is < the corresponding counter in V2

V1 > V2 (V1 happened after V2)

• The reverse of above

V1 || V2 (Concurrent, conflict)

• Some counters in V1 are greater, some in V2 are greater
• Neither happened before the other—they're concurrent

Example comparison:

V1 = [{A: 2, B: 1}]
V2 = [{A: 1, B: 2}]

A: 2 > 1 (V1 has more from A)
B: 1 < 2 (V2 has more from B)

Result: V1 || V2 (CONCURRENT)
Conflict detected—application must resolve

Now we can see how Dynamo's components work together to create a highly available, eventually consistent key-value store. Each component addresses a specific challenge:

Component summary:

A complete write flow:

1. Client sends PUT(key=K, value=V) to any node
2. Node computes preference list for K: [A, B, C]
3. If this node is in the list, it acts as coordinator
4. Coordinator sends write to all preference list nodes in parallel
5. If B is down, write goes to D with hint for B
6. Coordinator waits for W acknowledgments (quorum)
7. Returns success to client
8. Background: D checks for B recovery, hands off data when possible
9. Background: Anti-entropy verifies all replicas match

A complete read flow:

1. Client sends GET(key=K) to any node
2. Node computes preference list for K: [A, B, C]
3. Coordinator requests value from R nodes (quorum)
4. Responses return with vector clocks
5. If all vector clocks match: return value
6. If vector clocks diverge: detect conflict
7. Read repair: update stale replicas with latest
8. Return value (or conflicting versions) to client

We've explored the architectural innovations that made Dynamo revolutionary. Let's consolidate these insights:

What's next:

With Dynamo's architecture understood, we'll examine quorum reads and writes in depth. The next page explores how quorum parameters (N, R, W) provide tunable consistency, the mathematics behind quorum intersection, and practical guidance for configuring quorums.