subroute.
Intermediate10 min readlive prototype

Rendezvous Hashing (HRW)

Score every server for the key with hash(key, server) and pick the highest. No ring, even load, and weighting is trivial.

Overview

What this concept solves

The ring methods all share one assumption: you keep a structure (the ring, the vnode list) and look keys up against it. Rendezvous hashing throws that away. There is no ring and no stored positions. Instead, for every key you ask each server one question — 'what's your score for this key?' — and the highest score wins. That's the entire algorithm.

The score is just a hash of the two names combined: score = hash(server + key). Because the hash mixes both the server's name and the key's name, every (server, key) pair gets its own pseudo-random number between 0 and 1. The server with the biggest number for a given key owns that key. It's also called HRW — Highest Random Weight — for exactly this reason.

The magic is what happens when a server leaves. A key only moves if the server that left was its winner. In that case the key simply falls to whoever had the second-highest score — and no other key is touched, because their winners didn't change. You get minimal, surgical reassignment without ever placing anything on a ring.

Mechanics

How it works

Score everyone, pick the max

  1. For the key you're placing, loop over every server.
  2. For each server, compute score = hash(server_name + key_name).
  3. Keep the server with the highest score. That server owns the key.
  4. To replicate to R servers, just take the top R scores instead of the top 1.

Each key decides independently, so the work is O(N) per lookup — you score all N servers. There's no ring to keep sorted and no virtual nodes to manage; the only state is the list of server names. For small to medium N this is wonderfully simple.

Why removal is so clean

Imagine a key's scores ranked: alpha (0.91), gamma (0.62), beta (0.40). alpha wins. Remove alpha and the ranking is just gamma (0.62), beta (0.40) — gamma takes over. Crucially, every key whose winner wasn't alpha sees no change at all, because dropping alpha doesn't alter anyone else's scores. The prototype shows this directly: the second-place bar is already visible before you remove the leader.

Weighting is easy too

To make a bigger server take more keys, multiply (or transform) its score so it wins more often — a small formula change, no extra ring positions. This is why rendezvous is popular when you want capacity-awareness without the bookkeeping of virtual nodes.

The cost is the O(N) scan

Because every lookup scores every server, rendezvous gets expensive when N is large (thousands of nodes). For big fleets people either cap N, use it only at a small top layer, or switch to a method with cheaper lookups (jump hash, Maglev). For tens of servers, the scan is nothing.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

Each key runs its own little lottery: every server computes a score of hash(server + key), and the highest score wins. Click any key chip to see its bars — the tallest one (badged WINS) is its server. Remove a server with the ✕ and watch only its keys jump to their second-place bar; everyone else is untouched.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Read a lottery

Click any key chip. The bars show every server's hash(server + key) score for that key; the tallest, badged WINS, is the owner. Try a few keys — each has a totally different winner because each runs its own independent lottery.

try 02

Remove the winner, watch second place take over

Pick a key, note its winner and its second-place bar. Now click the ✕ on that winning server's card. The key (and only keys it was winning) flips to second place — the narration tells you how many moved and how many were untouched.

try 03

Add servers and watch balance hold

Use Add server and +5 keys. Notice the per-server counts stay fairly even without any virtual nodes — and adding a server only pulls over the keys whose new ticket beats their old winner. No global reshuffle, no ring.

In practice

When to use it — and what you give up

When to reach for it

  • Small or medium clusters — a handful to a few hundred servers, where an O(N) scan per key is cheap.
  • You want weights without vnodes — capacity-aware placement falls out of a small tweak to the score.
  • You need the top-R for replication — picking the R highest scores gives a natural, stable replica set.
  • Caching layers — its original use (CARP, web proxy caches): clients independently agree on which cache holds an object, with no coordination.

Pros

  • No ring, no virtual nodes — the only state is the list of server names.
  • Naturally even distribution, even with few servers (no lumpy arcs to fix).
  • Removal is surgical: only the leaving server's keys move, each to its second choice.
  • Weights and top-R replication come from tiny formula changes.

Cons

  • O(N) per lookup — you score every server — so it scales poorly to very large N.
  • More hashing work per lookup than a ring's single binary search.
  • Less common in off-the-shelf infrastructure than the ring, so fewer ready-made libraries.
  • Still hash-based, so balance is statistical, not exactly equal.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

// Rendezvous (HRW) hashing: score every server, pick the highest.
package main

import "sort"

type Rendezvous struct {
	servers []string
}

func (r *Rendezvous) hash(s string) uint32 {
	var h uint32 = 2166136261
	for i := 0; i < len(s); i++ {
		h ^= uint32(s[i])
		h *= 16777619
	}
	return h
}

// score combines server + key, so each pair gets its own number
func (r *Rendezvous) score(server, key string) uint32 {
	return r.hash(server + "|" + key)
}

func (r *Rendezvous) GetServer(key string) (string, bool) {
	best, bestScore, found := "", uint32(0), false
	for _, s := range r.servers {
		v := r.score(s, key)
		if !found || v > bestScore {
			bestScore, best, found = v, s, true
		}
	}
	return best, found // O(N): we looked at every server
}

// Top-R servers => a natural replica set
func (r *Rendezvous) GetReplicas(key string, n int) []string {
	sorted := append([]string(nil), r.servers...)
	sort.Slice(sorted, func(i, j int) bool {
		return r.score(sorted[i], key) > r.score(sorted[j], key)
	})
	if n > len(sorted) {
		n = len(sorted)
	}
	return sorted[:n]
}

func main() {
	rv := &Rendezvous{servers: []string{"alpha", "beta", "gamma"}}
	rv.GetServer("user:42")      // the highest-scoring server
	rv.GetReplicas("user:42", 2) // its primary + backup
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. Sign in to save your best score.

question 01 / 03

How does rendezvous hashing decide which server owns a key?

question 02 / 03

When a server is removed, which keys move and where?

question 03 / 03

What is the main downside of rendezvous hashing?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Consistent Hashing