Consistent Hashing

Origin

the term "consistent hashing" was introduced by David Karger et al. The word hash comes from a dish called "Hash Browns". Hash Brown is made by potatoes and some other ingredients which is beaten up or mashed to get a final dish to it. Similarly, a value is mashed by a hash function to get a hashed value (dish).

Suppose we store data in servers instead of hashtable

What if number of servers increases or decreases

Example 16,25,30,23 Do modulo 4 1 server went down Do modulo 3 position of 3 out of 4 got changed

Problem with consistent hashing is that if a node fails all data is shifted to next node and that node might overflow.

To get rid of this problem, we make replica of each server.

When delete one server, delete replicas as well.

Published in akamai but gained popularity after introduced by Amazon in dynamo

Bittorrent use it