Consistent Hashing

Introduction to Consistent Hashing

When scaling a massive web application, engineers rely heavily on distributed caches (like Memcached or Redis clusters) to store frequently accessed data in RAM, bypassing the slow main database.

If you have a massive dataset of user profiles and 4 cache servers (Node 0, 1, 2, 3), how do you decide which server gets which user? The naive approach is Modulo Hashing. You take the User_ID, run it through a basic hash function, and use the modulo operator (%) against the total number of servers:

• Hash(User_ID 10) % 4 Servers = Node 2
• Hash(User_ID 11) % 4 Servers = Node 3

This works perfectly to distribute the data evenly.

The Catastrophic Failure: What happens if Node 2 crashes? You now only have 3 servers. The mathematical formula changes.

• Hash(User_ID 10) % 3 Servers = Node 1
• Hash(User_ID 11) % 3 Servers = Node 2

Because the denominator changed, every single piece of data is suddenly mapped to the wrong server. The entire cache is instantly invalidated. Millions of requests will simultaneously bypass the cache and slam into the main database, bringing the entire company offline in seconds. This is known as a Cache Stampede.

Consistent Hashing is the brilliant algorithm designed to solve this exact problem.

How Consistent Hashing Works: The Hash Ring

Instead of mapping data directly to the number of available servers, Consistent Hashing maps both the Data AND the Servers onto an abstract, circular mathematical ring (The Hash Ring).

Imagine a circle representing all possible hash values from 0 to 359 (like degrees on a compass).

1. Place the Servers: The algorithm hashes the IP addresses of the 4 cache servers and places them on the ring (e.g., Node 0 is at 0°, Node 1 is at 90°, Node 2 is at 180°, Node 3 is at 270°).
2. Place the Data: The algorithm hashes User_ID 10. Let’s say it lands at 100°.
3. The Routing Rule: To find out which server holds the data, the algorithm simply starts at the data’s location (100°) and walks clockwise around the ring until it bumps into the very first server it finds. In this case, walking clockwise from 100°, the first server is Node 2 (at 180°).

The Magic of Node Failure

What happens if Node 2 (180°) crashes? Node 2 is removed from the ring. User_ID 10 is still located at 100°. The algorithm walks clockwise. Because Node 2 is gone, it continues walking until it hits Node 3 (at 270°).

Crucially, the data assigned to Node 0 and Node 1 did not move. When a server crashes (or a new server is added) in a Consistent Hashing system, only the data residing directly next to that specific server on the ring needs to be remapped. The other 75% of the cluster is completely unaffected.

Virtual Nodes (VNodes)

There is one flaw with basic Consistent Hashing: Uneven Distribution. If you only have 3 servers, they might randomly hash close together on the ring (e.g., 10°, 20°, 30°). This means Server 1 handles almost 100% of the traffic for the rest of the 330-degree circle, while Server 2 and 3 sit idle.

To fix this, modern systems use Virtual Nodes. Instead of placing Server A on the ring once, the algorithm hashes Server A 100 different times with slight variations (A1, A2, A3…), placing 100 “Virtual Nodes” evenly around the ring. It does the same for Server B and C. This guarantees that the data load is perfectly balanced across the physical hardware.

Conclusion

Consistent Hashing is one of the most elegant and critical algorithms in modern distributed systems. By decoupling the routing logic from the absolute count of active servers, it allows massive databases (like Apache Cassandra and Amazon DynamoDB) to seamlessly add or remove hardware on the fly, auto-scaling to meet traffic demands without triggering catastrophic, system-wide data migrations.