Notespartitioning🌱 seedling

Consistent Hashing

Also: Hash Ring · Virtual Nodes · Vnodes · Jump Consistent Hash · Rendezvous Hashing · Highest Random Weight

A way to map hashed keys to nodes so that adding or removing one of N nodes moves only about 1/N of the keys, instead of nearly all of them as with hash mod N.

Why it exists

With hash mod N, going from N to N+1 nodes keeps a key in place only when h mod N = h mod (N+1): about 1 in N+1 keys. From 4 to 5 nodes, ~80% of the data moves.

How it works

  • Ring: hash nodes and keys onto the same circle; a key belongs to the first node clockwise. A new node takes over one arc from one neighbour.
  • Virtual nodes: each machine gets many points on the ring, so arcs even out and a departing node's load spreads over many survivors instead of one neighbour.
  • Rendezvous (HRW): score every (key, node) pair with a hash and pick the highest; removing a node only moves the keys it won.
  • Jump consistent hash: no stored state, about five lines of code, perfectly even; buckets must be numbered 0..n−1, so you can only add or remove at the end.

Trade-offs

Gains Costs
~1/N of keys move per membership change one point per node gives uneven arcs
no central rebalancing plan needed vnodes add neighbours per node and slow cluster-wide repair
works for caches and stores alike ordering is lost, like any Hash Partitioning

In practice

  • Cassandra used 256 random tokens per node in 2.x; 4.0 defaults to 16, with a deterministic token allocator doing the balancing.
  • Load balancers and caches use it for affinity; Discord's data services route all requests for a channel to one instance to coalesce reads.

Pitfalls

  • Treating "consistent hashing" as a synonym for "hash partitioning": it is specifically the stable mapping to nodes.
  • Few nodes, one token each: load can be badly skewed.

Recall

These cards are also in your review deck, scheduled with spaced repetition.