Consistent hashing places servers and requests on a ring so adding or removing servers barely disturbs load.
Hash servers and requests onto one ringRequests and server IDs share the hash space 0 to M minus 1, and a request goes to the first server clockwise.
Membership changes touch only one neighbourAdding the fifth server changed only S3, which fell from a load of 3 to 1 while the newcomer took 2.
Virtual nodes fix skew without buying hardwareK hash functions give each server k ring points, so K equal to 3 turns 4 points into 12 and spreads a failed server's load across many regions.
Executive SummaryAI
The speaker frames the real problem as adding and removing servers rather than load balancing itself, since that churn changes the local data held in each server, and proposes a ring of hash positions from 0 to M minus 1 onto which request IDs are hashed.
Server IDs are hashed with the same or a different hash function and taken modulo M, so with M equal to 30 and h of 0 being 49, 49 mod 30 gives 19 and server 1 lands at position 19 on the ring.
Each request is served by the nearest server found going clockwise, which leaves S1 with a load of two requests and the others with one each, and because the hashes are uniformly random the expected load factor is 1 by n.
Adding a fifth server only affects S3, whose load drops from 3 to 1 while the new server takes 2, but when S1 crashes about half the load lands on S4, because with only four servers the distribution can be badly skewed in practice.
The fix is virtual servers: pass each server ID through K hash functions so every server holds k points on the ring, turning 4 points into 12 when K is 3, and choosing k around log n or log m almost entirely removes the chance of a skewed load.
Key Quote
“So the problem is not actually load balancing, the problem is adding and removing servers”
— Speaker
Key Quote
“In which case, because the distance is uniform, the load is uniform.”
— Speaker
Key Quote
“S1 is not affected, S4 is not affected, S2 is not affected, only S3 is affected.”