Plain hash(key) % N looks fine until you add one server — then N changes and almost every key remaps at once, and a sharded cache stampedes its database into the ground. Consistent hashing puts servers and keys on a ring and hands each key to the next server clockwise. Add or drop a server and only the keys in one arc move — about 1/N of them. Place the nodes, add one, and watch.
O(log N) lookup · ~K/N keys moved per node change · the sharding primitive
the ring
The hash output space bent into a circle — 0 and the max value meet at the top.
node
A server, placed on the ring at hash(server-id).
key → owner
A key is owned by the first node clockwise from where hash(key) lands.
virtual nodes
Each server placed at many ring points, so load evens out.
ring.js — servers, keys, and one arc that moves
Ready
Three servers sit on the ring; keys land where their hash falls and walk clockwise to the next server. Press Add node — watch how few keys change hands.
3
servers
12
keys
–
last moved
How it works
The whole idea is to break the dependency between a key's home and the number of servers. With hash(key) % N, every key's destination is a function of N, so changing N by one reshuffles nearly everything. On the ring, a key's home is the next server clockwise — which doesn't depend on N at all, only on who its immediate clockwise neighbor happens to be.
1
Place servers on the ring
Hash each server id to a point on the circle. They partition the ring into arcs, one per server.
2
Each key walks clockwise
Hash the key to a point, then walk clockwise to the first server. That server owns the whole arc behind it.
3
Adding a node splits one arc
A new server lands inside exactly one existing arc and takes over just the keys in the slice behind it. Every other arc is untouched — only ~1/N of keys move.
✓
Virtual nodes even the load
One point per server gives lumpy arcs. Placing each server at many points (vnodes) makes the arcs interleave, so load per server converges to fair.
Lookup
O(log N)
Keys moved / change
~K / N
vs hash % N
~all keys
Used in
caches, DBs, LBs
The code
# keys and nodes both hash onto the same ring [0, 2^32)class HashRing:
def __init__(self, nodes, vnodes=150):
self.ring = {} # point -> nodefor node in nodes:
for v in range(vnodes): # many points per node = even load
self.ring[hash_(f"{node}#{v}")] = node
self.points = sorted(self.ring) # sorted ring positionsdef owner(self, key):
h = hash_(key)
i = bisect_left(self.points, h) # first point clockwiseif i == len(self.points): i = 0 # wrap past the topreturn self.ring[self.points[i]]
# add a node: only keys in its new arcs move — not the whole keyspace
Quick check
1. Why does adding a server to hash(key) % N remap almost every key?
The destination is hash(key) % N. Change N and the remainder changes for almost every key, so almost everything moves — a cache-wide miss storm.
2. When you add a node to the ring, which keys move?
A new node lands inside one existing arc and takes over only the slice of keys behind it, up to its clockwise neighbor. Every other arc is untouched — about K/N keys move.
3. What problem do virtual nodes solve?
With one point per server, a few servers can randomly own large arcs. Placing each server at many points interleaves the arcs, so per-server load converges to fair.
FAQ
What is consistent hashing?
A way to map keys to servers so that adding or removing a server only moves about 1/N of keys instead of nearly all of them. Both keys and servers hash onto a ring, and each key is owned by the first server clockwise from it.
Why not just use hash(key) % N?
Because N is baked into the destination. Add or remove a server and N changes, so nearly every key gets a new bucket — a cache-wide miss storm or massive reshuffle. The ring removes that dependency on N.
What are virtual nodes?
Each physical server is placed at many ring points (often 100–200) instead of one. This interleaves the arcs so no server randomly owns a huge slice, making load converge to fair — and spreads a removed node’s keys across many others, not one neighbor.
Where is consistent hashing used?
Sharded caches (Memcached), distributed databases (Cassandra, DynamoDB, Riak), CDNs, and load balancers — anywhere you shard across a changing set of servers and want to avoid reshuffling everything on every membership change.