Rendezvous Hashing Interview Questions: Membership Changes and Weighted Nodes

Rendezvous hashing interview questions test whether you can explain what moves when membership changes. Saying “consistent hashing minimizes movement” is incomplete: you should identify which keys move, why unaffected rankings stay stable, and how weighted ownership differs from real server load.

The central rule is rank each key against every eligible node using a stable key–node score. The highest score wins in the unweighted construction. Removing a node exposes the next surviving score; adding one changes a key's owner only when the newcomer outranks its current owner.

Evidence boundary: RFC 2991 describes highest-random-weight routing as an informational discussion. The weighted formula below is also described in an expired IETF draft, which is work in progress rather than an adopted standard. Membership tables, probability derivations, and design recommendations here are original exercises, not candidate reports.

Use Debug Round-Robin and Consistent-Hash Routing to practice the distinction between deterministic ownership and a policy that reacts to instantaneous load. Both are useful, but they solve different contracts.

What exactly goes into the score?

For key k and node n, compute a deterministic hash of a canonical encoding of the pair. Choose the eligible node with the highest resulting score. RFC 2991 discusses this highest-random-weight approach in the context of multipath routing.

A stable node identifier matters more than its position in an array. Hashing (key, list_index) means removing the first node changes the identities of every subsequent entry. That breaks the stability argument even though the selection loop still looks like rendezvous hashing.

Specify the encoding, hash algorithm, seed, score width, and tie-breaking rule. Naively concatenating strings can make (ab,c) indistinguishable from (a,bc). Length prefixes or another unambiguous format prevent that collision of representations. Every client must use the same bytes and interpret the score the same way.

Use a stable node ID to break exact score ties. Otherwise, two clients with different list order may choose different owners for the same key. Do not rely on a language's process-randomized hash for a cross-process protocol. Determinism includes restarts, deployment versions, and implementations in different languages.

The basic lookup evaluates N scores for N nodes, so its straightforward cost is O(N). It needs no ring of virtual positions. That can be attractive for a modest membership set, but a very large set still makes per-request hashing expensive. State the actual lookup cost before claiming simplicity translates into cheap routing.

Trace node removal without hand-waving

This original score table deliberately uses small illustrative numbers. They are not outputs from a production hash function.

Key	A	B	C	Original owner
p	90	70	20	A
q	40	95	60	B
r	30	50	99	C

Remove B. Key p remains on A because its surviving scores did not change. Key r remains on C for the same reason. Key q moves to C, its highest surviving score. Only keys formerly owned by B need new owners.

That conclusion follows from stable rankings, not from the particular numbers. If the removed node was not a key's winner, deleting it cannot change which remaining score is highest. If it was the winner, the next eligible node wins.

Under an idealized symmetric hash model, each of N equal nodes owns an expected fraction 1/N of keys. Removing one therefore moves about 1/N of the old key population in expectation. A finite key set need not match that fraction exactly. A hot key can make a small key-count change into a large traffic change.

Now add D to the original three-node membership. Give D scores 85 for p, 98 for q, and 10 for r. The resulting owners are A, D, and C. Only q moves because D outranks its old winner. Under the same symmetric model, a new equal node receives an expected 1/(N+1) of keys after joining.

Do not confuse removing B and then adding D with adding D to the original set. Name the old and new memberships in your trace. Many apparently contradictory movement calculations compare different starting states.

Why is multiplying a score by weight usually wrong?

Suppose A has weight two and B has weight one. A tempting rule chooses the maximum of 2 × U_A and U_B, where the U values are independent uniform samples on the interval from zero to one. That rule does not give A its intended two-thirds share.

The original derivation is short. Conditional on U_A=u below one-half, A wins with probability 2u. Above one-half, A always wins. Therefore:

P(A wins) = integral(0 to 1/2, 2u du)
          + integral(1/2 to 1, 1 du)
          = 1/4 + 1/2
          = 3/4

Three-quarters is different from two-thirds. “Multiply by weight” changes the distribution of winning scores, so a plausible-looking weighted implementation can systematically overallocate a node.

One weighted construction transforms each deterministic uniform score U_i into an exponential race time:

T_i = -log(U_i) / weight_i
choose the smallest T_i

Under independent ideal uniform scores and positive weights, the probability that node i wins is its weight divided by the sum of weights. The equivalent maximum-score form is -weight_i / log(U_i).

The weighted HRW draft describes that form. Its expired status means it is evidence for a proposed mechanism, not a mandate for your system. RFC 2992 provides a separate routing comparison focused on equal-cost multipath behavior. The probability claim here follows from the explicitly stated exponential-race model.

What numerical and membership details can break weighting?

Convert hash bits into U strictly between zero and one. U=0 makes the logarithm undefined; U=1 produces a zero race time. Document the conversion and test its endpoint behavior. Floating-point rounding can introduce an endpoint even when the mathematical formula appears to exclude one.

Weights should be positive finite values for eligible nodes. Treat a zero-capacity or unavailable node as excluded according to an explicit membership policy rather than letting division by zero decide its fate. Reject negative weights and nonfinite values at configuration boundaries.

Multiplying every weight by the same positive constant leaves the winner unchanged: every race time is divided by that constant. Normalizing all weights by their sum also preserves the ranking. A configuration update that changes only normalization should therefore not move keys in a correctly implemented formula.

Changing one node's relative weight can move keys to or from that node. Rankings among the other nodes remain unchanged if their relative weights and scores remain unchanged. This is a useful invariant for tests and a way to distinguish real weight changes from encoding or hash-version errors.

Weight measures the capacity model you supplied. CPU cores, memory, connection limits, and storage space are not interchangeable. Choose a weight for the constrained resource, and monitor whether its ownership share approximates useful load. Changing weights frequently in response to noisy measurements can cause churn even when membership stays fixed.

Does rendezvous hashing guarantee balanced load?

It balances expected ownership under its assumptions; it does not guarantee equal requests, bytes, latency, or work. Ten thousand small objects on one node can be cheaper than one extremely hot object on another. Weighted key counts can look correct while a server is saturated.

Ask what a “key” means: user ID, cache item, partition, or request. Hashing each request with a changing identifier may distribute traffic while destroying cache affinity. Hashing an entire tenant to one server preserves affinity but can concentrate a large tenant's workload.

Replication can select the top R distinct eligible nodes from the ranking. That is a placement rule, not a complete durability or availability protocol. If the first three ranked nodes share one failure domain, three replicas may still have one correlated point of failure. Failure-domain constraints require an additional explicit policy.

When membership changes, readers and writers can disagree about ownership until they share the same configuration. Version memberships, define when each version becomes active, and plan migration or fallback reads. A mathematically stable ranking does not atomically copy stored data.

For a cache, accepting a miss and refilling may be sufficient. For durable storage, ownership transfer needs evidence that the new owner has the data before the old copy disappears. Explain acknowledgments, old-version reads, or a staged cutover in terms of the system's consistency requirements.

How do you test more than a distribution histogram?

Build deterministic fixtures for the three-key table. Remove B and assert that only q moves. Add D to the original membership and assert the same result. Permute input node order and require identical ownership. Restart the process and compare mappings again.

Across a larger fixed key population, assert the stronger invariants: removal never moves a key owned by a surviving node; addition moves keys only to the newcomer. These tests catch accidental dependence on membership length or list position even when aggregate counts appear balanced.

For weights two and one, compare observed ownership against two-thirds over many deterministic hash samples. Also implement the deliberately wrong multiplication rule and observe its roughly three-quarter share. This is a calibration exercise under a chosen hash model, not proof of exact production load.

Test malformed weights, duplicate node IDs, score ties, Unicode encodings, and mixed client versions. A duplicate ID means two physical servers may be treated as the same logical candidate. A different normalization or serialization between languages can silently create split ownership.

Finally, measure actual traffic and migration work separately from key movement. Record keys moved, bytes copied, cache misses, and load concentration. The algorithm's movement property predicts one of these metrics directly; the others depend on workload and operational choices.

Practice a membership change as a complete answer

Start with a score table and state the winner rule. Explain removal, addition, and the expected movement fraction with its assumptions. Derive the weighted formula or at least demonstrate why multiplying a uniform score by weight is biased. Finish by naming the membership-version and data-transfer boundaries.

That sequence gives you a score table, a movement prediction, and a concrete configuration boundary to defend. It also makes clear which guarantees come from hashing and which need a separate routing, replication, or migration protocol.

Practice question	What to explain
Consistent Hashing Ring with Virtual Nodes for Shard Rebalancing	Contrast a virtual-node ring with per-node rankings.
Debug a Round-Robin Load Balancer, Then Implement Consistent Hashing	Check stable ownership when switching routing policies.
Debug Round-Robin and Consistent-Hash Routing	Test membership order and deterministic selection.
Design a Distributed Key-Value Store	Separate placement from durable replication and migration.
Job Dispatcher with Least-Loaded, Round-Robin Assignment and Executor Removal	Contrast load-aware dispatch with fixed key ownership.

Start with Consistent Hashing Ring with Virtual Nodes for Shard Rebalancing and write your assumptions before answering. Compare your explanation against the specific invariants above, then use a second question to test whether the reasoning transfers to a different constraint.

Sources and Further Reading

• RFC 2991: Multipath Issues in Unicast and Multicast Next-Hop Selection
• Expired IETF draft: Weighted HRW
• RFC 2992: Analysis of an Equal-Cost Multi-Path Algorithm