Rendezvous hashing

Rendezvous or highest random weight (HRW) hashing is an algorithm that allows clients to achieve distributed agreement on a set of k options out of a possible set of n options. A typical application is when clients need to agree on which sites (or proxies) objects are assigned to. When k is 1, it subsumes the goals of consistent hashing, using an entirely different method.

Rendezvous hashing was invented in 1996 by David Thaler and Chinya Ravishankar at the University of Michigan. Consistent hashing appears to have been devised around the same time at MIT. One of the first applications of rendezvous hashing was to enable multicast clients on the Internet (in contexts such as the MBONE) to identify multicast rendezvous points in a distributed fashion. It was used in 1998 by Microsoft's (CARP) for distributed cache coordination and routing. Some routing protocols use rendezvous hashing to pick a rendezvous point.

Given its simplicity and generality, rendezvous hashing has been applied in a wide variety of applications, including mobile caching, router design, secure key establishment, and sharding and distributed databases.

Rendezvous hashing solves the distributed hash table problem: How can a set of clients, given an object O, agree on where in a set of n sites (servers, say) to place O? Each client is to select a site independently, but all clients must end up picking the same site. This is non-trivial if we add a minimal disruption constraint, and require that only objects mapping to a removed site may be reassigned to other sites.

The basic idea is to give each site S_j a score (a weight) for each object O_i, and assign the object to the highest scoring site. All clients first agree on a hash function h(). For object O_i, the site S_j is defined to have weight w_i,j = h(O_i, S_j). HRW assigns O_i to the site S_m whose weight w_i,m is the largest. Since h() is agreed upon, each client can independently compute the weights w_i,1, w_i,2, ..., w_i,n and pick the largest. If the goal is distributed k-agreement, the clients can independently pick the sites with the k largest hash values.

If a site S is added or removed, only the objects mapping to S are remapped to different sites, satisfying the minimal disruption constraint above. The HRW assignment can be computed independently by any client, since it depends only on the identifiers for the set of sites S₁, S₂, ..., S_n and the object being assigned.

...
Wikipedia