# Rendezvous Hashing Lookup

# Rendezvous Hashing Lookup

Rendezvous hashing, also called highest random weight hashing, maps a key to the node with the highest score for that key. Each candidate node is scored together with the key, and the node with the maximum score is selected.

You use it in distributed systems when keys must be assigned to changing sets of nodes with minimal movement and no shared hash ring.

## Problem

Given a set of nodes $N$ and a key $k$, choose the node responsible for $k$.

## Model

For every node $v \in N$, compute a score:

$$
s(v, k) = h(v, k)
$$

The selected node is:

$$
\operatorname*{argmax}_{v \in N} s(v, k)
$$

The hash function should distribute scores uniformly.

## Algorithm

```text id="ftvqdo"
rendezvous_lookup(nodes, k):
    best_node = null
    best_score = -infinity

    for each node in nodes:
        score = h(node, k)
        if score > best_score:
            best_score = score
            best_node = node

    return best_node
```

## Example

Suppose the nodes are:

$$
N = {A, B, C}
$$

For key `"user:42"`, assume the scores are:

| node | score |
| ---- | ----: |
| A    |    18 |
| B    |    73 |
| C    |    41 |

The highest score is 73, so the key maps to node B.

If node B is removed, the key moves to the remaining node with the next highest score, which is C in this example.

## Correctness

The algorithm computes the score for every candidate node and keeps the maximum. Therefore it returns exactly the node defined by the rendezvous hashing rule.

When a node is added or removed, only keys for which that node wins or previously won need to move. Other keys keep the same winner.

## Complexity

| operation | time   |
| --------- | ------ |
| lookup    | $O(n)$ |

The lookup scans all nodes. Optimized variants reduce this cost for large node sets.

## Space

$$
O(1)
$$

Lookup uses only the current best node and score, aside from the node list itself.

## When to Use

Rendezvous hashing is appropriate when:

* nodes change over time
* key movement should be minimal
* implementation simplicity matters
* each client can know the node list
* weighted node assignment may be needed

It is common in distributed caches, sharded storage, request routing, and replicated systems.

## Implementation

```python id="6mjvqh"
import hashlib

def score(node, key):
    data = f"{node}:{key}".encode()
    digest = hashlib.blake2b(data, digest_size=8).digest()
    return int.from_bytes(digest, "big")

def rendezvous_lookup(nodes, key):
    best_node = None
    best_score = -1

    for node in nodes:
        s = score(node, key)
        if s > best_score:
            best_score = s
            best_node = node

    return best_node
```

```go id="ul94kc"
import (
	"encoding/binary"
	"hash/fnv"
)

func rendezvousScore(node string, key string) uint64 {
	h := fnv.New64a()
	h.Write([]byte(node))
	h.Write([]byte{0})
	h.Write([]byte(key))
	return binary.BigEndian.Uint64(h.Sum(nil))
}

func RendezvousLookup(nodes []string, key string) string {
	bestNode := ""
	var bestScore uint64

	for i, node := range nodes {
		score := rendezvousScore(node, key)
		if i == 0 || score > bestScore {
			bestScore = score
			bestNode = node
		}
	}

	return bestNode
}
```