Recording intelligenceAI-generated brief · check the source for context

What is CONSISTENT HASHING and Where is it used?

10:50 recording · AUTO · 1 speaker

Watch the original

Executive Summary AI
  • 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.

Brief overview

Consistent hashing places servers and requests on a ring so adding or removing servers barely disturbs load.

  1. 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.
  2. 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.
  3. 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.

Questions this recording answers

10 questions, each answered where it is said
What problem does this ring-based hashing actually solve?

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.

How do you decide which server serves an incoming request?

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.

How are the servers themselves placed on the ring?

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.

Why should the load come out evenly across the servers?

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.

What changes when you add a fifth server to the ring?

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.

Why does the load still end up skewed in practice?

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.

What are virtual servers and how do you create them?

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.

How many hash functions K should you use?

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.

What happens to the load when a server is removed?

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.

Where is consistent hashing used in real systems?

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.

Key Quote

“So the problem is not actually load balancing, the problem is adding and removing servers”

— What is CONSISTENT HASHING and Where is it used?, at 0:00▶ watch at 0:00
Key Quote

“In which case, because the distance is uniform, the load is uniform.”

— What is CONSISTENT HASHING and Where is it used?, at 4:01▶ watch at 4:01
Key Quote

“S1 is not affected, S4 is not affected, S2 is not affected, only S3 is affected.”

— What is CONSISTENT HASHING and Where is it used?, at 5:29▶ watch at 5:29
Key Quote

“If you had a lot of servers, the chance of this happening was really low.”

— What is CONSISTENT HASHING and Where is it used?, at 6:19▶ watch at 6:19
Key Quote

“The reason for that is because there are multiple points where they exist.”

— What is CONSISTENT HASHING and Where is it used?, at 9:13▶ watch at 9:13
Key Quote

“Load balancing is a concept which is used in distributed systems extensively.”

— What is CONSISTENT HASHING and Where is it used?, at 9:45▶ watch at 9:45

Cite this

“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.

Report this page
What is wrong with this page?