Senior · Algorithms

Distribute keys without remapping every key on membership change

A service assigns keys with hash(key) % nodeCount. Adding a node moves many keys. What does rendezvous hashing change, and what does it not solve?

Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.

EXAMPLE · FRAGMENT UNLESS A COMPLETE PROGRAM IS SHOWN

package main

import (
	"crypto/sha256"
	"encoding/binary"
	"fmt"
)

func owner(key string, nodes []string) string {
	best := ""
	var high uint64
	for _, node := range nodes {
		sum := sha256.Sum256([]byte(fmt.Sprintf("%d:%s%d:%s", len(key), key, len(node), node)))
		score := binary.BigEndian.Uint64(sum[:8])
		if best == "" || score > high || (score == high && node < best) {
			best = node
			high = score
		}
	}
	return best
}
func main() {
	fmt.Println(owner("order-7", []string{"a", "b", "c"}) == owner("order-7", []string{"c", "a", "b"}))
}

Reveal a strong answer

Compute a deterministic score for each key–node pair and choose the highest under an explicit tie rule. Adding or removing a node changes winners only where membership affects the maximum, under the chosen scoring model. Plain modulo routing changes the partition formula for many keys.
Every participant must use the same stable node identity, membership view, hash encoding and weighting policy. Length-prefix or otherwise unambiguously encode the pair, so concatenated strings cannot represent different logical pairs. The example uses unweighted scoring and a deterministic lexical tie break.
Hash-based routing is not replication, durability, consensus or an authentication primitive. Membership changes still need migration, stale-owner handling, retries and capacity policy. Hot keys remain hot. Weighted nodes and adversarial keys need a reviewed extension; do not claim that a particular database protocol uses this exact scheme without checking it.

Common trap

A stable hash function does not make divergent membership views agree or preserve data during a migration.

Complexity & use

Naive unweighted lookup scores every node: O(N) hash operations per key; O(1) extra space beyond inputs, with hash input length included in cost.

Try it

Compare key assignments before and after adding a node, then explain how readers find data while migration is incomplete.

Worked solution

Use a stable pair encoding and choose the greatest score independently of the order nodes were listed, with an explicit tie rule. Keep membership versioned and define how owners transfer data or redirect requests. Measure distribution and hot keys on realistic input; do not present expected balance as a deterministic guarantee for every small key set.

Change the constraint

When would a hash ring or precomputed partition table be preferable to scanning every node per lookup?

How did you do?

Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.

Not marked. Progress stays on this browser, separate from course completion.

Primary references

Checked 2026-10-28. Use documentation for your pinned runtime, driver and tool version.