Consistent Hashing Explained: Add Nodes Without a Reshuffle

Almost every key changes server, so the cache misses on nearly every request and the slow storage behind it gets flooded. Consistent hashing is the rule that avoids this. This guide builds it one step at a time on one example.

Picture a common setup. An image hosting service serves photos that wedding studios and small shops show on their websites. The setup is made up, but the problem is real.

A cache is fast memory that keeps copies of popular data, so you do not fetch it from slow storage every time. The service's cache tier is 8 servers, called cache nodes, that keep thumbnails in RAM, a server's fast working memory. Behind them sits the origin store, the slow but safe storage that holds every original photo.

On a normal day the service gets about 20 crore (200 million) image requests. The cache answers 95 out of every 100, so only 5 reach the origin store. The origin store is sized for that small trickle.

A cache router picks the node for each image with one line of maths. A hash function turns any text into a big number, always the same number for the same text. The router hashes the image name, divides by 8 and uses the remainder as the node number.

This rule is called hash mod N, where mod means the remainder and N is the number of nodes. In the diagram, follow a request from the left and notice that the router's rule contains the number 8.

Then festival week arrives and traffic climbs, so the team adds a ninth node. Only about 1 key in 9 stays on its old node. The hit rate, the share of requests the cache answers, falls from 95 percent to about 11 percent.

Misses jump from 5 in every 100 requests to about 89 in 100. At the same traffic, that is roughly 18 times the load on the origin store, in its busiest week. The extra server made everything worse.

Because the answer to hash mod N depends on N, changing N changes the answer for most keys. Going from 8 to 9 nodes, a key stays put only when both remainders match, which happens for about 1 key in 9.

Take an image whose hash is 100. 100 mod 8 is 4, so it lived on node 4. 100 mod 9 is 1, so now the router sends it to node 1, which has never seen this image.

You can count this in Python over 100,000 made-up image names. Python's built-in hash() gives text a different number each time a program starts, unless you fix the PYTHONHASHSEED setting. So the code uses hashlib, which always gives the same number for the same text.

import hashlib

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

def node_by_modulo(key, n):
    return h(key) % n

keys = [f"img-{i}.jpg" for i in range(100_000)]
moved = sum(node_by_modulo(k, 8) != node_by_modulo(k, 9) for k in keys)
print(f"{moved / len(keys):.0%} of keys moved")   # prints 89%

Save it as modn.py and run python3 modn.py. You should see 89% of keys moved. In our run on Python 3.13 the exact count was 88,737 of 100,000, against the 88.9 percent that 8 in 9 predicts.

MD5, an older hash function, is fine here because you only need an even spread, not security. Any hash that every machine computes the same way would do.

Consistent hashing is a way to assign keys to servers so that adding or removing one server moves only a small share of the keys. Keys and servers are hashed onto the same circle, and each key goes to the next server clockwise.

A key is the name you look data up by. For the image service, a key is an image name such as palace-night.jpg. A server, node or bucket all mean the same thing here: one place a key can live.

The idea comes from a 1997 paper by Karger and colleagues at MIT. They wanted to spread web caching load and avoid hot spots, which they describe as many clients wanting data from a single server at once. Their abstract calls a consistent hash function one that changes minimally as its range, the set of buckets, changes.

The paper itself places buckets and items at random points between 0 and 1, sends each item to the closest bucket, and already gives each bucket several points. The circle with a clockwise walk is how later systems such as Dynamo describe the same idea.

Picture a ring road with houses all along it and a few post offices. Each house sends its letters to the next post office clockwise. When a new office opens, only the houses on the stretch just before it switch to it.

Map it part by part. Houses are keys, post offices are servers, the ring road is the circle of hash values, and walking clockwise is the lookup. Under hash mod N, by contrast, opening one office would reassign almost every house in town.

Where the picture breaks: real offices land at random spots picked by a hash, not by a town planner, so some stretches are far longer than others. And one real server can run many offices at once, which is the virtual nodes idea later.

A consistent hashing ring works in two moves: hash each server's name to a point on a circle, then hash each key and walk clockwise to the first server point. That server owns the key.

Imagine every possible hash value laid around a circle, from 0 up to the largest value, which then wraps back to 0. This circle is called the hash ring. Real rings use huge numbers, but a ring from 0 to 99 is easier to follow.

Say the team has four nodes, whose names hash to 10, 35, 60 and 85. The image sunset.jpg hashes to 47, so you walk clockwise from 47 and meet the node at 60 first. In the diagram, follow both images to their owners.

So each node owns the stretch of ring between the node before it and itself. The 2007 Dynamo paper, about a key-value store built at Amazon, states the same rule. A key-value store is a database that saves each value under a key. Here is how the router does a lookup, step by step.

1. 1

   Keep a sorted list of points

   When the node list changes, the router hashes each node name and sorts the results. For the small ring, that list is 10, 35, 60, 85.

2. 2

   Hash the key

   For each request, hash the image name with the same function. sunset.jpg becomes 47.

3. 3

   Find the first point at or above

   Binary search the sorted list for the first point equal to or above the key's hash. Binary search halves the list each step, so even a million points take about 20 steps.

4. 4

   Wrap around if needed

   If no point is bigger, go back to the first point in the list. That is how palace-night.jpg, at 92, lands on the node at 10.

5. 5

   Send the request

   Forward the request to the node that owns that point. The router stores nothing about individual keys.

When you add a node, it takes over only the keys between the point before it and its own point. When you remove a node, its keys move to the next node clockwise. Every other key stays exactly where it was.

Keys from 36 to 50 used to walk on to cache-C at 60. Now they stop at cache-E first. Here is what that means for each key.

• sunset.jpg, at 47, moves from cache-C to cache-E. Its first request is a miss, and then it is cached again.
• A key at 55 still reaches cache-C, because cache-E sits before it.
• Keys owned by cache-A, cache-B and cache-D do not move at all.
• No key moves between two old nodes. Keys only flow into the new one.

The 1997 paper states the last point as a property it calls monotonicity. When buckets are added, an item may move to a new bucket, but not from one old bucket to another. Our 100,000-key test agreed: every one of the moved keys went to the new node.

Removing a node is the mirror image. On the ring road, an office closes, and its houses simply walk on to the next office. No other house changes office.

There is a catch. With one point per node, all of a removed node's keys land on one neighbour. In our test, removing one of 8 nodes sent all 14,491 of its keys to a single neighbour. That neighbour went from 16,429 keys to 30,920, nearly double.

Virtual nodes are extra points on the ring for the same physical server. Each server gets many points instead of one, so its keys come from many small stretches, and load evens out.

With one point per server, the gaps between points are random, and some are much wider than others. We measured this on 8 nodes with 100,000 image names, using the Python code in the next section. Load is shown as a multiple of each node's fair share, one eighth of the keys.

• 1 point per node: the busiest node got 2.75 times its fair share, and the quietest got 0.10 times.
• 10 points per node: busiest 1.62, quietest 0.60.
• 100 points per node: busiest 1.16, quietest 0.91.
• 1,000 points per node: busiest 1.08, quietest 0.94.

Adding a ninth node shows the same effect. With one point each, 19.2 percent of keys moved, about 1.7 times the ideal 1 in 9, and all of them came from a single old node. With 100 points each, 11.8 percent moved, and all 8 old nodes gave up a slice.

The Dynamo paper names the same two problems with one point per node. Random positions give uneven load, and the basic scheme ignores that some machines are stronger than others. Its answer is virtual nodes, and it calls each node's ring positions tokens.

Dynamo lists three gains. A failed node's load spreads evenly over the remaining nodes. A new node takes roughly equal load from every other node, and a stronger machine can get more virtual nodes.

The image service uses that last gain at festival time. The new node has twice the RAM of the old ones, so the team gives it twice the points. In the diagram, follow the clockwise arrows and count the points each server owns.

Twice the points gives roughly, not exactly, twice the keys. In our test, 200 points against 100 gave the new node 2.39 times an old node's keys. With 800 against 400, it got 2.09 times.

What virtual nodes cost

Virtual nodes are not free. As of October 2026, the Cassandra docs (the 5.0 pages) say 2.x could only pick random tokens, so the default had to be high, at 256 per node. A deterministic token allocator added in 3.x needs far fewer per node.

The same page warns that every token adds neighbours on the ring. More tokens mean more node-failure combinations that make data partly unavailable, more repair operations and slower cluster-wide maintenance. Repair is the job that brings copies on different nodes back in sync.

Dynamo itself moved on from random tokens. Its paper reports that random tokens made a joining node's bootstrap slow, sometimes almost a day in busy seasons. It switched to splitting the ring into equal-sized partitions shared out among nodes, which gave the best load balance of the three strategies it tested.

Keep a sorted list of ring points, then binary search for the first point at or after the key's hash. Python's bisect module does that search for you, so a working ring fits in about a dozen lines.

This block reuses h() and keys from the first code block, so add it to the same file. Ring takes a list of node names and a number of virtual nodes per node.

import bisect

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.points = sorted((h(f"{n}#{i}"), n)
                             for n in nodes for i in range(vnodes))
        self.hashes = [p for p, _ in self.points]

    def node_for(self, key):
        i = bisect.bisect_left(self.hashes, h(key)) % len(self.hashes)
        return self.points[i][1]

old = Ring([f"cache-{n}" for n in range(8)])
new = Ring([f"cache-{n}" for n in range(9)])
moved = sum(old.node_for(k) != new.node_for(k) for k in keys)
print(f"{moved / len(keys):.0%} of keys moved")   # prints 12%

Three parts matter. The f-string gives each node 100 different names, such as cache-3#7, so it lands on 100 points. bisect_left finds the first point equal to or above the key's hash, and % len(self.hashes) wraps a key past the last point back to the first.

To check the load spread yourself, add this block to the same file and run it. It compares 1 point per node with 100 points per node on the same 100,000 keys.

from collections import Counter

for v in (1, 100):
    ring = Ring([f"cache-{n}" for n in range(8)], vnodes=v)
    counts = Counter(ring.node_for(k) for k in keys)
    fair = len(keys) / 8
    print(v, round(max(counts.values()) / fair, 2),
          round(min(counts.values()) / fair, 2))

It prints two lines: 1 2.75 0.1 and 100 1.16 0.91. Each number is a multiple of the fair share. With 1 point the busiest node carries 2.75 times its share; with 100 points it carries 1.16 times.

The HAProxy 3.0 manual gives the same warning for its consistent mode. To get the same spread on several load balancers, every server must have exactly the same ID on each of them.

Consistent hashing with bounded loads adds a cap: no node may carry more than a set multiple of the average load. If a key's first-choice node is full, the request moves on to the next node with room.

Virtual nodes spread keys evenly, but not requests. On the second night of the festival, one photo of a lit-up palace goes viral. Every request for it hits the same node, and that node's network card is soon maxed out.

A 2016 paper by Mirrokni, Thorup and Zadimoghaddam made this cap precise. You pick a factor c such as 1.25, and no server holds more than c times the average load, rounded up. They also bound how many extra keys move when servers change, and that cost grows as c gets closer to 1.

We tried a simplified, static version on the 8 to 9 move with 100 points per node. A loose cap of 1.25 never triggered, so it moved the same 11.8 percent as no cap. A tight cap of 1.05 moved 12.9 percent. With one point per node, a cap of 1.25 moved 26.6 percent against 19.2 percent uncapped.

Here is the lookup with a cap of 1.25 times the average. Start at the request and follow the Yes arrow to see where the overflow goes.

You do not have to build this yourself. HAProxy, a widely used open-source load balancer, has a setting called hash-balance-factor for its consistent mode. It counts load as concurrent requests, and a value of 150 means no server may carry more than 1.5 times the average.

The manual says the default of 0 turns the feature off, and calls values from 125 to 200 reasonable. A higher factor allows more imbalance. A lower one checks more servers per request, which costs time.

Spilling has a price. Every node that takes overflow for the viral photo fetches and caches its own copy, so the origin store sees a few extra misses. For a single, extremely hot photo, the team also keeps a small copy in the router's own memory.

Consistent hashing is used wherever data or requests are split across a changing set of machines. Common examples are distributed caches, key-value stores such as Dynamo and Cassandra, and load balancers such as HAProxy.

• Dynamo, from 2007, hashes each key with MD5 onto a ring with virtual nodes. Its stated goal was to scale out one storage host at a time.
• Cassandra hashes each key to a token and walks the ring clockwise until it finds enough distinct nodes to hold the copies.
• HAProxy's consistent hash-type fills a tree with many occurrences of each server, which is virtual nodes by another name. The manual says adding a server moves only a few mappings, which makes it ideal for caches.
• Jump consistent hash, from 2014, needs no stored ring at all. Its catch is that buckets must be numbered in order.

The HAProxy manual also describes the old way, which it calls map-based. It is still the default, and the manual recommends it for most uses. Because a server is picked by its position in an array, most mappings change when the server count changes. That is the festival-week problem in one sentence.

The manual is also honest about the cost. It says the consistent mode's distribution will never be very smooth, and you may need to adjust a server's weight or ID to balance it.

How rings place copies

Rings also decide where copies go. Dynamo stores each key on its owner node, then copies it to the next N minus 1 nodes clockwise. That ordered list of nodes for a key is called its preference list.

Virtual nodes add a wrinkle, because the next few points clockwise might belong to the same machine. So Dynamo skips points until the list holds only distinct machines. In our test with 8 nodes and 100 points each, 36 percent of starting points had a repeated machine among the next 3.

Without that skip, one machine failure could take out two copies of those keys, and in rare cases all three. The table puts the main choices side by side, using the 8 to 9 node move.

Start from the problem it solves, a cache that goes cold when it grows, and then build the ring one layer at a time. Each layer should fix a failure you have just named.

1. 1

   Show the hash mod N trap

   Say that going from N to N plus 1 servers moves about N in N plus 1 keys. For a cache, that means a near-total miss storm on the storage behind it.

2. 2

   Draw the ring

   Hash servers and keys onto one circle. Each key belongs to the next server clockwise. Adding a server moves only about 1 key in N plus 1.

3. 3

   Add virtual nodes

   Give each server many points to even out load. Give bigger servers more points. Mention that in stores like Cassandra, more points mean more repair and maintenance work.

4. 4

   Add replication

   Copy each key to the next few distinct machines clockwise, skipping points owned by a machine already on the list.

5. 5

   Handle hot keys

   Mention bounded loads, which cap each node near the average, and a small local cache for the hottest keys.

6. 6

   Say how routers agree

   All routers must build the ring from the same node list. Keep that list in one shared, versioned place.