Rendezvous hashing, also called highest random weight hashing, is an algorithm that lets independent clients agree on the same set of target servers for an object out of a larger pool, without any central coordination. It was developed by David Thaler and Chinya Ravishankar at the University of Michigan in 1996, a year before the related technique of consistent hashing appeared in the literature. The algorithm solves the problem of distributing objects across a changing pool of servers with minimal disruption: when a server is added or removed, only the objects that were assigned to that one server need to be remapped, rather than the entire dataset. It is used in systems including the load balancer at GitHub, Apache Kafka, Apache Ignite, the EventBus system at Twitter and IBM Cloud Object Storage, as well as in mobile caching, router design and database sharding.
Facts
Time Complexity
Time Complexity (category) Connections
In Field
Source Wikipedia: Rendezvous hashing
Sources
1. Wikipedia: Rendezvous hashing
Lead section
Rendezvous or highest random weight (HRW) hashing is an algorithm that allows clients to achieve distributed agreement on a set of k {\displaystyle k} options out of a possible set of n {\displaystyle n} options.
- In Field: Distributed Computing, Lead paragraph
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.