Consistent Hashing

Caching.

The obvious problem with naive hashing and % modulo is rebalancing. Coz otherwise whenever a node is added or removed, it totally messes up the item - node assignment. It can be solved with consistent hashing.

In essence makes sure of two things:

1. Nodes go through the same hashing algorithm as the items.
2. Regardless of number of nodes in the system, same hash will always find the same node.

But how?? Let me explain:

Okay, take an item with the hash value 507. Will you agree if I say it’s not going to change? Obviously!! As long as you don’t change the hashing method!

Now, take a node with the name “third” and say it’s hash value is 520. Now will this change? Of course not!! It is always 520. Now imaging hashing range is between 0 to 1024 - and your job is to find a node that’s closest to the item’s hash 507.

Two more nodes show up into the system, their corresponding hashes are 100 and 650. It doesn’t matter. Our “third” node is still closer to the item we trying to map with, and thus regardless of the number of nodes in the system, an item always matches to the same node.

…

Except… it really doesn’t. At least with a small number like 1024. You need a bigger hash range, so big that another node would never insert itself near the “third” node and ruin the party for everyone.

Even after taking care of that, there will be lots of new problem… like the item distribution could not be uniform and overwhelming selected server… Well considering how interested you are, I will leave that as a homework for you ~

Consistent hashing: https://eli.thegreenplace.net/2025/consistent-hashing/