Consistent Hashing

Build the mental model

The naive way to shard N servers is `hash(key) % N`, which distributes keys evenly — but the moment N changes (a server is added or removed to scale), the modulus changes for nearly every key, meaning almost every key now maps to a different server. In a cache or sharded database, this triggers a massive, disruptive reshuffle: nearly all data must be moved, and caches effectively empty out all at once. Consistent hashing fixes this by hashing both servers and keys onto the same circular numeric space (a 'ring'), and assigning each key to the first server found going clockwise from the key's position. Adding a new server only takes over the keys between it and its clockwise neighbor — everyone else's assignment is untouched — so only about 1/N of keys move on average, instead of nearly all of them. This is why systems like DynamoDB, Cassandra, and many CDNs and load balancers use it: it makes horizontal scaling an incremental, low-disruption operation instead of an all-at-once migration.

Connect it to a real scenario

As the Tutorial Platform's cache layer (storing rendered lesson pages, popular quiz results) grows, it distributes cache entries across many cache servers. Using naive hash % N meant that adding a single new cache server during a traffic spike remapped almost every cached lesson to a different server, causing a cache-miss storm right when the site needed caching most. Switching to consistent hashing means adding a cache server during peak load only reassigns a small slice of keys, keeping the rest of the cache warm — the platform scales its cache tier without self-inflicted downtime.

Naive hash % N reassigns nearly every key whenever the number of servers N changes.
Consistent hashing places both servers and keys on a ring, assigning each key to the next server clockwise.
Adding a server only reassigns about 1/N of keys, leaving everyone else's mapping untouched.

Try the working example

python

import bisect
import hashlib

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

class ConsistentHashRing:
    def __init__(self, servers):
        self.ring = []  # sorted list of (hash, server) pairs
        for s in servers:
            self.add_server(s)

    def add_server(self, server):
        point = h(server)
        bisect.insort(self.ring, (point, server))

    def get_server(self, key):
        point = h(key)
        hashes = [p for p, _ in self.ring]
        idx = bisect.bisect(hashes, point) % len(self.ring)
        return self.ring[idx][1]

# Demo: how many keys move when we add a server
keys = [f"lesson-{i}" for i in range(1000)]

ring = ConsistentHashRing(["cache-A", "cache-B", "cache-C"])
before = {k: ring.get_server(k) for k in keys}

ring.add_server("cache-D")
after = {k: ring.get_server(k) for k in keys}

moved = sum(1 for k in keys if before[k] != after[k])
print(f"{moved} of {len(keys)} keys moved ({moved/len(keys):.1%})")

You should see

Prints that going from 3 to 4 servers moves 310 of the 1000 keys (31.0%) — close to the 1/N = 25% expected on average, and nowhere near the almost-total reshuffle naive hash % N would cause. It isn't exactly 25% because each server sits at only one point on the ring here, not many virtual nodes (see this lesson's first pitfall).

5-minute try-it

Run the code, then predict what percentage of keys would move if you added 2 servers at once (going from 3 to 5), and verify by running it.

One important caution

Hashing each server to just one point on the ring gives uneven key distribution — production systems add many virtual nodes (100+) per server to balance load more evenly.

Using a weak or non-stable hash function (like Python's built-in randomized hash()) can shift the mapping on every process restart, invalidating the entire cache — a stable hash like md5/sha1 avoids this.

Wikipedia — Consistent hashing — System Design