Design patterns and optimization · Intermediate

Choose owners with rendezvous hashing

Rank key-node scores and distinguish addition, removal, ties, replication, weighting and lookup cost.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Score each key and stable candidate identity
  2. Trace addition, removal and lookup cost
  3. Fix encoding, ties and compatibility
  4. Add replica and weighting rules explicitly
  5. Compare reassignment and scoring cost with fixed inputs
  6. Version cached rankings with their membership inputs
  7. Solve winner and runner-up exercises
  8. Ask Logeia about this articleCheck your understanding

Score each key and stable candidate identity

Rendezvous hashing deterministically scores each key-node pair and selects the highest score. It is also called highest-random-weight mapping, but does not draw fresh randomness for every lookup. Read hashing and partitioning first. Equal key, candidate set and scoring contract should produce equal ownership across clients. Its lookup procedure differs from searching points on a consistent-hash ring.

Use illustrative scores for order-7: A seventeen, B 81 and C 54, so B wins. Adding D at ninety moves that key to D. For order-8, A 91, B 24, C forty and D twelve leave A selected. These are teaching scores, not observed outputs of a named hash. Existing candidate rankings remain unchanged when D does not win, provided existing IDs and scoring rules remain stable.

Trace addition, removal and lookup cost

On addition, only keys for which the new candidate outranks the previous winner change. On removal, only keys owned by that candidate move to the next remaining score. Recomputing scores does not change existing relative rankings when their inputs stay stable. A simple lookup evaluates N candidates, which differs from ring search in cost and metadata. Compare actual membership sizes and caching opportunities instead of ranking methods by name.

Different candidate sets can give clients different winners. Independently excluding unreachable nodes can change authoritative ownership. Distinguish an alternate readable destination from permission to accept writes. Configuration generations, propagation and stale-owner refusal or redirection remain necessary. Rendezvous scoring does not agree on membership or copy data, even though it makes a consistent placement decision once those inputs have been supplied.

KeyABCDBefore to after
order-717815490B to D
order-891244012A to A

Fix encoding, ties and compatibility

Plain concatenation can make pairs ab,c and a,bc both encode as abc. Use unambiguous framing, with specified normalization, encoding, integer interpretation and hash version. Resolve equal scores deterministically, for example by stable identity. Arrival order as a tie-breaker can make clients disagree despite equivalent membership.

Do not use a process-randomized built-in hash for persistent placement without a compatibility contract. Cross-language ports need test vectors containing encoded input, scores and winner, not merely strings that look alike. A stable logical node ID need not be its IP address. Decide whether an address change should actually remap ownership. If identity and connection location are separated, their mapping still needs authoritative update handling. Determinism depends on every input convention, not only naming the same hash family.

Add replica and weighting rules explicitly

A replica candidate rule selects the top k distinct physical nodes, but failure-domain diversity may require additional constraints. All implementations must agree on that constrained selection procedure. Choosing top candidates is separate from durably storing their values or committing a write. Quorum and agreement rules still apply.

Capacity weighting needs a verified weighted scoring method; multiplying an arbitrary integer score by weight does not automatically give the desired assignment ratio. Check its formula, input distribution, ties and numerical precision, then measure finite-key distribution and movement. The worked table is unweighted. Changing weights is another placement change requiring data and authority migration. Key count also does not necessarily reflect bytes or hot-key traffic, so a proportional score policy is not a guarantee of balanced useful work.

Compare reassignment and scoring cost with fixed inputs

Hold keys and node identities fixed while measuring owners, movement, per-node counts, maximum load and lookup cost. Changed keys would mix input variation with placement variation. Check that addition moves affected keys only to the new node and removal changes only the old owner's assignments. Placement-property tests and completed live migration are different evidence.

Large candidate sets can make full scoring expensive. Hierarchical or restricted-candidate designs need their movement properties reverified. Small cache-server sets may favor the simplicity of evaluating every candidate. Range-query requirements can instead motivate range placement. The worked article is an algorithmic trace, not a measurement of weighted allocation or production lookup performance. Compare the complete required operation rather than treating a compact scoring definition as an unconditional implementation winner.

Version cached rankings with their membership inputs

Caching a key's ranking can reduce repeated scoring, but the cache must distinguish membership and weight generations. After adding winning D, indefinitely using an old cached B does not implement the new placement even if the scoring function itself is correct. Verify invalidation or generation selection together with the optimization. Stale requests still need authority-aware refusal or redirection at the old destination. This shows why a fast cached lookup and safe membership propagation are related but distinct tests. The retained ranking should identify the exact candidate set whose scores it summarizes rather than being treated as timeless information about the key.

Reproduce a lookup before and after invalidation using the same key and candidate generations. This distinguishes correct scoring from correct use of its current result. A cache optimization must preserve that contract as well as reduce computation.

Solve winner and runner-up exercises

For order-7 scores A seventeen, B 81, C 54 and D ninety, removing D selects B. The original top two are D and B; after removal they are B and C. State which candidate set the question uses. Ranking two candidates does not prove two stored replicas already exist.

Regenerating every node ID also changes existing scores and can destroy localized addition behavior. Preserve stable identity, encoding, membership generation and tie-breaking. The learning outcome explains lookup differences from a ring while retaining their shared obligations for migration and agreement.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 18

Choose a learning path