Rendezvous Hashing (Highest Random Weight)

Rendezvous Hashing is a distributed hashing technique where every node independently computes a weighted score for a given key using a shared hash function, and the node with the highest score owns the key. It provides the same minimal-disruption remapping guarantees as consistent hashing without requiring a shared ring structure or virtual nodes.

Practical example

An L4 load balancer fleet uses Weighted Rendezvous Hashing so that every balancer instance, given the same backend pool list, independently routes a given client connection to the same backend — preserving connection affinity during backend scaling events without a centralized session store.

Rendezvous Hashing (also called Highest Random Weight, HRW) solves the same problem as Consistent Hashing — distributing keys across a dynamic set of nodes with minimal churn on membership change — but with a fundamentally different mechanism. Instead of placing nodes on a hash ring and walking clockwise, every client independently computes hash(key, node_id) for every node in the current membership set and selects the node yielding the maximum value. No shared ring state, no virtual node bookkeeping, and no coordination protocol is required; any client with the current member list arrives at the identical answer.

The critical property is that when a node is added or removed, only the keys that would have hashed highest for that specific node are remapped — statistically 1/N of the keyspace — and every other key-to-node assignment is untouched, matching consistent hashing’s minimal-disruption guarantee but derived from a stateless computation rather than a data structure. This makes it attractive for systems where maintaining a synchronized ring (with virtual node replication factors, rebalancing metadata, etc.) is undesirable, such as client-side sharding in CDN request routing, distributed cache client libraries, or fault-domain-aware load balancer selection.

The naive implementation is O(N) per key lookup since every node’s weight must be computed, which becomes a real bottleneck at high cardinality (thousands of nodes, millions of lookups/sec). Production systems mitigate this with weighted variants for heterogeneous capacity (multiplying the hash score by a node’s relative weight before comparison) and with tree-based or bucketed approximations that reduce the lookup to sub-linear time at the cost of exact HRW semantics. Weighted Rendezvous Hashing is notably used by Apache Cassandra’s token-aware clients in some configurations and by Google Maglev and similar L4 load balancers for consistent backend selection across a fleet without a coordinating control plane.

A subtle edge case: because every participant computes assignments independently from the same membership view, any transient divergence in the membership list (e.g., during a gossip convergence window) causes different clients to disagree on ownership simultaneously — there is no shared source of truth to arbitrate, unlike a centrally-updated hash ring service. This makes Rendezvous Hashing well-suited to read-heavy, cache-like workloads tolerant of brief misrouting, but risky for strongly consistent partitioned storage without an additional consensus layer reconciling membership views.