The Ring.

A map that works.

Say it plainly: you run a cache farm — 3 servers, 600 active sessions — and you must decide where each user’s data lives. The classic answer fits on a napkin: s = hash(key) mod N. It is stateless, instant, and perfectly balanced. Below is the whole farm: every dot is a live session, its color is its server.

Three healthy columns. Every server owns a third of the keyspace. Nobody is thinking about failure. Remember this moment — like the calm before a partition, this theorem has nothing to say about good days either.

Press the button.

Growth arrives. You go back to Figure 01 and press ADD A SERVER — the correct, responsible, load-balanced thing to do — and three out of four sessions vanish from the cache at once. Not because the new server is bad. Because the mod answer depends on N itself: change N and almost every key changes owners. hash(‘usr:4171’) mod 3 and mod 4 agree only by coincidence — about one time in four.

You added a computer to make things faster, and for an hour everything was slower. The bill arrived as a page at 2 a.m.: origin database on fire, hit rate in the basement.THE mod-N INCIDENT REPORT — FILED EVERYWHERE, CONSTANTLY

Every relocated key is a warm cache entry gone cold, a session that must be rebuilt, a request that lands on the backing store. Multiply by your traffic and you get a stampede. The naive map is fine right up until the exact moment you need it to change.

Bend the keyspace into a circle.

Karger’s trick is geometric. Stop thinking of the hash as a number — think of it as a position on a ring, 0° to 360°. Place each server on that same ring by hashing its name. A key belongs to the first server clockwise from it. That’s the whole algorithm.

Now adding a server doesn’t redraw the map — it inserts one point and inherits exactly one arc: the stretch of ring from its predecessor clockwise to the new point. Everyone else keeps their keys. Expected cost: about 1/(N+1) of the keyspace — a quarter, not three-quarters. Remove a server and the ring does the opposite: in this one-position model its whole arc falls to a single heir — one neighbor absorbs the load while everyone else sleeps.

But look at it honestly.

With few servers, placement is a lottery. Five servers, dropped at random — below, one of them owns half the ring. That server runs hot, thrashes its RAM, times out under load — and no dashboard will tell you why, because the map is “correct.” Randomness is fair in expectation, and you do not live in expectation.

The fix sounds like a joke and works like a charm: give every server many positions. Not one point on the ring — a hundred. The server becomes a hundred ghosts scattered around the circle, each owning many small arcs, and by the law of large numbers every share lands near 1/N. Real systems — Dynamo, Cassandra — ship with 100+ vnodes per server for exactly this reason.

One honest cost, visible in the counter when you flip to vnodes: adopting them is itself one last big rehash. After that, the ring only ever bends — servers join and leave, and the map barely ripples.

Where the ring lives.

Roughly — and each of these will happily argue with you about its placement at great length.

Dynamo & Cassandra

Examples of systems that have used virtual-node rings. Vnode counts are product and configuration choices, not a universal default; assigning more positions can weight a server’s share.

Memcached clients

The classic deployment (the “ketama” library): consistent hashing lives in the client, so servers join and leave the pool without a mass eviction.

Discord

Rendezvous hashing to bind keys to servers — same goal, no ring at all: score every server, pick the max. O(N) per lookup; ideal for small, stable pools.

Three scenarios.

From these figures, you can identify which keys move when a node joins and how replication changes that picture. Try changing one assumption and check whether your explanation still holds.