Module 5: Scaling the Database

7. Consistent hashing, executed

Next →

Description

By the end of this lesson you'll understand —and have executed— the technique that solves the problem lesson 6 measured: consistent hashing. You'll see the central idea, the ring: instead of computing hash(key) % N, you place both the keys and the nodes as points on a circle of positions, and each key belongs to the first node it finds turning clockwise. You'll understand why, with this arrangement, adding a node only moves the keys of the arc it gets —a fraction of ~K/N, not almost all—, and you'll measure it over the same keys and the same jump from 8 to 9 nodes as the previous lesson: 130,623 remappings instead of 888,920. You'll see the two numbers side by side —the heart of the module—, you'll meet the vnodes (virtual replicas) that keep the spread even, and you'll implement the complete ring in Python.

This matters because consistent hashing is one of those ideas that, once you see it, changes how you think about distributed systems forever. It's not an academic curiosity: it's the technique underneath real distributed data systems —Cassandra, DynamoDB, many distributed caches and load balancers— precisely because it disarms the mod-N remapping storm. Understanding it gives you two things: the ability to design a system that grows without migrating the world every time, and the understanding of why the systems you use daily can add and remove nodes without going down. It's the finish of the three-lesson arc and the piece that makes sharding a safe tool instead of a dangerous one.

Connection to the module: this is the remedy lesson, inseparable from lesson 6, which was the problem one. The whole weight of this lesson rests on the contrast: it reuses the same keys, the same jump from N to N+1, and measures consistent hashing against mod-N so the number —13.1% against 88.9%— speaks for itself. It's also the module's technical close before the project: with replicas (lessons 3-4) you scaled the reads, with sharding (lesson 5) you scaled the data, with lesson 6 you saw why the naive way to shard doesn't grow, and here you get the way that does. Lesson 8 puts it all together into a plan for Enlace. The boundary: consistent hashing as a spreading technique is from here; its use to replicate each shard across several nodes with quorum (the Dynamo style) brushes the resilience guide and is only mentioned.

The clock where each one serves up to the next

Think of it this way. Imagine a giant clock —a circle with positions from 0 to 12— and several on-call doctors standing at different hours of the clock: one at 2, another at 5, another at 9. A patient arrives and is also assigned an hour on the clock according to their file number. The service rule is simple: each patient walks clockwise from their hour until they find the first doctor, and that one sees them. The patient at hour 3 walks to 5 and is seen by the doctor at 5. The patient at hour 6 walks to 9. The one at hour 10 goes around past 12 and reaches the doctor at 2.

Now a new doctor arrives and stands at hour 7. Which patients change doctors? Only the ones between 5 and 7 —the ones who used to walk from there to 9 and now meet the doctor at 7 first—. The patients at hour 3, hour 10, hour 1: none of them notice the new doctor, they stay with theirs. Adding a doctor only reassigned the arc between the new doctor and the previous one, it didn't shuffle all the patients.

That clock is consistent hashing. The circle is the ring; the doctors are the nodes (shards); the patients are the keys (the short_codes); "walk clockwise to the first doctor" is the assignment rule. And the magic property is exactly the one mod-N lacked: adding a node only moves the keys of an arc, not those of the whole clock. Compare it with the parking lot of lesson 6, where adding a spot renumbered everyone: here, adding a doctor only affects the patients of a stretch. That's the whole difference, and it's enormous.

How the ring works, concretely

Let's bring the analogy down to exact mechanics. The ring is the range of numbers [0, 2^32) —more than four billion positions, folded into a circle, so that after 2^32 − 1 comes 0 again—. On that circle we place two things with the same hash function:

  1. Each node is placed at hash(node_name). The shard db-3 goes to position hash("db-3").
  2. Each key is placed at hash(short_code). The link aX9kR2q goes to position hash("aX9kR2q").

To know which node a key belongs to: from the key's position, you advance clockwise to the first node you find. That's its shard. In code, "advance clockwise to the first node" is a binary search over the sorted list of node positions —efficient, O(log N)—.

                    position 0 / 2^32
                          │
              db-3 ●──────┼──────● db-0
                 ╱        (ring)         ╲
          key k ○  ← walk clockwise →   ● db-1
               ╲                        ╱
              db-2 ●──────────────────● 
                          │
          k belongs to db-1 (the first node clockwise)

When you add a new node, it falls in one position of the ring, and it only "steals" the keys of the arc that goes from the previous node (counterclockwise) to it. All the other keys —the vast majority— keep pointing to the same node as before, because their clockwise path didn't change. That's the mechanism by which the remapping is ~K/N: the new node takes, on average, a portion of the ring equivalent to any other node's, that is ~1/(N+1) of the keys.

Worked example: the two numbers, side by side

This is the experiment that crowns the module. We reuse the same 1,000,000 keys from lesson 6 and the same jump from N=8 to N=9, and we measure the remapping of the two strategies in the same program:

import bisect
import hashlib

def ring_point(text):
    """Maps a text to a point of the ring [0, 2^32)."""
    return int(hashlib.md5(text.encode()).hexdigest(), 16) % (2 ** 32)

# --- Strategy 1: hash(key) % N ---
def node_modn(short_code, n):
    h = int(hashlib.md5(short_code.encode()).hexdigest(), 16)
    return h % n

# --- Strategy 2: consistent hashing (ring with vnodes) ---
def build_ring(nodes, vnodes=100):
    ring = {}
    for node in nodes:
        for i in range(vnodes):                 # vnodes virtual replicas per node
            ring[ring_point(f"{node}#{i}")] = node
    return ring

def node_ring(short_code, ring, sorted_points):
    point = ring_point(short_code)
    idx = bisect.bisect(sorted_points, point)    # first node clockwise
    if idx == len(sorted_points):
        idx = 0                                  # the ring wraps around
    return ring[sorted_points[idx]]

def make_keys(k):
    alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    out = []
    for i in range(k):
        num, s = 100_000_000 + i, ""
        while num:
            s, num = alphabet[num % 62] + s, num // 62
        out.append(s.rjust(7, "0"))
    return out

if __name__ == "__main__":
    K, N = 1_000_000, 8
    keys = make_keys(K)

    # mod-N: spread with N and with N+1, count those that change
    moved_modn = sum(node_modn(k, N) != node_modn(k, N + 1) for k in keys)

    # consistent hashing: same experiment over the ring
    nodes = [f"db-{i}" for i in range(N)]
    ring = build_ring(nodes)
    pts = sorted(ring)
    before = {k: node_ring(k, ring, pts) for k in keys}
    for i in range(100):                          # we add db-8 (the N+1 node)
        ring[ring_point(f"db-{N}#{i}")] = f"db-{N}"
    pts = sorted(ring)
    moved_ring = sum(node_ring(k, ring, pts) != before[k] for k in keys)

    print(f"K = {K:,} keys,  going from N={N} to N={N+1} nodes\n")
    print(f"  hash(key) % N        remap {moved_modn:>9,}  "
          f"({100*moved_modn/K:5.1f}%)   <- almost all")
    print(f"  consistent hashing   remap {moved_ring:>9,}  "
          f"({100*moved_ring/K:5.1f}%)   <- ~ K/(N+1) = {K//(N+1):,}")

What to expect. When you run it:

K = 1,000,000 keys,  going from N=8 to N=9 nodes

  hash(key) % N        remap   888,920  ( 88.9%)   <- almost all
  consistent hashing   remap   130,623  ( 13.1%)   <- ~ K/(N+1) = 111,111

There are the two numbers, side by side, and I want you to pause on them because they're the module's whole lesson in two lines. Adding the ninth node with mod-N remaps 888,920 keys —88.9%, almost everything—. Adding it with consistent hashing remaps 130,623 —13.1%, close to the theoretical ideal K/(N+1) = 111,111—. It's a reduction of almost 7 times. Translated to Enlace: where mod-N moved ~5.3 TB to add a shard, consistent hashing moves ~0.8 TB, and only the new node's arc is left with a cold cache instead of the whole system. The same operation —growing— goes from storm to routine. That's the ring's gift.

The vnodes: why one node is a hundred points on the ring

You'll have noticed that in the code each node is placed on the ring a hundred times (vnodes=100), not once. Those hundred copies are the vnodes (virtual nodes, or virtual replicas), and they solve a balance problem the basic ring has. Let's see it by measuring the spread with a single point per node against a hundred:

from collections import Counter
# ... reusing build_ring, node_ring, make_keys ...
K = 1_000_000
keys = make_keys(K)
nodes = [f"db-{i}" for i in range(8)]

for vnodes in (1, 100):
    ring = build_ring(nodes, vnodes=vnodes)
    pts = sorted(ring)
    dist = Counter(node_ring(k, ring, pts) for k in keys)
    print(f"vnodes={vnodes:>3}: {[dist[f'db-{i}'] for i in range(8)]}")

What to expect. When you run it:

vnodes=  1: [195282, 94531, 103575, 213431, 165023, 42013, 165652, 20493]
vnodes=100: [132419, 113119, 130610, 121018, 117023, 119447, 143609, 122755]

Look at the disaster of vnodes=1. With a single point per node, the spread is terribly uneven: db-3 receives 213,431 keys and db-7 only 20,493 —a difference of more than 10 times—. The reason: with 8 random points on the ring, the arcs between them come out very disparate in size; the node that ended up just before a large arc takes a bunch of keys, and the one in a small arc, almost none. A single point per node inherits its own kind of hotspot.

The cure is the vnodes: placing each node at a hundred different points on the ring. Now each node owns a hundred small arcs scattered around the whole circle, and the law of large numbers works its magic: a node's large arcs compensate for its small ones, and the total per node evens out. With vnodes=100, the spread goes from 113,119 to 143,609 —much more even, without the 20k node or the 213k one—. More vnodes, more even (at the cost of a bit more memory for the ring table). Real systems use on the order of hundreds per node. The lesson: the basic ring solves the remapping, and the vnodes solve the balance; you need both.

Consistent hashing on Enlace's map

Let's close by connecting the technique with the case. Enlace shards the short_code (lesson 5), by hash and not by range (to avoid sequence hotspots), and now you know how to hash: not with mod-N but with a consistent-hashing ring with vnodes. The result is a system that:

  • Spreads evenly the 6 TB and the writes among the shards (thanks to the vnodes).
  • Routes each resolve to a single shard in O(log N) (binary search on the ring).
  • Grows without a storm: adding a shard moves only ~1/(N+1) of the data and cools only that fraction of the cache, not everything.

And a boundary note: consistent hashing is also the basis of how Dynamo-style systems replicate each key —the arc's node plus the following ones on the ring store copies, to tolerate crashes—. That combination of sharding and replication with quorum is a topic of resilience and of the data-architecture guide; here it's enough to know that the ring is the spreading piece, and that on top of it are built the availability guarantees other guides cover.

Common mistakes

Implementing the ring without vnodes (balance mistake). What happens: someone implements consistent hashing with a single point per node, sees the low remapping (good) but an uneven spread (bad), and concludes that "consistent hashing doesn't spread well". Why it happens: the basic ring solves the remapping but not the balance; without vnodes, the arcs come out disparate in size. How to detect it: if one node has 10 times more keys than another, you're missing vnodes —you measured it: 213k against 20k—. How to fix it: place each node at many points on the ring (hundreds); the spread evens out by the law of large numbers.

Using Python's hash() for the ring positions (reproducibility mistake). What happens: the built-in hash() over strings is used to position keys and nodes, and the system assigns different keys on each process restart —because hash() over strings is randomized for security (PYTHONHASHSEED)—. Why it happens: hash() seems the obvious option. How to detect it: if after restarting the service the keys change shard without the topology changing, your hash isn't deterministic. How to fix it: use a deterministic hash that's stable across processes and machines —md5, sha, or a quality non-cryptographic hash—; all the machines and all the restarts must compute the same position for the same key.

Believing consistent hashing eliminates all the remapping (expectation mistake). What happens: someone expects adding a node to move zero keys and is disappointed to see it moves 13.1%. Why it happens: "moves much less" is confused with "moves nothing". How to detect it: if you expected 0% and see 13%, your expectation was miscalibrated. How to fix it: understand the real goal —move only the part that belongs to the new node, ~K/N, instead of almost all—. That 13.1% is the success: it's the fraction that inevitably must change owner when a new node takes its fair portion. Zero remapping is impossible (the new node has to receive something); ~K/N is the optimum, and it's what consistent hashing achieves.

Exercises

Exercise 1 — Walk the ring. In a ring with nodes at positions 10, 25, 40, and 70 (of a 0-99 circle, which wraps around after 99), say which node each key belongs to. (a) A key at position 5. (b) A key at position 30. (c) A key at position 85. Then, if you add a node at position 35, which of those three keys change node?

See solution

Rule: from the key's position, advance clockwise (increasing numbers, wrapping after 99) to the first node.

  • (a) position 5: the first node clockwise is 10.
  • (b) position 30: the first node clockwise is 40 (it passes 25, which is behind).
  • (c) position 85: there's no node between 85 and 99, so it wraps around and takes the first one past 0: 10.

When adding a node at 35:

  • (a) position 5 → still on 10. Doesn't change.
  • (b) position 30 → now the first node clockwise is 35, not 40. Changes (30 is in the 25-35 arc the new node steals).
  • (c) position 85 → still wraps to 10. Doesn't change.

Only key (b) changed, the one that fell in the arc the new node captured. The other two don't even notice. That's the ~K/N property in action: adding a node only remaps its arc.

Exercise 2 — Compare the two numbers. With the experiment's results (mod-N: 888,920; consistent hashing: 130,623; both going from 8 to 9 nodes over 1,000,000 keys), compute: (a) how many times less remapping does consistent hashing achieve? (b) If each remapped key costs moving ~6 MB of data, how many TB does each strategy move? (c) Explain in one sentence why the difference grows with the size of the system.

See solution
  • (a) 888,920 / 130,623 ≈ 6.8 times less remapping with consistent hashing (almost 7 times).
  • (b) mod-N: 888,920 × 6 MB ≈ 5.33 TB. Consistent hashing: 130,623 × 6 MB ≈ 0.78 TB. ~5.3 TB against ~0.8 TB are moved for the same operation of adding a node.
  • (c) Because mod-N remaps N/(N+1), which grows toward 100% as the system has more nodes, while consistent hashing remaps ~1/(N+1), which shrinks toward 0%. The larger the system, mod-N gets worse and consistent hashing gets better, so the gap between them widens: at N=100, mod-N moves 99% and consistent hashing ~1%.

Exercise 3 — Design Enlace's spread. You're going to shard Enlace with consistent hashing. Answer with judgment: (a) what text do you hash to position each key on the ring, and what for each node? (b) How many vnodes per node would you choose and what tradeoff governs that choice? (c) When Enlace grows and you need shard 9, describe what happens with the data and the cache, in contrast with what would happen with mod-N.

See solution
  • (a) For each key, you hash the short_code (ring_point(short_code)). For each node, you hash a stable shard identifier plus the vnode index (ring_point(f"db-3#{i}")). Both with the same deterministic hash (md5/sha), the same on all machines.
  • (b) On the order of 100 to a few hundred vnodes per node. The tradeoff: more vnodes → more even spread (the arcs average out better, you avoid the 20k-vs-213k imbalance you measured with 1 vnode) but → more memory for the ring table and slightly more expensive lookups. Hundreds is usually the sweet spot.
  • (c) With consistent hashing, adding shard 9 moves only ~1/9 of the data (~0.8 TB, those of the arc the new one captures) and cools only that fraction's cache; the rest of the system doesn't even notice and keeps serving with a warm cache. With mod-N, adding shard 9 would move 88.9% (~5.3 TB), empty almost the whole cache at once, and risk a latency and inconsistency spike for hours. Consistent hashing turns "adding a shard" from a major risk event into a routine maintenance operation.

Summary and next step

In this lesson you executed the remedy and crowned the module. With the clock where each patient walks to the next doctor, you understood the ring: keys and nodes as points on a circle [0, 2^32), and each key assigned to the first node clockwise. You saw why adding a node only moves the keys of its arc —not those of the whole clock— and you measured it over the same keys from lesson 6: consistent hashing remaps 130,623 (13.1%) where mod-N remapped 888,920 (88.9%), almost 7 times less, close to the K/(N+1) ideal. You discovered why the basic ring isn't enough —with 1 vnode the spread goes from 20k to 213k, a 10x imbalance— and how the vnodes even it out (113k to 143k with 100 vnodes). And you connected it all with Enlace: a short_code sharding that spreads evenly, routes to one shard, and grows without a storm.

Before moving on you should be able to: explain the ring's rule (first node clockwise); implement node_for_key with binary search; justify the vnodes from the imbalance they correct; and put the two numbers —88.9% against 13.1%— side by side and explain why the gap grows with the size of the system.

What comes next is putting it all together. In lesson 8 —the module's project— you'll produce Enlace's database-scaling plan: with the anchor numbers, you decide how many shards (by short_code, with consistent hashing and vnodes), how many read replicas per shard, where each read and each write goes, how you handle the lag, and how you add capacity without remapping the world. You deliver the topology diagram, the capacity table, and the list of tradeoffs. It's where the seven lessons become a design.

Resources

← Previous6. The `hash(key) % N` problemNext →8. Project: a sharding and replica plan for Enlace