Consistent hashing | Algorender

01Why it matters

Add one cache server, lose most of your cache

A site keeps hot data in a cache spread over three servers. The simplest way to pick a server for a key is hash(key) mod 3: quick, even, and every client gets the same answer without asking anyone.

Then traffic grows and a fourth server joins. Now it's hash(key) mod 4, and a key stays on the same server only if its hash leaves the same remainder for 3 and 4. That's about 1 key in 4. The other three quarters suddenly look up the wrong server, miss, and all hit the database at once, just when the site was already busy.

Consistent hashing fixes this: when a server joins or leaves, only about $1/N$ of the keys move, and everything else keeps its home.

02Key parts

The pieces you will see

the ring: Every possible hash value, from 0 to $2^{32} - 1$ , bent round into a circle: 0 at the top, values growing clockwise, and the largest one sitting just before 0 again.
server node: A server placed on the ring at the hash of its name. Its colour marks it and the arc it owns.
the owner rule: A key belongs to the first server node clockwise from where the key hashes, wrapping round past the top.
virtual nodes: Several places on the ring for each server (A#0, A#1, …), so each server owns many small arcs instead of one big one.

03See it work

Keys find their server by walking clockwise

Twelve fruit names are stored on three servers, each with a single node. Look up a key, then add server D and watch which keys change colour.

One node per server: each server owns the arc that ends at its node.

Notice the load readout too. With one node each, the arcs are whatever lengths the hash happens to give: here C owns 60% of the ring and stores 9 of the 12 keys.

04Predict

Your turn: say where it lands

Add a few keys of your own, look some up, then add or remove a server. Before each step plays, say which server a key lands on, or how many keys a change moves.

Make 3 predictions: step forward and answer each question before the next step plays.

05Try it

Try it

Start from one node per server:

Add server D. Only 2 of the 12 keys move, all to D. The readout says mod N would have moved 8.
Remove server C. All 9 of its keys land on B, the next node clockwise, which now holds 10 of 12.
Start over with ten virtual nodes each and remove a server. Its keys scatter over the others instead of piling onto one neighbour.

Ten virtual nodes per server: many small arcs, so each server's share of the ring evens out.

06Check yourself

Check yourself

Question 1 of 6
Server nodes sit at 10%, 40% and 70% of the way round the ring. A key hashes to 50%. Which node owns it?
Your answer comes back in Review in a few days, so it sticks.
Question 2 of 6
A key hashes to 95% of the way round, and the last node is at 80%. Where does it go?
Question 3 of 6
With one node per server, three servers end up holding 9, 2 and 1 of 12 keys. What is going on?
Question 4 of 6
You go from 4 to 5 servers. With hash mod N about 80% of keys move. With consistent hashing and virtual nodes, about how many?
Question 5 of 6
Why do caches spread over servers use consistent hashing rather than hash mod N?
Question 6 of 6
A store keeps 3 copies of every key. Where does consistent hashing put them?

07Explain it back

Say it in your own words

Why does consistent hashing move so few keys when a server joins or leaves, and what are virtual nodes for?

08Recap

What to remember

Hash keys and servers onto one ring; a key belongs to the first server node clockwise, wrapping round.
A server joining or leaving only changes the arcs beside its nodes, so about $1/N$ of the keys move. With hash mod N, most of them do.
One node per server gives lopsided arcs; virtual nodes even out the load and spread a leaving server's keys.
To keep copies, walk on past the owner to the next distinct servers. Memcached clients, Cassandra, Riak and CDNs all work this way.