Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not significantly change the mapping of keys to slots. In Computer science, a hash table, or a hash map, is a Data structure that associates keys with values. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped. By using consistent hashing, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots.
Consistent hashing was introduced in 1997 as a way of distributing requests among a changing population of web servers. Year 1997 ( MCMXCVII) was a Common year starting on Wednesday (link will display full 1997 Gregorian calendar Each slot is then represented by a node in a distributed system. The addition (joins) and removal (leaves/failures) of nodes only requires K/n items to be re-shuffled when the number of slots/nodes change. More recently it has been used to reduce the impact of partial system failures in large web applications as to allow for robust caches without incurring the systemwide fallout of a failure [1][2] [3].
However, the most significant application of consistent hashing has been to form the foundation of distributed hash tables (DHTs). Distributed hash tables ( DHTs) are a class of decentralized distributed systems that provide a lookup service similar to a Hash table: ( name, DHTs use consistent hashing to partition a keyspace among a distributed set of nodes, and additionally provide an overlay network which connects nodes such that the node responsible for any key can be efficiently located.
References
- David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. Frank Thomson ("Tom" Leighton is a Professor of Applied Mathematics at the Massachusetts Institute of Technology. Daniel "Danny" Mark Lewin ( דניאל (דני) מארק לוין; May 14, 1970 &ndash September 11 2001) was a Consistent Hashing and Random Trees: Tools for Relieving Hot Spots on the World Wide Web. STOC 1997.
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic