Consistent hashing

In computer science, consistent hashing is a special kind of hashing technique such that when a hash table is resized, only ${\displaystyle n/m}$ keys need to be remapped on average where ${\displaystyle n}$ is the number of keys and ${\displaystyle m}$ is the number of slots. Consistent hashing evenly distributes cache keys across shards, even if some of the shards crash or become unavailable. 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 is used by Content Delivery Networks because it is useful for distributing requests for content from a rotating population of web servers. Tim Berners-Lee credits consistent hashing algorithms, and Daniel Lewin as their inventor, with solving the slashdotting problem which plagued the World Wide Web in the 1990s.

The term "consistent hashing" was introduced by David Karger et al. at MIT for use in distributed caching, particularly for the web. This academic paper from 1997 in Symposium on Theory of Computing introduced the term "consistent hashing" as a way of distributing requests among a changing population of web servers. Each slot is then represented by a server in a distributed system or cluster. The addition of a server and the removal of a server (during scalability or outage) requires only ${\displaystyle num\_keys/num\_slots}$ items to be re-shuffled when the number of slots (i.e. servers) change. The authors mention linear hashing and its ability to handle sequential server addition and removal, while consistent hashing allows servers to be added and removed in an arbitrary order. The paper was later re-purposed to address technical challenge of keeping track of a file in peer-to-peer networks such as a distributed hash table.

Teradata used this technique in their distributed database^{[citation needed]}, released in 1986, although they did not use this term. Teradata still uses the concept of a hash table to fulfill exactly this purpose. Akamai Technologies was founded in 1998 by the scientists Daniel Lewin and F. Thomson Leighton (co-authors of the article coining "consistent hashing"). In Akamai's content delivery network, consistent hashing is used to balance the load within a cluster of servers, while a stable marriage algorithm is used to balance load across clusters.

Consistent hashing has also been used to reduce the impact of partial system failures in large web applications to provide robust caching without incurring the system-wide fallout of a failure. Consistent hashing is also the cornerstone of distributed hash tables (DHTs), which employ hash values to partition a keyspace across a distributed set of nodes, then construct an overlay network of connected nodes that provide efficient node retrieval by key.

Rendezvous hashing, designed in 1996, is a simpler and more general technique ^{[citation needed]}. It achieves the goals of consistent hashing using the very different highest random weight (HRW) algorithm.

In the problem of load balancing, for example, when a BLOB has to be assigned to one of ${\displaystyle n}$ servers on a cluster, a standard hash function could be used in such a way that we calculate the hash value for that BLOB, assuming the resultant value of the hash is ${\displaystyle \beta }$, we perform modular operation with the number of servers (${\displaystyle n}$ in this case) to determine the server in which we can place the BLOB: ${\displaystyle \zeta =\beta \ \%\ n}$; hence the BLOB will be placed in the server whose ${\displaystyle {\text{server ID}}}$ is successor of ${\displaystyle \zeta }$ in this case. However, when a server is added or removed during outage or scaling (when ${\displaystyle n}$ changes), all the BLOBs in every server should be reassigned and moved due to rehashing, but this operation is expensive.

Consistent hashing was designed to avoid the problem of having to reassign every BLOB when a server is added or removed throughout the cluster. The central idea is to use a hash function that maps both the BLOB and servers to a unit circle, usually ${\displaystyle 2\pi }$ radians. For example, ${\displaystyle \zeta =\Phi \ \%\ 360}$ (where ${\displaystyle \Phi }$ is hash of a BLOB or server's identifier, like IP address or UUID). Each BLOB is then assigned to the next server that appears on the circle in clockwise order. Usually, binary search algorithm or linear search is used to find a "spot" or server to place that particular BLOB in ${\displaystyle O(\log N)}$ or ${\displaystyle O(N)}$ complexities respectively; and in every iteration, which happens in clockwise manner, an operation ${\displaystyle \zeta \ \leq \ \Psi }$ (where ${\displaystyle \Psi }$ is the value of the server within the cluster) is performed to find the server to place the BLOB. This provides an even distribution of BLOBs to servers. But, more importantly, if a server fails and is removed from the circle, only the BLOBs that were mapped to the failed server need to be reassigned to the next server in clockwise order. Likewise, if a new server is added, it is added to the unit circle, and only the BLOBs mapped to that server need to be reassigned.