Consistent Hashing

In a traditional hash-based sharding system using shard = hash(key) % N, adding or removing a single server changes N, which causes a catastrophic reshuffling of almost all keys. If you go from 10 to 11 servers, approximately 90% of your cached data will map to a different server, causing a massive "cache stampede" to the database.

Consistent Hashing solves this elegantly. When a server is added or removed, only a tiny fraction of keys (~K/N keys, where K is total keys and N is total servers) need to be remapped.

1. How Consistent Hashing Works

The Hash Ring

1. Imagine a circular number line (a ring) ranging from 0 to some large maximum value (e.g., 0 to $2^32 - 1$).
2. Each Server is placed on this ring by hashing its identifier (e.g., IP address). position = hash("Server-A").
3. Each Data Key is also placed on this ring by hashing its value. position = hash("user:12345").
4. To determine which server stores a given key: Starting from the key's position on the ring, walk clockwise until you hit the first server. That server is responsible for storing that key.

Adding a Server

When a new Server D is added, it is placed on the ring at hash("Server-D"). Only the keys located between Server D and the previous server (counterclockwise) need to be reassigned to Server D. All other keys remain untouched.

Removing a Server

When Server B is removed, its keys are transferred to the next server clockwise on the ring. Again, only a small fraction of keys are affected.

2. Virtual Nodes (Vnodes)

A naive consistent hashing ring can suffer from uneven load distribution. If servers happen to be hashed close together on the ring, one server might be responsible for a disproportionately large arc of the ring.

Virtual Nodes solve this by creating multiple "replicas" of each physical server on the ring.

• Instead of placing Server-A at one position, place Server-A-1, Server-A-2, ..., Server-A-150 at 150 different positions on the ring.
• Because the points are distributed pseudo-randomly around the ring, the load becomes extremely well balanced.

3. Real-World Usage

Consistent Hashing is used extensively in industry:

• Amazon DynamoDB: Uses consistent hashing to distribute data across its storage nodes.
• Apache Cassandra: Uses it for partitioning data across the cluster.
• Memcached / Redis Cluster: Uses it for distributing cached data across multiple cache servers.
• Akamai CDN: Uses it to map web requests to the nearest cache server.