The Problem With Naive Hashing
When you have 4 servers and need to distribute keys, the obvious approach is: server = hash(key) % number_of_servers
This works perfectly — until you add or remove a server. When number_of_servers changes from 4 to 5, almost every key maps to a different server. In a cache, that means a near-total cache miss storm.
The Ring
Consistent hashing solves this by mapping both servers and keys onto a circular ring of hash values from 0 to 2³²-1. To find which server owns a key, you hash the key and walk clockwise until you hit a server.
What Happens When a Server Dies
Only the keys that were owned by the dead server need to move. Every other key stays exactly where it is. This is the core insight: O(K/N) keys move instead of O(K) keys.
Where It's Used
- DynamoDB — consistent hashing across storage nodes
- Cassandra — token ring is consistent hashing
- Nginx — consistent hashing upstream module