Scenario: The Session Cache Scaling Crisis
A startup has built a high-speed caching service to store active user sessions. Initially, the backend uses a standard in-memory Hash Map (dictionary) to store and retrieve the session tokens in $O(1)$ time.
Q:Under the hood, the Hash Map is backed by a simple array of size $N$. When a session token (a string) arrives, how does the system map it to a specific index, and what happens if two tokens map to the exact same index? Reveal ▾
The system passes the string through a hashing algorithm (like MurmurHash) to generate a large integer, then applies a modulo operator against the array size: $index = hash(token) \pmod N$.
If two distinct tokens map to the same index, a Hash Collision occurs. The map typically resolves this using Separate Chaining (storing a Linked List at that index) or Open Addressing (probing forward to find the next available empty slot).
Q:As traffic grows, the array becomes 100% full. If the collision resolution is Separate Chaining, the map doesn't technically crash, but what happens to the performance? Reveal ▾
The performance degrades from $O(1)$ to $O(K)$, where $K$ is the length of the linked list at a given bucket. In the worst-case scenario where all keys hash to the same bucket, the Hash Map devolves into a simple Linked List, drastically increasing CPU cycles required to traverse the chain during lookups.
To prevent this, Hash Maps track a “Load Factor” (e.g., 0.75). When it reaches 75% capacity, the map allocates a new, larger array (usually double the size) and entirely rehashes and redistributes all existing keys—an expensive $O(N)$ operation.
Q:The engineering team decides to scale horizontally. Instead of one large map on one server, they deploy 5 caching servers. They route traffic using $server\_index = hash(token) \pmod 5$. This works perfectly until they add a 6th server to handle increased load. What goes wrong? Reveal ▾
Adding the 6th server triggers a catastrophic cache invalidation event. Because the modulo denominator changes from 5 to 6, the calculation $hash(token) \pmod 6$ will yield a completely different server index for nearly every single existing key.
The load balancer will route requests for existing sessions to the wrong servers, resulting in massive cache misses. This forces the application to query the primary database to rebuild the sessions, potentially causing a Thundering Herd problem that crashes the primary database.
Q:How do you re-architect the hashing mechanism so that adding or removing a server only affects a tiny fraction of the cached data, rather than invalidating the entire cluster? Reveal ▾
You implement Consistent Hashing.
Instead of a modulo array, the hash space is treated as a continuous circular ring (e.g., from $0$ to $2^{32}-1$). Both the servers (by hashing their IP/ID) and the data keys are mapped onto this same ring. To find which server holds a key, the algorithm hashes the key, finds its position on the ring, and moves clockwise until it encounters the first server.
When a new server is added to the ring, it only takes over the keys that fall between its position and the preceding server. The rest of the ring remains entirely unaffected, meaning $\frac{1}{N}$ keys are remapped, minimizing the cache miss penalty.
Q:In a basic Consistent Hashing ring with 6 servers, the distribution of keys is rarely perfectly even. One server might handle 40% of the traffic while another handles 5%. How do you enforce a uniform load distribution? Reveal ▾
You introduce Virtual Nodes (VNodes). Instead of mapping each physical server to a single point on the ring, you apply multiple hash functions to the server’s ID to map it to hundreds of pseudo-random points across the ring.
Server A might be represented by $A_1, A_2, \dots, A_{100}$. Because the virtual nodes are statistically scattered throughout the hash space, the segments they control average out, resulting in a highly uniform distribution of the data load. If a server is physically more powerful, it can simply be assigned more virtual nodes.
Variations & Real-World Impact
- Content Delivery Networks (CDNs): Edge providers like Cloudflare use distributed Hash Tables with virtual nodes extensively. When an edge server fails, consistent hashing ensures that traffic is gracefully shunted to the next available clockwise node without requiring a global cache flush.
- Database Sharding: NoSQL databases like Cassandra and DynamoDB rely on consistent hashing for partitioning data across clusters. The use of Virtual Nodes allows these databases to dynamically stream partitions to newly provisioned nodes in the background without downtime.
Discussion & Comments