Rendezvous hashing

Rendezvous hashing solves a general version of the distributed hash table problem: We are given a set of ${\displaystyle n}$ sites (servers or proxies, say). How can any set of clients, given an object ${\displaystyle O}$, agree on a k-subset of sites to assign to ${\displaystyle O}$? The standard version of the problem uses k = 1. Each client is to make its selection independently, but all clients must end up picking the same subset of sites. This is non-trivial if we add a minimal disruption constraint, and require that when a site fails or is removed, only objects mapping to that site need be reassigned to other sites.

The basic idea is to give each site ${\displaystyle S_{j}}$ a score (a weight) for each object ${\displaystyle O_{i}}$, and assign the object to the highest scoring site. All clients first agree on a hash function ${\displaystyle h(\cdot )}$. For object ${\displaystyle O_{i}}$, the site ${\displaystyle S_{j}}$ is defined to have weight ${\displaystyle w_{i,j}=h(O_{i},S_{j})}$. Each client independently computes these weights ${\displaystyle w_{i,1},w_{i,2}\dots w_{i,n}}$ and picks the k sites that yield the k largest hash values. The clients have thereby achieved distributed ${\displaystyle k}$-agreement.

If a site ${\displaystyle S}$ is added or removed, only the objects mapping to ${\displaystyle 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 ${\displaystyle S_{1},S_{2}\dots S_{n}}$ and the object being assigned.

HRW easily accommodates different capacities among sites. If site ${\displaystyle S_{k}}$ has twice the capacity of the other sites, we simply represent ${\displaystyle S_{k}}$ twice in the list, say, as ${\displaystyle S_{k,1},S_{k,2}}$. Clearly, twice as many objects will now map to ${\displaystyle S_{k}}$ as to the other 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. Approaching the problem naively, it might appear sufficient to treat the n sites as buckets in a hash table and hash the object name O into this table. Unfortunately, if any of the sites fails or is unreachable, the hash table size changes, forcing all objects to be remapped. This massive disruption makes such direct hashing unworkable.

Under rendezvous hashing, however, clients handle site failures by picking the site that yields the next largest weight. Remapping is required only for objects currently mapped to the failed site, and disruption is minimal.[1][2]

Rendezvous hashing has the following properties:

1. Low overhead: The hash function used is efficient, so overhead at the clients is very low.
2. Load balancing: Since the hash function is randomizing, each of the n sites is equally likely to receive the object O. Loads are uniform across the sites.
   1. Site capacity: Sites with different capacities can be represented in the site list with multiplicity in proportion to capacity. A site with twice the capacity of the other sites will be represented twice in the list, while every other site is represented once.
3. High hit rate: Since all clients agree on placing an object O into the same site S_O , each fetch or placement of O into S_O yields the maximum utility in terms of hit rate. The object O will always be found unless it is evicted by some replacement algorithm at S_O.
4. Minimal disruption: When a site fails, only the objects mapped to that site need to be remapped. Disruption is at the minimal possible level, as proved in.[1][2]
5. Distributed k-agreement: Clients can reach distributed agreement on k sites simply by selecting the top k sites in the ordering.[8]

One can enhance resiliency to failures by replicating each object O across the highest ranking r < m sites for O, choosing r based on the level of resiliency desired. The simplest strategy is to replicate only within the leaf-level cluster.

If the leaf-level site selected for O is unavailable, we select the next-ranked site for O within the same leaf-level cluster. If O has been replicated within the leaf-level cluster, we are sure to find O in the next available site in the ranked order of r sites. All objects that were held by the failed server appear in some other site in its cluster. (Another option is to go up one or more tiers in the skeleton and select an alternate from among the sibling virtual nodes at that tier. We then descend the hierarchy to the real nodes, as above.)

When a site is added to the system, it may become the winning site for some objects already assigned to other sites. Objects mapped to other clusters will never map to this new site, so we need to only consider objects held by other sites in its cluster. If the sites are caches, attempting to access an object mapped to the new site will result in a cache miss, the corresponding object will be fetched and cached, and operation returns to normal.

If sites are servers, some objects must be remapped to this newly added site. As before, objects mapped to other clusters will never map to this new site, so we need to only consider objects held by sites in its cluster. That is, we need only remap objects currently present in the m sites in this local cluster, rather than the entire set of objects in the system. New objects mapping to this site will of course be automatically assigned to it.

Rendezvous hashing (HRW) is much simpler conceptually and in practice. It also distributes objects uniformly over all sites, given a uniform hash function. Unlike consistent hashing, HRW requires no precomputing or storage of tokens. Consider k =1. An object ${\displaystyle O_{i}}$ is placed into one of ${\displaystyle n}$ sites ${\displaystyle S_{1},S_{2}\dots S_{n}}$ by computing the ${\displaystyle n}$ hash values ${\displaystyle h(O_{i},S_{j})}$ and picking the site ${\displaystyle S_{k}}$ that yields the highest hash value. If a new site ${\displaystyle S_{n+1}}$ is added, new object placements or requests will compute ${\displaystyle n+1}$ hash values, and pick the largest of these. If an object already in the system at ${\displaystyle S_{k}}$ maps to this new site ${\displaystyle S_{n+1}}$, it will be fetched afresh and cached at ${\displaystyle S_{n+1}}$. All clients will henceforth obtain it from this site, and the old cached copy at ${\displaystyle S_{k}}$ will ultimately be replaced by the local cache management algorithm. If ${\displaystyle S_{k}}$ is taken offline, its objects will be remapped uniformly to the remaining ${\displaystyle n-1}$ sites.

Variants of the HRW algorithm, such as the use of a skeleton (see below), can reduce the ${\displaystyle O(n)}$ time for object location to ${\displaystyle O(\log n)}$, at the cost of less global uniformity of placement. When ${\displaystyle n}$ is not too large, however, the ${\displaystyle O(n)}$ placement cost of basic HRW is not likely to be a problem. 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 ${\displaystyle k}$-agreement.

Rendezvous hashing is both simpler and more general than consistent hashing. Consistent hashing can be shown to be a special case of HRW by an appropriate choice of a two-place hash function. From the site identifier ${\displaystyle S}$ the simplest version of consistent hashing computes a list of token positions, e.g., ${\displaystyle t_{s}=h_{c}(S)}$ where ${\displaystyle h_{c}}$ hashes values to locations on the unit circle. Define the two place hash function ${\displaystyle h(S,O)}$ to be ${\displaystyle {\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}}$ where ${\displaystyle h_{c}(O)-t_{s}}$ denotes the distance along the unit circle from ${\displaystyle h_{c}(O)}$ to ${\displaystyle t_{s}}$ (since ${\displaystyle h_{c}(O)-t_{s}}$ has some minimal non-zero value there is no problem translating this value to a unique integer in some bounded range). This will duplicate exactly the assignment produced by consistent hashing.

It is not possible, however, to reduce HRW to consistent hashing (assuming the number of tokens per site is bounded), since HRW potentially reassigns the objects from a removed site to an unbounded number of other sites.

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.[21] However, one disadvantage of this approach is that when any node's weight is changed, or when any node is added or removed, all the load factors must be re-computed and relatively scaled. When the load factors change relative to one another, it triggers movement of keys between nodes whose weight was not changed, but whose load factor did change relative to other nodes in the system. This results in excess movement of keys.[27]

Controlled replication under scalable hashing or CRUSH[28] is an extension to RUSH[29] that improves upon rendezvous hashing by constructing a tree where a pseudo-random function (hash) is used to navigate down the tree to find which node is ultimately responsible for a given key. It permits perfect stability for adding nodes; however, it is not perfectly stable when removing or re-weighting nodes, with the excess movement of keys being proportional to the height of the tree.

The CRUSH algorithm is used by the ceph data storage system to map data objects to the nodes responsible for storing them.[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.[31] This enabled the dual benefits of perfect precision when weighting nodes, along with perfect stability, as only a minimum number of keys needed to be remapped to new nodes.

A similar logarithm-based hashing strategy is used to assign data to storage nodes in Cleversafe's data storage system, now IBM Cloud Object Storage.[27]

Python code implementing a weighted rendezvous hash:[27]

import mmh3
import math
from dataclasses import dataclass
from typing import List


def hash_to_unit_interval(s: str) -> float:
    """Hashes a string onto the unit interval (0, 1]"""
    return (mmh3.hash128(s) + 1) / 2**128


@dataclass
class Node:
    """Class representing a node that is assigned keys as part of a weighted rendezvous hash."""
    name: str
    weight: float

    def compute_weighted_score(self, key: str):
        score = hash_to_unit_interval(f"{self.name}: {key}")
        log_score = 1.0 / -math.log(score)
        return self.weight * log_score


def determine_responsible_node(nodes: list[Node], key: str):
    """Determines which node of a set of nodes of various weights is responsible for the provided key."""
    return max(
        nodes, key=lambda node: node.compute_weighted_score(key), default=None)

Example outputs of WRH:

>>> import wrh
>>> node1 = wrh.Node("node1", 100)
>>> node2 = wrh.Node("node2", 200)
>>> node3 = wrh.Node("node3", 300)
>>> str(wrh.determine_responsible_node([node1, node2, node3], "foo"))
"Node(name='node1', weight=100)"
>>> str(wrh.determine_responsible_node([node1, node2, node3], "bar"))
"Node(name='node2', weight=300)"
>>> str(wrh.determine_responsible_node([node1, node2, node3], "hello"))
"Node(name='node2', weight=300)"
>>> nodes = [node1, node2, node3]
>>> from collections import Counter
>>> responsible_nodes = [wrh.determine_responsible_node(
...     nodes, f"key: {key}").name for key in range(45_000)]
>>> print(Counter(responsible_nodes))
Counter({'node3': 22487, 'node2': 15020, 'node1': 7493})