Consistent hashing places servers and requests on a ring so adding or removing servers barely disturbs load.
The real difficulty is not load balancing itself but adding and removing servers, which completely changes the local data held on each server. The fix keeps hashing every request by its request ID, but maps that hash onto a ring of positions 0 to M minus 1 instead of an array.
When a request lands somewhere on the ring, you move clockwise from that point and the first server you meet serves it. That simple rule gave S1 a load of two requests in the drawn example, while S2, S3 and S4 each ended up with a load of one.
The server IDs, 0 through 4, are hashed with the same hash function as the requests, or a different one, then reduced modulo M, the search space. In the worked example M is 30 and h of 0 is 49, so 49 mod 30 gives 19 and server 1 sits at position 19.
Because the hashes are uniformly random, the distances between the server points on the ring are also uniform, and uniform distance means uniform load. The requests are uniform too and get mapped to the right places, so the expected load factor per server works out to 1 by n on average.
Only the neighbouring server is disturbed. Two requests that previously went to S3, which had a load factor of about 3, now find the newly added server as their nearest clockwise server, giving it a load factor of 2 while S3 comes down to 1. S1 and S2 are unaffected.
Theoretically the load should be 1 by n, but practically you can get skewed distributions, because you do not have enough servers. With a lot of servers and many red points the chance would be really low, but with only four you get about half the load on a single server, which is terrible.
Virtual servers do not mean virtual boxes or buying more machines, which are expensive. Instead you use multiple hash functions: H1 for the requests, then H2 and further functions through which you pass the same server IDs to get different numbers. With K hash functions each server occupies K points.
If K equals 3, then instead of just 4 points you have 12 points on the ring, and the likelihood of one server getting a lot of the load is much, much lesser. Choosing K appropriately, for example log n or log m, almost entirely removes the chance of a skewed load.
You remove that server's K points and assign each of them clockwise to the nearest servers. Because the server existed at multiple places, removing it hits multiple regions at once, so some load goes to one server, some to another, and their loads increase expected uniformly. Adding a server behaves the same way.
It is used in many, many places. Load balancing is a concept used extensively in distributed systems, and this is used by web caches and by databases. Consistent hashing gives you flexibility and load balancing in a very clear and efficient way, so you should definitely know about it.
“So the problem is not actually load balancing, the problem is adding and removing servers”
“In which case, because the distance is uniform, the load is uniform.”
“S1 is not affected, S4 is not affected, S2 is not affected, only S3 is affected.”
“If you had a lot of servers, the chance of this happening was really low.”
“The reason for that is because there are multiple points where they exist.”
“Load balancing is a concept which is used in distributed systems extensively.”
“What is CONSISTENT HASHING and Where is it used?.” https://www.youtube.com/watch?v=zaRkONvyGr8. Transcript summary by WhipScribe, https://whipscribe.com/transcript-pages/what-is-consistent-hashing-and-where-is-it-used.html.