Consistent Hashing Explained: Hash Ring, Virtual Nodes and Rebalancing

You spread a cache across ten servers with hash(key) % 10. Traffic grows, you add an eleventh server, and the hit rate collapses: almost every key now maps to a different server, so the cache is cold everywhere at once and the database behind it takes the full load. Consistent hashing exists to prevent exactly this.

This post explains the hash ring and virtual nodes with a diagram, measures how much they help, shows a compact implementation, and compares the alternatives you will meet in real systems: rendezvous hashing, jump hash, Maglev and fixed hash slots.

Why modulo hashing breaks

With server = hash(key) % N, the mapping depends on N. Change N and a key stays put only if its hash gives the same remainder for both values, which is rare. In a quick simulation with one million keys:

The ideal is 1/11, about 9.1%: the new server should take its fair share and nothing else should move. The ring gets close, and the remaining gap comes from the new server's tokens landing on slightly larger arcs than average.

For a cache, the difference is a brief dip in hit rate versus a cold start. For a sharded database or a set of stateful workers, it is the difference between moving a tenth of the data and moving almost all of it.

The hash ring

Consistent hashing, introduced by Karger and colleagues in 1997 for web caching, maps both servers and keys onto the same circular hash space, for example the integers from 0 to 2^64 - 1 with the largest value wrapping around to 0.

1. Hash each server's name to a position on the ring.
2. Hash each key to a position on the ring.
3. Walk clockwise from the key's position. The first server you meet owns the key.

Adding a server places it at one position, and it takes over only the keys between its predecessor and itself. Every other key stays where it was. Removing a server hands its keys to the next server clockwise. Nothing else changes.

Virtual nodes: fixing the imbalance

With one position per server, the arcs between servers are random and uneven, so some servers own far more of the ring than others. The same simulation with ten servers shows how much:

The fix is to give each server many positions, called virtual nodes or tokens, by hashing names such as cache-a#0, cache-a#1 and so on. Virtual nodes also bring two other benefits:

• Weights. A server with twice the memory gets twice the tokens.
• Gentler failures. When a server dies, its many small arcs go to many different successors, so its load spreads across the cluster instead of doubling the load of one neighbor.

The cost is a bigger lookup table and more metadata to move when membership changes. Cassandra shows the trade-off in practice: it used 256 tokens per node by default before version 4.0 lowered the default to 16, paired with a token allocation algorithm that places those 16 evenly instead of randomly.

A small implementation

A ring is a sorted list of token positions and a binary search:

import bisect
import hashlib

def hash64(value: str) -> int:
    # MD5 for spread, not security; any well-mixed hash works
    return int.from_bytes(hashlib.md5(value.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted token positions
        self.owners = {}   # position -> server
        for server in servers:
            self.add(server)

    def add(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            bisect.insort(self.points, p)
            self.owners[p] = server

    def remove(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            self.points.remove(p)
            del self.owners[p]

    def lookup(self, key: str) -> str:
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owners[self.points[i]]

Lookups cost O(log T) for T tokens. Production versions also handle token collisions and keep every client's view of membership identical, since two clients with different server lists disagree about where keys live.

Replication on the ring

Storage systems use the ring for placement as well as routing. Amazon's Dynamo paper stores each key on the first N distinct servers clockwise from its position, its preference list, skipping extra tokens that belong to a server already in the list. With N = 3, losing one server still leaves two copies of everything it held, on servers that are its neighbors on the ring.

The same "walk clockwise and skip duplicates" idea extends to racks and zones: skip tokens until the replicas span different failure domains.

Alternatives you will meet

Jump consistent hash suits sharded storage where shards are numbered and only grow. Rendezvous hashing suits small server sets where O(N) per lookup does not matter. Hash slots trade automatic placement for explicit, operator-controlled moves, which many teams prefer for databases.

Hot keys and bounded loads

Consistent hashing balances keys, not traffic. One celebrity user or one viral product still lands on one server. Consistent hashing with bounded loads caps every server at a set percentage above the average and sends the overflow to the next server clockwise. HAProxy implements this with its hash-balance-factor setting. For truly hot keys, you still need replication of that key, request coalescing or a small local cache in front.

Operational pitfalls

• Changing the hash function or token scheme reshuffles everything, exactly like modulo hashing. Treat it as a migration.
• Membership must be consistent. Distribute the server list from one source, such as a coordination service or the load balancer's configuration, and change it in one step.
• Flapping servers cause churn. A server that fails health checks every few minutes moves its keys back and forth. Add hysteresis before removing and re-adding it.
• New servers start cold. A new cache node takes its share of requests immediately; warm it or ramp its weight up if the backend cannot absorb the misses.

The hash ring diagram

How to read it:

• The circle is the hash space. Positions increase clockwise, and the top is where the largest value wraps around to zero.
• Colored tokens are virtual nodes. Each color is one server, and each server owns several tokens spread around the ring.
• Keys sit at their hash positions, and the arrows point clockwise to the token that owns them.
• The dashed tokens belong to server D, being added. Only the keys just counterclockwise of D's tokens change owner.
• The legend and the Markdown block list the servers and the movement numbers from the simulation above.

Drawing hashing schemes clearly

• Draw the ring, not a table. The clockwise rule is visual; a lookup table hides why only some keys move.
• Color tokens by server and add a legend, instead of drawing an edge from every token to its server.
• Show a membership change. A static ring explains routing; a ring with one server joining explains the whole point of the technique.
• Put real numbers next to it: keys moved and load spread. They persuade people more than the picture.

Consistent hashing shows up across the system design posts on this blog: in the database sharding diagram for placing data, in the load balancer diagram for sticky routing, and in the caching strategies diagram for distributed caches.

Build it in Archboard

1. Sign in with Google or GitHub and create a diagram.
2. Add a large Shape from the Core pack, using the Ellipse variant, as the ring.
3. Add small Ellipse Shape nodes on the ring as tokens, colored by server: two each for servers A, B and C, and two dashed ones for the new server D.
4. Add four Redis nodes from the Data pack in a column beside the ring as the legend, colored like their tokens.
5. Add keys as Core Text labels on the ring with short arrows to their owning tokens.
6. Add a Markdown block from the Core pack with the key movement and load numbers.

The example uses 14 diagram nodes, within the Free plan.

FAQ

What problem does consistent hashing solve? It keeps most keys on the same server when servers are added or removed. With modulo hashing, changing the server count remaps almost every key; with consistent hashing, only about 1/N of keys move.

What are virtual nodes in consistent hashing? Each physical server is placed on the ring many times under different names. More positions make the arcs more even, allow weighting servers by capacity and spread a failed server's load across many others.

How many virtual nodes should each server have? Enough for an even spread at your cluster size: in our simulation, 100 per server kept the busiest server within 7% of the average across ten servers. Systems with smarter token allocation, such as Cassandra 4.0 and later, use far fewer.

Is Redis Cluster consistent hashing? Not in the ring sense. Redis Cluster maps keys to 16,384 fixed hash slots and assigns slots to nodes; moving data means moving slots explicitly.

What is the difference between consistent hashing and rendezvous hashing? Both move about 1/N of keys when membership changes. Rendezvous hashing scores every server for each key and picks the highest, which needs no ring but costs O(N) per lookup.

Start free — one seat, no credit card.