Consistent Hashing

The Problem: Distributing Data Across Many Servers

You have 1 billion key-value pairs and 4 servers. You need to decide which server stores which key. The simplest idea: hash the key and use modulo.

server_index = hash(key) % number_of_servers

This works. Keys spread evenly. Lookups are O(1). Done.

Now add a fifth server. The number of servers changes from 4 to 5. The modulo result changes for almost every key. Roughly 80% of your data has to be moved to a different server. The system grinds to a halt as it shuffles billions of records.

Remove a server (because it crashed)? Same disaster in reverse.

This is the problem consistent hashing solves. It changes how keys map to servers so that adding or removing one server only requires moving 1/N of the data, not 80%.

The Core Idea: Hash Onto a Ring

Instead of mapping keys to a small number of server slots, map both keys AND servers to positions on a giant circle. The circle represents the full output space of a hash function (e.g., 0 to 2³² - 1).

To find which server owns a key:

1. Hash the key. Place it on the ring.
2. Walk clockwise around the ring.
3. The first server you encounter owns this key.

Adding a Server: Only 1/N Keys Move

Now add Server E. It hashes to a position on the ring. Only the keys that were "between" the previous server and E now belong to E. Every other key stays where it was.

If you have 4 servers and add a 5th, on average 1/5 of the keys move. The other 4/5 stay put. This is the killer property: minimal data movement when topology changes.

Same logic on removal. If Server B dies, its keys go to the next clockwise server (C). All other keys are unaffected.

The Imbalance Problem

One issue: if you only have 4 servers placed randomly on a ring, the gaps between them are uneven. Some servers end up owning huge slices of the keyspace, others tiny ones. Hot servers, cold servers.

The Fix: Virtual Nodes

Instead of placing each server once on the ring, place it many times, with different hash positions. A real server might be represented by 100, 200, or 1000 "virtual nodes" scattered around the ring.

With many virtual nodes per real server, the law of averages kicks in. Each server ends up owning roughly the same total slice of the ring, even though individual virtual nodes are random.

Bonus benefit: heterogeneous servers. A more powerful server can have 400 virtual nodes while a weaker one has only 100, naturally directing more traffic to the powerful one.

Where Consistent Hashing Is Used

Distributed caches: Memcached and Redis cluster mode use consistent hashing to spread cache entries across nodes.
NoSQL databases: Cassandra, DynamoDB, and Riak use it to distribute data partitions.
CDNs: deciding which edge server caches which asset.
Load balancers: sticky sessions where the same user reliably hits the same server.
Sharded services: any system that needs to deterministically map a key to a host.

The One Thing to Remember

Consistent hashing turns "adding a server breaks everything" into "adding a server moves 1/N of the data." That single property is what makes horizontal scaling practical for caches, databases, and load balancers. Place items on a ring, walk clockwise to find the owner, and use virtual nodes to keep the load balanced. Once you understand it, you'll spot it everywhere in distributed systems.