Consistent Hashing Explained: Add a Server Without Moving Everything (2026)

A cache cluster has three servers and is doing fine. Traffic grows, so the team adds a fourth. Within seconds, three out of every four requests miss the cache and fall through to the database, which was sized for a cache that worked. The dashboard turns red.

Nothing was broken. The routing rule, key mod N, simply gave a different answer for most keys the moment N changed. This lesson shows a routing rule that does not: consistent hashingconsistent hashing: a way to assign keys to servers so that adding or removing a server moves only a small share of the keys. It is one of the few system design ideas you can explain with a circle and a pencil.

The Problem With Key Mod N#

Apache Cassandra’s documentation describes the naive scheme in one sentence. In naive data hashing, you allocate keys to buckets by taking a hash of the key modulo the number of buckets, and “adding a single node might invalidate almost all of the mappings”.

For a cache that is a stampede, and for a shardedsharded: split across servers so that each server holds a different part of the data database it is a migration of most of the data. The sharding lesson measured it: N out of every N+1 keys move. Consistent hashing is built so that the number is closer to 1 out of every N+1.

The Ring#

Picture the output of a hash function as a circle. The smallest value sits at the top and the values grow clockwise until they wrap around to the top again. Now do two things:

1. Hash each server onto the circle, using its name or address.
2. Hash each key onto the same circle.

A key belongs to the first server you meet going clockwise from the key’s position. Envoy’s ring hash load balancer works exactly this way: each host is mapped onto a circle by hashing its address, and each request is routed by finding the nearest host clockwise around the ring.

A key past the last server simply wraps around to the first, which is why k6 above belongs to server A. Nobody keeps a table of key locations. Anyone who knows the servers’ positions can work out the owner.

Adding a Server#

Only the keys between B and D. Those used to belong to C, because C was the first server clockwise. Now D sits in front of them and takes them. Every other key still meets the same server first.

Removing a server is the mirror image. Its keys go to the next server clockwise, and nobody else is touched.

How much really moves?#

A simulation is more convincing than an argument. Assume ten servers, 100,000 keys, an MD5 hash, and 100 points per server on the ring. Then add an eleventh server and count the keys whose owner changed.

The ring is close to the ideal, and every moved key went to the new server. The mod N figure matches the sharding lesson’s formula, 10 out of 11.

The Catch: A Lopsided Ring#

Three evenly placed servers make a tidy circle. Real hashes are random, so real servers land at random spots, and the arcs between them differ in length. A server with a long arc owns more keys.

In the simulation, about three times the even share, while the quietest held 0.13 times. The fix is to give each server many points on the ring, called virtual nodesOne of many positions a single physical server occupies on the hash ring, each hashed from a different name such as server-1#0, server-1#1.

Many small arcs average out. Cassandra’s documentation makes the same point: with evenly spaced tokens and a small number of physical nodes, incremental scaling is difficult because there are no token selections for new nodes that leave the ring balanced, and virtual nodes let a single physical node take many positions, so one added node takes many small pieces from many neighbours.

Virtual nodes also handle machines of different sizes. Give a larger server more points and it takes a larger share.

The Whole Thing in Code#

The ring is a sorted list and a binary search. This is the code used for the simulation above:

import bisect, hashlib
 
def h(s):
    d = hashlib.md5(s.encode())
    x = d.hexdigest()[:8]
    return int(x, 16)
 
def build(servers, v=100):
    ring = sorted(
        (h(f"{s}#{i}"), s)
        for s in servers
        for i in range(v)
    )
    ps = [p for p, _ in ring]
    return ps, ring
 
def owner(ring, key):
    ps, pairs = ring
    p = h(key)
    i = bisect.bisect_left(ps, p)
    i %= len(pairs)
    return pairs[i][1]

bisect_left finds the first point at or after the key, and i %= len(pairs) is the wrap-around. That is the entire idea. Production systems add membership changes and failure handling on top.

Replicas on the Ring#

Copies of a key, called replicasreplicas: extra copies of the same data kept on other servers, go on the next servers clockwise. In Cassandra, with a replication factor of 3, you hash the key and “walk” the ring in a clockwise fashion until we encounter three distinct nodes, and those are the replicas.

Other Ways to Do It#

Ring hashing is not the only answer to “add a server without moving everything”.

Redis Cluster’s specification maps keys with CRC16(key) mod 16384 and gives each master a subset of the slots. Resharding moves slots, not an arbitrary share of keys. Envoy offers Maglev as a drop-in replacement for ring hash, with a fixed table size of 65537.

In an interview, naming the ring and virtual nodes is enough. Mentioning that Redis moves fixed slots is a bonus.

What Consistent Hashing Does Not Fix#

Try It: Walk the Ring#

Before (first clockwise):
 5 -> A    25 -> B
45 -> C    65 -> C
85 -> A    95 -> A
After adding D at 55:
45 -> D    others the same
1 of 6 keys moved

Check Yourself#

In One Picture#

Ring    servers + keys, one circle
Owner   first server clockwise
Add     moves one arc (~1/(N+1))
Skew    fix with many points each
Replica next distinct servers
Limit   hot keys still hot

Hash onto a ring, give each server many points, and only the arc next to a change moves.