Skip to content
AfluidityAlgorithm Atlas
Distributed SystemsAll categories
CoreConcept & Pseudocode Entry

Rendezvous Hashing (Highest Random Weight / HRW)

Assigns each key to the server node s that maximizes hash(key, s), achieving uniform load and minimal O(K/N) key remapping when servers join or leave without maintaining a virtual-node ring.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Distributed Systems
Difficulty
Beginner
Family
Partitioning & Load Balancing
Tier
Core
Status
Reviewed
Review
AI Reviewed
Sources
1
Formulas
1
Relationships
1
Code example
Not ready
Visualization
Ready
Aliases
Highest Random Weight Hashing, HRW Hashing, Skeleton-Based Rendezvous Hashing

Overview

Rendezvous Hashing (also called Highest Random Weight or HRW hashing, Thaler & Ravishankar 1998) solves distributed key-to-server routing without a consistent-hashing ring or virtual nodes. Given a key k and a list of live servers S = {s_1, ..., s_N}, any client independently computes a fast hash w_i = hash(k, s_i) for each server and picks argmax_{s_i} w_i. If a server fails, only the 1/N fraction of keys mapped to that server move to their second-highest-weight server; all other keys remain untouched.

Core Concepts

highest random weight (HRW)minimal disruption O(K/N) remappingstateless client routingweighted exponential score

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(N) per lookup (or O(log N) with a skeleton tree)

Average

O(N)

Worst

O(N)

Space

O(N) server list (zero virtual-node ring table)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Rendezvous Hashing (Highest Random Weight / HRW) across input scales.

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO(N)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Worst-Case TimeO(N)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Working MemoryO(N) server list (zero virtual-node ring table)

1.53 MB

Standard Heap FitN=100,000

When to Use

  • Use Rendezvous (HRW) Hashing when distributing keys across a moderate number of cache or storage servers (e.g. N <= 500) and you want perfectly uniform balance and minimal key remapping without tuning virtual-node ring counts.
  • Use it when you need a deterministic top-r replica list or weighted node capacities.

When Not to Use

  • Avoid flat O(N) HRW evaluation when the cluster has tens of thousands of nodes and sub-microsecond O(log N) lookup is required (use a virtual-node consistent hash ring or skeleton-based HRW tree).

What It Does

  • Maps keys uniformly across N distributed cache or storage nodes with minimal O(K/N) key movement on node additions or removals
  • Provides a deterministic ranked preference list of k replica nodes per key without virtual-node ring hotspots

Use Cases

  • Distributed cache routing, CDN origin selection, and object storage shard placement (Ceph CRUSH, Apache Ignite)
  • Selecting top-k replica nodes for a key by taking the k servers with the highest hash weights
  • Weighted heterogeneous server routing via logarithmic capacity scaling -w_i / ln(u_i)

Inputs

  • Key k and set of available server identifiers S = {s_1, ..., s_N} (with optional capacity weights)

Outputs

  • Selected primary server s* = argmax_{s in S} hash(k, s) (or top-r replica list)

Key Formulas (1)

HRW Selection & Remapping Fraction

s·(k) = argmax_{s in S} H(k, s); P[s·(k) changes when nodeN+1 joins] = 1 / (N + 1)
s*(k) = argmax_{s in S} H(k, s); P[s*(k) changes when nodeN+1 joins] = 1 / (N + 1)

Achieves the theoretical minimum 1/(N+1) key movement bound with zero virtual nodes.

Pseudocode

  1. 1.Initialize bestServer = null, maxWeight = -infinity
  2. 2.For each live server s in cluster S:
  3. 3. Compute weight w = hash32(key + ':' + s.id)
  4. 4. If w > maxWeight: maxWeight = w; bestServer = s
  5. 5.Return bestServer

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

  1. Initialize bestServer = null, maxWeight = -infinity
  2. For each live server s in cluster S:
  3. Compute weight w = hash32(key + ':' + s.id)
  4. If w > maxWeight: maxWeight = w; bestServer = s
  5. Return bestServer

Canonical Example

Input
Key = 'user:42', Servers = ['nodeA', 'nodeB', 'nodeC'] with weights {nodeA: 0.81, nodeB: 0.94, nodeC: 0.37}
Output
Routes 'user:42' to 'nodeB' (highest weight 0.94); if nodeB fails, routes to 'nodeA' (0.81)
Explanation
Every client computes the same pseudo-random weights for (key, server) and picks the maximum without coordination.

Implementation Notes

  • For weighted servers with capacity w_i, score each server as -w_i / (-ln(hash_to_unit_interval(k, s_i))).

Common Pitfalls

  • Using a poorly mixed hash function like simple modular addition hash(k) + hash(s), which correlates server rankings across keys; use MurmurHash3, SipHash, or FNV-1a over (key || ':' || serverId).
  • Scaling node weights linearly as weight_i * hash(k, s_i) instead of -weight_i / ln(u_i), which biases distribution away from proportional share.

Interactive Mechanism Walkthrough & State Debugger

Iterative Convergence & State Trajectory
Rendezvous Hashing (Highest Random Weight / HRW) mechanism walkthrough step 1 of 5x₀x₁x₂x*
iteration kk = 0
state estimate x_k2.36828
residual |f(x_k)|3.92e-1
convergenceDescending gradient
Step 1 of 5: Initialize bestServer = null, maxWeight = -infinity

Notes

Concept entry for Rendezvous Hashing (Highest Random Weight / HRW): verified code implementation pending.

Sources (1)

What each reference supports for this entry.

Thaler & Ravishankar (1998) — Using Name-Based Mappings to Increase Hit Rates

Paper

IEEE/ACM Transactions on Networking paper introducing Highest Random Weight (Rendezvous) hashing.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative toConsistent Hashing Load Balancing

Distributed Systems · Extended

Achieves uniform load and minimal key movement by taking argmax_s H(k, s) instead of placing virtual nodes on a hash ring.

Compare with this

Relationships

View full relationship page
Alternative toConsistent Hashing Load Balancing

Achieves uniform load and minimal key movement by taking argmax_s H(k, s) instead of placing virtual nodes on a hash ring.

Related Algorithms

Consistent Hashing Load BalancingFNV-1a HashHash Table

Tags

Distributed SystemsHashingLoad BalancingSharding