# Consistent Hashing: Surviving the Resize

> hash(key) % N reshuffles nearly everything when N changes — a cache stampede with a math degree. Consistent hashing moves only 1/N of keys per node change, and virtual nodes fix the balance problem the elegant version hides.

URL: https://harshith.in/blog/consistent-hashing/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: distributed-systems, algorithms, systems

Shard a cache across 10 servers with `hash(key) % 10` and everything
works until the day you add an eleventh. Then `% 11` reassigns roughly
**10/11 of all keys** — 91% of your cache misses simultaneously, the
database behind it takes the full read load, and you've invented the
self-inflicted stampede. The fix that became load-bearing for Dynamo,
Cassandra, Riak, and most distributed caches is one of those ideas
that's obvious only afterward: stop hashing keys *to servers*; hash
both onto the same space and make assignment a matter of *proximity*.

## The Ring

Map the hash space onto a circle. Hash each node onto it; hash each
key onto it; a key belongs to the first node clockwise:

```text
        node A
       ╱      ╲
  key₁ →A      node B
      │          │
  key₄ →A     key₂ →B
       ╲      ╱
        node C ← key₃
```

Now add node D between B and C: the only keys that move are those in
the arc (B → D) — everything else's clockwise-next node is unchanged.
Expected movement: **K/N keys**, the theoretical minimum for
rebalancing onto a new node. Remove a node and its arc simply drains
to its clockwise successor. Membership changes went from global
reshuffles to local edits — that's the entire invention (Karger et
al., 1997, built for web caching; Dynamo made it famous a decade
later).

## The Fix the Textbook Version Needs

Hash N nodes onto a circle and the arcs are wildly unequal — with a
handful of nodes, the largest arc is routinely several times the
average, and when a node dies its *entire* load lands on one
neighbor. The production fix is **virtual nodes**: each physical node
claims 100–1000 points on the ring. Law of large numbers evens the
arcs; a failed node's load now scatters across *many* successors
instead of crushing one; and heterogeneous hardware falls out free —
give the double-sized box double the vnodes. (Cassandra defaulted to
256 per node for years; the cost is bigger membership metadata and
slower ring math, hence its newer allocation algorithms trimming the
count.)

Two sharper tools from the same drawer, worth knowing when the ring
isn't the right shape. **Jump consistent hash** (Google, 2014): a
few lines of arithmetic, no ring state at all, perfectly balanced —
but buckets must be numbered 0..N−1, so it fits sequentially-named
shards, not arbitrary node arrival/departure. **Rendezvous (HRW)
hashing**: for each key, score every node with hash(key, node), pick
the max — minimal disruption, no vnode tuning, O(nodes) per lookup;
the right answer at small N and the idea inside many load balancers.
And for the balancing problem under *skewed keys* (one hot key still
lands on one node — hashing can't fix popularity), **bounded-load
consistent hashing** (the 2017 result deployed at Vimeo/Google) caps
any node at (1+ε)× average and spills overflow clockwise —
worth knowing before you re-derive it badly in an incident.

Where you'll meet all this: Dynamo-lineage stores walk the ring
clockwise to pick N *distinct* replicas (the preference list);
memcached clients (ketama, since 2007) made ring hashing the standard
cache-client feature; Envoy/HAProxy expose ring and Maglev hashers
for session affinity; and DHTs (Chord) turned the same ring into
O(log N) routing. One caveat that saves design reviews: consistent
hashing gives you *placement*, not *membership* — deciding who's
alive (gossip, health checks) and handling the rehash-vs-replicate
question when a node is merely *slow* is the actual hard part of the
systems built on it.

## Takeaways

- Modulo sharding reshuffles (N−1)/N of keys per resize; ring
  placement moves the minimum K/N.
- Virtual nodes are non-optional: they fix arc variance, spread
  failure load, and encode capacity weights.
- Alternatives fit different shapes: jump hash (numbered buckets,
  zero state), rendezvous (small N, no tuning), bounded-load (skew
  and hot keys).
- The ring decides *where* keys live; replication (walk clockwise
  for N distinct nodes) and membership are separate protocols.
- Hashing balances key *count*, never key *popularity* — hot keys
  need caching/spreading strategies of their own.