Consistent Hashing

Why hash(key) % N collapses the day you add a node

The edge tier holds 50,000 WebSockets across 4 nodes plus a spare, fanning each message out through a shared bus, and every deploy adds or removes a box. You run four cache machines behind that edge and assign each key with hash(key) % 4, which means you hash the key to a number and take the remainder after dividing by the machine count. That remainder is the owner. It works beautifully until you add a fifth machine for load, because the divisor changes from 4 to 5 and nearly every remainder changes with it. Think of a traffic roundabout with four exits where every driver picked an exit by remainder math: repaint it to five exits overnight and almost everyone must re-learn their route at once.

The naive hope is that only one-fifth of keys should move, since the new node should take roughly one-fifth of the load. The arithmetic says otherwise. With hash(key) % N, a key stays put only if old and new remainders agree by luck, which happens about 1/N_new of the time, so roughly N_new minus 1 out of every N_new keys relocate. Going from 4 to 5 nodes moves about 80% of keys, and your cache hit rate falls off a cliff while every miss thunders to the database at the same moment.

N=4: key A hash 12 → 12%4=0(node0)  B hash 13 →1(node1)  C hash 14 →2(node2)
N=5: same hashes → 12%5=2 13%5=3 14%5=4  // 3 of 3 moved
40M keys, 4→5 nodes: ~32M move under mod-N; consistent hashing would move ~8M.

How a ring lets neighbors absorb joins without global reshuffling

Consistent hashing replaces the divisor with a ring, which means you hash both machines and keys onto one shared circle numbered 0 to 2^32 minus 1 and walk clockwise. Each key belongs to the first machine clockwise from its hash, so adding a machine carves arcs out of its clockwise neighbors only. Every other key stays exactly where it was, because its clockwise owner did not change.

The mechanics are deliberately boring so any client can route without asking a coordinator. Hash the key once, binary-search the sorted ring for the first machine hash at or above it, and wrap to the start if you pass the end. Joining means inserting points and sorting; leaving means the successor clockwise inherits the departing arcs. No central lookup, just the same sorted list everywhere.

Ring: 0 ── A(10) ── keyX(25) ── B(80) ── C(200) ── 2^32
  keyX → first clockwise is B → belongs to B
  Add D at 40 → keyX now maps to D (only keys between 10 and 40 move)
  Remove B → keys between A and B slide to C; others untouched

Why each machine claims a hundred points instead of one

Virtual nodes, meaning multiple hash positions per physical machine, fix ring lumpiness. Instead of hashing cache-a once, you hash cache-a#0 through cache-a#149, giving one box 150 evenly scattered claims on the circle. Each claim owns a small arc, so the law of large numbers evens out the total: 150 small random arcs per box vary far less than one big random arc.

Weighting falls out naturally. A box with twice the memory gets twice the virtual points, hence twice the arcs and twice the keys. The trade is memory for the ring itself, which costs k times N entries, plus the need to keep every client viewing the same ring version, plus the physical copy that still must move when arcs change hands. Logical movement is cheap; bytes on the wire are not.

function getNode(key: string): string {
  const h = hash(key);
  // ring sorted by hash
  const idx = lowerBound(ring, h); // first node hash >= h, wrap to 0
  return ring[idx].physical;
}
// Add node: add 150 virtual points, sort ring O(k log k)

Where rings already run your caches, tables, and balancers

The same ring idea recurs because the problem recurs. Memcached fleets behind compatible clients, Redis Cluster, a clustered in-memory store, with its 16384 hash slots, Cassandra token ranges, and Dynamo-style partitions, a design from Amazon's highly available key-value store, all map keys to owners with minimal remapping. Load balancers such as Maglev, Google's distributed balancer, and hash modes in NGINX, a widely used reverse proxy, keep session affinity the same way when backends come and go.

When three machines split the circle 80/10/10 by pure chance

You launch three cache boxes and random placement hands one of them four-fifths of the arcs. That box runs hot while two idle, and the instinct is to blame the hash function. The deeper cause is variance: with N physical points and K keys, each machine expects K/N keys but the standard deviation is nearly as large as the mean, so an 18k/8k/4k split over 30k keys is ordinary, not anomalous.

3 nodes, 30,000 keys, no vnodes:
  expected per node: 10,000
  typical spread:    4,000 / 8,000 / 18,000  (one node 1.8x overloaded)

With v=150 virtual points per physical (450 points total):
  expected per physical: still 10,000
  typical spread:        9,100 / 10,200 / 10,700  (+/-10% instead of +/-80%)
  rule of thumb: imbalance ~ 1/sqrt(v) → 150 vnodes ≈ 8% std dev

The three dials that decide whether scaling stays boring

Operating a ring means setting virtual-point count, replica count with rack-aware placement, and overflow behavior when a node fills. Virtual points default to 100 to 200 per box, since below 20 the ring stays lumpy and above 500 the gossip and sorting cost buys nothing visible. Replicas typically walk N minus 1 extra nodes clockwise past the owner with N equal to 3, placed on distinct racks so one switch failure cannot take all copies.

Counting the keys that move when the fifth cache joins

Four machines hold 40M keys, 10M each, and you add a fifth at peak. Only the arcs the newcomer carves from its clockwise neighbors relocate, roughly one-fifth of the total, and every other key stays put. With replication factor 3, the same ranges move but three physical copies transfer per range, so size the migration window in bytes, not just key counts.

4 nodes x 10M keys = 40M total, replication N=1 for clarity:
  add 5th node → it claims ~1/5 of the ring → ~8M keys move to it
  each old node donates ~2M (its arc shrinks 10M → 8M)
  keys moved: K/N_new = 40M/5 = 8M. Keys untouched: 32M (80%).

With replication N=3 (walk 2 extra clockwise nodes):
  moved key-ranges still ~1/5, but 3 copies transfer per range
  transfer ≈ 8M keys x 3 copies x value size; size the migration window.
Compare: hash(key) % N would move ~32M of 40M (all but 1/5 stay by luck).

Movement is logical until bytes copy. Either the newcomer pulls ranges from donors while serving partial hits, or misses fall through to the database and refill lazily. Lazy refill skips the copy at the cost of a cold-cache latency spike exactly when you added capacity to relieve pressure. During migration, route with both old and new rings by reading both and writing the new one, since no cutover is instant.

Weighting a fleet where new 64GB boxes sit beside a 16GB survivor

Fleets are rarely uniform. Two new 64GB boxes beside one old 16GB box would, with equal shares, fill the small box four times over while the big ones idle. Counting virtual points in proportion to the bottleneck resource fixes it: memory for caches, disk or throughput for stores. Re-weight after every hardware refresh, since stale weights silently reintroduce last year's skew.

Retiring a node by draining arcs before removing it from the ring

Decommissioning reverses a join. Mark the leaver as departing, copy its arcs to clockwise successors, distribute the new ring under a version number such as an epoch or config number, and during the handoff read the new owner first with fallback to the old one. Remove the node from the ring only once successors serve the full arc. Dynamo-style stores and Cassandra, a wide-column store, both drain before they depart, because killing a full node outright triggers an under-replicated storm.

Handling the celebrity key that no placement scheme can split

One profile key draws 40% of reads to a single owner. Replicate that key to extra nodes and read from any with invalidation on write, hedge by asking two replicas and taking the first answer, or split it into numbered shards merged client-side. Rings place load across keys; only replication survives fame concentrated in one key, which connects directly to the replication and quorum reasoning the consensus chapters build on.

Surviving the thundering refill when a cold node rejoins empty

A rejoined node owns its arcs but holds no bytes, so every request for its keys misses simultaneously and thunders the database the ring was protecting. The naive cutover flips the ring at once and absorbs the spike as the price of scaling. The working handoff warms first: copy ranges from donors before advertising ownership, serve reads from donors while the copy lands, then flip the ring version once hit rates converge. Lazy refill without warming trades copy bandwidth for a cold-cache latency spike at peak, which is exactly when you added capacity to relieve pressure. Version the ring and dual-read across the handoff, since no cutover is instant.

Cold rejoin: node E claims 8M keys, cache empty → 8M misses × DB round trip
  naive flip: hit rate 95% → 60% for minutes; DB p99 triples under the wave
  warmed handoff: donors stream 8M keys at 500MB/s ≈ minutes, serve reads meanwhile
    → flip ring version → hit rate dips 95% → 90% → recovers, DB never spikes
  rule: bytes must exist before ownership advertises; logical moves are free, fills are not.

The habit that saves every scaling story

Rings move 8M of 40M keys when the fifth cache joins and warm the rest across a versioned handoff. Yet during that handoff two clients hold two ring versions and disagree on who owns the arc. Placement cannot vote, so how do scattered machines elect one agreed sequence when the leader dies mid-sentence?