Consistent Hashing: Adding a Server Shouldn't Hurt

Add a fifth server to a four-server cache cluster using plain key % num_servers hashing, and simulate it with 10,000 real keys: 79.8% of them land on a different server than before. Every one of those is a cache miss, a redundant fetch, or in a sharded database, data that has to move. Do the same thing with consistent hashing instead, and 18.6% move, close to the 20% theoretical minimum for going from 4 servers to 5. Same scaling event, four times less disruption. That gap is the entire reason consistent hashing exists.

Why mod-N hashing falls apart

hash(key) % num_servers is the obvious first approach, and it works fine as long as num_servers never changes. The problem is the modulus itself. Change num_servers from 4 to 5, and for almost every key, hash(key) % 4 and hash(key) % 5 land on completely different values. There’s no partial overlap to exploit, the whole assignment function shifted.

def assign_mod_n(key: str, num_servers: int) -> int:
    return hash(key) % num_servers

# Going from 4 to 5 servers reassigns almost every key:
assign_mod_n("user-42", 4)  # -> server 2, say
assign_mod_n("user-42", 5)  # -> server 0, unrelated to the old answer

For a cache, that means a near-total cold start right when your system is under enough load to need a new server. For a sharded database, it means moving nearly all your data during a rebalance instead of just the fraction that actually needs to move.

The ring, and how a key finds its server

Consistent hashing fixes this by putting servers and keys on the same number line, and making it circular. Hash each server’s identifier to get its position on the ring. To find which server owns a key, hash the key to get its own position, then walk clockwise until you hit a server. That server owns the key.

import hashlib
import bisect

def ring_hash(s: str) -> int:
    return int(hashlib.md5(s.encode()).hexdigest(), 16)

class ConsistentHashRing:
    def __init__(self, servers: list[str], vnodes: int = 150):
        self.vnodes = vnodes
        self.ring: dict[int, str] = {}
        for server in servers:
            for i in range(vnodes):
                pos = ring_hash(f"{server}#{i}")
                self.ring[pos] = server
        self.sorted_positions = sorted(self.ring.keys())

    def get_server(self, key: str) -> str:
        pos = ring_hash(key)
        idx = bisect.bisect(self.sorted_positions, pos) % len(self.sorted_positions)
        return self.ring[self.sorted_positions[idx]]

    def add_server(self, server: str):
        for i in range(self.vnodes):
            pos = ring_hash(f"{server}#{i}")
            self.ring[pos] = server
        self.sorted_positions = sorted(self.ring.keys())

    def remove_server(self, server: str):
        for i in range(self.vnodes):
            pos = ring_hash(f"{server}#{i}")
            del self.ring[pos]
        self.sorted_positions = sorted(self.ring.keys())

Adding a server inserts new points into the ring. Only the keys that fall between the new server’s position and the previous server clockwise of it get reassigned, everyone else’s clockwise walk still hits the same server it always did. Removing a server does the reverse: only the keys it owned move, to whatever server is now next clockwise.

Why single positions aren’t enough: virtual nodes

Hash one point per server onto the ring and you get uneven coverage purely from randomness. With four servers, one might own 45% of the ring’s circumference and another 8%, just because hashes don’t space themselves out evenly by chance. That defeats the purpose: you’ve bounded how many keys move on a scaling event, but load between servers is still lumpy.

The fix is to give each physical server many positions on the ring, its virtual nodes, instead of one. server-2#0, server-2#1, server-2#37, and so on, each hashed to a different point. With 150-200 virtual nodes per server, the law of large numbers takes over and each server ends up owning close to its fair share of the ring, regardless of cluster size. The code above does this already, vnodes is the knob.

Measuring the difference

The claim “consistent hashing moves fewer keys” is checkable, so here’s an actual simulation rather than a hand-wavy argument: 10,000 synthetic keys, going from 4 servers to 5, measuring how many keys land on a different server after the change.

Mod-N hashing moved 79.8% of keys, essentially the whole dataset. Consistent hashing with 200 virtual nodes per server moved 18.6%, just above the theoretical floor of 20% (1 new server out of 5 total should own roughly a fifth of the keys). That’s the mechanism working exactly as designed: the new server picks up its fair share, and everyone else’s assignments are untouched.

	mod-N hashing	Consistent hashing
Keys moved (4→5 servers, simulated)	79.8%	18.6%
Theoretical minimum for this change	n/a (whole-table reshuffle by design)	20.0%
Distribution evenness	Perfect (by construction)	Near-even with virtual nodes
Implementation complexity	Trivial	Moderate (ring, vnodes, lookup)

Where it actually shows up

Distributed caches. Memcached clients and similar systems use consistent hashing to route keys to cache servers, specifically so that scaling the cluster up doesn’t invalidate most of the cache at once, the exact scenario simulated above.

Database sharding and replica placement. DynamoDB’s original design paper and Cassandra both use consistent hashing (with vnodes) to place data around a ring of nodes, so adding capacity redistributes a bounded slice of data instead of triggering a full reshard. This is a close cousin of the Merkle tree anti-entropy sync those same systems use to keep replicas consistent once the ring has decided who owns what.

CDN and load balancer request routing. Routing a request consistently to the same backend or cache tier, for session affinity or cache locality, without needing a central lookup table that changes on every scaling event, is the same ring-lookup problem in a different context, closely related to the tradeoffs covered in load balancing algorithms explained.

Content-addressable and P2P systems. Chord and similar distributed hash table designs use the ring structure directly as their routing mechanism, not just as a load-balancing trick, letting nodes find data with O(log n) hops instead of a full table.

When to skip it

If your server count is fixed, three database replicas that aren’t going to become four next quarter, mod-N hashing is simpler, has zero ring-maintenance overhead, and distributes perfectly evenly by construction. The complexity of a ring, virtual node tuning, and the lookup structure earns its cost specifically when servers scale up and down, fail and get replaced, or the fleet resizes often enough that reshuffling nearly everything on each change is a real, recurring cost, not a hypothetical one. If you’re also weighing how to shard the underlying data itself, consistent hashing is usually the mechanism that decides which shard a key lands on, not a replacement for the sharding decision.

The simulation above is the whole argument in one picture: same scaling event, four times less disruption, because the ring only reassigns the keys that actually need to move.