Consistent hashing

The problem with hash % N

The obvious way to spread keys over N servers is hash(key) % N. It works until N changes. Go from 4 to 5 servers and almost every key maps somewhere new, which for a cache means a sudden flood of misses, and for a database means moving almost all the data.

The ring

Consistent hashing puts both servers and keys on a circle (the hash space wrapped around). Each key belongs to the first server clockwise from it. Add a server and it only takes keys from its clockwise neighbour; remove one and only its keys move to the next server. On average just 1/N of the keys move.

Try it

Add and remove servers. Keys that move get bigger. Compare with how many keys hash % N would move.

Virtual nodes

With one point per server, the arcs between servers are uneven, so some servers own far more keys. The fix is to place each server at many points on the ring (virtual nodes). Load evens out, and when a server leaves, its keys spread across many servers instead of piling onto one neighbour. Turn on virtual nodes above to see it.

Where it's used

• Distributed caches (spreading keys across Memcached or Redis nodes).
• Leaderless databases like Cassandra and DynamoDB for partitioning data.
• Load balancers that need the same client to keep hitting the same server.