Consistent hashing

  • Lesson 14 of 40
  • 10 min
  • Intermediate
  • 10 steps

With hash(key) % N, changing N shuffles almost everything. On a ring, each change touches a single arc and the rest of the data stays put.

Live servers
4
Keys that move
—
Largest share
30%
Server AServer ACache AServer AServer BServer BCache BServer BServer CServer CCache CServer CServer DServer DCache DServer DServer EServer ECache EServer Ekey k1key k2B#2D#2A#2From 4 to 5 servershash(k) % 4 → % 5~80 % moveideal~20 % (1/5)ring · 0 … 2^32 − 1clockwisek1 → Ak2 → CShare per server (example)A22 %B24 %C30 %D24 %total100 %newk2 now → E18 % of the keysdownits keys go on to D54 % of the keysWithout C (example)A22 %B24 %D24 % + 30 % = 54 %B#2D#2A#2Two positions per server (example)A33 %B32 %D35 %total100 %key k1copy 1copy 2copy 3empty on arrivalMisses going from 4 to 5 cacheshash(k) % N~80 %consistent hashing18 %18 %: E’s arc in the example; 1/5 on averagek1 → Ak2 → C
  • request
  • batch
  • cache miss

Step 1 of 10

Problem

hash % N breaks when N changes

Last lesson spread keys with server = hash(key) % N. As long as N stays the same, every key has a fixed home and the load is even: 25 % per server with 4.

Going to 5 servers changes the answer for 4 keys out of 5. A key only stays where it was when h % 4 and h % 5 agree, and that happens for 4 values in every 20. 80 % of the data would have to travel.

Step 2 of 10

Technique

Close the hash space into a circle

A 32-bit hash returns numbers between 0 and 2^32 − 1. Glue the end to the start and that range becomes a ring: after the highest value comes 0 again.

Now run each server’s name through the same hash and put it at the point it lands on. They are not evenly spaced: each one sits wherever its hash says.

What changed

  • Hash ring
  • Each server at position hash(name)

Step 3 of 10

Technique

Every key moves clockwise

Keys go through the hash too and land on the ring. Their owner is the first server you meet going clockwise. k1 lands between D and A, so it belongs to A; k2 lands between B and C, so it belongs to C.

Each server keeps the arc that ends at it. In this example the arcs differ in length and C’s is the longest: 30 % of the ring.

What changed

  • Keys k1 and k2 on the ring
  • Each key belongs to the next server clockwise

Step 4 of 10

Solution

A new server takes a single arc

E joins the ring between B and C. From then on, keys in the arc from B to E no longer go on to C: they stop at E. That is what happens to k2.

Only those keys change owner, 18 % in this example, and all of them come from C. A, B and D never notice.

What changed

  • Server E
  • 18 % of the keys move from C to E
  • Everything else stays

Step 5 of 10

Technique

When a server fails, one arc moves too

Back to the original four servers, and now C goes down. Its keys keep moving clockwise until they reach D. No other server changes.

With % N, going from 4 to 3 servers would move 3 keys out of 4. Here only C’s 30 % moves.

What changed

  • Server C
  • C’s keys, 30 %, move to D

Step 6 of 10

Problem

Random positions, uneven arcs

Since every server lands wherever its hash says, the arcs are not the same length. Without C, D inherits its arc and ends up with 54 % of the keys: more than twice what A or B hold.

With few servers, chance alone is enough for one of them to carry far more work than the rest.

What changed

  • D holds 54 % of the keys

Step 7 of 10

Solution

Several positions per server

Instead of one position, every server gets several: hash «A#1», «A#2» and so on. Each one is a virtual node. Here every server has two and owns several short arcs instead of one long one.

The shares even out: the largest drops from 54 % to 35 % in this example. And when a server leaves, its arcs are split among several neighbours instead of landing on just one.

What changed

  • Two positions per server
  • Largest share: 54 % → 35 %

Step 8 of 10

Technique

Copies on the next servers

One copy per key is not enough: if its server goes down, the data is gone. So every key is stored on the first three distinct servers it meets going clockwise: its owner and the next two.

To keep the drawing readable we go back to one position per server. k1 is stored on A (copy 1), B (copy 2) and C (copy 3). If A fails, B and C still have it.

What changed

  • Every key on 3 servers
  • Survives up to two failures without losing the key

Step 9 of 10

Concept

Case: growing a group of caches

A group of cache servers answers reads before the database. If clients pick a server with hash(key) % N, going from 4 to 5 changes the target of ~80 % of the keys: nearly all of them miss at once and those reads land on the database.

With consistent hashing, the fifth cache only gets its arc: 18 % of the keys in this example. Those miss until E fills up; the rest keep hitting.

What changed

  • Fifth cache, E
  • Misses after the change: ~80 % → 18 %

Step 10 of 10

Summary

Consistent hashing in short

Servers and keys share one hash ring; each key belongs to the first server clockwise.

Adding or removing a server moves a single arc: about 1/N of the keys.

Virtual nodes even out the shares and spread the load when a server leaves.

Store every key on the next distinct servers along the ring to get replicas.

You will learn

  • See why hash % N moves almost every key
  • Place servers and keys on a hash ring
  • Know which keys move when a server joins or leaves
  • Even out the load with virtual nodes
  • Keep replicas on the next servers along the ring