STANDARDwalkthrough
Consistent Hashing
We have 8 Redis cache nodes handling 260K read requests per second. One node dies at 2 AM.
When N drops from 8 to 7, every key rehashes to a different node, invalidating roughly 87% of cached entries. That sends 260K requests per second directly to MySQL, a thundering herd that saturates the database in under a second.
“Without consistent hashing, we use modular hashing: key mod N.”
We chose consistent hashing (not modular hashing) because when a node dies, only K/N keys migrate to the neighbor instead of rehashing all K keys. On a ring with 8 nodes, losing one node remaps only 12.5% of keys, not 87%.
Trade-off: we accept more complex ring management and a routing layer that maintains ring state, in exchange for dramatically fewer cache invalidations during topology changes. Without virtual nodes, physical nodes map to single points on the ring, creating uneven arc sizes where one node might own 40% of the keyspace.
We assign 150-200 virtual nodes per physical node, spreading each server across many ring positions to equalize load. Implication: at 200 virtual nodes per physical server and 8 servers, the ring has 1,600 positions, making each arc roughly 0.06% of the keyspace, virtually eliminating hotspots.
Cassandra and DynamoDB both use consistent hashing as their primary partitioning strategy. What if the interviewer asks: why not just use a hash table with a backup?
Because adding or removing any node in a modular scheme reshuffles the entire keyspace, while consistent hashing limits disruption to one arc of the ring.
Formula & tradeoffs
Formula
Related concepts