Rendezvous hashing

Deep dive

How it works

In: a key, the node list (stable IDs, optional weights), replica count k · Out: the owner, or the top-k nodes by score · State: the node list and one precomputed seed per node · Cost: O(n) hashes per lookup

1. score(key, node) = mix(hash(key) ⊕ seed(node)), where seed(node) is a hash of the node's stable ID.
2. Owner = argmax score. Replicas = top k by score (in order: primary, secondary, ...).
3. Weighted: map the 64-bit score to u ∈ (0, 1) and use −w / ln(u). Ln(u) < 0, so larger w → larger score; P(node i wins) = wᵢ / Σw.
4. Large n: arrange nodes in a virtual tree (e.g. fan-out 8-16), apply HRW at each level: O(f · log_f n). Movement stays near-minimal.

key "user:42"   node A: 0x91..  node B: 0xE3..  node C: 0x4F..
                owner = B; replicas (k=2) = [B, A]
remove B → owner = A (only B's keys move; each goes to its own runner-up)

Code

fn mix(mut z: u64) -> u64 {                                   // splitmix64 finalizer
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
    z ^ (z >> 31)
}

pub fn hash_bytes(b: &[u8]) -> u64 {                          // stable FNV-1a + mix
    let mut h: u64 = 0xcbf29ce484222325;
    for &x in b { h = (h ^ x as u64).wrapping_mul(0x100000001b3); }
    mix(h)
}

#[derive(Clone)]
pub struct Node { pub id: String, pub weight: f64, seed: u64 }

impl Node {
    pub fn new(id: &str, weight: f64) -> Self {
        Node { id: id.to_string(), weight, seed: hash_bytes(id.as_bytes()) }
    }
}

#[inline]
fn score(key_hash: u64, n: &Node) -> u64 { mix(key_hash ^ n.seed) }

/// Unweighted owner. Ties (equal 64-bit scores) are astronomically rare; break by id.
pub fn owner<'a>(nodes: &'a [Node], key: &[u8]) -> Option<&'a Node> {
    let kh = hash_bytes(key);
    nodes.iter().max_by(|a, b| score(kh, a).cmp(&score(kh, b)).then_with(|| a.id.cmp(&b.id)))
}

#[inline]
fn weighted_score(key_hash: u64, n: &Node) -> f64 {
    // 53 random bits → u in (0, 1): never 0, so ln(u) is finite and negative.
    let u = ((score(key_hash, n) >> 11) as f64 + 0.5) / (1u64 << 53) as f64;
    -n.weight / u.ln()
}

/// Top-k by weighted score: primary first. O(n log k) via a small sorted buffer.
pub fn top_k<'a>(nodes: &'a [Node], key: &[u8], k: usize) -> Vec<&'a Node> {
    let kh = hash_bytes(key);
    let mut best: Vec<(f64, &Node)> = Vec::with_capacity(k + 1);
    for n in nodes {
        let s = weighted_score(kh, n);
        if best.len() == k && s <= best[k - 1].0 { continue; }
        let pos = best.partition_point(|&(b, _)| b > s);  // keep descending order
        best.insert(pos, (s, n));
        best.truncate(k);
    }
    best.into_iter().map(|(_, n)| n).collect()
}

fn main() {
    let nodes = vec![Node::new("a", 1.0), Node::new("b", 1.0), Node::new("c", 2.0)];
    let mut counts = [0u32; 3];
    for i in 0..100_000u32 {
        let o = top_k(&nodes, &i.to_le_bytes(), 1)[0];
        counts[nodes.iter().position(|n| n.id == o.id).unwrap()] += 1;
    }
    println!("{counts:?}"); // ≈ [25000, 25000, 50000]
}

Complexity and constants

• Unweighted: one mix per node, order of 1-2 ns each; 100 nodes ≈ 100-200 ns, comparable to a ring's cache-missing binary search.
• Weighted: adds an ln per node (order of 5-20 ns), so ≈ 1-2 µs for 100 nodes.
• Memory: the node list only; nothing proportional to keys or vnodes.
• Balance: each key's owner is an independent draw, so per-node load is binomial with relative spread ≈ 1/√(keys per node), with no vnode artifacts.

Efficiency

• Cost: unweighted, one mix per node at order of 1-2 ns each: 100 nodes is about 100-200 ns per key, comparable to a ring's cache-missing binary search. Weighted adds an ln per node (order of 5-20 ns): about 1-2 µs for 100 nodes. Memory is the node list only. Bound: compute, linear in n.
• Levers:
  • precompute seed(node) and vectorize the n mixes (SIMD over seeds) — one key hash plus n mixes — all lookups
  • cache the owner per key or key range, invalidate on membership change — O(1) for repeated keys — hot keys, stable clusters
  • store each key's winning score; on node add compute only the new node's score — one hash per key instead of n — rebalancing
  • hierarchical (skeleton) form with fan-out 8-16 — O(f · log_f n) instead of O(n) — thousands of nodes
  • precomputed forwarding table (GLB Director) — O(1) per packet — per-packet paths
• Naive → standard → state of the art:
  • hash(key) mod n · O(1) but reshuffles about all keys when n changes
  • rendezvous scan · O(n) mixes, 1/n of keys move
  • seeded SIMD scan, owner cache or skeleton tree · order of 100 ns for n = 100; O(log n) for large n

Implementation notes

• Precompute and store seed(node); the per-key work is then one key hash + n mixes, which vectorizes well (SIMD over node seeds).
• Combine with a strong 64-bit mixer, not key ^ node alone: a weak combiner correlates scores across nodes and skews load.
• Replica sets from top-k have the "spread on failure" property: when a node dies, its keys' new replicas are scattered across all nodes, so re-replication runs in parallel.
• For thousands of nodes use the hierarchical (skeleton) form or cache owner per key range.
• Keep node IDs stable (names or UUIDs); hashing addresses makes restarts reshuffle.
• Cost: at n = 100 nodes a scalar loop is order of 100-200 ns per key; when the same keys repeat, cache the owner and invalidate on membership change.
• Adding a node needs no full recomputation: store each key's winning score, compute only the new node's score, and move the key if it wins. One hash per key.
• Ceph CRUSH straw2 buckets pick the maximum of ln(u) / w, which is the same ordering as −w/ln(u).

Pitfalls

• Using w * score (linear weighting): shares are not proportional to w. Use −w/ln(u).
• u = 0 from a zero hash → ln(0) = −∞ → score 0 or NaN; map to the open interval as above.
• Floating-point scores must be computed identically on every client (same formula, IEEE-754 f64; avoid fast-math), or clients disagree on near-ties.
• O(n) on a per-packet path with large n: precompute a table (Maglev).

Variants and alternatives

In production

Data grids: Apache Ignite (RendezvousAffinityFunction). Load balancing: GitHub GLB Director (builds its forwarding table with a variant of rendezvous hashing), Microsoft CARP for proxy arrays. Cache routing: Meta's mcrouter (RendezvousHashFunc). Storage: Ceph CRUSH straw2 buckets (same ordering), Tahoe-LAFS server selection (permuted ring, a variant of HRW).

Implementations

Sources

• David G. Thaler, Chinya V. Ravishankar, Using Name-Based Mappings to Increase Hit Rates, IEEE/ACM Transactions on Networking, 1998. paper
• Christian Schindelhauer, Gunnar Schomaker, Weighted Distributed Hash Tables, SPAA 2005. paper
• GitHub, GLB Director Hashing: Generating the GLB Forwarding Table. docs
• Sage Weil et al., CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data, SC 2006. paper