Key Question

How does Dynamo distribute data across nodes without rehashing everything when nodes join or leave?

Deep Dive

Traditional hash-based partitioning (key % N) is simple but fragile: when N changes (a node joins or leaves), almost every key is remapped to a different node. For a system with petabytes of data, moving every key is catastrophic.

Consistent hashing solves this. Both keys and nodes are hashed onto a fixed circular space (0 to 2^160 - 1 for SHA-1). Each key is stored on the first node encountered when moving clockwise from the key’s hash. When a node joins, it only “steals” keys from its immediate neighbor. When a node leaves, its keys are taken over by its neighbor.

The Ring

                    Node C
               ┌───────────┐
               │  SHA-1    │
               │  space    │
               │           │
    Node D     │    ●      │     Node B
       ●       │   / \     │        ●
        \      │  /   \    │       /
         \     │ /     \   │      /
          ──────●───────●───────
              Node E     Node A

  Key K1 (hash = 0x4A...) ──► stored on Node A
  Key K2 (hash = 0x8F...) ──► stored on Node B
  Key K3 (hash = 0xC2...) ──► stored on Node C
  Key K4 (hash = 0x1D...) ──► stored on Node E

  (Going clockwise from key hash to first node)

Lookup is simple: hash the key, walk clockwise until you find a node. Returns the node.

Node Join

When a new node joins, it inserts itself at some position on the ring:

Before: Keys between Node D and Node A go to Node A.

    Node D (hash=0x10)       Node A (hash=0x50)
       ●────────────────────────●
                        ^
                        Keys here go to A

After: Node X joins at hash=0x30.

    Node D (0x10)    Node X (0x30)    Node A (0x50)
       ●─────────────────●───────────────●

     Keys (0x10 to 0x30) → Node X (NEW)
     Keys (0x30 to 0x50) → Node A (unchanged)

Node X only takes over keys in the range (D, X] — i.e., keys that previously belonged to Node A. No other nodes are affected. In a cluster of 1000 nodes, a single node join moves only ~0.1% of keys. Compare this to key % N where ≈ (N-1)/N of keys would move (99.9%).

Node Leave

When Node X leaves (failure or decommission):

    Node D (0x10)    Node X (0x30)    Node A (0x50)
       ●─────────────────●───────────────●

  X leaves → keys (D, X] are reassigned to Node A
  Only Node A is affected. Other nodes are unchanged.

Virtual Nodes

Physical machines have different capacities. And with few nodes on the ring, key distribution can be unbalanced (some nodes get many keys, others get few).

Dynamo’s solution: virtual nodes. Each physical node maps to multiple positions on the ring (tokens):

Physical node P1 → virtual nodes V1, V4, V7, V10...
Physical node P2 → virtual nodes V2, V5, V8, V11...
Physical node P3 → virtual nodes V3, V6, V9, V12...

Ring:
  V1 (P1) → V2 (P2) → V3 (P3) → V4 (P1) → V5 (P2) → V6 (P3) → ...

Key K → first virtual node clockwise → physical node

With 100+ virtual nodes per physical node, the law of large numbers ensures balanced key distribution even if a few virtual nodes get unlucky. When a physical node joins, its virtual nodes are spread across the ring, taking a proportional share of keys from each neighbor.

Lookup Efficiency

Each node maintains a “finger table” (or routing table) mapping segments of the ring to nodes. Lookups are O(log N) in the number of virtual nodes, using binary search on the sorted ring positions.

Dynamo vs. Cassandra

Cassandra inherited consistent hashing from Dynamo but calls it “partitioning.” Both use the ring with virtual nodes. The key difference: Cassandra allows operators to assign tokens manually, while Dynamo handles it automatically.

Check Your Understanding

1. A ring has 100 nodes. One node joins. What fraction of keys are remapped (on average)?

2. What happens if the hash function produces very unbalanced key distribution even with virtual nodes? Can consistent hashing still cause hot spots?

3. Why are virtual nodes important? What’s the worst-case load imbalance without them?

The “So What?”

Consistent hashing is the foundation of DynamoDB, Cassandra, Riak, and many other NoSQL systems. When you create a DynamoDB table and choose your partition key, you’re relying on consistent hashing to distribute data across partitions. The ring + virtual node pattern is also used in load balancers (e.g., consistent hashing for HTTP caching) and CDNs.

✏️ Exercises

Dynamo: Exercises

1. Quorum consistency. N = 3, R = 1, W = 3. Under what conditions can a read return stale data? What happens to the latency of writes and reads in this configuration?

2. Hinted handoff durability. In a sloppy quorum scenario, node A is down. The coordinator writes key K to B, C, D (D holds hinted data for A). Then D crashes before handing off to A. B and C remain healthy. Node A recovers. How many copies of key K exist? Is any data lost?

3. Merkle tree depth. A Dynamo node stores 16 million keys. It builds a Merkle tree of depth 16 (65,536 leaves). What is the average number of keys per bucket? If the root hashes differ between two nodes, how many hash comparisons are needed in the worst case to find the differing bucket?

4. Dynamo vs. GFS. GFS uses a single master with lease-based replication. Dynamo uses a fully distributed ring with quorums. Why did Amazon choose the Dynamo architecture instead of a GFS-like master-based replication? What constraints drove this decision?