Consistent Hashing

---
name: consistent-hashing
description: >
  Stable key-to-node placement across membership changes: modulo remapping, consistent-hash
  rings, virtual points, rendezvous hashing, collision-safe Java implementations, hash
  contracts, replica selection, weighting, testing and membership handoff. Use when changing
  node count causes a miss storm or migration, ownership is uneven, or placement relies on
  Object.hashCode. Does not choose the shard key (sharding-and-partitioning), repair hot keys
  (hot-partitions-and-rebalancing), define cache topology
  (cache-sharding-and-replication), or balance interchangeable replicas
  (load-balancing-and-routing).
---

# Consistent Hashing

## Purpose

Own one function: given a key and a set of nodes, which node holds it — and how much of that
mapping survives when a node joins or leaves. Nothing else in the partitioning family
computes placement; this skill is where any hashing arithmetic belongs.

With a sufficiently uniform hash, `hash(key) % N` can distribute keys evenly, but changing N
can remap a large fraction depending on the divisors and node-index mapping. A cache can incur
miss/refill traffic; a store may need to migrate changed ownership. The operational cost depends
on the moved keys' bytes and request share, surviving copies and the handoff/refill policy.
Adding capacity can trigger overload when those costs exceed the recovery budget; key movement
alone does not establish a miss storm or outage.
The second failure is subtler: a ring with one point per node is _not_ well balanced, so a
naive implementation gets minimal disruption while handing one node several times another's
share.

## Workflow

Reuse the existing placement/configuration and supplied workload evidence before asking questions.
Establish whether the owner holds authoritative state, a recomputable cache entry or only affinity;
ask only about unresolved durability, failure-domain or movement constraints that change the choice.
Keep a sound current mapping when it meets those constraints. Apply only the relevant branches below.

1. **State the disruption and migration budget.** How many keys, bytes and requests may
   change owner, at what transfer rate, and under what availability target? `% N` can remap
   a large fraction; with equal nodes, a ring or rendezvous moves about K/(N+1) on a join and
   the removed node's approximately K/N share on a removal.
2. **Count the nodes.** With a small membership, rendezvous hashing is fewer
   moving parts than a ring and needs no virtual-node tuning. A ring earns its complexity at
   larger N or where lookup must be sub-linear.
3. **Specify the placement contract completely:** algorithm and variant, seed, byte encoding,
   field framing, signed/unsigned ordering, virtual-point format and membership epoch. Prove
   cross-runtime agreement with golden vectors. MurmurHash3 or xxHash can be suitable when
   the exact implementation is pinned. See
   `references/mapping-functions.md` for what disqualifies the obvious candidates.
4. **Pick V by measurement, not by folklore.** Simulate representative keys, bytes, request
   rates and per-key cost over relevant node counts and seeds. Raise virtual points until the
   worst load/mean for the relevant resource is inside tolerance, within a rebuild/memory budget. If skew is dominated by
   an indivisible hot key or poor hashing, more points are not the remedy. Measure lookup and rebuild cost.
5. **For a ring, implement the wrap-around explicitly.** `ceilingEntry(h)` returning `null` means the key
   hashed past the last point on the ring and belongs to the first entry. This single branch
   is the most commonly omitted line in the pattern.
6. **Separate invariants from statistical expectations.** For primary ownership with existing points unchanged,
   a join may move keys only to the new node; a removal may move only the removed node's
   keys. Measure movement against K/(N+1) or K/N using a justified tolerance, not a hard
   upper bound. See `references/ring-in-java.md` for implementation and tests.
7. **Model heterogeneous capacity explicitly.** Proportional virtual-point counts are one
   coarse mechanism, but CPU, memory, I/O and workload costs may not scale together. Prefer
   fixed logical partitions or an assignment service when placement needs constraints.
8. **Choose the membership transition from the state contract.** For authoritative state, propose a new epoch, copy and verify the newly
   owned ranges, coordinate reads/writes during handoff, activate the epoch, and retire old
   owners only after stale clients and in-flight work are bounded. Minimal remapping is not a
   migration protocol. Disposable cache entries may instead refill from an authoritative source
   if origin capacity, staleness and recovery budgets permit; do not mandate copying them.

## Decision block

For Java changes, inspect compiler release/toolchains, runtime images and resolved hash
library versions first. The ring example requires Java 16+ syntax/APIs and Guava; this is
an example prerequisite, not authorization to upgrade the target or add a dependency.
If topology or workload evidence is missing, keep the algorithm/V recommendation conditional
and identify the simulation or measurement needed. Deliver the placement contract, chosen or
retained trade-off, primary/replica movement and balance evidence, and handoff risks. State what
new evidence would change the decision; stop when remaining unknowns do not change it. Keep simple reviews concise.

```text
Use a ring with virtual nodes when:
- membership changes are routine (autoscaling, rolling replacement) and the disruption
  budget forbids remapping the whole keyspace
- N is large enough that O(log N) lookup matters, or nodes have different capacities and
  weighting by virtual-node count is the natural expression of that
Use rendezvous (highest random weight) hashing when:
- N is small enough for O(N) hashes per lookup within the measured budget; it avoids
  virtual-node tuning and gives probabilistically even shares, even with frequent churn
- you need the ordered list of candidates for a key (primary, then replicas) — rendezvous
  produces it directly, with probabilistic balance under a suitable hash
Use bounded-load consistent hashing when:
- the chosen algorithm's capacity unit matches the workload, allocation state is agreed,
  and displacement is acceptable; a key-count cap alone does not bound bytes or QPS
Use hash(key) % N when:
- N is fixed for the lifetime of the data, and changing it is understood to be a full
  migration — a fixed set of logical partitions, for example, later mapped to physical nodes
Prefer a directory (sharding-and-partitioning) instead when:
- placement must be decided per key rather than computed — pinning a known-large tenant to
  its own node is a placement policy, and no hash function expresses it
```

## Rules

- `hash(key) % N` can remap a large fraction when N changes. For uniform residues on an
  N-to-N+1 change, about N/(N+1) move; not literally every key. Fix logical partition count
  independently of physical membership, or explicitly budget a rehash migration.
- With equal nodes, a join moves **about K/(N+1)** keys to the new node; removing one moves
  its **about K/N** share. These are expectations over the hash and key population. This is
  not a guarantee for a particular key set, and it says nothing about how much _traffic_
  moves.
- **One point per node has high variance.** The shares are the gaps between N random points
  on a circle; virtual nodes
  exist for that, not for the disruption property, which the plain ring already has.
- Without virtual nodes, removing a node transfers its entire share to one successor. That
  successor's increment equals the failed node's share; it is not necessarily a doubling.
  With V virtual points the departing ranges usually spread across several successors.
- V costs memory and lookup time: the ring holds `V × N` entries, so lookup is O(log(V×N))
  and construction is O(V×N log(V×N)) with ordinary ordered-map insertion. Rebuild, snapshot
  publication and cache effects must be measured; V in the thousands per node is a data
  structure, not merely a tuning knob.
- **The hash must agree across all participants using the same placement-contract version.** Two
  clients that disagree about placement are two clients writing the same key to different
  owners. This rules out default `Object.hashCode()` (identity-based), record and enum `hashCode()`
  (unspecified), and any library hash documented as version-unstable — Guava's
  `Hashing.goodFastHash` says so explicitly, while `Hashing.murmur3_128()` names a fixed
  algorithm. Changing the hash/seed or encoding is a versioned remapping and migration decision,
  not a harmless library or key-format cleanup.
- `String.hashCode()` **is** specified and deterministic, but it is only 32 bits and was not
  designed as a placement hash. Its distribution depends on the actual key set; do not infer
  pathological clustering from prefixes alone. Evaluate representative keys and prefer a
  pinned 64-bit-or-wider hash with good avalanche. A cryptographic or keyed hash may be
  justified for adversarial keys, at additional CPU cost.
- Consistent hashing distributes **keys**, never **traffic**. A perfectly even ring with one
  celebrity key still has one saturated node. That is not a hashing bug and no value of V
  fixes it — the diagnosis and the repairs are `hot-partitions-and-rebalancing`.
- Every participant must agree on the ring: the membership epoch, node set and weights, the
  virtual-node count, the full hash contract, and the exact string hashed to place a virtual
  node (`"node-3#7"` is not
  `"node-3-7"`). Version the membership and treat a change as a coordinated deployment, or
  route through one component that owns it. During a transition, old and new epochs need an
  explicit handoff and fencing policy; eventual membership dissemination alone permits
  split ownership and lost writes.
- Replication follows the ring by walking clockwise to the next R **distinct physical** nodes
  — skipping further virtual nodes of a node already chosen. Forgetting the distinctness
  check places every replica of a key on one machine, which is the failure the replication
  was bought to prevent.
  Distinct nodes can still share a host, rack or zone: define and enforce the required failure-domain
  and residency policy. Replica-set changes must be measured separately from primary movement;
  a key whose primary stays put can still need a new replica. Constrained placement may require an
  assignment layer, and its movement rules need separate verification.
- Do not use this to spread requests over interchangeable replicas. Consistent hashing pins a
  key to an owner deliberately; a least-request policy deliberately does not, and
  `load-balancing-and-routing` owns that decision.

## References

- [Consistent hashing and random trees](https://www.cs.princeton.edu/courses/archive/fall09/cos518/papers/chash.pdf)
  — the original consistent-hashing model and disruption result.

- [The ring in Java](references/ring-in-java.md) — a collision-safe `TreeMap<RingPoint, String>` ring with
  virtual nodes, add and remove, the wrap-around branch, replica selection across distinct
  physical nodes, the hash-stability requirement in code, and a test that measures the
  fraction of keys that move when a node is added. Read when implementing or reviewing
  placement code.
- [Choosing the mapping function](references/mapping-functions.md) — modulo, ring with
  virtual nodes, rendezvous and bounded-load compared on disruption, lookup cost,
  distribution quality and implementation complexity, with a decision table and the hash
  function shortlist. Read when choosing between them, or when justifying a ring over the
  simpler option.