Everything About Hashing in Load Balancing!

In this section, we are talking about hashing and how it is related to load balancing. I am taking one example for explaining load balancing and how hashing is related to it.

Suppose we have a server where we hosted our algorithm, users are requesting and our server is serving them with responses. Our algorithm is a face app where the user uploads the image and our algorithm detects the face in that image and makes the face older/aged and returns this as a response to the user.

Our user liked the algorithm, so he told their friends about it. slowly the incoming traffic to our server starts increasing. Now traffic is too much so that a single server can’t bear this load. To troubleshoot this issue we’ve added another server to the system. As shown in the diagram below.

But now we have one problem, Where do we send the request i.e. on which server we should send traffic server1 or server2.

If we have N servers we want in general to balance the load among all the servers. All servers are carrying a load as they have to process the user’s request.

The concept of Scaling to N servers and trying to balance (Distribute in balance) the load evenly is called Load Balancing.

So we’ll take the request from the user and try to balance the load evenly on the servers. And concepts of consisting hashing will help us to do that.

So we want to distribute weight/load among all the servers, When the user sends the request we’ll also get the request-id in each request. For now, we consider that request-id we get is uniformly random so when the user sends a request, it randomly generates a number from 0 to M-1. And this request-id is sent to the user accordingly.

Now, we’ll call this request-id as r. Before sending it to the user we have to do one operation on it. It is hashing. We’ll hash the request-id, And when we hash it we’ll get a particular number let’s call that M1, this number can be mapped to the particular server.

How can we map it?. For mapping, we have N servers so we’ll make a mod operation and take the remainder. That remainder is the index of the server, now we can send the request to the respective server.

So for our example, it will be as follows:

For the first request(r1):

For the second request(r2):

For the third request(r3):

In our case our request ID is random, So all of the servers will have a uniform load. For each of the servers, If there are x requests, then we’ll have x/n load and the load factor is 1/n.(x= request, n = number of servers).

This is perfect till now, Except what if our system got a lot more requests than before we have to add another server for this. When we add a new server our system will be scaled but there is one problem. The request which was served on the existing server is now served by another server.

Because n’s value is changed(n = number of the server are 5 now), Now whenever request-id goes in hash function and give the hashed number which will be further mod by the new value of n (which is 5). The will be routed in different server than usual

So the r3 request was routed on server1 and if we increase the server by 1, that request will go on server0.

If we consider a pie diagram for this. As shown below.

The above diagram shows the initial stage of the system where we have only 4 servers. 4 quadrants as we have 4 servers. They have 25 buckets assigned. (we’ll call number as bucket 25 as 25 buckets)

But when a new server is added to our system this happens.

A lot of operation happens after we add a new server in the system here it is:

In server0 we have to change the 5 buckets, In server1 we have to take the remaining 5 buckets. Now server1 will go till 40 instead of 50 that is 10 number change

Now server2 has to take the previous 10 buckets plus it will go to 60 now instead of 75, that is again 15 buckets, now server2 is done.

We’ll go to server3 now which was the last server in the previous system, now server3 will only go to 80, The operation will be we have to add 15 numbers and we had the last 20 numbers.

And after all this operation our new server server4 will finally take 20 buckets.

But the total cost of this operation (Exchange till now) is 100, which is actually our entire search space.

Now, Why it is such a big deal? The whole thing is changed so what.

It is a big deal Because in the real world the Request ID is never random, or rarely random. Request id usually encapsulates some of the information of the user.

Example user-id(req id) ⇒ Nishant

So if I hast Nishant, The hash function will always return the same result again, again, and again. Because our hash function is constant

If we are getting the same result from the hash function then it means that when we do the mod operation with n. It will send the request to the same server again, again, and again.

If the server is receiving the same request then why don’t use that information like fetching the profile from the database. Why should the server go to the database again and again, Why not store that data in the local cache. That is a smart move depending on the request-id we can send users to the specific servers and once they send them the request we can store the relevant information in the local cache in these servers.

But because of the operation we did to add a new server, What is going to happen is the entire system changes and all users will route to different servers than usual. So our stored cache is completely useless. Because the number we are serving is completely changing (4 to 5 now).

To avoid this we want something so that whenever we add a new server we don’t have to go for a huge change we want some small change.

For that solution will be the new server will take a small bucket from each server so that the total number will be 20 each and the overall change will be minimum. Here is the diagram for it:

This is why old general hashing doesn’t work in this scenario, We need an advanced approach and that’s where consistent hashing comes into the picture.

I am going to write a blog about consistent hashing. I will provide a link here.