What is LOAD BALANCING? ⚖️
ฝัง
- เผยแพร่เมื่อ 4 มิ.ย. 2024
- Load Balancing is a key concept in system design. One simple way would be hashing all requests and then sending them to the assigned server.
The standard way to hash objects is to map them to a search space and then transfer the load to the mapped computer. A system using this policy is likely to suffer when new nodes are added or removed from it.
One term you would hear in system design interviews is Fault Tolerance, in which case a machine crashes. And Scalability, in which devices must be added to process more requests. Another term used often is request allocation. This means assigning a request to a server.
Load balancing is often tied with service discovery and global locks. The type of load we want to balance is that of sticky sessions.
Looking to ace your next interview? Try this System Design video course! 🔥
interviewready.io
00:00 Load Balancing - Consistent Hashing
00:33 Example
01:29 Server-Client Terms
02:12 Scaling
02:40 Load Balancing Problem
03:58 Hashing Requests
06:37 Request Stickiness
08:00 Splitting the Pie
10:35 Request Stickiness
13:29 Next Video!
With video lectures, architecture diagrams, capacity planning, API contracts, and evaluation tests. It's a complete package.
Code: github.com/coding-parrot/Low-...
References:
stackoverflow.com/questions/1...
www.citrix.co.in/glossary/loa...
www.nginx.com/resources/gloss...
en.wikipedia.org/wiki/Load_ba...)
www.tomkleinpeter.com/2008/03/...
michaelnielsen.org/blog/consis...
• Consistent Hashing - G...
System Design:
highscalability.com/
• What is System Design?
www.palantir.com/how-to-ace-a...
#LoadBalancer #Proxy #SystemDesign
For anyone confused by the pie chart, the explanation he does makes sense only when you watch the whole video. In a nutshell, when you at first have 4 servers, each server handles 25% of the users. The hashing function takes users' user id or some other information that somehow encapsulates the user data (and is consistent) so any time you want to, for example, fetch a user profile you do it via the same server over and over again since user id never changes (therefore hash of a user id never changes and will always point to the same server). The server remembers that and it creates a local cache for that information for that user so that it doesn't have to execute the (expensive) action of calculating user profile data, but instead just fetches it from the local cache quickly instead. Once your userbase becomes big enough and you require more processing power you will have to add more servers. Once you add more servers to the mix, the user distribution among server will change. Like in the example from the video, he added one server (from 4 servers to 5 servers). Each server needs to now handle 20% of the users. So here is where the explanation for the pie chart comes from.
Since the first server s0 handles 25% of the users, you need to take that 5% and assign it to 2nd server s1. The first server s0 no longer serves the 5% of the users it used to, so the local cache for those users becomes invalidated (i.e. useless, so we need to fetch that information again and re-cache it on a different server that is now responsible for those users). Second server s1 now handles 25%+5%=30% of the traffic, but it needs to handle 20%. We take 10% of its users and assign it to the third server s2. Again like before, the second server s1 lost 10% of its users and with it the local cache for those users' information becomes useless. Those 10% of users become third server's users, so the third server s2 handles 25%+10%=35% of the traffic. We take third server's 15% (remember, it needs to handle only 20%) and give it to the fourth server s3. Fourth server now handles 25%+15%=40% of the traffic. Like before, fourth server lost 20% of its users (if we're unlucky and careless with re-assignment of numbers it lost ALL of its previous users and got all other servers' users instead) and therefore those 20% of users' local cache becomes useless adding to the workload of other servers. Since fourth server handles 40% of the traffic, we take 20% of its users and give it to the new fifth server s4. Now all servers handle users uniformly but the way we assigned those users is inefficient. So to remedy that, we need to look at how to perform our hashing and mapping of users better when expanding the system.
Nice one
amazing explanation dude
thanks buddy it got cleared here, now i want to ask you that how would we utilize this and make it scalable because loosing cache data will be costly.
Thanks buddy ❤
thanks dude
I'm a UX Designer, irrelevant for me to know this but just watching your video and sitting here willing to complete the whole series, thats how brilliant you are explaining chap.
Thank you!
Absolutely.
First of all, this is a perfect lesson and I have absorbed 100% of it as a school student. the pie chart was little confusion at first cus with 4 servers it's like 25 Buckets and then you added 1 server it's pretty much 20 - 5 buckets. so divide pie to 5 and mark each one 20 buckets is the easiest way
If anyone is confused by the pie diagram,
We need to reduce the distribution from 25 each to 20 each. So we take 5 from the first server and merge it with the second one. Then we take 10(5 from the first one and 5 from the second one) and merge it with third. So now, both one and two have 20 each. Then we go on taking 15 from third and merging it with fourth and finally, taking 20 from four to create the fifth server's space.
Please correct me if I'm wrong. This is just a simple breakdown which I think is what he intended
your comment saved my day.
I replayed the video for the pie diagram so many times but didn't get it.
Thanks for explanation...
Same here..
Thank you for your explanation. It is very helpful.
Can you please tell what is this pie chart signifying, as to what are these 25 buckets, is it storage space or number of requests handled? It will be very helpful if you could help with this question.
@@arymansrivastava6313 I think the numbers represent # of users. Let's say each user has one request. Before, we can say users 1-25 were mapped to server 0, 26-50 mapped to server 1, 51-75 mapped to server 2, and 76 - 100 mapped to server 3. By adding another server (server 4), we have to redistributed/remap these users across 5 servers now instead of 4. The redistribution process she showed in the video made it so that each user is now assigned to a new server. This is problematic because server 1 used to cache the information of users 1-25, but now that entire cache is useless. Instead, it's better to minimize the changes we make to each server. That's how I understood it, please correct me if I'm wrong
This channel is a total gem. I don't think i've seen anything similar on youtube in regards to quality. Really appreciated it !
😁
Notes to self:
* Load balancing distributes requests across servers.
* You can use `hash(r_id) % n_servers` to get the server index for a request `r_id`.
-> Drawback: if you add an extra server `n_servers` changes and `r_id` will end up on a different server. This is bad because often we want to map requests with the same ids consistently to the same servers (there could e.g. be cached data there that we want to reuse).
* "Consistent hashing" hashes with a constant denominator `M`, e.g. `hash(r_id) % M`, and then maps the resulting integer onto a server index. Each server has a range of integers that map to their index.
* The pie example demonstrates, that if an extra server is added, the hashing function stays the same, and one can then change the range-to-server-index mapping slightly so that it remains likely that an `r_id` gets mapped to the same server as before the server addition.
Thanks for this. I have a question which may easy
But I am not sure about it.
It is basically based on the hash value we are deciding which server do we save our data out of n number of database.
What is the guarantee that hash function returns value by which request will be stored n different number of servers equally
Thanks for notes. It's good for lazy people watching video, like me :)
@@naatchiarvel Take few processes with different r_id and let's say there are 5 servers ...now do mod and try to find which process will load in which server...You will get your answer
@@adityachauhan1182 thank you .it answered my question.
thanks for the summary
seems like a 4th-year senior teaching the juniors...your videos are Beast :)
I love how you've taken the time and effort to teach complex topics in a simple manner with real world examples. You also stress on words that are important and make analogies. This helps us students remember these topics for life! Thank you and really appreciate the effort!
Notification Squad :-)
The problem with having awesome teachers like Gaurav Sir, is that you want the same ones to teach you in college too :-) Thanks Gaurav sir for System Design series.
Thanks CodeArchery!
relatable
@@gkcs sir could you please explain that hoe does the server goes upto 40 buckets .......I did not understand at (8:46)
That's an eye-opener. Have been working in industry for a few years now but never realised how small changes like this can affect the system. Thank you so much for the content!
Your way of explanation with real-life examples is really effective. I can visualize everything and remember it easily. Thanks for this.
This method is ok when accessing a cache and the problems that arise are somewhat mitigated by consistent hashing.
However there are two thing i want to point out
1. Caching is typically done using a distributed cache like memcached or redis and the instances should not cache too muchinformation.
2. If you want to divert requests from a particular request id then you should configure your load balancer to use sticky sesssions . The mapping between the request id and the ec2 instance can be stored in a git repo or cookies can be used etc.
Yes, distributed caches are more sensible to cache larger amounts of data. I read your comment on the other video and found that useful too.
Thanks for sharing your thoughts 😁
This was really insightful, I thought load balancing was simple but the bit about not losing your cached data was something I didn't know before.
You seem very passionate about the subject.
It makes it 10x better to learn that way.
Thank you.
Thank you!
Hey man, cool explanation for all the advanced system design learners... nice! keep it coming!!
Thanks!
Hey Gaurav,
You have a knack for explaining things in a very simple manner (ELI5).
There is one part of this discussion which I feel conveys some incorrect information (or I might have understood it incorrectly). You mention that 100% of requests will be impacted on addition of a new server. However, I believe that only 50% of the requests should be impacted (server 1 retains 20% of its original requests, server 2 15%, server 3 10%, and server 4 5%).
In fact, it's always exactly 50% of the requests that are impacted on addition of 1 new server irrespective of the number of original servers. This turned out to be a pretty fun math problem to solve (boils down to a simple arithmetic progression problem at the end).
The reason your calculation results in a value of 100% is because of double calculation: Each request is accounted for twice, once when it is removed from the original server, and then again when it is added to the new server.
Man, thanks! You made this easy to 100% understand. Your teaching style is excellent!
I really like how you explained why we need consistent hashing.
you made it really simple and easy to understand. I don't bother searching any other video on system design, I can simply look into your channel. Thank you very much, appreciate your efforts .
Thank you!
I subscribed/bookmarked your channel I don't know when I knew that I'll need it at some point in time and that time is now. Thank you for the series...❤️❤️
You give great explanations !! And little video editing efforts make the video so interesting. Going to watch all videos uploaded by you.
you are amazing teacher, teaching such a complicated topic in such a efficient manner,I didn,t get even a first job , and i am able to understand
Done thanks
Traditional hashing will make requests go to different servers if new servers are added, and ideally we want requests from the same user to hit the same server to make use of local caching
indian accent is one of accent that can make my learning process easier. It sounds clear on my ears rather native english spoken by most western tutors. Great job man
amazing video with extremely lucid explanations. wishing you the best, keep growing your channel. from a Civil Engineer just randomly crazy about Comp Science.
Just stumbled on your channel, and in few minutes, i have learned a lot
Thanks for the concept lesson !
Hey Gaurav , in the first part of the video you mention and by taking the mod operation you distribute the requests uniformly . What kind of assumptions do you make ( and why) on the hash function which insures that the requests are uniformly distributed . I could come up with a hash function which would send all the requests to say server 1
Quite a smart way of explaining the concept. Keep up the good work. Subscribed!
Thanks bro for sharing your knowledge.Your style of explaining is Great.
This is like the closest thing to an ELI5 on TH-cam !! Greta stuff man 😀🙌
Thank you Gaurav, very cool!
Seriously though, thanks, your videos are really helping me through college. Very epic.
Thanks for sharing. The concept of changing the cache on every server is cool.
The only tutorial with an Indian accent which I enjoy watching :)
Thanks dude! :)
Hi Gaurav great video, can you quickly elaborate on the Pie Chart you made and did the 5+5+10... maths you kinda lost me there and I am trying to figure out intuitively what you tried to show using the Pie Chart example when a new server is added. Thank you!
The pie represents the load on each server, based on the range of requests it shall handle.
The requests have random ids between 0 and M. I draw the pie chart with each point in the circle representing a request ID. Now a range of numbers can be represented by a slice in the pie.
Since the request IDs are randomly and uniformly distributed, I assume that the load on each server is proportional to the thickness of pie slice it handles.
IMPORTANT: I assume the servers cache data relevant to their request ID range, to speed up request processing. For example, take the profile service. It caches profiles. It's pie chart will be all profiles from 0 to M. The load balancer will assign loads to different nodes of this service.
Suppose one node in this service handles the range 10 to 20. That means it will cache profiles from 10 to 20. Hence the cached profiles are (20 - 10) = 10.
The pie calculations in the video show the number of profiles a node has to load or evict, when the number of nodes changes. The more a node has to load and evict, the more work it needs to do. If you put too much pressure on one node (as shown here with the last node), it has a tendency to crash.
The consistent hashing video talks about how we can mitigate this problem :)
@@gkcs Thank you so much for a fast and well detailed response! I understand perfectly now. Very much appreciative of your hard work and dedication when it comes to making videos and reaching out to your audience. Keep up the great work and stay safe! Sending love from Bay Area! 💯
thanks for asking this question, I was also lost in the calculation.
@@gkcs This comment really helped, was a bit confused about the pie chart explanation at first. Thanks.
@@gkcs Still not very clear. DOnt know how you jump to 40 :(
Hello gaurav, when the number of servers increase due to scaling reason from 4 to 5, why do we need the previous request which were getting redirected to a server calculated using %4 needs to be changed? Because those requests are already served that time in past using %4, and from the time we introduce new servers, then the requests from that point of time can be redirected to a server using %5 right?
Love this!
Nice Explanation. Was finding a perfect playlist on YT to teach me SD. Now, its solved. Thank you for such a valuable content.
Awesome!
You can also watch these videos ad-free (and better structured) at get.interviewready.io/learn/system-design-course/basics/an_introduction_to_distributed_systems.
Simple & clean explanation
10:26 - my expression to this video. Amazing content!
Thank you for putting this out!
Helped me a lot! Thank u👏
Hey @Gaurav! Amazing set of videos on system design for newbies like me. I would just like to know if there is any suggested order in which we've to grasp material? Like after the 8th video in this playlist, we have whatsapp system design and then what is an API, NoSQL databases and so on. So, if at all any order exists which allows to learn/grasp concepts in a better way, what order/approach would you suggest ? Thanks :)
Gaurav, your explanation is awesome . i addicted to your way of teaching .
God bless you with more power :-)
This is what I understand about the pie chart explanation. The objective is to reduce the measure of randomness in the distribution of request among the servers because of the caching done on each server and the fact that user request are mapped to specific servers. So you have 100% request been served to 4 servers which means the load is distributed by 25% to each server. When you scaled up and add a new server, you reduce the load on each server by 5% to make up the extra 20% needed by the new server, that way reducing the random user distribution to each server and ensuring that user data stored in the caches is relatively consistent. Correct me if I'm wrong about this, thank you.
Hi Gaurav, you explained the concepts properly. keep it up.
Also focus on the tools you use.
use a better and darker maker.
manage light reflection from the board.
in this video these 2 were bit annoying.
Your way of teaching is good and to the point.
Good luck.
On the entire TH-cam this is best❤️
nice video.thanks.
In case of pie chart explanation, i got overall idea but when u are summing up the delta changes and u sum that to 100.My question is , if a server has lost 10 key and other gained 10 keys , why are we adding this 10 two times?Once as gain and other as loss?Only one time we could have considered 10?
Because it seems u made a total change of 100 keys but instead total change is less than 100 as some keys stayed at original location.Did i miss anything?
I'm late here but the videos are amazing. I'm going to watch the whole playlist
Brilliant. thank you!
Hi Gaurav. Thanks for the informative video . Quick question. How did u got the values h(10) , h(20) and h(35) ? are these the random numbers generated from the server for each request ? Also did how did each of these request generated the hash value of 3, 15 and 12 respectively?
This is informative and thanks once again :-)
You are a great teacher!
Very well explained!!
Hi Gaurav, the concept of load balance design is very good and understandable. Thanks for your effort.
I have small doubt that if same number of old servers removed and added new servers to the distributed system, will this load balance have effect? or will this consistent hashing mechanism be same with no cost effective?
bro I have a doubt can you clarify it.
how does a load balancing with round-robin work internally?
Suppose I want to browse youtube, according to round-robin my request will be sent to one of the servers from the pool of healthy servers after getting a response, next I want to browse my history feature available in youtube(so this a new request will this request go to same previous server or it will go to a new server according to the round-robin algorithm?( i am confused because the new request comes from the same IP address )
Really amazing lecture. Waiting for your B+ Trees video as promised :P
Haha, thanks!
Dear Mr Gaurav,
I am a civil engineer and currently working on one project where we are trying to add some technology in construction activity,
I was struggling to understand what is system design, which is the best combination of front end and back end language, which system design should I adopt and many more things like this as I am not from IT field but I must say you made me understood so many technical thing in very layman language.
Thank you so much for that
Thanks Love!
Check out the first video in this channel's system design playlist for a good definition of system design 😁
I would suggest using python and JavaScript (React or Vue.js) as backend and frontend tech respectively, to start with your software development journey.
Great videos, thank you!
Thanks Gaurav for this interesting series
Keep it up... : )
amazing info..thank you for sharing
Superb bro .. thanks a lot for your efforts to make videos...
awesome! consider blocking the background light with something to reduce light reflection!
Nice video.
I feel that you are meant to be a teacher :) ! You have the flair for it. Not everyone with knowledge can teach it. Do consider when you get time in life ;) ! Cheers, all the best!
Didn't got the pie chart division , by general maths we can get that once we introduce one another server in the pool of 4 servers each server will have 20 buckets (20*5)=100 but that bucket division which is being demonstrated here is bit confusing... Is there any blog or subsequent video on this channel which can clarify the doubt? It would be helpful.
@Gaurav Sen: I want to summarize what I understood from PI chart part, just rectify me if I understood it wrong.
Directly adding another server will definitely reduce the load on each server but if not implemented properly then it
could impact on the cache part. If major of the request got re-directed to different servers than our cache part will be of
not that help to us.
Taking small % of req load will not impact the cache part much.
Exactly!
You got a new subscriber.
You are very very great
8:25 Hi Gaurav - I am somewhat confused by the series of steps for the buckets handover/change ( as illustrated by the pie reallocation diagram ). If I am not mistaken, we have to traverse each server sequentially ( until the last, when we add the 5th server), and additionally, we account first for the buckets lost from the current server, and then account for the buckets gained by the following server, correct?
Take 100 servers and n is 4 , split up is 25 , when n increased to 5 the split up is 20. That is he tries to convey☺️
You got a subscriber!!!
+1
Gaurav your videos are amazing ! Its being a great help . Thank you so much :-)
Thanks!
Thank you sensei !
How adding server to the normal hashing technique is a big change? Are we storing these mapping somewhere of yes then what's the need to that?
I have multiple machines on my backend, all are connected to my load balancer running HAProxy. I just learnt that the response also goes through the load balancer, instead of one of server directly sending it to the client.
But will it not create a bottleneck in case of huge traffic and overload my load balancer itself.
Is there any way to directly send response from server to client.
Also when response goes through load balancer, does my source file also sits there temporarily to be sent to the client.
Can't we use load balancer only to send request to my servers and response to directly go from server to client.
My main goal to make my system distributed was to distribute traffic among my servers, now since load balancer is handling both request and response am I not back to where I started?
nice explanation of the concepts
Hey, thanks for this video. I have a question. If request IDs are randomly generated (with equal probability) why don't we just have them in a range 0..n which maps directly to servers?
Answer: there is an infinite number of requests and only n servers, that's why we need modulo here.
That moment at 10:25.... 😂😂 I actually felt the server engineer cry for help
i couldnot understand the pie chart thing well, what should i read to understand this?
i didn't get the pie chart thing. What he mean by this has to take this 5 bucket at 8:40? and bucket means numbers so here that number is the number of requests that comes to the server? Can somebody please explain me ?
Thanks for the great video!
Is the caching always saved on the server? it can not be saved the api gateway for example? and also, the load balancer, it is on a separate server ? caching can not be saved there? where the pai gateway exist in this architecture?
Have a look at the caching video in the system design series.You can cache on the server, but I'd suggest a global cache.
Awesome explanation
Awesome gk. I would suggest you to more focus on system design videos as it's resources are less
Gaurav, I just love the way you deliver the lectures.
I have a query, You spoke about spending people to specific servers and have their relevant information will be stored in the cache. But won't it be a good idea if we have an independent cache server running master-slave?
That's a good idea too. Infact, for large systems, it's inevitable.
@Gaurav Sen sir could you please explain that how does the server goes up to 40 buckets .......I did not understand at (8:46)
Hi Gaurav, nice an informative video, thanks for that. I have a question, what happens when one server gets overloaded, how does the request gets transferred to the next server, do we just send it the the next server, or is there a better approach for that, like keeping track of requests and sending it to the one having least requests.
Saw the next video, found the answer , thanks
What about deployinng same application on diff servers for tiny change ...is it not expensive
Damn man, you are really good at instruction... sub’d!
Very well explained
Hi Gaurav, Awesome video . Can you please do a video on Distributed Transaction Managment
Thanks! I'll be working on this, yes 😁
You will have a problem if you’re generating random number before hash, without adding one more server, the random number you’re using will make the result from Hash be changed, and the request has already been sent to different server, is it true? Why not use a unique ID before hashing, then you can keep the request always goes to the same server. (The case I’m talking happens before you add one more server since you’re saying request goes to different server if we add one more server is a problem, looks like the problem already there if you’re using random number, is it true?)
X/N, where 1/N is the load factor. What exactly does this load factor represent ?
awesome video brother. keep it up!
Gaurav, one genuine question..All these concepts are so well taught and I'd love to buy your interview prep course. Why isn't concepts like these covered there ?
These are fundamental concepts which I believe should be free. You can watch them ad-free and better structured there.
@@gkcs Hi Gaurav...I have an onsite interview day after tomorrow...and I only gave 1 day to system designing....I am not so proficient in this.... moreover I think I will not do better on coding interviews.... Is 1 day enough for system designing?
@@hossainurrahaman It's less. Are you a fresher or experienced?
@@gkcs I have 4 years of experience...in a service based company
Hi,you are just great!!,when I watched your video first time ,Atonce I subscribed your channel ... I want to know that this system design playlist is enough for placements interview preparation???
Waiting for your reply ....
Amazing!
Nice topic, thank you
:D
Awesome explanation... Waiting for middle ware admin related issues... Was tomcat weblogic
@Gaurav Thank you for the video. I have a question, why do you calculate a hash value for every request id? Why not to determine the node number based on the request id immediately? such as 'requestId % n' instead of 'hash(requestId) % n'?
That is possible too. Hashing guarantees uniform distribution. So if your ID generator does that already, there is no point hashing it again :)
@@gkcs thank you for your reply
@@gkcs
Gaurav Sen Can this also be the reason :
the ID can consist of characters .. so when we hash, it is gonna be a number of which we can take a mod ?
@Gaurav Sen, There is one confusion you create. You mentioned you will get requestId which can be hashed. So when user first time coming to the server, from where you get the requestId, someone need to assign the requestId. If you say that there is one more server/gateway who assign the requestId, then how that server/gateway handle so much of load.
@Gaurav Sen, I appreciate you replied to me on the comments on Code Review Video. I asked this question here because one of my friends got confused after watching this video. He told me that we can always use Consistent Hashing with Load Balancer and Round Robing is no more needed. I then explained to him that when the request comes to the server very first time then there is no request-id and hence you cannot use consistent hashing there.
Awesome, I subscribed ...thanks