Adding one server to a cache cluster shouldn't invalidate 90% of your cache. Consistent hashing is why it doesn't, and the math is simpler than you think.
Imagine you have a cache cluster of 10 Redis nodes. Your key routing is key % 10. You get a traffic spike and add an 11th node. Suddenly key % 11 routes almost every key to a different node than before. Your entire cache is cold. This is the classic cache stampede that has taken down production systems. Consistent hashing was designed specifically to eliminate this problem.
Consistent hashing maps both servers and keys onto the same circular ring. Imagine a clock face representing the range 0 to 2^32. Each server is hashed to a position on the ring. Each key is also hashed to a position on the ring. The rule is simple: a key is owned by the first server clockwise from its position on the ring. To find which server owns a key, hash the key, walk clockwise until you hit a server.
When you add an 11th server, it lands at some position on the ring. Only the keys between the new server and its anticlockwise neighbor need to move. They now belong to the new server instead of the neighbor. Every other key is unaffected. In a 10-server cluster, adding one server moves approximately 1/11 of the keys (~9%), instead of ~90% with modular hashing. The cache stays mostly warm.
With one point per server on the ring, the distribution is not uniform. Hash functions produce pseudo-random output, and 10 random points on a circle divide it into 10 arcs of wildly different sizes. The server that 'owns' a large arc handles far more keys than one owning a small arc. That's uneven load. If you remove a server, all its load shifts to a single neighbor (the next clockwise), potentially overloading it.
The fix is virtual nodes: instead of placing each server at one position on the ring, you place it at many positions, typically 100-300 in production systems. Dynamo uses ~100 virtual nodes per physical node; Cassandra historically uses 256. Each position is hashed independently (server_id + '_' + i). With many virtual nodes per server, the load distributes evenly because each server owns many small arcs spread across the ring rather than one large arc. When a server fails or is removed, its load spreads across all other servers (each neighbor takes a few virtual nodes' worth of traffic), not one unlucky neighbor.
Consistent hashing is used in Amazon DynamoDB, Apache Cassandra, Memcached (libketama), Redis Cluster (which uses hash slots, a variant of the same idea), and almost every distributed cache or NoSQL store. It's also used in distributed rate limiters (route a user's requests to a consistent shard so their counter lives in one place) and in load balancers that need sticky routing for stateful sessions. The key insight is reusable: any time you need to distribute keys across a changing set of nodes, consistent hashing gives you a formula that minimises disruption on every topology change.