The Cache Invalidation Catastrophe
Suppose you have 10 cache servers and you use a simple modulo hash to route requests: server = hash(request_key) % 10. This works perfectly until you add an 11th server. Now the formula becomes % 11, and almost every key maps to a different server than before. Effectively, your entire cache is invalidated simultaneously. Every request misses the cache and hits your database. Your database falls over. This is called the Thundering Herd problem.
Consistent Hashing solves this. The algorithm works by imagining all possible hash values arranged in a circle (called a hash ring):
- Each server is placed at one or more points on the ring (its hash value).
- Each incoming request is hashed to a point on the ring.
- The request is routed to the first server clockwise from its hash point.
- When you add a new server, it takes over only the requests that hash to the arc between it and its predecessor. All other requests are unaffected.
In practice, adding one server to a 10-server pool remaps approximately 1/11 of requests (about 9%) instead of nearly 100%. Your cache stays warm. Your database survives.
Virtual nodes (vnodes) are a refinement: instead of placing each server at one point on the ring, you place it at many points (e.g., 150 virtual positions). This prevents the uneven distribution that can occur when servers happen to cluster on one side of the ring.
Maglev Hashing, developed by Google for their production load balancers, is a further optimization. It builds a large lookup table (e.g., 65,537 entries) where each entry maps to a backend server. The table is constructed so that lookups are O(1) (constant time), the distribution is near-perfectly uniform, and adding or removing a server disrupts the minimum possible number of entries. Maglev is used in Google's front-end infrastructure and has been adopted in projects like Cilium (a Kubernetes networking layer) for its combination of speed and minimal disruption.