What is Load Balancing? ⚖️

everyone this is GK CS we are talking about consistent hashing now so this is as you can expect relevant to the concept of hashing objects so consistent hashing has certain properties and this is something that you need to know if you are building systems if you are building systems which can scale to a large extent so many of these terms that I'm stating right now might be you know jargon for you you might be saying what do you mean scale what you mean systems so if you have let us say a box just just a computer which is running a program right and someone your comes to you and says that you know what I really like your algorithm I'll pay you money just to use your algorithm okay so there's this person over here who has their cell phone and they can connect to your box your computer they want to use your algorithm get the result and every time they do that they pay you some money or maybe at the end of the month or whatever but keeping the money better side keeping the sales marketing everything aside we have technical specifications right this algorithm needs to run for the customer to be happy and you to be happy in turn so when I say that this is an algorithm running on a computer this is like a server right that's what it means a server is something which serves requests and when that person is connecting through the mobile they're technically sending a request okay use they are send a request your algorithm runs you understand what they want let's say the algorithm is a facial recognition algorithm which gives a mustache right so your response is going to be having that image sent back so your server takes requests sends backs response now let's say one person comes to you and that damn happy they're really really happy so they tell all their friends and you have thousands and thousands of requests coming in your computer cannot handle this anymore so what you do is you add another computer because you know you're getting a lot of money from all these people now you can afford to buy a new computer a new server if you can do this there's one problem where do you send the requests like if there's a second person then should the requests go here or should the requests go here at the bare minimum level if you have let's say n servers you want in general to balance the load on all of these servers now you can imagine all of these servers actually carrying load these requests are things which they need to process so the server has load on it this is pretty important right and the concept of actually taking n servers and trying to balance the load evenly on all of them is called load balancing ok so this is a very simple problem what we are going to try to do is take these requests and evenly balance the load on all of our n servers and the concept of consistent hashing will help us do that so you want to evenly distribute the weight across all servers you will get a request ID in each request right so that request ID is you can expect uniformly random so when the client says when the when the mobile actually sends you a request it randomly generates a number from 0 to M minus 1 and what happens is this request ID is sent to your server what you can then do is take this request ID I'll call it I or I'll call it our r1 and hash it when you hash it you get a particular number let's say m1 this number can be mapped to a particular server how because you have n servers you take the remainder within whatever index you get here you just send that to the respective server right so let's say your four servers s0 s1 s2 and s3 r1 is 10 when you pass it through your hash function you get the value 3 3 mod 4 n is 4 in our case is 3 so this will go to bucket number this request r1 will go to the server 3 okay another example H of 20 let's say this somehow gives you 15 and mod 4 again this gives you 3 so r2 also goes to 3 and finally if we have H of 35 when hashed gives you 12 this mod 4 gives you 0 so our 3 maps to the first server right and in general because this is uniformly random and your hash function is uniformly random you can expect all of the server's to have uniform load so each of the server's if they're XFS --tz-- will have x by n load and the load factor is 1 by n so everything is perfect and that's all we need to do except what happens if you need to add more servers we said that initially our clients are very happy with us so we are getting viral or for some reason you know people are really really hitting our servers a lot what happens if that happens we need to add more servers s4 but now there's a problem the requests which are being served here are completely bamboozled they request ID so when you pass them through the hash functions the values you are getting for 3 mod 4 this has to change now you have in total 5 servers so 3 mod 5 r1 has to go to server 3 so that's ok what about 15 mod 5 this has to change it has to go to server 0 because this is 0 right what about this 12 mod 5 this is equal to 2 so this request r3 again has to change and go to s2 and this is very clearly illustrated in a pie diagram right this is your PI initial you add for servers so the PI was 25% for every person right so this is having 25 25 25 25 so they have 25 numbers assigned to them now when the 5th server came in this had to lose five of its buckets so there was a change of 5 buckets this had to take these 5 buckets so that is plus 5 go up to 40 right so instead of 50 it goes up to 40 only so this lost 10 buckets so that's 10 buckets changed when I mean buckets I just mean numbers so those are just numbers which it lost so this is up to 40 now this so uh s3 or other s2 so this is s0 s1 s2 has to take these 10 so that's plus 10 as a change plus it goes only up to 60 now so instead of 75 it goes only up to 16 so that's 15 plus 15 buckets changed now s2 is done we go to s3 which is the last server that we had and this now has to go only up to 80 so what happens is it lost so it has five buckets remaining in its old section it lost 20 buckets here and it had to take 15 buckets from here to have a total of 20 in s3 okay so that is 15 buckets added to it and 20 buckets lost and finally s4 has to actually take 20 buckets so the cost of the operations if you see the cost of the change in this is 5 plus 5 10 20 30 40 50 60 70 80 90 100 so in total the change was 100 which is actually your entire search space now why is this such a big deal you know okay 100 changes the whole thing change so what well because in practice the request ID is never random or it is rarely random the request ID usually encapsulate some of the information of the user for example the user ID so if I hash Ghorab this hash is going to give me this same result again and again and again because the hash function is constant if I'm getting the same result it means that when i modeli with n it's going to send me to the same server again and again and again now why not use that information if I'm being sent to the same server again and if there is something like fetching a profile from a database why should I do that all the time why not store it in the local cache right that seems like a smart thing to do depending on the user ID so instead of r1 i'll i can call it u1 but I'll still call it r1 so depending on the user ID we can send people to specific servers and once they're sent there you can store relevant information in the cache for those servers but through this policy what is going to happen is the entire system changes all users are now happily sent to different places and all the useful cache information you had is just dumped it's useless almost all of it is useless now because the numbers that you are serving completely changed so what you want to avoid is a huge change in the range of numbers that you are serving if you are serving from this to this then a small change is what you want here if you're serving from here to here then you don't want a huge change sure what you want is a tiny change sure so in a new pie chart what's going to happen is if this is the pie chart and this is the quartered thing what I would like to do is take a little from this first server so that is that is this big take a little from the second server take a little from the third server and take a little from the fourth server such that the the sum of these areas is going to be 20% right because you added one server your five servers you want wente percent on each so the sum of these areas should be 20% but the overall change should be minimum that's the general idea why the old standard way of hashing doesn't work in this case we need more advanced approaches and that's where consistent hashing comes in we talk about today is valuing - hashing and it's called consistent hashing

Channel: Gaurav Sen

Views: 720,890

Keywords: System Design, Load Balancing, Server architecture, Request Allocation, Hashing, Fault Tolerance, scalability, flexibility, Hash Buckets, Technical Interview, Software Interview, IT Interview, interview practice, software interview practice, Gaurav Sen, gkcs, sticky sessions, service discovery

Id: K0Ta65OqQkY

Length: 13min 50sec (830 seconds)

Published: Sat Apr 21 2018