Consistent Hashing Explained: How Distributed Caches Avoid a Total Reshuffle

Quick Answer

Consistent hashing maps both servers and keys onto the same circular hash space, so each key belongs to the next server found going clockwise around the ring. Adding or removing one server only reassigns the keys that fell between it and its neighbor — roughly 1/N of all keys for N servers — instead of reshuffling almost everything, which is what plain key-modulo-N hashing does. A real 100,000-key simulation below shows this: 17.35% of keys moved when going from 5 to 6 nodes with consistent hashing, versus 83.42% with naive modulo hashing.

The Problem: Why key % N Falls Apart

The obvious way to spread keys across N cache servers is hash(key) % N — compute a hash of the key, take the remainder when divided by the number of servers, and that remainder tells you which server owns the key. It's simple, it distributes keys evenly, and it works fine right up until N changes.

The moment you add or remove a single server, N changes, and hash(key) % N produces a completely different remainder for nearly every key. A key that hashed to remainder 7 out of 5 servers might hash to remainder 3 out of 6 servers, with no relationship between the two — the modulo operation has no memory of the previous mapping. In a cache, that means almost every key is suddenly "owned" by a different server than the one that has it cached, which looks to the system exactly like a mass cache miss: read traffic that used to hit cache now falls straight through to the database, all at once, right at the moment you were trying to scale up capacity.

This is the exact problem consistent hashing was invented to solve. It first appeared in a 1997 paper by Karger et al. at MIT, built for web caching (Akamai's early architecture used it), and the same idea now sits underneath Amazon DynamoDB, Apache Cassandra, and the ketama hashing scheme used by memcached client libraries. The goal in every case is the same: when the set of servers changes, move as few keys as mathematically necessary, and no more.

The Hash Ring: Mapping Servers and Keys to the Same Space

Consistent hashing works by hashing servers and keys into the same numeric space and treating that space as a circle instead of a line. Concretely: pick a hash function that outputs, say, a 32-bit integer, so the output range is 0 to 2^32 - 1. Hash each server's identifier (its hostname or IP) into that range — that gives each server a fixed position, a point on the circle. Then, to find which server owns a given key, hash the key into the same range, and walk clockwise around the circle from that point until you hit the first server position. That server owns the key.

The reason this survives adding or removing a server is entirely about locality. When you add a new server, it lands at one new point on the circle. That point sits between two existing server positions, splitting the arc that used to belong entirely to the server after it. Only the keys that hash into that specific arc — the ones that used to walk clockwise to the old server but now hit the new server first — get reassigned. Every other key's clockwise walk is completely unaffected, because their nearest clockwise server hasn't moved. Removing a server works the same way in reverse: its arc merges into the next server clockwise, and only the keys that were in that arc move, to exactly one new owner.

Compare that to modulo hashing, where every key's assignment depends on the total count N through a division operation that has no concept of "neighboring" servers — changing N perturbs the remainder for almost every key simultaneously, because there's no ring structure limiting the blast radius to a local region.

Virtual Nodes: Fixing the Uneven-Split Problem

A ring with one point per physical server has a real problem: with only a handful of servers, the arcs between them can be wildly uneven purely by chance, the same way flipping a coin 5 times doesn't reliably give you 2.5 heads. One server might end up owning a tiny sliver of the ring while its neighbor owns half of it, just because of where their hash values happened to land. That means uneven load — some cache servers run hot, others sit nearly idle — for reasons that have nothing to do with capacity planning and everything to do with hash luck.

The standard fix is virtual nodes (sometimes called "vnodes" or "replicas" in the ring, not to be confused with data replication): instead of hashing each physical server to one point on the ring, hash it to many points —100, 150, 200, whatever the implementation chooses — each derived from the server's identifier plus an index, like "cache-a#vn0", "cache-a#vn1", and so on. Now each physical server owns many small, scattered arcs instead of one large contiguous one, and the law of large numbers takes over: with enough virtual nodes, the sum of each server's scattered arcs converges toward an equal share of the ring, regardless of hash luck on any individual point. It also means that when a server is added or removed, the keys that move are drawn roughly proportionally from every remaining server rather than dumped disproportionately onto one unlucky neighbor.

Proving the ~1/N Claim With a Real Simulation

It's one thing to assert that consistent hashing only moves "about 1/N of the keys." It's another to actually build a ring, populate it with real keys, and count. Here's a complete, runnable implementation with 150 virtual nodes per server, using MD5 for the hash function (fine for this purpose — no security property is needed, just good distribution):

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, nodes=None, vnodes=150):
        self.vnodes = vnodes
        self.ring = {}          # hash value -> node name
        self.sorted_keys = []   # sorted list of hash values
        if nodes:
            for n in nodes:
                self.add_node(n)

    def _hash(self, key):
        h = hashlib.md5(key.encode("utf-8")).hexdigest()
        return int(h, 16) % (2**32)

    def add_node(self, node):
        for i in range(self.vnodes):
            h = self._hash(f"{node}#vn{i}")
            self.ring[h] = node
            bisect.insort(self.sorted_keys, h)

    def remove_node(self, node):
        for i in range(self.vnodes):
            h = self._hash(f"{node}#vn{i}")
            del self.ring[h]
            self.sorted_keys.remove(h)

    def get_node(self, key):
        h = self._hash(key)
        idx = bisect.bisect(self.sorted_keys, h)
        if idx == len(self.sorted_keys):
            idx = 0
        return self.ring[self.sorted_keys[idx]]

First, the baseline: 5 servers, 100,000 keys (user:0 through user:99999), 150 virtual nodes each. Here's the actual distribution this run produced:

cache-a: 22686 keys (22.69%)
cache-b: 19701 keys (19.70%)
cache-c: 18648 keys (18.65%)
cache-d: 19536 keys (19.54%)
cache-e: 19429 keys (19.43%)
ideal share per node (1/5): 20.00%

Reasonably close to the ideal 20% each, with natural variance from 18.65% to 22.69% — that spread is a real, honest artifact of 150 virtual nodes rather than a perfectly uniform split; doubling or tripling the virtual node count per server tightens this further at the cost of a larger routing table to search.

Now the actual test — add a 6th server, then remove one of the original five, and count exactly how many of the 100,000 keys changed which server they map to:

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

ring = ConsistentHashRing(["cache-a", "cache-b", "cache-c", "cache-d", "cache-e"], vnodes=150)
before = {k: ring.get_node(k) for k in keys}

ring.add_node("cache-f")
after_add = {k: ring.get_node(k) for k in keys}
moved_add = sum(1 for k in keys if before[k] != after_add[k])
print(f"Added cache-f: {moved_add}/{NUM_KEYS} keys moved ({100*moved_add/NUM_KEYS:.2f}%)")

ring.remove_node("cache-b")
after_remove = {k: ring.get_node(k) for k in keys}
moved_remove = sum(1 for k in keys if after_add[k] != after_remove[k])
print(f"Removed cache-b: {moved_remove}/{NUM_KEYS} keys moved ({100*moved_remove/NUM_KEYS:.2f}%)")

The real output from running this:

Added cache-f: 17353/100000 keys moved (17.35%)
Removed cache-b: 17349/100000 keys moved (17.35%)

17.35% moved when scaling from 5 to 6 nodes, against a theoretical expectation of 1/6 = 16.67% — close, with the small gap being exactly the kind of sampling variance you'd expect from a finite number of virtual nodes rather than a perfectly continuous ring. A sanity check built into the test (not shown in the trimmed snippet above, but run as part of verifying this) confirmed every single one of those moved keys landed specifically on the new server cache-f, and confirmed that after removing cache-b, the keys that moved were exactly and only the keys that had been assigned to cache-b — not one key belonging to cache-a, cache-c, cache-d, or cache-e was touched by cache-b's removal.

For contrast, here's the naive hash(key) % N approach doing the identical 5-to-6 transition on the same 100,000 keys:

def naive_node(key, n):
    h = int(hashlib.md5(key.encode("utf-8")).hexdigest(), 16)
    return h % n

naive_before = {k: naive_node(k, 5) for k in keys}
naive_after = {k: naive_node(k, 6) for k in keys}
naive_moved = sum(1 for k in keys if naive_before[k] != naive_after[k])
print(f"Naive mod-N, 5 -> 6 nodes: {naive_moved}/{NUM_KEYS} moved ({100*naive_moved/NUM_KEYS:.2f}%)")

Naive mod-N, 5 -> 6 nodes: 83418/100000 moved (83.42%)

83.42% of keys moved. That's the entire point of consistent hashing in one number: roughly 1 in 6 keys displaced instead of roughly 5 in 6.

Where This Algorithm Actually Runs in Production

Consistent hashing is the routing layer underneath several systems this site has already covered from other angles. When we've discussed sharding a database that outgrew one machine, consistent hashing is one of the concrete algorithms used to decide which shard a given row's key belongs to, specifically because it lets you add shards later without recomputing every row's shard assignment from scratch. When we've discussed load balancers, some load balancing strategies — particularly for stateful or cache-aware routing, where you want the same client or key to keep landing on the same backend — use a hash ring instead of round-robin for exactly the locality property described above.

Amazon's DynamoDB paper (2007) used consistent hashing with virtual nodes as its core partitioning mechanism, explicitly citing the uneven-load problem of plain hash rings as the reason for adding virtual nodes. Apache Cassandra inherited the same approach. Memcached itself doesn't have any built-in clustering, but essentially every memcached client library that supports multiple servers (like the ketama algorithm used in libmemcached) implements consistent hashing client-side, so the client — not the cache servers — decides which server a key belongs to, and can do so consistently across every application server without coordination.

CDN edge routing and some peer-to-peer systems (the original Chord distributed hash table paper is a close relative of the same idea) also use ring-based hashing for the same underlying reason: minimizing disruption when nodes join or leave a large distributed set.

Remaining Weaknesses: Hot Keys and Bounded-Load Variants

Consistent hashing solves the rebalancing problem, but it doesn't solve an uneven key access pattern. If one key is dramatically more popular than the others — a celebrity's profile, a viral product page — the server that owns that key gets disproportionate traffic no matter how evenly the ring divides the key space. The ring guarantees even distribution of key ownership, not even distribution of key access frequency, and those are genuinely different problems.

A related weakness shows up under real (non-uniform) workloads even without a single hot key: because each server's share of the ring is only approximately equal, a server can end up serving somewhat more request volume than its neighbors purely from owning a slightly larger combined arc, and that gap can widen under skewed access patterns. Google published a variant called Consistent Hashing with Bounded Loads (2016) specifically to address this: instead of always routing a key to its nearest clockwise server regardless of that server's current load, the algorithm allows a key to be routed to the next server around the ring if the nearest one is already over some configurable load threshold, capping how far any single server's load can exceed the average.

None of this changes the core rebalancing property demonstrated above — it's a refinement layered on top for workloads where request volume per key varies enormously, which is common in real caching workloads (the classic 80/20 or even more skewed access distribution) but wasn't modeled in the uniform-key-access simulation in this post.

Practical Considerations When Implementing This

Choosing a hash function matters less than intuition suggests — MD5, as used above, or a fast non-cryptographic hash like MurmurHash3 both work fine, since no security property is needed and the only requirement is good distribution across the output range with low collision rates between different virtual node identifiers. What matters more is picking a virtual-node count that's high enough to smooth out load variance (100-200 per physical server is a common range in real implementations) without making the ring's sorted key list so large that lookups become a bottleneck — each lookup is a binary search over that list, so it's O(log(N × vnodes)), still fast, but not free at extreme scale.

Replication for availability layers on top of the same ring cleanly: instead of a key belonging to just the first server found clockwise, many systems (Cassandra and DynamoDB both do this) replicate a key to the next R servers found walking clockwise, so losing any single server doesn't lose data, only redundancy. And when a node is permanently removed rather than just temporarily down, remember that its keys need to be actively migrated to their new owner before it's decommissioned — consistent hashing tells you cleanly which keys moved and to where, but the actual data transfer is still your application's or database's job to execute.

Frequently Asked Questions