Weighted rendezvous vs consistent hash ring

Weighted rendezvous hashing vs consistent hash ring is a choice between computing a capacity-aware score on every lookup and searching a precomputed ring of node positions.

Both approaches keep most keys on the same owner when membership changes. They differ in how they express weights, where they keep metadata, and which keys move after one capacity changes.

For small candidate sets with changing weights, weighted rendezvous is usually cleaner. Use a ring when lookup speed or an existing token-based storage layout matters more than exact expected shares.

Weighted rendezvous hashing vs consistent hash ring

The original highest random weight paper assigns every key-node pair a deterministic random score. The node with the highest score owns the key.

If a node disappears, scores for the surviving nodes do not change. Only keys owned by the missing node need another winner.

The original consistent hashing paper defines a broader goal: a hash function should change little when its range changes.

The familiar ring implementation hashes nodes and keys onto a circle. A key belongs to the first node position clockwise from its own position.

A physical node normally receives many virtual positions. Those virtual nodes smooth random arc lengths and give the operator a way to approximate different capacities.

Fanout's consistent hashing guide builds the ring and its movement rule from a small worked example.

Multiplying a uniform score by weight is wrong

A common weighted rendezvous shortcut takes a uniform hash value u and compares weight times u. That biases the result, but it does not make win probability proportional to weight.

Take node A with weight 1 and node B with weight 2. Let both nodes draw independent uniform values between zero and one.

B wins whenever 2 times uB is greater than uA. When uB is at least 0.5, B always wins. That half of B's possible draws already contributes probability 0.5.

When uB is below 0.5, B's average win probability across that half is 0.5. This contributes another 0.25, so B wins 0.75 of all keys.

The requested capacity share was 2 divided by 3, or about 0.667. Raw multiplication produced 0.75 instead.

More nodes make the error harder to spot. A score can look weight aware in a quick simulation while assigning the wrong long-run fraction.

The logarithmic score gives proportional shares

The weighted distributed hash tables paper develops a logarithmic method for heterogeneous nodes.

For each key and node, turn the hash into u in the interval above zero through one. Compute negative ln(u) divided by the node's weight, then choose the smallest value.

An equivalent form computes negative weight divided by ln(u) and chooses the largest value.

Negative ln(u) behaves like an exponential random variable. Dividing by weight gives each node an exponential clock whose rate equals that weight.

The chance that one clock rings first is its rate divided by the sum of all rates. Weights 1, 2, and 3 therefore receive expected shares 1/6, 2/6, and 3/6.

The result is an expectation. A finite set of keys still has sampling variance, and a poor hash can add bias. The formula does not promise exactly 3,000 keys out of every 6,000 to the largest node.

It does make the target probability exact without rounding a weight into a chosen number of virtual nodes.

Reweighting changes one competition

Suppose nodes A, B, and C have stable identities. Raising B's weight changes only B's score for each key.

B can steal a key from A or C when its new score passes the old winner. A key cannot move directly from A to C because their scores and relative order did not change.

Lowering B's weight has the reverse property. Keys can leave B for their next-highest candidate, but keys already owned by A cannot jump to C because of B's change.

That movement rule depends on keeping the key hash, node identities, and score function stable. Renaming every node or changing the hash seed creates a different competition and can remap almost everything.

Adding a new node is similarly local. The newcomer takes only keys where its score beats every existing score. Removing it returns those keys to their previous best survivor.

Capacity changes do not require rebuilding a shared geometric structure.

Fanout's weighted Jump Hash guide explains a different two-layer approach where logical buckets carry the weights.

A weighted ring approximates capacity with positions

A ring gives a larger node more virtual positions. For weights 1, 2, and 3, an operator might create 100, 200, and 300 positions.

Those counts are proportional, but the owned keyspace depends on the random arc before each position. The resulting physical shares fluctuate around 1/6, 2/6, and 3/6.

More virtual nodes reduce that variance and increase metadata. The ring must store or reproduce every position, sort them, and map each position back to a physical node.

Some systems place tokens deliberately instead of hashing them at random. That can improve balance, but now the control plane owns token allocation, collision rules, and movement planning.

Changing a ring weight means adding or removing positions. Each changed position captures or releases its clockwise arc, so movement depends on the exact token edit rather than only the final weight ratio.

The ring is still consistent: most keys stay put. It simply expresses capacity through a discretized placement map instead of a per-key probability race.

Lookup cost points in the other direction

Plain weighted rendezvous scores every candidate node. A lookup takes work proportional to the number of nodes and needs no virtual-node index.

A ring hashes the key once and performs a binary search over the sorted positions. With N physical nodes and V positions per node, lookup work grows with the logarithm of N times V.

That distinction barely matters for five cache servers. It can dominate when thousands of backends receive millions of lookups per second.

A ring uses memory and update logic to make each lookup cheaper. Rendezvous repeats the score computation while keeping placement metadata small and weighting direct.

Do not compare Big O alone. Hash cost, cache locality, vectorization, membership update rate, and the number of candidates after topology filtering all affect the measured crossover.

A common compromise narrows the candidate set first, then runs weighted rendezvous inside that set. The outer topology rule and inner capacity rule should be tested as one placement function.

Removal spreads work differently

When one rendezvous node fails, its keys fall to their second-highest surviving scores. Across many keys, that work spreads over all remaining nodes according to their weights.

On a simple ring, a removed position hands its arc to the next clockwise position. Virtual nodes spread one physical node across the circle, so its total keyspace can still land on many survivors.

The number and placement of virtual nodes control how evenly that failed share disperses. Weighted rendezvous gets broad dispersal from independent per-key rankings without arranging tokens.

Neither algorithm decides whether moving a key is safe. A storage system still needs replication, handoff, version checks, and a policy for reads during migration.

For request affinity, recomputing an owner may be enough. For durable shards, placement and data movement must remain separate operations.

Choose from the membership pattern

Use weighted rendezvous when the candidate set is modest, nodes have arbitrary stable IDs, and capacities change independently.

It is also a good fit when removing one node should spread its keys across all survivors without maintaining hundreds of virtual positions per node.

Use a consistent hash ring when the system already exposes token ranges, operators need direct range control, or lookup volume makes a linear candidate scan too expensive.

Measure four outputs with the same key corpus: physical share, keys moved after add or remove, keys moved after reweighting, and lookup time.

For weighted rendezvous, use the logarithmic score rather than weight times a uniform hash. For a ring, test finite virtual-node variance instead of assuming proportional token counts create exact shares.

The system design course connects these placement choices to replication and migration, where the cost of a changed owner becomes concrete.