Consistent hashing: how to add servers without moving everything
Plain hash-mod-N remaps almost every key when you add a server. Consistent hashing moves only a small share. Here is how the ring works.
Suppose you spread cache keys over N servers with server = hash(key) mod N. It works until N changes. Go from 4 servers to 5 and most keys map to a different server, so the cache looks empty and your database takes the hit.
The idea
Consistent hashing places both servers and keys on a circle (a hash ring), for example the range 0 to 2^32.
- Hash each server name to a point on the ring.
- Hash each key to a point on the ring.
- A key belongs to the first server found moving clockwise from its point.
Why it helps
- Add a server: it takes over only the keys between itself and its counter-clockwise neighbour. On average only about 1/N of the keys move.
- Remove a server: only its keys move, to the next server clockwise. The rest are untouched.
Virtual nodes
With only a few points, servers get uneven slices of the ring. The fix is virtual nodes: each physical server appears at many points (for example 100 to 200) on the ring. This evens out load, and a stronger server can simply get more virtual nodes.
Replication on the ring
To keep copies, store each key on the next several distinct servers clockwise. Dynamo-style databases do this.
Where it is used
Distributed caches, sharded databases, CDNs and load balancers that need sticky routing, and systems such as Cassandra and DynamoDB.
Limits
It balances well on average but a very hot key still overloads its server. Replicating hot keys or splitting them helps.
Takeaway: use consistent hashing whenever the set of servers changes and you cannot afford to reshuffle all data.
Part 10 of 15 in the System Design series. Previous: Database replication: leader-follower, lag and failover.
