Learning Hub

How to Build Rendezvous Hashing in Python and Keep Caches Warm When Nodes Come and Go

Build rendezvous (highest random weight) hashing in Python, measure how few keys move when a node leaves, then add replicas, weights, a cache-hit simulation and a constant-time table, backed by 20...

November 3, 2026 39 Min Read
26

Every system that spreads work over several servers keeps asking one small question: which server should handle this key? A cache fleet asks it for every cached page, a sharded database for every row, and a load balancer for every connection. A fleet of language-model servers asks it for every conversation, because the server that already holds a conversation’s KV cache (the attention data it computed for the earlier turns) can answer the next turn faster than a server starting cold. The vLLM documentation puts the idea this way: Automatic Prefix Caching “caches the KV cache of existing queries, so that a new query can directly reuse the KV cache if it shares the same prefix with one of the existing queries, allowing the new query to skip the computation of the shared part.”

Table Of Content

The hard part is not picking a server. It is picking the same server every time, from many machines that never talk to each other, while servers join and leave. The obvious method, hash(key) % number_of_servers, breaks that promise the moment the number changes. In the first measurement below, removing one server out of ten sends about 90 percent of all keys to a different server, and every one of those keys starts with a cold cache.

This tutorial teaches a different method called rendezvous hashing, also known as highest random weight (HRW) hashing. Its rule fits in one sentence: give every server a score for the key, and send the key to the server with the highest score. Wikipedia’s article credits David Thaler and Chinya Ravishankar of the University of Michigan with inventing it in 1996, in the technical report A Name-Based Mapping Scheme for Rendezvous, and says that it is “much simpler conceptually and in practice” than consistent hashing and that, “Unlike consistent hashing, HRW requires no precomputing or storage of tokens.” If you read our walkthrough of consistent hashing with a hash ring, this is the other major answer to the same question, and you will measure the two side by side.

You will write rendezvous hashing from scratch in about 20 lines of standard-library Python, measure what it does when servers come and go, and then extend it step by step: replica lists for failover, weights for servers of different sizes, a cache simulation for a fleet of eight replicas, and a precomputed table for constant-time lookups. You will finish with a 20-test suite and a check that ten deliberately planted bugs all get caught. By the end you will be able to:

  • explain why hash(key) % N reshuffles almost every key, and measure it;
  • build rendezvous hashing and show that removing a node moves only that node’s keys;
  • avoid two traps in the hash itself (Python’s salted hash() and ambiguous concatenation);
  • produce replica lists whose failover target is the node that was already the second choice;
  • weight nodes correctly, and see why the tempting formula gives the wrong shares;
  • simulate cache hit rates for five routing strategies when a replica leaves and another joins;
  • choose between rendezvous hashing, a hash ring, and a precomputed table.

Everything below was run on Python 3.13.14 and pytest 9.2.0 on Windows 11 on November 3, 2026. Every output block is copied from those runs. Timing numbers will differ on your machine, so compare the ratios, not the digits.

The terms used in this tutorial

  • Key. The thing you want to route: a user ID, a cache key, a conversation ID.
  • Node. A server, cache instance, database shard or model replica that can hold keys. The code identifies each node by a stable name such as node-03.
  • Owner. The node a key is sent to.
  • Hash function. A function that turns text into a number, giving the same number for the same text every time. Rendezvous hashing needs one that behaves like a fair lottery: every score is equally likely and unrelated to the others.
  • Score. The number the hash gives for one (key, node) pair. The highest score wins.
  • Ranking and replicas. Sorting every node by score gives a ranking. The first node is the owner and the next ones are the replicas, the nodes that would take over in order.
  • Cache hit and miss. A hit means the node already had the data. A miss means it had to compute or fetch it. LRU (least recently used) is the common rule for a full cache: throw away whatever was used longest ago.
  • Virtual node (vnode). A hash-ring term: one physical node placed at many points on the ring so that it gets a fair share. Rendezvous hashing does not need them.

Prerequisites

  • Python 3.13 (the version I tested; the code uses only the standard library). Where I write python, use python3 if that is your command name.
  • pytest 9.2.0 for the tests. Nothing else is installed.
  • Any operating system. I used Windows 11; the commands for Linux and macOS are shown where they differ.
  • Comfort reading Python functions, lists, dictionaries and comprehensions. No distributed-systems background is assumed.
  • About an hour. The scripts themselves run in seconds.

Step 0: Create the project folder

Put everything in one folder with its own virtual environment, so nothing touches your system Python.

mkdir rendezvous-lab
cd rendezvous-lab
python -m venv .venv
.venv\Scripts\activate
python -m pip install pytest==9.2.0
python -m pytest --version

On Linux or macOS, replace the activation line with source .venv/bin/activate. The last command should print pytest 9.2.0. If it does, you are ready. Every file below goes into this folder, and every command is run from it.

Step 1: See the problem with hash % N

The idea

Suppose you have 10 cache servers and 100,000 keys. The simplest routing rule is: hash the key to a number, divide by the number of servers, and use the remainder as the index into the server list. It is perfectly even and needs no state. Its flaw shows up when the list changes length, because the remainder of a number divided by 9 has nothing to do with its remainder when divided by 10.

The code

Save this as step01_modn.py. It uses hashlib.blake2b to turn text into a stable 64-bit number (Step 4 explains why it is not Python’s built-in hash()), then counts how many keys change servers when node-03 leaves and when a new node-10 joins.

"""step01_modn.py: how many keys change servers when one server leaves, if the server is chosen by hash % N?"""
import hashlib

KEYS = [f"key-{i}" for i in range(100_000)]
NODES = [f"node-{i:02d}" for i in range(10)]


def stable_hash(text):
    """The same 64-bit number in every process (Step 4 explains why the built-in hash() is not used)."""
    return int.from_bytes(hashlib.blake2b(text.encode("utf-8"), digest_size=8).digest(), "big")


def mod_n_owner(key, nodes):
    return nodes[stable_hash(key) % len(nodes)]


def moved(before_nodes, after_nodes):
    return sum(mod_n_owner(k, before_nodes) != mod_n_owner(k, after_nodes) for k in KEYS)


left = [n for n in NODES if n != "node-03"]
more = NODES + ["node-10"]
leave, join = moved(NODES, left), moved(NODES, more)
print("100,000 keys on 10 nodes, each key sent to nodes[hash(key) % N]")
print(f"node-03 leaves (10 -> 9 nodes):  {leave:,} keys change server ({leave / len(KEYS):.1%})")
print(f"node-10 joins  (10 -> 11 nodes): {join:,} keys change server ({join / len(KEYS):.1%})")

Run it

python step01_modn.py
100,000 keys on 10 nodes, each key sent to nodes[hash(key) % N]
node-03 leaves (10 -> 9 nodes):  90,123 keys change server (90.1%)
node-10 joins  (10 -> 11 nodes): 90,931 keys change server (90.9%)

What the output tells you

Removing one server in ten moved 90,123 of 100,000 keys, or 90.1 percent, and adding an eleventh moved 90.9 percent. Nine keys in ten land on a server whose cache does not have them. For a cache that means a wall of misses hitting your database at once; for model replicas it means almost every conversation loses its warm KV cache. The ideal answer is far smaller: a leaving server should only give up the keys it owned, about one in ten.

Step 2: Build rendezvous hashing in 20 lines

The idea

Rendezvous hashing replaces the divide-and-take-the-remainder step with a small tournament that runs separately for every key. Each node enters with a score computed from the key and the node’s own name. The highest score wins and that node owns the key. Because a node’s score for a key does not depend on which other nodes exist, removing a node can only change the tournaments that node won, and adding a node can only change the tournaments the newcomer wins. Every other key keeps its winner, which is exactly the stability that hash % N lacks. The algorithm needs no ring, no table and no coordination: any client with the same list of node names computes the same answer.

The code

Save this as rendezvous.py. It has three functions: _hash64 turns text into a stable 64-bit number, score hashes one (key, node) pair, and pick returns the node with the highest score.

# rendezvous.py
"""Rendezvous (highest random weight) hashing: every node scores every key and the best score wins."""
import hashlib


def _hash64(text: str) -> int:
    """A stable 64-bit number for a string. Do not swap in the built-in hash(): Python salts it in every process."""
    digest = hashlib.blake2b(text.encode("utf-8"), digest_size=8).digest()
    return int.from_bytes(digest, "big")


def score(key: str, node: str) -> int:
    """The score of one (key, node) pair. The NUL byte keeps node 'a' + key 'bc' apart from node 'ab' + key 'c'."""
    return _hash64(f"{node}\x00{key}")


def pick(key: str, nodes) -> str:
    """Return the node with the highest score. A tie (practically impossible) goes to the larger node name."""
    if not nodes:
        raise ValueError("no nodes to pick from")
    return max(nodes, key=lambda node: (score(key, node), node))

Three details worth understanding

Before you move on, make sure these three are clear:

  • digest_size=8 asks BLAKE2b for an 8-byte (64-bit) digest, and int.from_bytes(..., "big") turns those bytes into an integer. A 64-bit score makes ties astronomically unlikely.
  • The max key is a pair, (score, node). Python compares pairs left to right, so the node name only matters when two scores are exactly equal. That cannot be allowed to depend on the order of the list, so ties go to the larger name on every client.
  • The \x00 inside the f-string is a NUL character used as a separator. Step 4 shows what goes wrong without it.

Run a worked example

Save this as step02_first_pick.py. It prints the five scores for one key, removes the winner, and then shows what happens to ten other keys when that same node is removed.

"""step02_first_pick.py: score one key against five nodes, then remove the winner and see who takes over."""
from rendezvous import pick, score

NODES = ["cache-a", "cache-b", "cache-c", "cache-d", "cache-e"]
KEY = "user-42"

print(f"scores for key {KEY!r} (higher wins):")
for node in NODES:
    print(f"  {node}  {score(KEY, node):016x}")
winner = pick(KEY, NODES)
print(f"winner: {winner}")

by_score = sorted(NODES, key=lambda node: score(KEY, node), reverse=True)
survivors = [n for n in NODES if n != winner]
print(f"after removing {winner}: {pick(KEY, survivors)} (second-highest score: {by_score[1]})")
print()
print("what happens to ten other keys when the same node is removed:")
print(f"{'key':<9} {'before':<9} {'after':<9}".rstrip())
for i in range(40, 50):
    key = f"user-{i}"
    before, after = pick(key, NODES), pick(key, survivors)
    print(f"{key:<9} {before:<9} {after:<9} {'<- moved' if before != after else ''}".rstrip())
python step02_first_pick.py
scores for key 'user-42' (higher wins):
  cache-a  3f58b35a89a9e958
  cache-b  7aaf4d5588246133
  cache-c  c82ead9cc646898c
  cache-d  df00970c6aa5e2b9
  cache-e  990a9ed364f9feaf
winner: cache-d
after removing cache-d: cache-c (second-highest score: cache-c)

what happens to ten other keys when the same node is removed:
key       before    after
user-40   cache-a   cache-a
user-41   cache-d   cache-b   <- moved
user-42   cache-d   cache-c   <- moved
user-43   cache-d   cache-a   <- moved
user-44   cache-e   cache-e
user-45   cache-c   cache-c
user-46   cache-c   cache-c
user-47   cache-d   cache-b   <- moved
user-48   cache-b   cache-b
user-49   cache-d   cache-b   <- moved

What the output tells you

For user-42 the highest of the five scores belongs to cache-d, so cache-d owns the key. When cache-d is removed, the key moves to cache-c, which is exactly the node with the second-highest score. Now look at the ten-key table. Five keys (user-41, user-42, user-43, user-47 and user-49) were owned by cache-d and all five moved, spreading over three different survivors. The other five were owned by other nodes and did not move at all. That is the whole idea: a node’s departure only disturbs the keys it owned.

Step 3: Measure what moves when a node leaves or joins

The idea

One example is not a measurement. Here you will compare three strategies on 100,000 keys: hash % N, a consistent-hash ring with 100 virtual nodes per server, and rendezvous hashing. A ring places each server at many pseudo-random points on a circle of hash values and sends a key to the first point clockwise from the key’s own hash; our consistent hashing tutorial builds one step by step. A tiny version is enough for a fair comparison.

The code

Save the ring as ring.py. It sorts every node’s virtual points once and answers each lookup with a binary search.

# ring.py
"""A small consistent-hash ring with virtual nodes. It is here only to compare against rendezvous hashing."""
import bisect

from rendezvous import _hash64


class Ring:
    def __init__(self, nodes, vnodes: int = 100):
        points = sorted((_hash64(f"{node}#{v}"), node) for node in nodes for v in range(vnodes))
        self._hashes = [h for h, _ in points]
        self._owners = [node for _, node in points]

    def pick(self, key: str) -> str:
        index = bisect.bisect_right(self._hashes, _hash64(key)) % len(self._hashes)
        return self._owners[index]

Now save step03_movement.py. For each strategy it records who owns every key before and after the change. A move counts as needless when the membership change did not force it: a key whose old owner is still alive, or a key that moved to a node other than the newcomer.

"""step03_movement.py: which keys move when a node leaves or joins? hash % N, a hash ring and rendezvous hashing."""
from rendezvous import _hash64, pick
from ring import Ring

KEYS = [f"key-{i}" for i in range(100_000)]
NODES = [f"node-{i:02d}" for i in range(10)]


def make_mod_n(nodes):
    return lambda key: nodes[_hash64(key) % len(nodes)]


def make_ring(nodes):
    return Ring(nodes, vnodes=100).pick


def make_rendezvous(nodes):
    return lambda key: pick(key, nodes)


STRATEGIES = {"hash % N": make_mod_n, "ring, 100 vnodes": make_ring, "rendezvous": make_rendezvous}


def report(title, after_nodes, needless):
    """needless(old, new) is True for a move that the membership change did not force."""
    print(title)
    print(f"{'strategy':<18}{'moved keys':>11}{'share':>8}{'needless moves':>16}")
    for name, make in STRATEGIES.items():
        old_owner, new_owner = make(NODES), make(after_nodes)
        moves = [(old_owner(k), new_owner(k)) for k in KEYS]
        moved = [(old, new) for old, new in moves if old != new]
        extra = sum(needless(old, new) for old, new in moved)
        print(f"{name:<18}{len(moved):>11,}{len(moved) / len(KEYS):>8.1%}{extra:>16,}")
    print()


report("node-03 leaves (10 -> 9 nodes)", [n for n in NODES if n != "node-03"], lambda old, new: old != "node-03")
report("node-10 joins (10 -> 11 nodes)", NODES + ["node-10"], lambda old, new: new != "node-10")
python step03_movement.py
node-03 leaves (10 -> 9 nodes)
strategy           moved keys   share  needless moves
hash % N               90,123   90.1%          80,107
ring, 100 vnodes        9,146    9.1%               0
rendezvous             10,107   10.1%               0

node-10 joins (10 -> 11 nodes)
strategy           moved keys   share  needless moves
hash % N               90,931   90.9%          81,828
ring, 100 vnodes        8,955    9.0%               0
rendezvous              9,141    9.1%               0

What the output tells you

Both the ring and rendezvous hashing move only what they must. When node-03 leaves, 9,146 keys move on the ring and 10,107 with rendezvous hashing, and in both cases not a single key moves between surviving nodes (0 needless moves). With hash % N the same event moves 90,123 keys, of which 80,107 were on servers that never left. When node-10 joins, the ideal share for the newcomer is one eleventh, or 9.1 percent, and rendezvous hashing gives 9.1 percent while the ring gives 9.0 percent.

So minimal movement is not what separates the ring from rendezvous hashing; both have it. The ring moved a little less than ten percent here simply because node-03 happened to own 9.1 percent of the ring. That hints at the real difference, balance, which is the next measurement.

Step 4: Avoid two traps in the hash itself

Trap 1: Python’s built-in hash() is different in every process

It is tempting to write hash(key + node) and be done. Do not. The Python documentation says that “Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.” (see the __hash__ documentation). Python salts string hashes on purpose, to defend dictionaries against attackers who pick colliding keys. For routing, that means two client processes, or one client before and after a restart, would disagree about who owns a key. Setting PYTHONHASHSEED can pin it (“PYTHONHASHSEED allows you to set a fixed value for the hash seed secret.”), but that only works for Python clients, and the value comes from the interpreter rather than from a portable definition that other languages and versions are bound to reproduce, which makes it a fragile basis for a routing function. Use a hash with a fixed definition instead, such as BLAKE2b from hashlib.

Trap 2: concatenation can be ambiguous

If you build the hashed text as node + key with nothing between them, then node cache-1 with key 1x and node cache-11 with key x both produce the text cache-11x, so they receive the same score. The two pairs have nothing to do with each other, so they should not be correlated. Putting a NUL character between node and key fixes it, as long as node names and keys never contain one. The same family of bug is the subject of our article on Trail of Bits’ SequenceHash.

Prove both traps

Save step04_hash_trap.py. It starts eight fresh Python processes, asks each for the built-in hash and for pick of the same key, and then checks the separator.

"""step04_hash_trap.py: the built-in hash() disagrees between processes, a stable hash does not."""
import os
import subprocess
import sys
from pathlib import Path

from rendezvous import _hash64, score

HERE = Path(__file__).parent
CODE = (
    "from rendezvous import pick\n"
    "nodes = [f'node-{i:02d}' for i in range(10)]\n"
    "print(hash('user-42') % 10, pick('user-42', nodes))\n"
)


def run_once(hash_seed=None):
    env = {k: v for k, v in os.environ.items() if k != "PYTHONHASHSEED"}
    if hash_seed is not None:
        env["PYTHONHASHSEED"] = hash_seed
    done = subprocess.run([sys.executable, "-c", CODE], cwd=HERE, env=env, capture_output=True, text=True, check=True)
    builtin, rendezvous = done.stdout.split()
    return builtin, rendezvous


random_runs = [run_once() for _ in range(8)]
seeded_runs = [run_once("0") for _ in range(8)]
print("=== the built-in hash() across processes")
print("8 fresh Python processes, key 'user-42', 10 nodes")
print(f"hash('user-42') % 10 is the same in every process: {len({b for b, _ in random_runs}) == 1}")
print(f"pick('user-42', nodes) is the same in every process: {len({r for _, r in random_runs}) == 1} ({random_runs[0][1]})")
print(f"with PYTHONHASHSEED=0 the built-in hash agrees too: {len({b for b, _ in seeded_runs}) == 1}")

print()
print("=== why score() puts a separator between the node and the key")
pair_a, pair_b = ("cache-1", "1x"), ("cache-11", "x")
print(f"without a separator both pairs hash the text 'cache-11x': {_hash64(pair_a[0] + pair_a[1]) == _hash64(pair_b[0] + pair_b[1])}")
print(f"with score() the two pairs get different scores: {score(pair_a[1], pair_a[0]) != score(pair_b[1], pair_b[0])}")
python step04_hash_trap.py
8 fresh Python processes, key 'user-42', 10 nodes
hash('user-42') % 10 is the same in every process: False
pick('user-42', nodes) is the same in every process: True (node-04)
with PYTHONHASHSEED=0 the built-in hash agrees too: True
without a separator both pairs hash the text 'cache-11x': True
with score() the two pairs get different scores: True

The built-in hash gave different answers across the eight processes, while pick answered node-04 in all of them, and with PYTHONHASHSEED=0 the built-in hash finally agreed. The second block confirms the separator: without it, the two unrelated pairs hash identical text; with score() they differ. (The chance that all eight random-seed runs agree by luck is about one in ten million, so the first line of that block is safe to print as False.)

Step 5: Check how evenly the keys spread

The idea

A routing function should give every node about the same share of keys. We will measure spread: the standard deviation of the per-node key counts divided by their mean, as a percentage. Zero would be perfectly even. Even a perfectly random assignment cannot reach zero, because chance alone makes some nodes luckier than others, so the script also prints that floor, labelled pure chance.

The code

Save step05_balance.py. It sends 200,000 keys to 10 nodes with rings of 1, 10, 100 and 1000 virtual nodes and with rendezvous hashing.

"""step05_balance.py: how evenly do rings with 1, 10, 100 and 1000 virtual nodes and rendezvous hashing spread 200,000 keys?"""
import math
import statistics
from collections import Counter

from rendezvous import pick
from ring import Ring

KEYS = [f"key-{i}" for i in range(200_000)]
NODES = [f"node-{i:02d}" for i in range(10)]


def summarize(name, owners):
    counts = Counter(owners)
    loads = [counts[node] for node in NODES]
    mean = statistics.fmean(loads)
    spread = statistics.pstdev(loads) / mean * 100
    print(f"{name:<20}{max(loads) / mean:>8.3f}x{min(loads) / mean:>9.3f}x{spread:>9.2f}%")


print(f"{'strategy':<20}{'busiest':>9}{'quietest':>10}{'spread':>10}")
for vnodes in (1, 10, 100, 1000):
    ring = Ring(NODES, vnodes=vnodes)
    summarize(f"ring, {vnodes} vnodes", [ring.pick(key) for key in KEYS])
summarize("rendezvous", [pick(key, NODES) for key in KEYS])
ideal = math.sqrt((1 - 1 / len(NODES)) / (len(KEYS) / len(NODES))) * 100
print(f"{'pure chance':<20}{'':>9}{'':>10}{ideal:>9.2f}%")
python step05_balance.py
strategy              busiest  quietest    spread
ring, 1 vnodes         4.071x    0.019x   121.66%
ring, 10 vnodes        1.653x    0.555x    30.88%
ring, 100 vnodes       1.186x    0.862x    11.03%
ring, 1000 vnodes      1.054x    0.916x     4.13%
rendezvous             1.019x    0.991x     0.78%
pure chance                                 0.67%

What the output tells you

A ring needs many virtual nodes to even itself out: with one point per node the busiest node got 4.07 times its fair share and the quietest got 0.02 times; at 100 points the spread is still 11.03 percent; at 1000 points it is 4.13 percent. Rendezvous hashing has a spread of 0.78 percent, only about a tenth of a percentage point above the 0.67 percent that pure chance gives, and it needed no tuning knob at all. There is nothing to configure because each key runs its own fair lottery among all the nodes. Wikipedia makes the same point: rendezvous hashing “distributes objects uniformly over all sites, given a uniform hash function.”

That evenness has a price. Every lookup scores every node, so the cost grows linearly with the number of nodes. Step 9 measures it and shows how a precomputed table removes it.

Step 6: Add replicas and failover

The idea

Sorting all nodes by score instead of taking only the maximum gives a ranking for each key, and the ranking has a lovely property: the ranking never depends on which other nodes exist, only on the nodes’ own scores. So when a node leaves, the new ranking is the old ranking with that node deleted. The second choice becomes the owner, the third becomes the second, and nothing else is reshuffled. If you keep two copies of each key on the top two nodes, then when the owner dies, the node that takes over is the one that already holds a copy.

GitHub’s load balancer relies on exactly this ordering. In its GLB Director write-up the engineers explain: “Relative order will be maintained because the hash for each server will be the same regardless of which other servers are included.” They take the best two nodes for each slot: “We take the first two as the primary and secondary respectively.”

The code

Append these two functions to rendezvous.py. ranked returns all nodes best first, using the same pair of (score, name) as pick, so that pick(key, nodes) is always ranked(key, nodes)[0]. replicas returns the first few.

# rendezvous.py (continued)
def ranked(key: str, nodes) -> list[str]:
    """Every node, best first: the owner, then its replicas in the order they would take over."""
    return sorted(nodes, key=lambda node: (score(key, node), node), reverse=True)


def replicas(key: str, nodes, count: int) -> list[str]:
    """The first `count` nodes of the ranking."""
    return ranked(key, nodes)[:count]

Save step06_replicas.py. It fails node-03 in a 10-node cluster that keeps two copies of each of 50,000 keys and checks three claims.

"""step06_replicas.py: the node that takes over a key is the node that was already its second choice."""
from rendezvous import ranked

KEYS = [f"key-{i}" for i in range(50_000)]
NODES = [f"node-{i:02d}" for i in range(10)]
GONE = "node-03"
LEFT = [n for n in NODES if n != GONE]

owned = took_over_by_second = 0
in_pair = pair_fixed_by_third = 0
outside_pair = pair_unchanged = 0
for key in KEYS:
    before = ranked(key, NODES)
    after = ranked(key, LEFT)
    if before[0] == GONE:
        owned += 1
        took_over_by_second += after[0] == before[1]
    if GONE in before[:2]:
        in_pair += 1
        pair_fixed_by_third += after[:2] == [n for n in before[:3] if n != GONE]
    else:
        outside_pair += 1
        pair_unchanged += after[:2] == before[:2]

print(f"{GONE} fails. 50,000 keys, 2 copies of each key on the two best-ranked nodes.")
print(f"keys owned by {GONE}:               {owned:>6,}   new owner was the old second choice: {took_over_by_second:,}")
print(f"keys with a copy on {GONE}:         {in_pair:>6,}   new pair = old pair minus {GONE} plus the old third: {pair_fixed_by_third:,}")
print(f"keys with no copy on {GONE}:        {outside_pair:>6,}   pair unchanged: {pair_unchanged:,}")
print(f"copies that must be re-created:     {in_pair:>6,}   ({in_pair / len(KEYS):.1%} of keys)")
python step06_replicas.py
node-03 fails. 50,000 keys, 2 copies of each key on the two best-ranked nodes.
keys owned by node-03:                4,991   new owner was the old second choice: 4,991
keys with a copy on node-03:          9,957   new pair = old pair minus node-03 plus the old third: 9,957
keys with no copy on node-03:        40,043   pair unchanged: 40,043
copies that must be re-created:      9,957   (19.9% of keys)

What the output tells you

All 4,991 keys that node-03 owned were taken over by the node that had been their second choice. For the 9,957 keys that had a copy on node-03 (19.9 percent of all keys, twice the owner share because every key has two copies), the new pair was exactly the old pair minus node-03 plus the old third choice. And the 40,043 keys with no copy on node-03 did not change at all. The only work left after a failure is to re-create the 9,957 lost copies on the new second choices, a number you can compute in advance and that no other keys have to share.

The same ordering gives you failover without removing anything. If a node is merely unreachable for a minute, skip it and use the next node in ranked. Every client that skips the same node picks the same substitute, and when the node returns the keys go home. That is attractive for caches, where two clients briefly disagreeing about who is up costs a miss rather than corrupt data.

Step 7: Give bigger nodes more keys with weights

The idea

Real fleets are not uniform. One server has twice the memory of another, and you want it to hold about twice the keys. The tempting fix is to multiply each score by the node’s weight. It does not work, and the measurement below shows how badly. The correct trick turns the hash into a fair race.

Take the hash as a uniform random number u strictly between 0 and 1. Then -ln(u) is a random waiting time (statisticians call it exponentially distributed, with an average of 1). Divide the waiting time by the node’s weight, and a heavy node tends to finish sooner: its waiting time has an average of 1/weight. The node that finishes first wins, and a standard fact about such races says that node i wins with probability weight_i / total weight. Taking the first to finish is the same as taking the highest of -weight / ln(u), which is the score used below. Ceph’s CRUSH placement code uses the same construction for its straw2 buckets; the source comment above its draw function reads “Compute exponential random variable using inversion method.”

The code

Save this as weighted.py. unit builds the number u from 52 bits of the hash; the reason for 52 is in the last measurement of this step.

# weighted.py
"""Weighted rendezvous hashing: a node with twice the weight wins twice as many keys."""
import math

from rendezvous import score


def unit(key: str, node: str) -> float:
    """A number strictly between 0 and 1 for this pair, built from 52 bits of the hash so the float is exact."""
    return ((score(key, node) >> 12) + 0.5) / 2**52


def weighted_score(key: str, node: str, weight: float) -> float:
    """Higher wins. Dividing by ln(u) turns a uniform number into an exponential race that heavy nodes win more often."""
    return -weight / math.log(unit(key, node))


def pick_weighted(key: str, weights: dict[str, float]) -> str:
    """Pick a node in proportion to its weight. A weight of 0 drains the node; a negative weight is an error."""
    if any(weight < 0 for weight in weights.values()):
        raise ValueError("weights cannot be negative")
    live = {node: weight for node, weight in weights.items() if weight > 0}
    if not live:
        raise ValueError("no node has a positive weight")
    return max(live, key=lambda node: (weighted_score(key, node, live[node]), node))

Save step07_weights.py in three parts, appending each part to the same file. The first compares the naive formula with the correct one on four nodes with weights 1, 2, 3 and 4, whose wanted shares are 10, 20, 30 and 40 percent, and also rewrites the race the way Ceph does.

"""step07_weights.py: weighted rendezvous hashing, the wrong way to weight, and the edges of the unit interval."""
import math
from collections import Counter

import weighted
from weighted import pick_weighted, unit

WEIGHTS = {"small": 1, "medium": 2, "large": 3, "xlarge": 4}
KEYS = [f"key-{i}" for i in range(100_000)]
TOTAL = sum(WEIGHTS.values())


def naive_pick(key, weights):
    """The tempting version: multiply the weight by a uniform number and take the biggest."""
    return max(weights, key=lambda node: (weights[node] * unit(key, node), node))


def shares(chooser, weights):
    counts = Counter(chooser(key, weights) for key in KEYS)
    return {node: counts[node] / len(KEYS) for node in weights}


print("=== shares of 100,000 keys")
naive, proper = shares(naive_pick, WEIGHTS), shares(pick_weighted, WEIGHTS)
print(f"{'node':<8}{'weight':>7}{'wanted':>8}{'weight*u':>10}{'-w/ln(u)':>10}")
for node, weight in WEIGHTS.items():
    print(f"{node:<8}{weight:>7}{weight / TOTAL:>8.1%}{naive[node]:>10.1%}{proper[node]:>10.1%}")

print()
print("=== the same race written the way Ceph writes it")


def straw2_pick(key, weights):
    """Ceph's straw2 keeps the node with the highest ln(u) / weight."""
    return max(weights, key=lambda node: (math.log(unit(key, node)) / weights[node], node))


agree = sum(straw2_pick(key, WEIGHTS) == pick_weighted(key, WEIGHTS) for key in KEYS)
print(f"ln(u) / weight picks the same node as -weight / ln(u) for {agree:,} of {len(KEYS):,} keys")
python step07_weights.py
node     weight  wanted  weight*u  -w/ln(u)
small         1   10.0%      1.1%     10.1%
medium        2   20.0%     10.6%     19.9%
large         3   30.0%     31.7%     30.1%
xlarge        4   40.0%     56.6%     39.9%

Multiplying the weight by a uniform number gave the smallest node 1.1 percent instead of 10, and the largest 56.6 percent instead of 40. The race formula landed within 0.1 percentage point of every wanted share (10.1, 19.9, 30.1 and 39.9). The multiplication fails because a weight-4 node’s scores spread evenly over 0 to 4 while a weight-1 node’s spread over 0 to 1. Whenever the big node draws above 3 it wins outright, and the smallest node can only win when every other node happens to draw very low.

ln(u) / weight picks the same node as -weight / ln(u) for 100,000 of 100,000 keys

Ceph’s straw2 code keeps the node with the highest ln(u) / weight. Since ln(u) is negative, this is the same ranking as the smallest -ln(u) / weight, and the output confirms that it picks the same node as -weight / ln(u) for all 100,000 keys.

Append the second part, which checks what happens when you change weights, as you do when you add capacity or drain a node.

# step07_weights.py (continued)
print()
print("=== raise large from 3 to 6")
heavier = {**WEIGHTS, "large": 6}
moves = [(pick_weighted(k, WEIGHTS), pick_weighted(k, heavier)) for k in KEYS]
moved = [(a, b) for a, b in moves if a != b]
to_large = sum(b == "large" for _, b in moved)
print(f"keys that moved: {len(moved):,} ({len(moved) / len(KEYS):.1%}); moved into large: {to_large:,}; moved between other nodes: {len(moved) - to_large}")
print("new shares:", ", ".join(f"{n} {s:.1%}" for n, s in shares(pick_weighted, heavier).items()))

print()
print("=== drain small by setting its weight to 0")
drained = {**WEIGHTS, "small": 0}
print("new shares:", ", ".join(f"{n} {s:.1%}" for n, s in shares(pick_weighted, drained).items()))
keys that moved: 16,154 (16.2%); moved into large: 16,154; moved between other nodes: 0
new shares: small 7.7%, medium 15.3%, large 46.2%, xlarge 30.8%
new shares: small 0.0%, medium 22.2%, large 33.3%, xlarge 44.5%

Raising large from 3 to 6 moved 16,154 keys (16.2 percent) and every one of them moved into large; no key moved between the other nodes. That is the weighted version of the minimal-movement guarantee, because the other nodes’ scores did not change. The new shares (7.7, 15.3, 46.2 and 30.8 percent) match the new wanted shares of 1, 2, 6 and 4 parts out of 13. A weight of 0 drains a node: small now gets 0.0 percent and its keys spread over the others in proportion to their weights (22.2, 33.3 and 44.5 percent).

Why unit() uses 52 bits

The race divides by ln(u), so u must never be exactly 0 or exactly 1: ln(0) is undefined and ln(1) is 0, which would divide by zero. The obvious construction, hash / 2**64, produces both extremes. A Python float carries 53 bits of precision, so the largest 64-bit hash rounds up to exactly 1.0. Append the third part of the script, which feeds both extreme hash values to the naive conversion and to unit().

# step07_weights.py (continued)
print()
print("=== the edges of the unit interval")
for h in (0, 2**64 - 1):
    naive_u = h / 2**64
    try:
        outcome = f"{-1 / math.log(naive_u):.3g}"
    except (ValueError, ZeroDivisionError) as error:
        outcome = type(error).__name__
    weighted.score = lambda key, node, h=h: h
    print(f"hash {h:>20}: h / 2**64 = {naive_u!r:<5} -> {outcome:<18} unit() = {unit('k', 'n')!r}")
hash                    0: h / 2**64 = 0.0   -> ValueError         unit() = 1.1102230246251565e-16
hash 18446744073709551615: h / 2**64 = 1.0   -> ZeroDivisionError  unit() = 0.9999999999999999

The naive conversion raises ValueError for hash 0 and ZeroDivisionError for the largest hash, while unit() returns 1.1102230246251565e-16 and 0.9999999999999999, both strictly inside the interval. Using the top 52 bits and adding 0.5 puts every possible value exactly on a float and away from both ends. To be clear about the risk, a real hash lands on one of these values about once in 254 score evaluations (roughly 18 quadrillion), so you would almost never see this in production; the point is that one line removes the possibility and a test (Step 10) pins it.

Step 8: Keep caches warm in a replica fleet (a simulation)

The idea

Now put the pieces together on the problem from the introduction. You run eight replicas of a model server (here a replica is one running copy of the server, not a copy of data). Each keeps the KV caches of up to 250 recent conversations (an LRU, as defined above), out of 4,000 conversations in play, and a router decides which replica handles each request. A request is a hit when its conversation is still in that replica’s cache. After a warm-up, the simulation measures the hit rate; then replica-3 fails, and later a fresh, empty replica-8 joins. Five routers compete: random, round-robin, hash % N, a ring with 100 virtual nodes, and rendezvous hashing.

This is a deliberately simple model. It treats a whole conversation as one cache entry, ignores token counts and latency, and uses one synthetic traffic pattern in which popular conversations return often (the weight of the conversation with popularity rank r is 1 / r**0.9). It cannot tell you your real hit rate. It can tell you how the routing strategies compare, and every strategy sees exactly the same traffic.

The code

Save step08_router_sim.py. The first part holds the five routers. Each has a route method that takes a conversation ID and the list of live replicas.

"""step08_router_sim.py: does a router keep per-replica caches warm while replicas leave and join?"""
import random
from collections import Counter, OrderedDict

from rendezvous import _hash64, pick
from ring import Ring

CONVERSATIONS = 4000
CAPACITY = 250          # conversations one replica can keep warm
START = [f"replica-{i}" for i in range(8)]


class RandomRouter:
    name = "random"

    def __init__(self):
        self.rng = random.Random(1)

    def route(self, conversation, replicas):
        return self.rng.choice(replicas)


class RoundRobin:
    name = "round-robin"

    def __init__(self):
        self.turn = 0

    def route(self, conversation, replicas):
        self.turn += 1
        return replicas[self.turn % len(replicas)]


class HashModN:
    name = "hash % N"

    def route(self, conversation, replicas):
        return replicas[_hash64(conversation) % len(replicas)]


class RingRouter:
    name = "ring, 100 vnodes"

    def __init__(self):
        self.rings = {}

    def route(self, conversation, replicas):
        members = tuple(replicas)
        if members not in self.rings:
            self.rings[members] = Ring(members, vnodes=100)
        return self.rings[members].pick(conversation)


class Rendezvous:
    name = "rendezvous"

    def route(self, conversation, replicas):
        return pick(conversation, replicas)

Append the second part, which generates the traffic and runs the timeline. A window serves a number of requests and returns the hit rate. After each membership change, the script measures four windows of 500 requests and reports the worst one, so a short dip is not averaged away, and then 8,000 more requests to show how far things recover.

# step08_router_sim.py (continued)
def make_traffic(count, seed=7):
    """Popular conversations come back often: weight of rank r is 1 / r**0.9."""
    rng = random.Random(seed)
    weights = [1 / (rank + 1) ** 0.9 for rank in range(CONVERSATIONS)]
    return [f"conv-{c}" for c in rng.choices(range(CONVERSATIONS), weights=weights, k=count)]


def simulate(router, traffic):
    caches = {name: OrderedDict() for name in START}
    members = sorted(caches)
    routed = Counter()
    stream = iter(traffic)

    def serve(conversation):
        target = router.route(conversation, members)
        routed[target] += 1
        cache = caches[target]
        hit = conversation in cache
        if hit:
            cache.move_to_end(conversation)
        else:
            cache[conversation] = True
            if len(cache) > CAPACITY:
                cache.popitem(last=False)
        return hit

    def window(count):
        return 100 * sum(serve(next(stream)) for _ in range(count)) / count

    window(30_000)                       # warm-up, not reported
    routed.clear()
    steady = window(10_000)
    busiest = 100 * max(routed.values()) / sum(routed.values())
    del caches["replica-3"]              # a replica fails or is scaled in
    members = sorted(caches)
    leave_low = min(window(500) for _ in range(4))
    leave_rest = window(8_000)
    caches["replica-8"] = OrderedDict()  # a fresh, empty replica joins
    members = sorted(caches)
    join_low = min(window(500) for _ in range(4))
    join_rest = window(8_000)
    return steady, busiest, leave_low, leave_rest, join_low, join_rest


traffic = make_traffic(60_000)
top_name, top_count = Counter(traffic).most_common(1)[0]
print(f"{top_name} is the most popular conversation: {top_count / len(traffic):.1%} of all {len(traffic):,} requests")
print("cache hit rate in percent (8 replicas, each keeps 250 of 4,000 conversations)")
print(f"{'':<18}{'':>7} | {'replica-3 leaves':^17} | {'replica-8 joins':^17} | busiest replica")
print(f"{'router':<18}{'steady':>7} | {'worst 500':>9}{'later':>8} | {'worst 500':>9}{'later':>8} | share of requests")
for router in (RandomRouter(), RoundRobin(), HashModN(), RingRouter(), Rendezvous()):
    steady, busiest, a, b, c, d = simulate(router, traffic)
    print(f"{router.name:<18}{steady:>7.1f} | {a:>9.1f}{b:>8.1f} | {c:>9.1f}{d:>8.1f} | {busiest:>12.1f}%")
python step08_router_sim.py
conv-0 is the most popular conversation: 7.4% of all 60,000 requests
cache hit rate in percent (8 replicas, each keeps 250 of 4,000 conversations)
                          | replica-3 leaves  |  replica-8 joins  | busiest replica
router             steady | worst 500   later | worst 500   later | share of requests
random               44.9 |      42.8    46.1 |      40.8    45.6 |         13.4%
round-robin          45.3 |      43.6    46.5 |      40.8    45.9 |         12.5%
hash % N             83.4 |      43.6    78.7 |      43.2    80.7 |         19.7%
ring, 100 vnodes     83.6 |      78.0    80.5 |      72.4    82.9 |         18.6%
rendezvous           83.5 |      76.4    80.6 |      73.6    83.3 |         18.7%

What the output tells you

Affinity nearly doubles the hit rate

Random and round-robin routing sit at about 45 percent, while the three hashing routers reach about 83.5 percent in the steady state, because a conversation always lands where its cache already is.

Membership changes separate the hashing routers

When replica-3 left, the worst 500-request window fell to 43.6 percent with hash % N, down to the level of random routing, while the ring held 78.0 percent and rendezvous hashing 76.4 percent. When replica-8 joined, hash % N fell to 43.2 percent again, against 72.4 percent for the ring and 73.6 percent for rendezvous hashing. In this small simulation hash % N recovers within a couple of thousand requests (78.7 and 80.7 percent later) because the most popular conversations re-warm quickly; the most popular one alone is 7.4 percent of all traffic. Real caches with longer tails and bigger entries recover more slowly, and a recovery period is exactly when your origin is under the most pressure.

Affinity has a cost

The last column shows the share of requests that went to the busiest replica. Round-robin gives every replica 12.5 percent, but the hashing routers gave the busiest one 18.6 to 19.7 percent, because the hottest conversations all pile onto whichever replica owns them. Pure affinity trades load balance for cache hits. Production routers handle this with more than one signal. The vLLM production stack’s router, for instance, has a session router described as “Route the request to the appropriate engine URL based on the session key in the request headers”, which keeps a hash ring (from the uhashring package, “Full featured consistent hashing python library compatible with ketama.”) and falls back to “a server with lowest qps” when a request has no session ID. The same file also contains a router that picks “by where the KV cache of the longest prefix match is found” and one described as “KV-cache-aware placement weighted by live engine load.” That is the same trade-off, handled with more information than a hash alone.

Step 9: Make lookups constant time with a table

The idea

Rendezvous hashing scores every node on every lookup, so the cost is linear in the number of nodes. For 10 nodes that is nothing; for 1,000 nodes on a hot path it adds up. GitHub faced this in its load balancer. Its introduction to GLB says the design it settled on is “a variant of Rendezvous hashing that supports constant time lookups”, and explains how: “We then generate a single, fixed-size forwarding table and fill each row with a set of proxy servers using the ordering component of Rendezvous hashing.”

The trick is to run the tournament for each row of a fixed-size table instead of for each key. A key is mapped to a row by hashing it once and taking the remainder by the table size, which never changes, so lookups become one hash and one list index. When a node leaves, you rebuild the table with the same rules and only the rows it owned change.

The code

Save table.py. Each row stores the best two nodes for a pseudo-key named after the row.

# table.py
"""A forwarding table: rank the nodes once per row, then answer every lookup by indexing a list."""
from rendezvous import _hash64, ranked


class Table:
    def __init__(self, nodes, rows: int = 4096, copies: int = 2):
        self.rows = rows
        self.table = [tuple(ranked(f"row-{i}", nodes)[:copies]) for i in range(rows)]

    def row(self, key: str) -> tuple[str, ...]:
        return self.table[_hash64(key) % self.rows]

    def pick(self, key: str) -> str:
        return self.row(key)[0]

Save step09_table.py. It measures how rows trade accuracy for size, confirms that table rows agree with plain rendezvous hashing, and times lookups for 10, 100 and 1,000 nodes.

"""step09_table.py: a precomputed table gives constant-time lookups, at the price of a coarser spread."""
import math
import statistics
import time
from collections import Counter

from rendezvous import pick
from ring import Ring
from table import Table

KEYS = [f"key-{i}" for i in range(100_000)]
NODES = [f"node-{i:02d}" for i in range(10)]
LEFT = [n for n in NODES if n != "node-03"]

print("=== spread and movement, 10 nodes, 100,000 keys")
print(f"{'rows':>7}{'spread':>9}{'moved when node-03 leaves':>27}{'needless moves':>16}")
for rows in (256, 4096, 65536):
    before, after = Table(NODES, rows=rows), Table(LEFT, rows=rows)
    owners = [before.pick(k) for k in KEYS]
    counts = Counter(owners)
    loads = [counts[n] for n in NODES]
    spread = statistics.pstdev(loads) / statistics.fmean(loads) * 100
    moved = [(o, after.pick(k)) for o, k in zip(owners, KEYS) if o != after.pick(k)]
    needless = sum(old != "node-03" for old, _ in moved)
    print(f"{rows:>7}{spread:>8.2f}%{len(moved) / len(KEYS):>27.1%}{needless:>16,}")
ideal = math.sqrt((1 - 1 / len(NODES)) / (len(KEYS) / len(NODES))) * 100
print(f"pure chance for {len(KEYS):,} keys on {len(NODES)} nodes: {ideal:.2f}%")

print()
print("=== the table agrees with plain rendezvous hashing on its own rows")
table = Table(NODES, rows=4096)
print("rows whose primary equals pick(row id):", sum(table.table[i][0] == pick(f"row-{i}", NODES) for i in range(4096)), "of 4096")

print()
print("=== lookup cost in microseconds (your numbers will differ)")


def per_lookup(func, count):
    start = time.perf_counter()
    for i in range(count):
        func(f"probe-{i}")
    return (time.perf_counter() - start) / count * 1e6


for size in (10, 100, 1000):
    nodes = [f"node-{i:04d}" for i in range(size)]
    ring, small = Ring(nodes, vnodes=100), Table(nodes, rows=512)
    hrw = per_lookup(lambda key: pick(key, nodes), 3000 if size < 1000 else 500)
    print(f"{size:>5} nodes: rendezvous {hrw:9.1f}   ring {per_lookup(ring.pick, 20000):6.1f}   table {per_lookup(small.pick, 20000):6.1f}")
python step09_table.py
   rows   spread  moved when node-03 leaves  needless moves
    256   23.11%                       8.9%               0
   4096    2.71%                       9.9%               0
  65536    1.59%                       9.9%               0
pure chance for 100,000 keys on 10 nodes: 0.95%
rows whose primary equals pick(row id): 4096 of 4096
   10 nodes: rendezvous       4.5   ring    0.5   table    0.4
  100 nodes: rendezvous      41.6   ring    0.6   table    0.4
 1000 nodes: rendezvous     416.5   ring    0.7   table    0.4

What the output tells you

The table still moves only what it must: when node-03 leaves, 8.9 to 9.9 percent of the keys move and none of them needlessly. Its price is granularity. With 256 rows the spread is a lumpy 23.11 percent, with 4,096 rows it is 2.71 percent, and with 65,536 rows 1.59 percent (part of which is the 0.95 percent that pure chance gives for 100,000 keys on 10 nodes, printed below the table). More rows mean a more even table, at the cost of a bigger table to rebuild: building one takes rows times nodes hashes.

The timings show why the table exists. Plain rendezvous hashing took 4.5 microseconds per lookup with 10 nodes, 41.6 with 100 and 416.5 with 1,000, which is linear, about 0.4 microseconds per node. The ring (0.5 to 0.7 microseconds) and the table (0.4) barely change. At 1,000 nodes the table is roughly 1,000 times faster than scoring every node. Use plain rendezvous hashing when you have tens of nodes or lookups are rare; use the table when you have many nodes or need every microsecond on the hot path. Wikipedia mentions another option, a skeleton-based variant that reduces the lookup to O(log n), at the cost of less even placement.

Step 10: Test it

The idea

The properties you just measured are guarantees you want to keep, so turn them into tests. They are also what lets you change the implementation later without fear. Save test_rendezvous.py in three parts, appending each part to the same file. The first group pins behavior that every client must share.

# test_rendezvous.py
import random
import subprocess
import sys
from pathlib import Path

import pytest

import rendezvous
from rendezvous import pick, ranked, replicas, score
from table import Table

HERE = Path(__file__).parent
NODES = [f"node-{i:02d}" for i in range(10)]
KEYS = [f"key-{i}" for i in range(3000)]
PINNED = {"user-42": "node-04", "user-43": "node-09", "session-abc": "node-00"}


def test_known_picks_never_change():
    # Every client, in every language, has to reproduce these. A different hash would fail this on purpose.
    assert {key: pick(key, NODES) for key in PINNED} == PINNED


def test_pick_is_the_first_ranked_node():
    assert all(pick(key, NODES) == ranked(key, NODES)[0] for key in KEYS)
    assert replicas("user-42", NODES, 3) == ranked("user-42", NODES)[:3]


def test_node_order_does_not_matter():
    shuffled = NODES[:]
    random.Random(1).shuffle(shuffled)
    assert all(pick(key, NODES) == pick(key, shuffled) for key in KEYS)


def test_same_answer_in_another_process():
    code = "from rendezvous import pick; print(pick('user-42', [f'node-{i:02d}' for i in range(10)]))"
    done = subprocess.run([sys.executable, "-c", code], cwd=HERE, capture_output=True, text=True, check=True)
    assert done.stdout.strip() == pick("user-42", NODES)

test_known_picks_never_change pins three answers. Changing the hash function, the separator or the score formula would reshuffle every key in production, so it should fail loudly in review rather than quietly in your cache hit rate. The cross-process test runs a fresh Python and compares, which is the test that the built-in hash() fails.

Append the second group, which checks the movement and ranking guarantees on 3,000 keys.

# test_rendezvous.py (continued)
def test_removing_a_node_moves_only_its_keys():
    left = [n for n in NODES if n != "node-03"]
    for key in KEYS:
        before = pick(key, NODES)
        if before != "node-03":
            assert pick(key, left) == before


def test_adding_a_node_moves_keys_only_to_the_new_node():
    more = NODES + ["node-10"]
    assert all(pick(key, more) in (pick(key, NODES), "node-10") for key in KEYS)


def test_the_ranking_after_a_removal_is_the_old_ranking_minus_that_node():
    left = [n for n in NODES if n != "node-03"]
    for key in KEYS:
        assert ranked(key, left) == [n for n in ranked(key, NODES) if n != "node-03"]

The last test in that group is the strongest statement of the whole idea: after removing a node, the ranking for every key equals the old ranking with that node deleted. Append the third group, which covers edge cases and the table.

# test_rendezvous.py (continued)
def test_concatenation_cannot_collide():
    assert score("1x", "cache-1") != score("x", "cache-11")


def test_ties_go_to_the_larger_name_whatever_the_list_order(monkeypatch):
    monkeypatch.setattr(rendezvous, "score", lambda key, node: 7)
    assert pick("k", ["b", "a", "c"]) == pick("k", ["c", "b", "a"]) == "c"
    assert ranked("k", ["b", "a", "c"]) == ["c", "b", "a"]


def test_an_empty_node_list_is_an_error():
    with pytest.raises(ValueError):
        pick("k", [])


def test_one_node_gets_every_key():
    assert {pick(key, ["only"]) for key in KEYS} == {"only"}


def test_load_is_even():
    loads = [sum(pick(key, NODES) == node for key in KEYS) for node in NODES]
    assert all(abs(load - 300) < 60 for load in loads)


def test_table_rows_agree_with_rendezvous_hashing():
    table = Table(NODES, rows=512)
    assert all(table.table[i] == tuple(ranked(f"row-{i}", NODES)[:2]) for i in range(512))


def test_table_removal_moves_only_the_rows_of_the_removed_node():
    before, after = Table(NODES, rows=512), Table([n for n in NODES if n != "node-03"], rows=512)
    for old, new in zip(before.table, after.table):
        if old[0] != "node-03":
            assert new[0] == old[0]

The tie test replaces score with a constant using pytest’s monkeypatch, so that every node ties, and checks that the answer does not depend on list order. Now the weighted tests, saved as test_weighted.py.

# test_weighted.py
import math
from collections import Counter

import pytest

import weighted
from weighted import pick_weighted, unit, weighted_score

KEYS = [f"key-{i}" for i in range(40_000)]
WEIGHTS = {"small": 1, "medium": 2, "large": 3, "xlarge": 4}


def test_shares_follow_the_weights():
    counts = Counter(pick_weighted(key, WEIGHTS) for key in KEYS)
    for node, weight in WEIGHTS.items():
        assert abs(counts[node] / len(KEYS) - weight / 10) < 0.01


def test_raising_a_weight_only_pulls_keys_toward_that_node():
    heavier = {**WEIGHTS, "large": 6}
    for key in KEYS[:5000]:
        assert pick_weighted(key, heavier) in (pick_weighted(key, WEIGHTS), "large")


def test_a_zero_weight_drains_a_node():
    drained = {**WEIGHTS, "small": 0}
    assert all(pick_weighted(key, drained) != "small" for key in KEYS[:5000])


def test_impossible_weights_are_errors():
    with pytest.raises(ValueError):
        pick_weighted("k", {"a": 0, "b": 0})
    with pytest.raises(ValueError):
        pick_weighted("k", {"a": -1, "b": 1})


@pytest.mark.parametrize("hash_value", [0, 2**64 - 1])
def test_unit_stays_strictly_between_0_and_1(monkeypatch, hash_value):
    monkeypatch.setattr(weighted, "score", lambda key, node: hash_value)
    assert 0 < unit("k", "n") < 1
    assert math.isfinite(weighted_score("k", "n", 1.0))
python -m pytest -q -p no:cacheprovider test_rendezvous.py test_weighted.py
....................                                                     [100%]
20 passed in 0.52s

Twenty tests pass in about half a second. The -p no:cacheprovider flag just keeps pytest from writing a cache folder next to your code.

Step 11: Break it on purpose

The idea

Passing tests only matter if they would fail when the code is wrong. A mutation check proves that: plant one bug at a time in a copy of the code, run the tests, and require a failure. Save mutations.py. Each entry is a file, a description, the exact text to replace and its buggy replacement; the script asserts that the text occurs exactly once, so a refactor cannot silently turn a mutant into a no-op.

"""mutations.py: plant one bug at a time in a copy of the code and check that the tests notice."""
import pathlib
import shutil
import subprocess
import sys
import tempfile

HERE = pathlib.Path(__file__).parent
CODE = ["rendezvous.py", "weighted.py", "ring.py", "table.py", "test_rendezvous.py", "test_weighted.py"]

MUTANTS = [
    ("rendezvous.py", "built-in hash() instead of blake2b",
     'digest = hashlib.blake2b(text.encode("utf-8"), digest_size=8).digest()\n    return int.from_bytes(digest, "big")',
     "return hash(text) & 0xFFFFFFFFFFFFFFFF"),
    ("rendezvous.py", "no separator between node and key", r'f"{node}\x00{key}"', 'f"{node}{key}"'),
    ("rendezvous.py", "tie-break by list order", "max(nodes, key=lambda node: (score(key, node), node))",
     "max(nodes, key=lambda node: score(key, node))"),
    ("rendezvous.py", "pick() takes the lowest score", "return max(nodes,", "return min(nodes,"),
    ("rendezvous.py", "ranked() sorts the wrong way", "node), reverse=True)", "node))"),
    ("rendezvous.py", "replicas() skips the owner", "return ranked(key, nodes)[:count]", "return ranked(key, nodes)[1:count + 1]"),
    ("weighted.py", "weight times a uniform number", "return -weight / math.log(unit(key, node))", "return weight * unit(key, node)"),
    ("weighted.py", "unit() from all 64 bits", "return ((score(key, node) >> 12) + 0.5) / 2**52", "return score(key, node) / 2**64"),
    ("weighted.py", "negative weights accepted", "if any(weight < 0 for weight in weights.values()):", "if False:"),
    ("weighted.py", "zero-weight nodes stay in the race", "live = {node: weight for node, weight in weights.items() if weight > 0}",
     "live = dict(weights)"),
]


def run_tests(folder):
    done = subprocess.run([sys.executable, "-B", "-m", "pytest", "-x", "-q", "-p", "no:cacheprovider"],
                          cwd=folder, capture_output=True, text=True, encoding="utf-8")
    return done.returncode, done.stdout.strip().splitlines()[-1] if done.stdout.strip() else ""


caught = 0
for filename, label, old, new in MUTANTS:
    with tempfile.TemporaryDirectory() as tmp:
        for name in CODE:
            shutil.copy(HERE / name, tmp)
        path = pathlib.Path(tmp) / filename
        text = path.read_text(encoding="utf-8")
        assert text.count(old) == 1, (label, text.count(old))
        path.write_text(text.replace(old, new), encoding="utf-8", newline="\n")
        code, last = run_tests(tmp)
    caught += code != 0
    print(f"{'CAUGHT' if code else 'MISSED':<7}{label:<40}{last}")
print(f"{caught} of {len(MUTANTS)} planted bugs caught")
python mutations.py
CAUGHT built-in hash() instead of blake2b      1 failed in 0.04s
CAUGHT no separator between node and key       1 failed in 0.04s
CAUGHT tie-break by list order                 1 failed, 8 passed in 0.24s
CAUGHT pick() takes the lowest score           1 failed in 0.04s
CAUGHT ranked() sorts the wrong way            1 failed, 1 passed in 0.04s
CAUGHT replicas() skips the owner              1 failed, 1 passed in 0.07s
CAUGHT weight times a uniform number           1 failed, 14 passed in 0.50s
CAUGHT unit() from all 64 bits                 1 failed, 18 passed in 0.55s
CAUGHT negative weights accepted               1 failed, 17 passed in 0.53s
CAUGHT zero-weight nodes stay in the race      1 failed, 17 passed in 0.55s
10 of 10 planted bugs caught

All ten bugs were caught. Several of them are the traps from earlier steps: the built-in hash() (Step 4), the missing separator (Step 4), weight times a uniform number (Step 7) and the 64-bit conversion of u (Step 7). Others are plain slips that are easy to write: sorting the ranking the wrong way, skipping the owner in replicas, letting list order break ties, accepting negative weights, and keeping zero-weight nodes in the race.

Step 12: Run everything and confirm it works

Save one last file, run_all.py, which runs every step script, the tests and the mutation check, and saves each output to an out folder so you can compare it with this article.

"""run_all.py: run every step, the tests and the mutation check; save each output to out/NAME.txt."""
import subprocess
import sys
from pathlib import Path

HERE = Path(__file__).parent
OUT = HERE / "out"
OUT.mkdir(exist_ok=True)
STEPS = ["step01_modn", "step02_first_pick", "step03_movement", "step04_hash_trap", "step05_balance",
         "step06_replicas", "step07_weights", "step08_router_sim", "step09_table"]
ONLY = sys.argv[1:]


def run(name, args):
    done = subprocess.run([sys.executable, "-B", *args], cwd=HERE, capture_output=True, text=True, encoding="utf-8")
    text = (done.stdout + done.stderr).rstrip("\n") + "\n"
    with open(OUT / f"{name}.txt", "w", newline="\n", encoding="utf-8") as f:
        f.write(text)
    print(f"== {name} (exit {done.returncode})", flush=True)
    print(text, flush=True)


for step in STEPS:
    if not ONLY or step in ONLY:
        run(step, [f"{step}.py"])
if not ONLY or "pytest" in ONLY:
    run("pytest", ["-m", "pytest", "-q", "-p", "no:cacheprovider", "test_rendezvous.py", "test_weighted.py"])
if not ONLY or "mutations" in ONLY:
    run("mutations", ["mutations.py"])
python run_all.py

You are done when all of these hold:

  • every step prints (exit 0);
  • hash % N moves about 90 percent of the keys in Step 1, while rendezvous hashing moves about 10 percent in Step 3 with no needless moves;
  • the same pick comes back from every process in Step 4;
  • pytest reports 20 passed and the mutation check reports 10 of 10 planted bugs caught.

The random-looking numbers (scores, key counts) come out identical on every run because the keys, node names and seeds are fixed. Only the timing lines in Step 9 and the test durations change from machine to machine.

Common mistakes and how to avoid them

Naming nodes by something unstable

A node’s name is its identity: scores are computed from it. If you name nodes by list position, or by an IP address that changes when a pod restarts, a restarted node becomes a different node and all its keys move. Use a stable identifier such as a StatefulSet pod name or an explicit ID. Rename nodes only when you intend to move their keys.

Assuming the algorithm makes clients agree on who is alive

Rendezvous hashing guarantees that clients with the same node list pick the same node. It says nothing about how they come to share that list. Distributing the membership is a separate problem, solved with service discovery, a consensus system (see our Raft tutorial) or a failure detector (see heartbeats, phi accrual and SWIM). For caches, a short disagreement costs a miss. For anything stateful, decide the membership first.

Changing the hash or the score formula casually

Every client must compute exactly the same scores, in every language and every version. If you change the hash function, the separator, the node naming or the weight formula, you change every owner at once, which is the same disaster as hash % N. That is why test_known_picks_never_change exists. If you really must change it, roll it out as a migration with a version tag, not as a refactor.

Forgetting the stampede after a node loss

Rendezvous hashing limits the damage to one node’s keys, but those keys still arrive cold. If thousands of requests miss at once, protect the origin with single-flight loading, as in our cache stampede tutorial, and consider warming the new owner from the old replica when you control the drain.

Expecting balanced load from balanced keys

The spread in Step 5 counts keys. Step 8 shows that requests per key are rarely equal: the busiest replica carried 18.7 percent of requests against a fair share of 12.5. A hash gives you stable placement, not load balancing. Combine it with load signals, or split very hot keys across several nodes using the replica list.

Changing weights in big jumps

Raising one node’s weight moves keys toward it (Step 7 moved 16.2 percent for a change from 3 to 6). That is the minimum for the new shares, but it is still a lot of cold keys at once. Step weights up or down gradually, or use a weight of 0 to drain a node deliberately.

Which scheme should you pick?

All three strategies below move only the keys they must when a node leaves. They differ in what you pay for that. The numbers come from the measurements in this article (10 nodes for spread and movement, 100 nodes for lookup cost).

Strategy Spread over 10 nodes Share moved when a node leaves Lookup cost at 100 nodes State you keep
hash % N Even with a uniform hash 90.1 percent One hash None
Ring, 100 virtual nodes 11.03 percent 9.1 percent 0.6 microseconds Sorted points: nodes times vnodes
Rendezvous hashing 0.78 percent 10.1 percent 41.6 microseconds None
Rendezvous table (4,096 rows) 2.71 percent 9.9 percent 0.4 microseconds Rows times copies

The table’s lookup was timed with 512 rows, because a lookup is one hash and one list index whatever the row count.

As a rule of thumb: pick plain rendezvous hashing when the node list is short, you value having no state and no tuning, or you need weights and replica lists with the least code. Pick a ring when the node count is large and you want the cheapest lookup with a simple structure, accepting that you must tune virtual nodes. Pick a table when you need the evenness of rendezvous hashing and a constant-time lookup and can afford a rebuild on every membership change.

Where rendezvous hashing is used

  • GitHub’s load balancer. The GLB Director uses the table variant from Step 9, with a primary and a secondary per row, as quoted above.
  • Ceph. The straw2 bucket in the CRUSH mapper draws an exponential random number for each item and keeps the highest, which is the weighted race of Step 7 (the check in that step confirms that ln(u) / weight and -weight / ln(u) pick the same node).
  • Other systems. Wikipedia lists Apache Ignite, Tahoe-LAFS, Apache Druid, Apache Kafka and Twitter’s EventBus among the systems that use it.
  • For contrast, LLM routing. The vLLM production stack’s session router uses a hash ring, as quoted in Step 8. Both families work for the job; the choice is about tuning, weights and lookup cost.

Next steps

  • Read the original report, A Name-Based Mapping Scheme for Rendezvous, and the 1998 follow-up in IEEE/ACM Transactions on Networking, Using Name-Based Mapping Schemes to Increase Hit Rates.
  • Change the simulation in step08_router_sim.py: make the replicas different sizes and route with weights, or add a load-aware fallback that skips to the second-ranked replica when the first is busy, and see what the busiest-replica column does.
  • Add the table’s second copy to the cache simulation, so that a failed replica’s conversations fall back to a replica that already has them.
  • Pair the router with a failure detector and a single-flight loader, and test the whole path with random node failures, in the style of our Raft lab.
  • Replace the router’s fake LRU with token-level cache accounting from a real inference engine and compare your measured hit rate with the simulated one.

Tags:

CachingConsistent HashingDistributed SystemsKV CachePythonRendezvous Hashing

Share

No Comment! Be the first one.

Leave a Reply

Your email address will not be published. Required fields are marked *

Related Posts