Module 5: Scaling the Database

6. The `hash(key) % N` problem

Next →

Description

By the end of this lesson you'll understand —and have measured with your own code— why the most obvious way to spread keys among shards is a trap. The formula is tempting for its simplicity: shard = hash(short_code) % N, where N is the number of shards. It spreads the keys almost perfectly, it's one line of code, and it works without problems... until the day you add or remove a shard. At that moment, N changes, and with it the result of hash(key) % N changes for almost all the keys, not for a few. You'll run an experiment with a million short_codes and measure the exact number: going from 8 to 9 shards remaps 888,920 of 1,000,000 —88.9%—. You'll understand why the modulo does that, and why "almost all move" turns the most routine operation of sharding —growing— into a storm capable of bringing down the system.

This matters because hash(key) % N is the first idea everyone thinks of, and for good reasons: it spreads evenly (you saw it in lesson 5: [27, 27, 28, 18]) and it's trivial to implement. The defect isn't seen in the tests or in the first year of operation, because it only manifests when you change the number of nodes. That's why it's a trap: it looks correct until the exact moment it hurts most, when the system has grown and you need to add capacity. Understanding why it fails —and measuring how much it fails— is what leads you to value the next lesson's solution. You can't appreciate consistent hashing until you feel, in numbers, the pain it avoids.

Connection to the module: this is the problem lesson, and lesson 7 is the remedy one; they form an inseparable pair. Lesson 5 established that Enlace shards the short_code by hash and uncovered that hash(short_code) % N depends on N. Here we squeeze that dependency to the bottom with a reproducible experiment. Lesson 7 will take the same experiment —the same keys, the same jump from N to N+1— and measure how much better consistent hashing spreads, putting the two numbers side by side. The whole weight of lesson 7 rests on you really feeling here how bad the 88.9% is.

The parking lot that renumbers all the spots

Think of it this way. A parking lot assigns each car a spot with a simple rule: you take the last digits of the plate, divide them by the number of spots, and the remainder is your spot. With 8 spots, the plate ending in ...042 goes to spot 042 % 8 = 2. Everyone memorizes their spot, it works perfectly for years.

One day the parking lot adds a spot: now there are 9. The rule didn't change in shape —it's still "remainder by the number of spots"— but the number changed, from 8 to 9. And here's the disaster: the plate ...042 now goes to spot 042 % 9 = 6, not 2. And it's not just that plate: almost everyone has to change spots, because dividing by 9 instead of by 8 gives a different remainder for almost any number. The parking lot has to move almost all the cars at the same time, tell each owner their new spot, and during the move it's chaos: no one finds their car where they left it.

The maddening part is that you only added one spot —you'd expect to move at most a ninth of the cars, the ones that "don't fit" and go to the new spot—. But the remainder rule doesn't work that way: changing the divisor shuffles almost everyone, not just the ones at the margin. That's exactly the hash(key) % N problem. Adding a shard should move a small fraction of the data —the ones the new shard gets— but the modulo moves almost all. In Enlace, "almost all the data" is terabytes, and "moving" means copying them between machines while the system serves 4,000 reads/s. The move isn't an annoyance: it's a storm.

Why the modulo remaps almost everything

The parking lot's intuition has a precise mathematical reason. A key does not move only if hash(key) % N == hash(key) % (N+1) —if its old spot and its new spot coincide—. How often do two remainders of different moduli coincide? Almost never. If the hash result behaves like a random number, the probability that x % 8 equals x % 9 is low, and it drops further the larger N is.

In fact there's an approximate closed form: going from N to N+1, the fraction of keys that stays in place is approximately 1/(N+1), so the fraction that moves is approximately N/(N+1). Look at what that formula says:

  • From 4 to 5 nodes: 4/5 = 80% moves.
  • From 8 to 9 nodes: 8/9 ≈ 88.9% moves.
  • From 10 to 11 nodes: 10/11 ≈ 90.9% moves.
  • From 100 to 101 nodes: 100/101 ≈ 99.0% moves.

Notice how cruel the trend is: the more nodes you have, the worse it is. With 100 shards, adding a single one remaps 99% of the data. Exactly when your system is largest —and moving its data is most expensive— the mod-N punishes you most. It's the opposite of what you want: you'd want adding a node to a large system to move a small fraction (a hundredth), and instead it moves almost everything. Let's verify it by running, not by trusting the formula.

Worked example: measuring the mod-N remapping

We spread a million short_codes among N shards with hash(key) % N, then we go to N+1 shards and count how many keys changed shard. We use a deterministic hash (md5) so the experiment is reproducible on any machine:

import hashlib
from collections import Counter

def make_keys(k):
    """k deterministic short_codes, like Enlace's."""
    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

def node_modn(short_code, n):
    """The shard of a key with hash(key) % N."""
    h = int(hashlib.md5(short_code.encode()).hexdigest(), 16)
    return h % n

def remap_modn(keys, n_from, n_to):
    """How many keys change shard when going from n_from to n_to nodes."""
    return sum(node_modn(k, n_from) != node_modn(k, n_to) for k in keys)

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

    print(f"K = {K:,} keys\n")
    print("hash(key) % N  ->  remapping when adding 1 node")
    for n in (4, 8, 10, 100):
        moved = remap_modn(keys, n, n + 1)
        print(f"  N={n:>3} -> N={n+1:<3}   {moved:>9,} move  ({100*moved/K:5.1f}%)")

    # the spread IS even as long as N doesn't change
    dist = Counter(node_modn(k, 8) for k in keys)
    print(f"\nSpread with N=8: {[dist[s] for s in range(8)]}")

What to expect. When you run it (K = 1,000,000):

K = 1,000,000 keys

hash(key) % N  ->  remapping when adding 1 node
  N=  4 -> N=5       800,321 move  ( 80.0%)
  N=  8 -> N=9       888,920 move  ( 88.9%)
  N= 10 -> N=11      909,306 move  ( 90.9%)
  N=100 -> N=101     990,176 move  ( 99.0%)

Spread with N=8: [124659, 125030, 125443, 125044, 124990, 124573, 125441, 124820]

Read the two facts that coexist in that output, because together they're the complete trap.

The spread is excellent. With N=8, the eight shards receive ~125,000 keys each —almost perfectly even, no hotspots—. This is what makes people fall in love with mod-N: it spreads beautifully. If N never changed, it would be the ideal solution.

The remapping is catastrophic. But the moment you add a node, almost all move: 80% with N=4, 88.9% with N=8 (888,920 of a million), 99% with N=100. The formula N/(N+1) holds dead on, measured on real data. The numbers confirm the cruelty: the larger the system, the worse the remapping.

Why that 88.9% is a storm, not an annoyance

An abstract number —"88.9% is remapped"— doesn't convey the danger. Let's translate it to Enlace. Suppose Enlace has 8 shards with its 6 TB spread, ~750 GB per shard, and you need to add the ninth because the data grew. With mod-N, adding that shard implies:

  • Moving ~5.3 TB of data (88.9% of 6 TB) between machines. Copying terabytes over the network takes hours and saturates the bandwidth the system needs to serve the normal traffic.
  • Invalidating almost the whole cache. Each key that moves to another shard leaves its cache entries stale; the module 4 cache, which took so much work to fill, goes cold at once, and the 4,000 reads/s fall directly on the databases right when they're busy moving.
  • Running the risk of inconsistency during the move. While a key is moving from the old shard to the new one, where does a read look for it? Coordinating that without losing or duplicating data, live, is fiendishly hard.

In other words: the most natural operation of sharding —growing— becomes the most dangerous event in the system's life, and it becomes more dangerous the larger you are. That's unacceptable for a service that must always be available. The obvious question: what if there were a way to spread that kept the even spread (the ~125k per shard) but moved only the fraction that really belongs to the new node —a ninth, not eight ninths—? That way exists, it's called consistent hashing, and it's lesson 7.

Common mistakes

Believing that adding a node moves only 1/N of the data (intuition mistake). What happens: someone reasons "I add 1 of 8 nodes, so ~1/9 of the data moves" and sizes the operation for moving terabytes when in reality mod-N moves almost all. Why it happens: intuition says a small change causes a small effect, and with mod-N it's false. How to detect it: if your "add a shard" plan assumes moving a small fraction and you use hash % N, your plan is broken —you're going to move 88.9%—. How to fix it: measure, as in the experiment; or use consistent hashing, where the "1/N" intuition does hold.

Confusing good spread with good scalability (criterion mistake). What happens: mod-N is chosen because it spreads evenly in the tests and the decision is called good, without testing what happens when N changes. Why it happens: the even spread is visible immediately (the ~125k per shard) and the remapping problem is invisible until you grow. How to detect it: ask yourself "what happens when I add node N+1?". If you didn't test that case, you didn't test what matters. How to fix it: evaluate a sharding scheme by two properties, not one: how it spreads (balance) and how much it remaps when changing nodes (stability). mod-N passes the first and fails the second.

Choosing a weak hash and blaming the scheme (implementation mistake). What happens: someone uses a poor-quality hash function (or Python's hash() over strings, which also changes between runs for security) and sees an uneven spread, and concludes that hash sharding "doesn't spread well". Why it happens: the hash's defect is confused with the scheme's defect. How to detect it: if your spread with fixed N is already uneven, the problem is your hash, not the sharding. How to fix it: use a well-distributed and deterministic hash (md5, sha, or a quality non-cryptographic hash like the ones real libraries use); the uneven spread with fixed N is almost always a poor hash, not the concept.

Exercises

Exercise 1 — Compute by hand. Without running code, use the formula N/(N+1) to estimate the percentage of keys that are remapped in these jumps, and order them from least to most remapping. (a) From 2 to 3 nodes. (b) From 9 to 10 nodes. (c) From 49 to 50 nodes. What pattern does the order confirm?

See solution
  • (a) From 2 to 3: 2/3 ≈ 66.7%.
  • (b) From 9 to 10: 9/10 = 90.0%.
  • (c) From 49 to 50: 49/50 = 98.0%.

From least to most remapping: (a) 66.7% < (b) 90.0% < (c) 98.0%. The pattern it confirms: the larger N is, the greater the fraction remapped —N/(N+1) tends to 100% as N grows—. It's mod-N's counterintuitive and cruel result: adding a node to a large system is worse, not better, than adding it to a small one. Exactly the opposite of what a good scaling scheme should do.

Exercise 2 — Translate the number to Enlace. Enlace has 10 shards with 6 TB spread (600 GB per shard). You need to add shard 11. Using the measured number from the experiment for the 10-to-11 jump (90.9%), compute how many TB have to move and explain two concrete operational consequences of that move.

See solution

Data to move: 90.9% × 6 TB ≈ 5.45 TB have to be copied between machines to add a single shard.

Two operational consequences:

  1. Time and network saturation. Copying ~5.45 TB over the network takes hours and consumes the bandwidth the system needs for the normal 4,000 reads/s; during the move, the service competes with itself for the network and degrades.
  2. Massive cold cache. Almost all the keys change shard, so almost all their cache entries become stale. The module 4 cache empties de facto, and the reads it used to serve in microseconds fall on the databases —which are already busy moving— causing a latency spike at the worst moment.

The conclusion: adding a shard with mod-N isn't a routine maintenance task; it's a risk event that has to be planned like a major migration. And that's precisely the pain consistent hashing eliminates.

Exercise 3 — The two properties. A colleague says: "I tested hash(short_code) % N and it spreads perfectly, ~125k per shard with N=8; it's the solution". What test are they missing before concluding that? Describe the experiment they should run and what they'd expect to see, and which property of a good sharding scheme they're ignoring.

See solution

They're missing testing the second property: what happens when N changes. They only verified the balance (spreads evenly with fixed N), but a good sharding scheme needs two properties:

  1. Balance: spreads evenly among the nodes. mod-N meets it (~125k per shard).
  2. Stability: when adding or removing a node, it remaps only a small fraction. mod-N fails it.

The experiment they should run: spread their keys with N=8, then with N=9, and count how many change shard. They'd expect to see —and be surprised— that 888,920 of 1,000,000 (88.9%) move, almost all. That number would show them their "solution" turns adding a shard into moving 88.9% of the data. The property they're ignoring is stability under topology changes, which is exactly the one consistent hashing comes to guarantee in the next lesson.

Summary and next step

In this lesson you measured, with your own code, why hash(key) % N is a trap. With the parking lot that renumbers all the spots when adding a single one, you saw the intuition: changing the modulo's divisor shuffles almost everyone, not just those at the margin. The formula N/(N+1) predicts it and the experiment confirmed it over a million short_codes: 80% remapping going from 4 to 5 nodes, 88.9% going from 8 to 9 (888,920 keys), 99% going from 100 to 101 —worse the larger the system—. And you saw the bright side that makes the trap so treacherous: with fixed N, mod-N spreads beautifully (~125k per shard). The defect only appears when growing, which is exactly when it hurts most: adding a shard becomes a storm of moving terabytes, emptying the cache, and risking inconsistency.

Before moving on you should be able to: explain why the modulo remaps almost everything when N changes; use N/(N+1) to estimate the remapping; translate that percentage into TB moved and operational consequences in Enlace; and name the two properties of a good sharding scheme —balance and stability— and which one mod-N fails.

What comes next is the remedy, and the module's climax. In lesson 7 you'll run consistent hashing —the ring— over the same keys and the same jump from 8 to 9 nodes, and you'll measure how many are remapped now. The number, previewed so you feel the contrast: 130,623 instead of 888,920. You'll see the two side by side, understand why the ring moves only the arc that belongs to the new node, and meet the vnodes that keep the spread even. It's act three, where this lesson's problem is resolved.

Resources

← Previous5. Sharding and the shard keyNext →7. Consistent hashing, executed