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.