Consistent hashing solves a problem you have to feel to understand

Add one server to a naive hash-mod-N cache and almost every key moves. Consistent hashing exists to make "almost every" become "almost none."

medium free

1/33

You're sharding a cache across servers. How do you pick which one holds a key?

The tempting answer: hash the key, take it mod the number of servers.

Simple and even. What's wrong with it?

Nothing, until the number of servers changes.

⚠ Trap

Why would that matter? You recompute and move on.

Because the index depends on N. Change N, and almost every key maps somewhere new.

Almost every key?

Go from 4 servers to 5, and nearly the whole cache is suddenly on the wrong node.

Which means what, in practice?

Every lookup misses at once. All that traffic stampedes your database.

So adding capacity knocks you over.

The exact thing you did to grow is the thing that breaks you.

So what's the goal instead?

Add a server and move the fewest keys possible. Ideally just the ones it should own.

How do you get there?

Put the keys and the servers on the same ring. A hash space bent into a circle.

And a key belongs to?

The first server you meet going clockwise from it.

Now add a server.

It drops onto one arc and takes over only the keys in that arc. About one-Nth. The rest stay put.

        [A]
     k3   \   k1
   [C]----(ring)----[B]
     k2   /
   key -> next node clockwise ; add [D] -> only D's arc moves

That's the whole idea?

That's the load-bearing idea. It turns "remap the world" into "remap a slice."

⚠ Trap

With four servers on a big ring, won't the arcs be wildly uneven?

They will. That's the real weakness: hot spots.

So how do you even it out?

Virtual nodes. Place each server at many points around the ring, not one.

And that helps because?

Each server owns lots of small scattered arcs that average out. Give a bigger machine more points, it owns more.

Does this mean nothing ever moves?

No. It minimizes movement. Only the affected arc relocates, never the whole keyspace.

The interview line?

Hash-mod-N remaps everything when N changes. A ring moves only the neighbouring slice, and virtual nodes keep it even.

↑ answer it in your head first ↑

the mistakes this catches

Traps

⚠ Using hash(key) mod N to pick a server. Changing N remaps nearly every key, causing a cache stampede when you add or lose a node.
⚠ Forgetting node heterogeneity and hot spots. A plain ring can distribute load unevenly; virtual nodes are what fix it.
⚠ Thinking consistent hashing eliminates remapping. It minimizes it; only the keys near the changed node move, never zero.

test yourself, tap to flip

Flash drills

1 Why does hash(key) mod N fall apart when N changes? tap →

The server index depends on N, so changing the number of servers changes the result for almost every key. Adding one node remaps roughly all keys at once, triggering a stampede on the backing store.

2 How does consistent hashing limit what moves when a node joins or leaves? tap →

Keys and nodes are placed on a hash ring; a key belongs to the next node clockwise. Adding or removing a node only reassigns the keys in that node's arc, about 1/N of them, not all of them.

3 What problem do virtual nodes solve? tap →

A few real nodes placed randomly on the ring create uneven arcs and hot spots. Giving each node many virtual positions smooths the distribution and lets you weight more powerful nodes with more virtual points.

4 Does consistent hashing remove key movement entirely? tap →

No. It minimizes it. Only keys in the affected arc move; the point is to avoid remapping the whole keyspace, not to avoid all movement.

⟳ These drills come back on a spaced schedule. Review →

Spot a mistake? Flag it →