Consistent Hashing - Add a Server Without Reshuffling the World

Day 7 taught you to spread traffic across servers. Day 2 taught you to pin hot data in a cache. Both break when hash(key) % N meets a new N. Consistent hashing keeps most keys on the same node when the cluster grows or shrinks.

You already know IP hash (Day 7) and cache keys (Day 2). Today is the placement algorithm that lets distributed caches, sharded stores, and some load balancers change membership without moving almost every object. The win is not microsecond lookup. The win is minimal remapping.

The problem: hash % N is a trap

Suppose you store sessions or cache entries on 3 nodes:

node = nodes[ hash(key) % 3 ]

Traffic is fine. Then you add a fourth node:

node = nodes[ hash(key) % 4 ]

Almost every remainder changes. Keys that lived on node 0 may now land on node 1 or 2. The cache goes cold. Sticky sessions break. You just paid a full reshuffle to gain one server.

That is the problem consistent hashing was invented to solve: when N changes, only a small fraction of keys should move — ideally about 1/N when you add the Nth node.

The idea: a ring, not a remainder

Map both nodes and keys onto the same circular hash space (0 … 2³²−1, for example):

1. Place each server at one or more points on the ring (its hash).
2. Hash the key onto the ring.
3. Walk clockwise (or binary-search the sorted ring) until you hit the next server point. That server owns the key.

When you add a server, it takes ownership only of the arc that used to belong to its clockwise neighbor — keys on other arcs stay put. When you remove a server, only its arc moves to the next node.

// Conceptual placement (lesson lab uses SHA-1 → 32-bit + binary search)
function assign(key, ringSorted) {
  const h = hash(key);
  // first ring point with point >= h, else wrap to ring[0]
  return ringSorted[nextIndex(h)].node;
}

Virtual nodes: fix the “unlucky clump”

If each physical server is one point on the ring, bad luck can clump several servers in a small arc and leave another with a huge arc. Production systems place many virtual nodes (vnodes) per physical server — e.g. 100–200 hashes per machine — so each server owns many small arcs. Load smooths out. Dynamo popularized this for real clusters; many cache libraries (Ketama-style) do the same.

Our lab uses 150 vnodes per node. Balance is good enough for teaching; perfect balance is not free (see benchmark honesty below).

Benchmark — remap is the product metric

JS lab, 100,000 keys, 150 vnodes/node, SHA-1–derived 32-bit placement. Remap = fraction of keys whose assigned node changes after resize. Assign latency = 30-run median.

Change	Modulo remapped	Consistent remapped	Reduction
3 → 4 nodes	75.29%	20.71%	3.64×
4 → 5 nodes	79.63%	20.78%	3.83×
5 → 4 nodes	79.63%	20.78%	3.83×
10 → 11 nodes	91.01%	8.58%	10.61×

Ideal when adding the Nth node is about 1/N of keys (those that land on the newcomer). At 10→11, consistent hashing hit 8.58% vs ideal ~9.09% — close. Modulo still reshuffled 91%.

Where you will see this

• Distributed caches — memcached clients (Ketama), many Redis cluster designs, CDN / edge object placement (Day 21 family).
• Partitioned data stores — Dynamo-style rings, Cassandra token rings.
• Load balancing variants — sticky-ish routing that survives pool growth better than % N (Day 7 IP hash still doesn’t solve membership change by itself).

Worked example: scale-out miss storm

You run a 3-node product-cache. Hit rate is 90%. Marketing is fine. Ops adds a 4th box at peak:

1. Modulo fleet: ~75% of keys change owner (our lab). Almost every hot key misses once. Origin DB sees a thundering herd. Users feel a multi-minute “slow site,” not a clean scale-out.
2. Consistent-hash fleet: ~21% of keys move (lab 3→4). Only keys whose owner is the new node (plus a little balance noise) miss. Origin load rises, but not a full cold start.

That is why the product claim is blast radius of membership change, not “lookups got faster.”

Decision table: remap vs balance vs lookup

Goal	Modulo % N	Consistent hash (+ vnodes)	Pick when
Minimize keys moved on add/remove	Poor (~most keys)	Strong (~1/N ideal)	Caches, shards, sticky sessions under growth
Static even balance (fixed N)	Often excellent	Good with enough vnodes; can clump with few	Stable N, pure fairness
Assign latency	Cheaper (lab 309.7 ms / 100K)	Slightly higher (359.3 ms) binary search	Never the primary reason to choose modulo
Heterogeneous node capacity	Awkward (weights on remainder)	Weighted vnodes	Big boxes + small boxes in one ring

What breaks? — Anti-patterns

1. Using hash % N for a growing cache fleet. Every scale-out is a mass eviction. Fix: consistent hash (or a managed cluster protocol that remaps minimally).

2. One ring point per fat server. Hot arcs and cold arcs. Fix: virtual nodes (or weighted vnodes for heterogeneous hardware).

3. Assuming consistent hashing gives exactly-once data movement. About 1/N still moves — clients must handle misses, replication, or handoff. Fix: design for remaps; measure them.

4. Confusing ring placement with consensus. The ring says where a key goes. It does not elect a leader or replicate safely (Day 23). Fix: separate placement from durability and membership protocols.

5. Selling “faster lookups.” Our assign path was slightly slower than modulo. Fix: sell fewer moves on resize.

How it connects

• Day 2 (caching): a cache miss storm after scale-out is often “we remapped everyone,” not “the cache is broken.”
• Day 7 (load balancing): IP hash is sticky routing; consistent hashing is sticky under membership change.
• Day 21 (CDN): edge nodes are a placement problem — same “who owns this key?” shape at global scale.
• Day 23 (replication): followers apply WAL; sharding/placement is orthogonal — but bad remap still thrashes replicas and caches in front of them.
• Day 9 (rate limiting): distributed counters often shard by key — remap spikes can look like traffic spikes.

Transfer questions

1. You run a 10-node session cache with hash % 10. You must add an 11th node during peak. What user-visible failure mode do you expect, and how does a consistent-hash ring change the blast radius?
2. Your ring uses 1 vnode per node and one physical box is twice as large as the others. What goes wrong, and what knob (from today’s lesson) do you turn?
3. Day 14’s queue consumers must be idempotent under at-least-once delivery. How does that idea rhyme with “~1/N keys still move when you scale the cache”?

What you should be able to do

• Explain why hash % N remaps most keys when N changes.
• Describe ring placement: hash key, walk to next node clockwise.
• State the ideal remap fraction when adding a node (~1/N) and what our 3→4 and 10→11 runs measured.
• Name why virtual nodes exist (balance) without claiming they always beat modulo fairness.
• Separate placement (ring) from durability/replication (WAL, Day 23).

Your teach step

Close this lesson. From memory: explain like I’m 10 (ring + “only the neighbors move”), then a 60-second LinkedIn version with the 3→4 remap numbers. Post it, paste the link.

Questions? Ask the agent — weighted vnodes, rendezvous hashing, or how Redis Cluster slots differ from a classic ring are fair game.