Why use MD5 for hashing here instead of Python's built-in hash()?

Python's hash() is randomized per-process by default (for security reasons) and isn't guaranteed stable across runs or between different processes — which would make the ring itself different on every server holding a copy of it. MD5 is deterministic: the same key always hashes to the same point, everywhere, which is required for every node to agree on the ring.

What are 'virtual nodes' actually for?

One point per server on the ring can land unluckily close to another, giving one server a much bigger share of the keyspace than another purely by chance. Adding many virtual nodes (replicas) per real server spreads that server's share across many small ranges instead of one big one, measurably narrowing the gap between the most- and least-loaded server.

Does consistent hashing solve uneven load, or just uneven remapping?

Both, but they're separate properties. Uneven remapping (this lesson's main example) is about how much moves when membership changes. Uneven load is about how evenly keys are split at any single point in time, with no membership change at all — more virtual nodes improves both, but they're not the same measurement.

Is 100 replicas per server a rule, or just this lesson's choice?

Just this lesson's choice, picked because it gets close to even distribution without needing thousands of ring entries. Real systems (Amazon's Dynamo paper, Cassandra) use their own tuned values based on cluster size and measured skew, not a single universal constant.

Consistent Hashing: Why Adding a Server Shouldn't Remap Everything

Plain modulo hashing recomputes every key’s server the moment the server count changes; a hash ring only has to move the keys that actually land near the server that joined or left.

Removing one server: 77% remapped vs 23%

import hashlib
import bisect

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16)

def modulo_assignment(keys, servers):
    return {key: servers[h(key) % len(servers)] for key in keys}

class ConsistentHashRing:
    def __init__(self, servers, replicas=100):
        self.replicas = replicas
        self.ring = {}
        self.sorted_hashes = []
        for server in servers:
            self.add_server(server)

    def add_server(self, server):
        for i in range(self.replicas):
            point = h(f"{server}#{i}")
            self.ring[point] = server
            bisect.insort(self.sorted_hashes, point)

    def remove_server(self, server):
        points = [p for p, s in self.ring.items() if s == server]
        for p in points:
            del self.ring[p]
            self.sorted_hashes.remove(p)

    def get(self, key):
        point = h(key)
        idx = bisect.bisect(self.sorted_hashes, point)
        if idx == len(self.sorted_hashes):
            idx = 0
        return self.ring[self.sorted_hashes[idx]]

keys = [f"user-{i}" for i in range(1000)]
servers = ["server-a", "server-b", "server-c", "server-d"]

before_modulo = modulo_assignment(keys, servers)
after_modulo = modulo_assignment(keys, servers[:3])  # server-d removed
moved_modulo = sum(1 for k in keys if before_modulo[k] != after_modulo[k])
print(f"Modulo hashing: {moved_modulo}/{len(keys)} keys remapped after removing 1 of 4 servers")

ring = ConsistentHashRing(servers)
before_ring = {k: ring.get(k) for k in keys}
ring.remove_server("server-d")
after_ring = {k: ring.get(k) for k in keys}
moved_ring = sum(1 for k in keys if before_ring[k] != after_ring[k])
print(f"Consistent hashing: {moved_ring}/{len(keys)} keys remapped after removing 1 of 4 servers")

$ python consistent_hashing.py
Modulo hashing: 770/1000 keys remapped after removing 1 of 4 servers
Consistent hashing: 230/1000 keys remapped after removing 1 of 4 servers

key % 4 and key % 3 agree for almost no key, so removing one server changes where 77% of all keys land — every cache or shard using modulo routing would see a mass eviction/rebalance for a single server loss. The ring only remaps the ~23% of keys that actually lived in server-d’s ranges; everyone else’s assignment doesn’t change at all.

Practice

1. Compare key distribution evenness across 1, 10, and 100 virtual replicas per server.

import hashlib
import bisect

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16)

class ConsistentHashRing:
    def __init__(self, servers, replicas=100):
        self.replicas = replicas
        self.ring = {}
        self.sorted_hashes = []
        for server in servers:
            self.add_server(server)

    def add_server(self, server):
        for i in range(self.replicas):
            point = h(f"{server}#{i}")
            self.ring[point] = server
            bisect.insort(self.sorted_hashes, point)

    def get(self, key):
        point = h(key)
        idx = bisect.bisect(self.sorted_hashes, point)
        if idx == len(self.sorted_hashes):
            idx = 0
        return self.ring[self.sorted_hashes[idx]]

keys = [f"user-{i}" for i in range(1000)]
servers = ["server-a", "server-b", "server-c", "server-d"]

for replicas in [1, 10, 100]:
    ring = ConsistentHashRing(servers, replicas=replicas)
    counts = {}
    for k in keys:
        s = ring.get(k)
        counts[s] = counts.get(s, 0) + 1
    values = list(counts.values())
    print(f"replicas={replicas:>3}: {counts}  (min={min(values)}, max={max(values)})")

$ python replica_count_evenness.py
replicas=  1: {'server-a': 364, 'server-c': 77, 'server-d': 294, 'server-b': 265}  (min=77, max=364)
replicas= 10: {'server-c': 251, 'server-b': 271, 'server-d': 294, 'server-a': 184}  (min=184, max=294)
replicas=100: {'server-d': 230, 'server-c': 242, 'server-a': 265, 'server-b': 263}  (min=230, max=265)

At 1 replica per server, one unlucky hash placement gives server-a almost 5x server-c’s share. By 100 replicas, the min/max gap shrinks from 287 keys down to 35 — more virtual nodes trades ring size for evenness.

2. Add a 4th server instead of removing one, and confirm every remapped key moved specifically to the new server.

import hashlib
import bisect

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16)

class ConsistentHashRing:
    def __init__(self, servers, replicas=100):
        self.replicas = replicas
        self.ring = {}
        self.sorted_hashes = []
        for server in servers:
            self.add_server(server)

    def add_server(self, server):
        for i in range(self.replicas):
            point = h(f"{server}#{i}")
            self.ring[point] = server
            bisect.insort(self.sorted_hashes, point)

    def get(self, key):
        point = h(key)
        idx = bisect.bisect(self.sorted_hashes, point)
        if idx == len(self.sorted_hashes):
            idx = 0
        return self.ring[self.sorted_hashes[idx]]

keys = [f"user-{i}" for i in range(1000)]
servers = ["server-a", "server-b", "server-c"]

ring = ConsistentHashRing(servers)
before = {k: ring.get(k) for k in keys}

ring.add_server("server-d")
after = {k: ring.get(k) for k in keys}

moved = sum(1 for k in keys if before[k] != after[k])
moved_to_new = sum(1 for k in keys if after[k] == "server-d")
print(f"Keys remapped after adding server-d: {moved}/{len(keys)}")
print(f"Of those, keys that moved TO server-d: {moved_to_new}")

$ python add_server.py
Keys remapped after adding server-d: 230/1000
Of those, keys that moved TO server-d: 230

Every single remapped key moved to the new server — none moved between two of the three existing servers. That’s the property modulo hashing doesn’t have: joining a ring only steals keys from whichever ranges the new node’s points happen to fall into.

3. Confirm modulo hashing is just as disruptive when ADDING a server as it was removing one.

import hashlib

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16)

def modulo_assignment(keys, servers):
    return {key: servers[h(key) % len(servers)] for key in keys}

keys = [f"user-{i}" for i in range(1000)]
servers = ["server-a", "server-b", "server-c"]

before = modulo_assignment(keys, servers)
after = modulo_assignment(keys, servers + ["server-d"])

moved = sum(1 for k in keys if before[k] != after[k])
print(f"Modulo hashing: {moved}/{len(keys)} keys remapped after ADDING a 4th server")

$ python modulo_add_server.py
Modulo hashing: 770/1000 keys remapped after ADDING a 4th server

Same 77% churn as the removal case — key % 3 and key % 4 disagree for almost every key regardless of which direction the server count changes, since the modulus itself changed.

4. Measure how the remap fraction compares to the theoretical ideal (1/N) as cluster size grows.

import hashlib
import bisect

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16)

class ConsistentHashRing:
    def __init__(self, servers, replicas=100):
        self.replicas = replicas
        self.ring = {}
        self.sorted_hashes = []
        for server in servers:
            self.add_server(server)

    def add_server(self, server):
        for i in range(self.replicas):
            point = h(f"{server}#{i}")
            self.ring[point] = server
            bisect.insort(self.sorted_hashes, point)

    def remove_server(self, server):
        points = [p for p, s in self.ring.items() if s == server]
        for p in points:
            del self.ring[p]
            self.sorted_hashes.remove(p)

    def get(self, key):
        point = h(key)
        idx = bisect.bisect(self.sorted_hashes, point)
        if idx == len(self.sorted_hashes):
            idx = 0
        return self.ring[self.sorted_hashes[idx]]

keys = [f"user-{i}" for i in range(1000)]

for n in [4, 8, 16]:
    servers = [f"server-{i}" for i in range(n)]
    ring = ConsistentHashRing(servers)
    before = {k: ring.get(k) for k in keys}
    ring.remove_server("server-0")
    after = {k: ring.get(k) for k in keys}
    moved = sum(1 for k in keys if before[k] != after[k])
    ideal = len(keys) / n
    print(f"{n} servers: {moved}/{len(keys)} remapped (ideal ~1/{n} = {ideal:.0f})")

$ python remap_fraction_vs_ideal.py
4 servers: 226/1000 remapped (ideal ~1/4 = 250)
8 servers: 77/1000 remapped (ideal ~1/8 = 125)
16 servers: 45/1000 remapped (ideal ~1/16 = 62)

The theoretical minimum for removing 1 of N servers is exactly 1/N of the keys — whatever that one server owned has to go somewhere. Consistent hashing gets close to that floor at every cluster size tested here; modulo hashing has no relationship to it at all, since its remap fraction depends on how the old and new modulus happen to agree, not on how many servers changed.

Removing one server: 77% remapped vs 23%

Practice

Frequently Asked Questions