Lesson 3.5 · 15 min
Consistent hashing
Watch keys move when a server joins, see why virtual nodes fix lopsided load, and walk the ring to place replicas.
The idea in plain words
If you assign keys to servers with “key number mod server count”, adding one server reshuffles almost every key. Consistent hashing places servers and keys on a circle so a change only moves the keys next to it.
The problem it solves
To spread keys over N servers, the simple rule is server = hash(key) mod N. But when N changes, almost every key maps to a different server, so a resize moves nearly all the data or empties the whole cache.
How it works
- Picture a circle of hash values from 0 to the maximum, joined at the ends.
- Hash each server to a point on the circle.
- Hash each key to a point, then walk clockwise to the first server: that server owns the key.
- Adding a server only takes the keys between it and the previous server; removing one hands its keys to the next.
- Each server is placed at many points (virtual nodes) so the load comes out even.
Example
With 4 servers, mod N sends about 80% of keys somewhere new when you add a fifth. On the ring, only the keys in the new server’s arcs move, about 1 in 5 (20%), and every other key stays where it was.
Key terms
- Hash
- A function that turns any key into a number that looks random but is always the same for that key.
- Hash ring
- The range of hash values bent into a circle; each key belongs to the next server clockwise.
- Virtual nodes
- Each server appears at many points on the ring, so the load spreads evenly.
- Rebalancing
- Moving keys when a server is added or removed.
- N
- The number of servers; consistent hashing moves about 1/N of keys per change.
In this lesson you'll learn
- Why hash % N moves almost every key when servers change.
- How a hash ring with virtual nodes moves only about 1/N of keys.
- How replicas are placed, and how to defend a partitioning design.
Sections
- Add a server, count what moves
- Four strategies compared
- Placing replicas
- Design review
Cheat sheet
| hash % N resize | ~80% of keys move |
|---|---|
| Ring | ~1/N of keys move |
| Virtual nodes | 100–256 per server |
| Quorum | R + W > N |
| N replicas survive | ⌊(N−1)/2⌋ failures |
The interactive simulations and the scored design review load with JavaScript.