01 / The idea
Every web server must pick the same cache server.
The app resizes photos and keeps the thumbnails on four cache servers, cache-a to cache-d. Any web server that needs photo-7’s thumbnail has to ask the cache server that holds it, or it misses and resizes the photo again. There is no shared table of who holds what: each web server works it out from the photo’s key and the list of cache servers.
The first answer most of us write is to hash the key and take the remainder after dividing by 4. It spreads the photos well, until the number of servers changes. When cache-c leaves, the divisor becomes 3 and 16 of the 24 photos get a different answer, half of them moving between servers that never went anywhere. Across 10,000 photos, 7,577 move. That is nginx’s warning, and a cache that has to warm up again.
Rendezvous hashing gives each server a score for each key, a number made by hashing the two together, and the key belongs to the server with the highest score. When a server leaves, nothing about the other servers’ scores changes, so only the keys it held move. Watch it place the photos, then take cache-c away.
Every server scores every key.
photo-7
a cache-a · 0
b cache-b · 0
c cache-c · 0
d cache-d · 0
Score every server. Keep the highest.
photo-7 gets one score from each server: cache-a 2,125,994,304, cache-b 161,229,223, cache-c 1,658,989,238, and cache-d 2,441,075,413. cache-d’s is the highest, so cache-d owns photo-7.
Reduced motion: choose a scene to see its completed state.
Read this scene
photo-7 gets one score from each server: cache-a 2,125,994,304, cache-b 161,229,223, cache-c 1,658,989,238, and cache-d 2,441,075,413. cache-d’s is the highest, so cache-d owns photo-7.
Scores for photo-7: cache-a 2,125,994,304.
Watch and Step through replay the placement of the lesson’s 24 photos. Try it runs the same TypeScript on the servers you add or take away, and starts fresh each time you open it.
cache-c held 4 photos, and those 4 moved. The other 20 stayed where they were, because their highest score still belonged to a server that was still there.
02 / Name the rule
Hash both, mix them, keep the highest.
For each key, one step repeats for every server in the list:
The key once, each server once
FNV-1a turns each name into a 32-bit number. The same name always gives the same one.
Combine and mix
XOR the two hashes, then stir the result so every bit can affect every other.
Keep the highest
The highest score owns the key. A tie goes to the server whose name sorts first.
The hash is the one from the Hash map lesson: FNV-1a over the name’s bytes. A hash map uses it to pick one of its own buckets. Here it goes one step further, because the buckets are other machines and the list of them changes.
A score depends on exactly two things, the server and the key. So when cache-c leaves, cache-a, cache-b, and cache-d keep every score they had, and they stay in the same order for every photo. A photo’s owner can only change if the owner was cache-c, and then the photo goes to the server that scored second for it. photo-12’s scores rank cache-c, cache-b, cache-a, cache-d, so it moves to cache-b.
Joining works the same way from the other side. cache-e adds one new score to every photo and changes none of the old ones, so a photo moves only if cache-e’s score is its highest, and then it moves onto cache-e. With five servers that is about one photo in five: 4 of the 24, or 2,031 of 10,000.
Nobody has to agree on anything but the list. Any web server with the same four names computes the same 24 answers, and a new web server can start answering straight away, without asking the others. The method is also called highest random weight, or HRW.
Why mix after the XOR?Without it, cache-c wins half the photos
Take the mix out and score a key as just the server’s hash XOR the key’s hash. With four servers the photos still spread evenly, so nothing looks wrong. Now use cache-a, cache-b, and cache-c only. Of 10,000 photos, cache-c wins 4,997, and cache-a and cache-b split the rest, 2,507 and 2,496.
The cause is in the three hashes. The highest bit where they disagree is bit 26: cache-c has a 1 there, cache-a and cache-b both have a 0. XOR with a key flips that bit for all three or for none, so for every key either cache-c alone or the other two together come out ahead at that bit, and bit 26 of the key decides which. That is half the keys each way, however many servers are on a side.
The mix is MurmurHash3’s 32-bit finalizer: two multiplications and three shifts that spread every input bit across the output. With it, the same three servers get 3,342, 3,282, and 3,376. The lab’s Three servers, no mix preset shows the lopsided version on the 24 photos: 4, 6, and 14. Both languages test these counts.
03 / Read the shape
A hash, a mix, and a maximum.
Basic form is the whole algorithm: hashOf, mix, score, and ownerOf, which keeps the highest
score in one pass. In the wild ranks every server so a key can live on more
than one, and plans what a membership change means for each key. At the call site places the 24 photos and counts what moves, beside hash modulo
the server count. Both languages print the same four lines.
The whole algorithm: hashOf is FNV-1a over the bytes, mix is MurmurHash3’s finalizer, score combines a server’s hash with the key’s, and ownerOf keeps the highest score, breaking a tie by server name.
// Rendezvous hashing: every server scores every key, and the server with the highest score owns
// it. When a server leaves, only the keys it owned move, each to the server that scored second.
export const MAX_SERVERS = 64;
export const MAX_KEY_BYTES = 256;
export type Ranked = { server: string; score: number };
export type PlacementErrorCode =
'no-servers' | 'too-many' | 'bad-server' | 'bad-key' | 'bad-copies';
export class PlacementError extends Error {
readonly code: PlacementErrorCode;
constructor(code: PlacementErrorCode, message: string) {
super(message);
this.name = 'PlacementError';
this.code = code;
}
}
const utf8 = new TextEncoder();
// FNV-1a, 32 bits, over the UTF-8 bytes of a string: the hash the Hash map lesson uses.
export function hashOf(text: string): number {
let hash = 0x811c9dc5;
for (const byte of utf8.encode(text)) {
hash ^= byte;
hash = Math.imul(hash, 0x01000193);
}
return hash >>> 0;
}
// MurmurHash3's 32-bit finalizer: every input bit gets a chance to flip every output bit.
export function mix(hash: number): number {
hash ^= hash >>> 16;
hash = Math.imul(hash, 0x85ebca6b);
hash ^= hash >>> 13;
hash = Math.imul(hash, 0xc2b2ae35);
hash ^= hash >>> 16;
return hash >>> 0;
}
// A server's score for a key: the two hashes combined, then mixed. Without the mix, the highest
// bit where the servers' hashes differ would split them into two sides that each win half the
// keys, however many servers are on a side.
export const score = (serverHash: number, keyHash: number): number => mix(serverHash ^ keyHash);
export function checkServers(servers: string[]): void {
if (servers.length === 0) throw new PlacementError('no-servers', 'no servers to place keys on');
if (servers.length > MAX_SERVERS)
throw new PlacementError('too-many', `up to ${MAX_SERVERS} servers`);
const seen = new Set<string>();
for (const server of servers) {
if (!/^[a-z][a-z0-9-]{0,31}$/.test(server) || seen.has(server))
throw new PlacementError('bad-server', `server names are unique lowercase slugs: ${server}`);
seen.add(server);
}
}
export function checkKey(key: string): void {
const bytes = utf8.encode(key).length;
if (bytes === 0 || bytes > MAX_KEY_BYTES)
throw new PlacementError('bad-key', `keys are 1 to ${MAX_KEY_BYTES} bytes of UTF-8`);
}
// Highest score first. Equal scores go to the server whose name sorts first, so every caller
// agrees even on a tie.
export const byScore = (x: Ranked, y: Ranked): number =>
y.score - x.score || (x.server < y.server ? -1 : x.server > y.server ? 1 : 0);
export function ownerOf(servers: string[], key: string): string {
checkServers(servers);
checkKey(key);
const keyHash = hashOf(key); // once per lookup, not once per server
let best: Ranked | null = null;
for (const server of servers) {
const next = { server, score: score(hashOf(server), keyHash) };
if (best === null || byScore(next, best) < 0) best = next;
}
return best!.server;
}// Rendezvous hashing: every server scores every key, and the server with the highest score owns
// it. When a server leaves, only the keys it owned move, each to the server that scored second.
const (
MaxServers = 64
MaxKeyBytes = 256
)
type Ranked struct {
Server string
Score uint32
}
type PlacementError struct{ Code, Message string }
func (e *PlacementError) Error() string { return e.Message }
// HashOf is FNV-1a, 32 bits, over the bytes of a string: the hash the Hash map lesson uses.
func HashOf(text string) uint32 {
hash := uint32(0x811c9dc5)
for i := range len(text) {
hash ^= uint32(text[i])
hash *= 0x01000193
}
return hash
}
// Mix is MurmurHash3's 32-bit finalizer: every input bit gets a chance to flip every output bit.
func Mix(hash uint32) uint32 {
hash ^= hash >> 16
hash *= 0x85ebca6b
hash ^= hash >> 13
hash *= 0xc2b2ae35
hash ^= hash >> 16
return hash
}
// Score is a server's score for a key: the two hashes combined, then mixed. Without the mix, the
// highest bit where the servers' hashes differ would split them into two sides that each win half
// the keys, however many servers are on a side.
func Score(serverHash, keyHash uint32) uint32 { return Mix(serverHash ^ keyHash) }
var serverName = regexp.MustCompile(`^[a-z][a-z0-9-]{0,31}$`)
func CheckServers(servers []string) error {
if len(servers) == 0 {
return &PlacementError{"no-servers", "no servers to place keys on"}
}
if len(servers) > MaxServers {
return &PlacementError{"too-many", fmt.Sprintf("up to %d servers", MaxServers)}
}
seen := make(map[string]bool, len(servers))
for _, server := range servers {
if seen[server] || !serverName.MatchString(server) {
return &PlacementError{"bad-server", "server names are unique lowercase slugs: " + server}
}
seen[server] = true
}
return nil
}
func CheckKey(key string) error {
if len(key) == 0 || len(key) > MaxKeyBytes {
return &PlacementError{"bad-key", fmt.Sprintf("keys are 1 to %d bytes of UTF-8", MaxKeyBytes)}
}
return nil
}
// ByScore puts the highest score first. Equal scores go to the server whose name sorts first, so
// every caller agrees even on a tie.
func ByScore(x, y Ranked) int {
switch {
case x.Score > y.Score:
return -1
case x.Score < y.Score:
return 1
}
return strings.Compare(x.Server, y.Server)
}
func OwnerOf(servers []string, key string) (string, error) {
if err := CheckServers(servers); err != nil {
return "", err
}
if err := CheckKey(key); err != nil {
return "", err
}
keyHash := HashOf(key) // once per lookup, not once per server
var best Ranked
for i, server := range servers {
if next := (Ranked{server, Score(HashOf(server), keyHash)}); i == 0 || ByScore(next, best) < 0 {
best = next
}
}
return best.Server, nil
}Reading the TypeScriptMath.imul and >>> 0
JavaScript numbers are doubles, so hashOf multiplies with Math.imul, which keeps the low 32 bits exactly as unsigned 32-bit
multiplication would. XOR and imul give signed results; >>> 0 turns them back into a number from 0 to 2³² − 1, so the scores
compare correctly and match Go’s.
TextEncoder supplies the UTF-8 bytes, which is also how checkKey counts a key’s length: 129 copies of “é” is 129 characters but 258
bytes, and is refused. byScore subtracts two scores, which is safe because both
are below 2³².
Reading the Gouint32 wraps, and From is a pointer
uint32 arithmetic wraps around on its own, so HashOf and Mix are the published formulas with no masking. ByScore is a
total order, highest score and then name, so slices.SortFunc gives the same ranking
without needing a stable sort.
Change.From is a *string, nil when every copy was lost, which
encodes as null like the TypeScript. Empty lists start as []string{} for the same reason.
What is refusedServers, keys, and copies
An empty server list is no-servers, and more than 64 is too-many. Server names must be unique lowercase slugs (bad-server), keys 1 to 256 bytes (bad-key), and copies a whole number from 1 to 8 (bad-copies). Asking for more copies than there are servers gives every server.
Both languages run the same shared cases (Go skips one, a fraction of a copy, which its int can’t hold), and on hundreds of generated tiers check that removing a server
moves only its keys to their second choice, that adding one moves keys only onto it, and that
listing the servers in another order changes nothing.
04 / Try a decision
A server joins. Which photos move?
Decide before the feedback tells you.
Joining and leaving are one rule seen from two sides. A new server takes only the photos it now scores highest, and a leaving server’s photos fall to their second choice. No other score changes, so nothing else moves. In the lab, tick cache-e and only the outlined photos, the ones that moved, land on it.
05 / Follow the cost
One score per server, on every lookup.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Hash the key | O(L) | O(1) | Once per lookup, over the key’s L bytes. A server’s hash only changes with its name, so a tier can keep it. |
| Find the owner | O(S) | O(1) | One combine and mix per server, keeping the highest. No sort. |
| Rank every server | O(S log S) | O(S) | What ownersOf uses to take the first few as copies. |
| Plan a membership change | O(K × S log S) | O(K) | Two rankings for each of K keys, before and after. |
| Hash modulo the server count | O(L) | O(1) | One hash and one remainder, but most keys move when S changes. |
| Look up on a hash ring | O(L + log P) | O(P) | Consistent hashing: a binary search over P points kept in order, many points per server. |
Finding an owner scores every server, so a lookup costs O(S). With four cache servers that is four XORs and four mixes after hashing the key once. The lesson’s code also hashes each server’s name on every call to keep it short; a real tier hashes a name once, when the server joins.
With hundreds of servers, O(S) per lookup starts to matter. Consistent hashing, the other common answer, puts many points per server on a ring kept in sorted order and finds a key’s server with a binary search, O(log P). It pays for that with the ring’s memory and the points needed to spread keys evenly.
06 / Give it a real job
Take a server out without a cold cache.
With one copy of each photo, cache-c leaving still hurts: its 4 photos are gone, and the
first request for each resizes it again. So the tier keeps two copies. ownersOf takes a key’s first two servers in score order: cache-a ends up holding
14 photos, cache-b 11, cache-c 13, and cache-d 10.
Now plan cache-c’s exit before switching it off. planChange compares the two
tiers for every photo. 13 photos lose their copy on cache-c. Each of them gains exactly one
copy somewhere else, and each still has its other copy on a server that is staying, named in from. Copy those 13 thumbnails first, then remove cache-c, and no request
misses. That works because removing one server doesn’t change the order of the rest: a
photo’s third choice moves up to second.
It is the same property GitHub’s director relies on: each flow maps to “a pair of servers with a pre-determined order,” and it “leverages the state already stored on those servers to allow flows to complete after a server begins draining.” Two copies protect against one server at a time, though. If cache-c and cache-d leave together, photo-4, for one, loses both, because those were its two.
Adding a server is the mirror image. When cache-e joins a two-copy tier, 8 photos gain a copy on cache-e and drop their second choice, and nothing moves between the servers that were already there.
Rendezvous hashing runs on the servers and load balancers that place keys, behind your
requests; nothing in a component computes it. A fetch to github.com, for one, passes
through GitHub’s director, which uses a derivative of rendezvous hashing and, by its own README,
“is used in production to serve all traffic from GitHub’s datacenters.” A browser shouldn’t pick
those servers itself: every client placing keys has to see the same server list at the same moment,
and keeping that list agreed while servers fail or drain is a server-side job.
07 / Make the call
Rendezvous, a ring, or plain modulo?
Plain modulo is fine when the number of servers never changes, or when moving most keys is cheap: a nightly job that splits files across workers can recompute everything.
A ring is what nginx offers. With hash $key consistent, “the ketama consistent
hashing method will be used instead. The method ensures that only a few keys will be
remapped to different servers when a server is added to or removed from the group.” Its
lookups stay fast with many servers, and the documentation notes it is compatible with a
Perl client whose ketama_points parameter is set to 160. Rendezvous needs no ring
and no points, spreads keys evenly from the hash alone, and gives copies from the same ranking;
it costs a score per server per lookup.
Apache Ignite chose rendezvous for placing data. Its RendezvousAffinityFunction is an “Affinity function for partitioned cache based on
Highest Random Weight algorithm.” It places partitions rather than individual keys, and its scoring
is close to this lesson’s shape, combine and then mix: it will “pack partition number and nodeHash.hashCode
to long and mix it by hash function based on the Wang/Jenkins hash,” then sorts the nodes, lowest
value first. Which end counts as best doesn’t matter, as long as every node agrees.
What it doesn’t do: it knows nothing about load, so a photo everyone views keeps hitting one
server. The scores here use FNV-1a with no secret seed, so someone who chooses the keys can
pick ones that all land on one server; GitHub’s director seeds its siphash with a shared
secure key for that reason. It treats every server as equal; giving a bigger server more
keys needs a weighted score, which this lesson doesn’t cover. And it doesn’t decide who is
in the list. If two web servers disagree about whether cache-c is up, they send the same
photo to different places. GitHub’s design plans for that: when a proxy looks unhealthy,
“Each director does this independently,” and it “won't break connections even if directors
disagree on health state providing all proxies are active,” because every flow
already has its pair of servers.
SourcesDocumentation, source, and the paper’s record, checked 14 September 2026
- nginx,
ngx_http_upstream_module, thehashdirective. - GitHub Load Balancer Director: README, and GLB hashing design, which describes taking “a
siphashof a seed for the row … and the IP of each proxy server, then sort the proxy servers using that value.” - Apache Ignite 2.16.0,
RendezvousAffinityFunction.java. - Austin Appleby,
MurmurHash3.cpp, forfmix32. - Wikipedia, Rendezvous hashing: “Rendezvous hashing was invented by David Thaler and Chinya Ravishankar at the University of Michigan in 1996.”
- D. G. Thaler and C. V. Ravishankar, “Using name-based mappings to increase hit rates”, IEEE/ACM Transactions on Networking 6(1), 1–14, 1998. Only the bibliographic record was checked, not the paper.
08 / Take the idea with you
Explain a cache pick without saying “rendezvous.”
“Every server gives every key a random-looking score that depends only on the two of them, and the key goes to the highest. Take a server away and only its keys move, each to its next-highest. Add one and keys move only onto it.”
Before moving on, find something in your systems that is spread over machines by a key: sessions, uploads, queue partitions, tenants. Ask how many keys move when one machine leaves, and whether anything still holds a copy when it does.
Connections to follow nextRelated lessons
- Hash map uses the same FNV-1a to pick a bucket inside one process.
- Binary search is how a consistent-hashing ring finds a key’s server.
- Token bucket is another small piece of arithmetic that keeps a busy service steady.