Consistent Hashing Explained & Visualized

What is Consistent Hashing?

Consistent hashing is a technique used in distributed systems (like caches, databases, and load balancers) to assign data or requests to nodes (servers). Its primary goal is to minimize disruption when nodes are added or removed from the system.

The Problem with Simple Hashing (Modulo N)

Imagine you have N servers and you want to distribute keys (e.g., user IDs, cache keys) among them. A simple approach is:

server_index = hash(key) % N

This works initially, but what happens when you add or remove a server?

• Adding a server: N becomes N+1. The result of the modulo operation changes for almost all keys. This means nearly all your data needs to be moved, causing massive disruption (e.g., cache invalidation storm).
• Removing a server: N becomes N-1. Again, the modulo result changes for most keys, leading to similar disruption.

How Consistent Hashing Solves It

Consistent hashing uses a different approach:

1. Imagine a Ring: Think of a conceptual ring or circle representing a large range of hash values (e.g., 0 to 2³²-1, or 0-359 degrees in our visualization).
2. Place Servers on the Ring: Hash each server's identifier (like its IP address or name) to get a position on this ring. Place the server at that point.
3. Place Keys on the Ring: Hash each data key to get its position on the same ring.
4. Assign Keys to Servers: To find which server should handle a key, start at the key's position on the ring and move clockwise until you encounter the first server. That server is responsible for the key.

The Key Benefit: Minimal Re-mapping

• Adding a Server (S4): When a new server S4 is added, it gets hashed to a position on the ring. Only the keys located between S4's new position and the next server clockwise (previously handled by that next server) need to be remapped to S4. Most other keys remain untouched.
• Removing a Server (S2): When S2 is removed, the keys it was responsible for (those between its predecessor S1 and S2) now simply continue clockwise and map to the *next* available server (S3). Only S2's keys are affected.

Virtual Nodes (Replicas)

A potential issue is uneven distribution. If servers happen to hash close together, one might get a disproportionately large segment of the ring. To fix this, we use virtual nodes (or replicas):

• Instead of placing each physical server once on the ring, we place it multiple times (e.g., 3, 100, or more times).
• We do this by hashing variations of the server name (e.g., serverA-1, serverA-2, serverA-3...).
• This breaks the ring into many smaller segments, leading to a much more balanced distribution of keys across the physical servers, even with few physical servers.
• When a key lands in a segment owned by a virtual node (e.g., serverA-2), it's ultimately handled by the corresponding physical server (serverA).