Consistent Hashing: The Algorithm That Keeps Million-User Apps From Falling Over

Your app just hit a million monthly users. Then you added one server. Then everything went down.

This happens more than people admit, and the cause is almost always the same: naive load distribution.

When you have millions of users, you cannot store everything on one machine. You spread the data across many servers. The question is: when a request comes in, which server holds the answer?

The obvious approach is to take the user ID, divide by the number of servers, and use the remainder. User 1001 with 10 servers goes to server 1. Simple. It works, until you add an eleventh server.

Now you divide by 11 instead of 10, and almost every user maps to a different server than before. Your cache is suddenly useless. Every request misses. Your database gets hit by the full force of a million users at once. The site goes down at the exact moment you were trying to scale it up.

This is the cruel irony of naive distribution: the moment you grow is the moment you break.

TL;DR: Consistent hashing maps both keys and nodes onto a fixed circular keyspace so that adding or removing a node relocates only K/N keys instead of nearly all of them. Virtual nodes fix the uneven-distribution problem. This post covers the mechanism, the implementation, and benchmarks showing the real difference under node churn.

The Problem: Why Modulo Hashing Fails at Scale

When you distribute K keys across N nodes, the naive approach is modulo hashing:

node_index = hash(key) % N

This is fast, simple, and evenly distributed. It has exactly one fatal flaw: N appears in the formula. The instant N changes, the mapping for almost every key changes with it.

Consider the redistribution cost. When N goes from 4 to 5, a key previously assigned by hash % 4 is now assigned by hash % 5. The probability that any given key keeps its assignment is roughly 1/N. For a 4-to-5 transition, that means about 80 percent of keys move.

In a caching layer, a moved key is a cache miss. A cache miss is a database read. A wave of simultaneous cache misses is a thundering herd hammering your backend at the worst possible moment.

The diagram below shows the catastrophe visually. Each key is colored by which node owns it. Adding one node should be a minor event. With modulo hashing, it is a near-total reshuffle.

Before: 4 nodes (hash % 4) vs after: 5 nodes (hash % 5)

Keys that changed node: k4 through k11, 8 of 12 (67%) in this small example. At realistic scale (N=10 to N=11) this reaches roughly 90%.

Every changed key is a cache miss. A million of them at once is a backend outage.

The Mechanism: The Hash Ring

Consistent hashing removes N from the assignment formula. Instead of mapping keys directly to node indices, it maps both keys and nodes onto the same circular keyspace, typically [0, 2^32).

The rules are simple:

1. Hash each node to a position on the ring.
2. Hash each key to a position on the ring.
3. A key belongs to the first node found walking clockwise from the key's position.

When a node is removed, only the keys that were walking clockwise into that node need to find a new home. They simply continue clockwise to the next node. Every other key is undisturbed. When a node is added, it claims only the keys in the arc immediately counter-clockwise of its position.

This is the entire idea. The redistribution is bounded by the size of one arc, not the size of the whole ring.

The ring is walked clockwise starting from position 0. Positions increase in the order: Node A, k5, k4, k1, k2, Node B, k3, Node C, then wrap back to Node A.

Each key is owned by the first node found walking clockwise from the key's position: k1 and k2 belong to Node B, k3 belongs to Node C, and k4 and k5 belong to Node A. If Node B is removed, only k1 and k2 move, continuing clockwise to Node C. Node A and its keys never move.

The Catch: Uneven Distribution

There is a problem with the basic ring. If you place three nodes randomly on the circle, the arcs between them are almost never equal. One node might own 50 percent of the ring while another owns 15 percent. With real hash functions and a small number of nodes, this skew is severe and it directly translates to one server melting while another sits idle.

The standard deviation of load with N randomly placed nodes is high precisely when N is small, which is exactly the regime most systems start in.

The Fix: Virtual Nodes

The solution is elegant. Instead of placing each physical node on the ring once, place it many times using multiple hash values. Each physical node gets, say, 150 virtual positions scattered around the ring. A key still maps to the next virtual node clockwise, and that virtual node points back to its physical owner.

With 150 virtual nodes per physical node, the arcs interleave finely enough that load variance drops dramatically. The law of large numbers does the work: many small arcs average out far better than a few large ones.

Each physical node appears many times around the ring via virtual positions, so the arcs interleave and load evens out. Walking clockwise from position 1:

With ~150 virtuals per physical node in production (rather than the 6-7 per node shown above), load variance across nodes typically drops below 5%.

Reference Implementation

A production-grade consistent hash ring in roughly 60 lines. The critical detail is the sorted ring and the binary search for the clockwise successor, which keeps lookups at O(log V) where V is the total number of virtual nodes.

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, nodes=None, virtual_nodes=150):
        self.virtual_nodes = virtual_nodes
        self._ring = {}          # hash position -> physical node
        self._sorted_keys = []   # sorted hash positions for binary search
        if nodes:
            for node in nodes:
                self.add_node(node)

    def _hash(self, key):
        # 32-bit hash position from the first 8 hex digits of MD5
        h = hashlib.md5(key.encode("utf-8")).hexdigest()
        return int(h[:8], 16)

    def add_node(self, node):
        for i in range(self.virtual_nodes):
            vkey = self._hash(f"{node}#{i}")
            self._ring[vkey] = node
            bisect.insort(self._sorted_keys, vkey)

    def remove_node(self, node):
        for i in range(self.virtual_nodes):
            vkey = self._hash(f"{node}#{i}")
            del self._ring[vkey]
            idx = bisect.bisect_left(self._sorted_keys, vkey)
            if idx < len(self._sorted_keys) and self._sorted_keys[idx] == vkey:
                self._sorted_keys.pop(idx)

    def get_node(self, key):
        if not self._ring:
            return None
        h = self._hash(key)
        # find first virtual node clockwise (wraps around at the end)
        idx = bisect.bisect_right(self._sorted_keys, h) % len(self._sorted_keys)
        return self._ring[self._sorted_keys[idx]]

Lookups are a single binary search. Adding or removing a node touches only virtual_nodes entries, independent of how many keys exist.

Benchmarks

The following numbers come from a simulation distributing 1,000,000 keys across a cluster, then adding one node and measuring how many keys were forced to relocate. Modulo hashing is compared against consistent hashing with 150 virtual nodes per physical node.

Key redistribution when growing from N to N+1 nodes:

The pattern is exact and predictable: consistent hashing moves approximately K/(N+1) keys, while modulo hashing moves approximately K · N/(N+1). The larger your cluster, the more dramatic the advantage, which is precisely the direction every growing system moves in.

Percent of keys relocated when adding one node:

Lookup latency: with a sorted-array ring and binary search, lookups remain in the low microseconds regardless of cluster size. At 150 virtual nodes across 50 physical nodes, the ring holds 7,500 entries and a lookup is a log2(7500) ≈ 13 step binary search. This is not the bottleneck. The network call that follows the lookup dominates by three orders of magnitude.

Where This Runs in Production

This is not an academic exercise. Consistent hashing is load-bearing infrastructure across the industry:

• Amazon DynamoDB and Apache Cassandra partition data across nodes using a consistent-hashing-derived ring, which is what lets them add capacity without downtime.
• Discord routes millions of concurrent users to the correct session servers using a consistent hashing layer.
• Content delivery networks use it to map each piece of content to a cache server, so adding cache capacity does not invalidate the entire cache.
• Distributed caches like the memcached client ecosystem use it so that losing one cache box costs you 1/N of your cache, not all of it.

The Business Case

For anyone building or funding software: scaling is not about adding more machines. It is about adding them without breaking the ones already running. The algorithms that make growth safe are invisible when they work and catastrophic when they are missing.

With naive hashing, adding one server to a cluster of ten reshuffles roughly 90 percent of your data. With consistent hashing, it moves about 9 percent. That difference is the line between a smooth scaling event and a 3 AM outage.

If your engineering team cannot explain how their system behaves when a server is added or removed under load, that is a risk worth asking about before your next growth phase, not after.