Tuesday, 27 November 2007 Consistent Hashing I've bumped into consistent hashing a couple of times lately. The paper that introduced the idea ( Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web by David Karger et al) appeared ten years ago, although recently it seems the idea has quietly been finding its way into more and more services, from Amazon's Dynamo to memcached (courtesy of Last.fm ). So what is consistent hashing and why should you care? The need for consistent hashing arose from limitations experienced while running collections of caching machines - web caches, for example. If you have a collection of n cache machines then a common way of load balancing across them is to put object o in cache machine number hash(o) mod n. This works well until you add or remove cache machines (for whatever reason), for then n changes and every object is hashed to a new location.
Read full article from Tom White: Consistent Hashing
No comments:
Post a Comment