The Full Wiki

More info on Consistent hashing

Consistent hashing: Wikis

Advertisements
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

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 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.

Contents

History

Consistent hashing was introduced in 1997 as a way of distributing requests among a changing population of web servers. 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 system wide fallout of a failure [1] [2].

More recently, consistent hashing has been applied in the design of distributed hash tables (DHTs). 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.

Technique

Consistent hashing is based on mapping items to a real angle (or equivalently a point on the edge of a circle). Slots correspond to angle ranges. Slots can be added or removed by either slightly readjusting all the angle ranges or just a subset of them (with the condition that every angle is assigned to one slot).

References

  1. ^ Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. (1997). "Consistent hashing and random trees". Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA. pp. 654–663. doi:10.1145/258533.258660. http://portal.acm.org/citation.cfm?id=258660. Retrieved 2008-06-17.  
  2. ^ Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). "Web caching with consistent hashing". Computer Networks 31 (11): 1203–1213. doi:10.1016/S1389-1286(99)00055-9. http://www8.org/w8-papers/2a-webserver/caching/paper2.html. Retrieved 2008-06-17.  

External links

Advertisements

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message