Consistent Hashing

The Problem It Solves

 modulo-N sharding breaks on resize:

 N=4:   key → hash % 4
 N=5:   hash % 5 → almost EVERY key changes shards!
        (only keys where both modulos agree survive ≈ 1/20)

 resize = remap ~80% of data = massive migration storm +
 cache flush stampede + connection chaos.

 CONSISTENT HASHING: adding/removing nodes moves only ~1/N of keys.

The Ring

 place nodes AND keys on a circular hash space:

         node A
       ╱       ╲
   key●         ●key
      |    ring |
      ●key      ●key
       ╲       ╱
         node B

 RULE: each key belongs to the NEXT node clockwise.
 
 add node C between A and B:
   only the arc B→C's keys move to C. everything else stays.

 [ring with C added]
   keys in that one arc migrate; rest are untouched ✓

The Uniformity Fix: Virtual Nodes

 naive rings create LUMPY distribution:
 few nodes = uneven arcs = hot nodes.

 VNODES: each physical node appears 100-200 times on the ring:

 node A = A₁,A₂,...,A₁₅₀ scattered around circle
 law of large numbers → even share per physical node

 bonus powers:
 - heterogeneous hardware: beefier node gets MORE vnodes
 - node removal scatters its load across MANY survivors
   (no single neighbor takes everything)
 
 this vnode trick is WHY consistent hashing became practical,
 not just theoretical.

Where You Already Use It

 the technique is embedded across infrastructure:

 DynamoDB/Cassandra: token-ring data placement
 Redis Cluster:      slot table (cousin — same goals)
 CDNs:               edge selection for cache objects
 Load balancers:     consistent-hash routing by session/user
 Discord/Cassandra, Netflix/Dynamo heritage: production proof

 recognizing "that's consistent hashing" in system diagrams
 is a genuine interview skill.

Variants Worth Naming

Variant	Adds
Bounded loads	Cap per-node load; overflow to next ring node (Google)
Rendezvous (HRW)	Each key computes score per node; highest wins — no ring needed
Jump hash	O(1) computation; no ring structure

 bounded-loads matters for skew: pure CH can't prevent a
 celebrity key overloading its owner; bounded variant spills
 excess to neighbors automatically.

Interview Framing

Consistent-hashing questions expect: the modulo-resize problem quantified (~80% remap), ring mechanics with clockwise-owner rule, MOVEMENT MATH (“adding node k moves only ~kth of keyspace”), vnodes as the uniformity fix with heterogeneous-cluster benefit. Bonus points: bounded-loads for skew and naming real systems using it. Drawing the ring beats describing it — practice the diagram.