Consistent hashing

Here is the wiki article I like to read.

In computer science, consistent hashing is a special kind of hashing such that when a hash table is resized, only ${\displaystyle K/n}$ keys need to be remapped on average, where ${\displaystyle K}$ is the number of keys, and ${\displaystyle n}$ is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped because the mapping between the keys and the slots is defined by a modular operation.

Consistent hashing achieves some of the goals of rendezvous hashing (also called HRW Hashing), which is more general, since consistent hashing has been shown to be a special case of rendezvous hashing. Rendezvous hashing was first described in 1996, while consistent hashing appeared in 1997. The two techniques use different algorithms.

Consistent hashing maps objects to the same cache machine, as far as possible. It means when a cache machine is added, it takes its share of objects from all the other cache machines and when it is removed, its objects are shared among the remaining machines.

The main idea behind the consistent hashing algorithm is to associate each cache with one or more hash value intervals where the interval boundaries are determined by calculating the hash of each cache identifier. (The hash function used to define the intervals does not have to be the same function used to hash the cached values. Only the range of the two functions need match.) If the cache is removed its interval is taken over by a cache with an adjacent interval. All the remaining caches are unchanged.