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.
Connections
- Part of
- Hash Partitioning
Recall
These cards are also in your review deck, scheduled with spaced repetition.