Rendezvous hashing
Rendezvous or highest random weight (HRW) hashing[1][2] is an algorithm that allows clients to achieve distributed agreement on a set of
A typical application is when clients need to agree on which sites (or proxies) objects are assigned to.
Rendezvous hashing was invented by David Thaler and Chinya Ravishankar at the University of Michigan in 1996.
[3][4][5] Rendezvous hashing was used very early on in many applications including mobile caching,[6] router design,[7] secure key establishment,[8] and sharding and distributed databases.
[9] Other examples of real-world systems that use Rendezvous Hashing include the Github load balancer,[10] the Apache Ignite distributed database,[11] the Tahoe-LAFS file store,[12] the CoBlitz large-file distribution service,[13] Apache Druid,[14] IBM's Cloud Object Store,[15] the Arvados Data Management System,[16] Apache Kafka,[17] and the Twitter EventBus pub/sub platform.
The HRW assignment can be computed independently by any client, since it depends only on the identifiers for the set of sites
Consider the simple version of the problem, with k = 1, where all clients are to agree on a single site for an object O.
Unfortunately, if any of the sites fails or is unreachable, the hash table size changes, forcing all objects to be remapped.
Remapping is required only for objects currently mapped to the failed site, and disruption is minimal.
[23][24][25] This approach creates a virtual hierarchical structure (called a "skeleton"), and achieves
Assuming 108 sites (real nodes) for convenience, we get a three-tier virtual hierarchy.
in octal (we can, of course, vary the fanout at each level - in that case, each node will be identified with the corresponding mixed-radix number).
Starting lower in the hierarchy requires more hashes, but may improve load distribution in the case of failures.
The figure shows how, if we proceed starting from the root of the skeleton, we may successively choose the virtual nodes
can be chosen based on factors like the anticipated failure rate and the degree of desired load balancing.
leads to less load skew in the event of failure at the cost of higher search overhead.
Recent examples of its use include the Github load balancer,[10] the Apache Ignite distributed database,[11] and by the Twitter EventBus pub/sub platform.
[18] Consistent hashing operates by mapping sites uniformly and randomly to points on a unit circle called tokens.
However, the tokens associated with a given site can be precomputed and stored in a sorted list, requiring only a single application of the hash function to the object, and a binary search to compute the assignment.
Variants of consistent hashing (such as Amazon's Dynamo) that use more complex logic to distribute tokens on the unit circle offer better load balancing than basic consistent hashing, reduce the overhead of adding new sites, and reduce metadata overhead and offer other benefits.
Unlike consistent hashing, HRW requires no precomputing or storage of tokens.
HRW completely avoids all the overhead and complexity associated with correctly handling multiple tokens for each site and associated metadata.
Rendezvous hashing also has the great advantage that it provides simple solutions to other important problems, such as distributed
In the standard implementation of rendezvous hashing, every node receives a statically equal proportion of the keys.
This behavior, however, is undesirable when the nodes have different capacities for processing or holding their assigned keys.
The Cache Array Routing Protocol (CARP) is a 1998 IETF draft that describes a method for computing load factors which can be multiplied by each node's hash score to yield an arbitrary level of precision for weighting nodes differently.
[30] In 2005, Christian Schindelhauer and Gunnar Schomaker described a logarithmic method for re-weighting hash scores in a way that does not require relative scaling of load factors when a node's weight changes or when nodes are added or removed.
A partial list includes Oracle's Database in-memory,[9] the GitHub load balancer,[10] the Apache Ignite distributed database,[11] the Tahoe-LAFS file store,[12] the CoBlitz large-file distribution service,[13] Apache Druid,[14] IBM's Cloud Object Store,[15] the Arvados Data Management System,[16] Apache Kafka,[17] and by the Twitter EventBus pub/sub platform.
is chosen (the original work on the HRW method makes a hash function recommendation).
Python code implementing a weighted rendezvous hash:[27] Example outputs of WRH:
