I Added a Fourth Shard in Python and 75% of the Keys Moved

Every sharding answer starts the same way. Hash the key, take it modulo the number of shards, done. It works right up to the day someone says "we need one more shard."

Then it breaks, and it breaks badly: almost every key lands on a different machine than it did yesterday.

You can say that in an interview, but it lands better if you have watched it happen. So I wrote a short Python script, used 100,000 fake keys like user:0 and user:1, and counted. I hash with md5, because Python's built-in hash() for strings changes between runs and would make the numbers useless. The code blocks in this post are one file, in order. Paste them together and it runs.

import bisect
import hashlib
from collections import Counter

def h(s):
    return int(hashlib.md5(s.encode()).hexdigest(), 16) % (2**32)

KEYS = [f"user:{i}" for i in range(100_000)]

def moved_modulo(old_n, new_n):
    moved = sum(1 for k in KEYS if h(k) % old_n != h(k) % new_n)
    return moved / len(KEYS)

print("hash(key) % N, 100,000 keys")
for a, b in [(3, 4), (10, 11), (10, 20), (10, 9)]:
    print(f"  {a} -> {b} shards: {moved_modulo(a, b):.1%} of keys move")

Here is what came out:

hash(key) % N, 100,000 keys
  3 -> 4 shards: 75.0% of keys move
  10 -> 11 shards: 91.0% of keys move
  10 -> 20 shards: 50.0% of keys move
  10 -> 9 shards: 89.9% of keys move

Three to four is the one everyone quotes, and 75% is right. The 10 to 11 line is why this post exists. Going from 10 shards to 11 moves 91% of keys, not 9%. A key only stays put when h % 10 and h % 11 happen to match, which is one hash in eleven.

I noticed because of Schoolabe's own system design lesson, Lesson 9: When Hash Modulo Breaks. As of 17 October 2026 it lists "10 → 11 shards: ~9% relocate" under "Naive resharding cost", and my code gave the mirror image of that. About 9% is the right figure for consistent hashing, so the number seems to have landed on the modulo line. I checked that too, with the Ring code from this post and 11 nodes named S0 to S10. Across 30 arrangements and 100,000 keys, 150 points per node moved 8.0% to 11.5% of keys (mean 9.1%). 100 points gave 6.8% to 11.0%, 200 points gave 8.0% to 11.4%, and one point per node gave 0.0% to 22.9%. The ideal is 1/11, or 9.09%.

The formula above the lesson's list, (1 - 1/oldN), doesn't fit either: it gives 67% for 3 to 4 shards, where the lesson itself says 75%. The rule that does fit is that a key stays only if h % old equals h % new, so the share that stays is min(old, new) divided by lcm(old, new). The comparison table further down has the same swap. It lists adding a node to a 10-node cluster as ~9% for modulo and ~10% for the ring, and removing one as ~10% for modulo. My run gives 91% for 10 to 11 and about 90% for 10 to 9, both for modulo.

Doubling is the mild case, and growth is rarely that tidy. A key survives 10 to 20 when h % 20 lands below 10, which is half the time, so half move.

The ring

A ring answers a different question: who is the next node clockwise from this key? You hash the node names onto a circle, hash each key onto the same circle, and walk clockwise until you hit a node. That node owns the key. In code it is a sorted list and a binary search:

class Ring:
    def __init__(self, nodes, vnodes=1, salt=""):
        self.points = sorted(
            (h(f"{salt}{n}#{v}"), n) for n in nodes for v in range(vnodes)
        )
        self.hashes = [p[0] for p in self.points]

    def lookup(self, key):
        i = bisect.bisect_left(self.hashes, h(key))
        return self.points[i % len(self.points)][1]

def moved_ring(old_nodes, new_nodes, vnodes, salt=""):
    a = Ring(old_nodes, vnodes, salt)
    b = Ring(new_nodes, vnodes, salt)
    return sum(1 for k in KEYS if a.lookup(k) != b.lookup(k)) / len(KEYS)

print()
print("ring, add a 4th node to 3")
for v in (1, 150):
    m = moved_ring("ABC", "ABCD", v)
    print(f"  {v:>3} point(s) per node: {m:.1%} of keys move")

ring, add a 4th node to 3
    1 point(s) per node: 28.0% of keys move
  150 point(s) per node: 25.3% of keys move

Only keys that now sit between D and its counterclockwise neighbour change owner, so about a quarter move, against 75% for modulo. That is the ideal 1/4. These particular node names gave 25.3%; the sweep below shows how much that varies.

def load(nodes, vnodes, salt=""):
    r = Ring(nodes, vnodes, salt)
    c = Counter(r.lookup(k) for k in KEYS)
    return [c[n] for n in nodes]

print()
print("keys per node with 4 nodes")
for v in (1, 150):
    L = load("ABCD", v)
    print(f"  {v:>3} point(s) per node: {L}")

full, minus_c = Ring("ABC", 150), Ring("AB", 150)
moved = [k for k in KEYS if full.lookup(k) != minus_c.lookup(k)]
print()
print("remove C from 3 nodes: moved keys that lived on C:",
      sum(full.lookup(k) == "C" for k in moved), "of", len(moved))

print()
print("30 different arrangements of the same node names, 3 -> 4 nodes")
for v in (1, 150):
    moves, smallest, largest = [], [], []
    for s in range(30):
        salt = f"{s}:"
        moves.append(moved_ring("ABC", "ABCD", v, salt))
        L = load("ABCD", v, salt)
        smallest.append(min(L))
        largest.append(max(L))
    print(f"  {v:>3} point(s): moved {min(moves):.1%} to {max(moves):.1%}, "
          f"smallest node held {min(smallest)}, largest held {max(largest)}")

keys per node with 4 nodes
    1 point(s) per node: [31186, 10531, 30259, 28024]
  150 point(s) per node: [25136, 24419, 25098, 25347]

remove C from 3 nodes: moved keys that lived on C: 33830 of 33830

Removal is the mirror image: with C gone, only keys that lived on C changed owner, all 33830 of them.

The part the diagram hides

Look at the one-point-per-node line in the load output. B holds about a third of what A holds. Four random points on a circle make uneven arcs, and a node's share is its arc. Virtual nodes fix that by giving each machine many points so the arcs average out. With 150 points per node the four counts sit between 24.4k and 25.3k.

Except that is one arrangement. Every number above comes from one fixed set of node names, and md5 decides where the points land. So I ran 30 different arrangements of the same names, by putting a different prefix in front of each name before hashing.

30 different arrangements of the same node names, 3 -> 4 nodes
    1 point(s): moved 0.8% to 71.4%, smallest node held 213, largest held 71383
  150 point(s): moved 21.5% to 28.2%, smallest node held 21055, largest held 29917

With one point per node, the share of keys that move on 3 to 4 nodes ranged from 0.8% to 71.4%, and in one arrangement a node held 213 keys out of 100,000. With 150 points it stayed between 21.5% and 28.2%, and no node fell below 21,055. The 28.0% I showed earlier was luck, and so, a little, was the tidy 25.3%.

For an interview, explaining the plain ring is not enough. Say that one point per node gives uneven load, and that virtual nodes fix it. The next lesson in the same course, Virtual Nodes and CDN Routing, covers that and where the ring shows up in caches and CDNs. Lesson 9 also has a short section on how Redis Cluster uses 16,384 fixed slots instead of a literal ring.

Real keys are skewed and a few hot ones can swamp any node. Nothing here handles replication or a node dying mid-move. The ring tells you where data lives; moving it safely is the harder half, and I haven't tried that.

Change the key count or the 150 and see how far that 21.5% to 28.2% moves.

Written by the Schoolabe team, who build schoolabe.com. Its homepage says tutorials, GATE CS prep, quizzes and practice are free, and that lessons and practice problems run in the browser.