14 ms·

Load Balancing

1143 points by kiyanwang 4y ago

akhayam 4y ago
If a picture is worth a thousand words.... a well done animation is gotta be at least 10K words. Thanks for making an old topic fun to read about again!
- samwho 4y ago
  Thanks for your lovely words! <3
  - akhayam 4y ago
    [dead]
  - robocat 4y ago
    Great visual - very elegant! Although the denied requests look slightly wrong: perhaps quickly “bouncing” (less ease-in) and off the outside of the receivers would make it more understandable? But still a fantastic demo without any changes, bravo.
- notyourwork 4y ago
  100% agree, although I have experience and knew the material, I read this through because it was a pleasure to read and the visualizations were engaging. Well done!
  - akhayam 4y ago
    [dead]
captures432 4y ago
[dead]
mystertea 4y ago
Just throwing another positive comment into the fray: Amazing work on this article. Informative, and easy to digest despite being a complex subject. Well done! I learned a lot from this article.
foxy4096 4y ago
This is so Correct! Load Balancing is essential for large websites with huge user base.
dswalter 4y ago
The simulations in this are great. It must have taken a ton of work to get this to such an apparently simple and almost self-explanatory state. Really effective as teaching material; kudos to the author!
- johnorourke 4y ago
  I came here to say the same thing! This is also a great tool for explaining it to non-technical customers.
- samwho 4y ago
  I really appreciate you saying this, you have no idea how much it means to me. I spent many evenings and weekends tweaking this asking myself "is this intuitive to someone whose only experience with this topic is everything prior in this post?" It's important to me that every section is grounded only in all of the previous sections. One of my fundamental beliefs is that anyone can learn anything, provided they're presented the material in the right order.
  - alottabit 4y ago
    I mostly work on desktop tools, and this was a great presentation on a topic I'm rather unfamiliar with. It was communicated very well. Nice work!
adamch 4y ago
Really excellent simulation and explanation. Thank you!
aqibgatoo 4y ago
Very nice depiction of load balancing!
mnutt 4y ago
The simulations are really cool. I'm trying to think of a real-world situation where you'd have differently-sized backends though. I guess it might help if your server runs hourly cron jobs that take away system resources from requests.
- deepfriedrice 4y ago
  Had the same thought. With AWS et al. it's just too easy to use the same instances and avoid that variable.
  - paulddraper 4y ago
    On the contrary, with AWS et al, it's just too easy to have noisy neighbors :)
    - samwho 4y ago
      I don't think many people are intentionally deploying their apps with replicas of different sizes, you're right. But this is it: noisy neighbours, inherent physical differences in even identical hardware, using different node sizes in your clusters. I think incidental differences in servers are very common, even within the same AWS instance category.
      - mnutt 4y ago
        I thought of another variant: with AWS autoscaling groups using spot instances you can list a number of different instance sizes and say "give me whatever is cheapest" and you'll often get a mix.
throwaway71271 4y ago
we are so stuck with this push request load balancing its crazy, if we just switch to pull instead of push things get much smoother, and resources get better utilized you cant reliably guess if the instance where you will push your request actually has capacity to handle it, even using ML to guess it will still have thrashing properties but if you just let instances pull work, things work out for themselves sadly, the whole industry is stuck on http push i was playing with it few years ago making a simple queue and wrote my ideas here: https://punkjazz.org/jack/we-got-it-all-wrong.txt https://punkjazz.org/jack/we-got-it-all-wrong.txt and some basic benchmarks https://punkjazz.org/jack/we-got-it-all-wrong-2.txt https://punkjazz.org/jack/we-got-it-all-wrong-2.txt in the same time, there is so much tooling for http, and its so natural to use it, that it is actually hard to switch to another transport layer, so now the best we have is some naive bayesian classifiers in the LB and some exponential backoff here is the difference i had in timings using synchronous io queue vs http for 2 endpoints, one fast and one slow (endpoints had the same code, just transport was different) 2019/02/19 22:26:27 synchronous QUEUE ... 20000 messages, took: 29.95s, speed: 667.74 per second - 0+10=9711 48.55% ****************************** - 10+ 5= 276 49.94% - 15+ 8= 20 50.03% - 23+12= 16 50.11% - 35+18=3398 67.11% ********** - 53+27=6549 99.85% ******************** - 80+40= 30 100.00% - 120+60= 0 100.00% - 180+90= 0 100.00% - 270+ 0= 0 100.00% 2019/02/19 22:26:56 http ... 20000 messages, took: 29.55s, speed: 676.91 per second - 0+10=3274 16.37% ******************** - 10+ 5=1523 23.98% ********* - 15+ 8=4439 46.18% **************************** - 23+12=4756 69.96% ****************************** - 35+18=3318 86.55% ******************** - 53+27=2037 96.73% ************ - 80+40= 581 99.64% *** - 120+60= 70 99.99% - 180+90= 2 100.00% - 270+ 0= 0 100.00% you can see how the fast endpoint is always fast with the queue transport, but with classic push load balancing it spills latency a lot, because the instance is sometime busy servicing the slow request PS: this post is absolutely amazing! and the animations are brilliant! thanks a lot for making it
- preseinger 4y ago
  if your load balancer holds on to each received request until a downstream server happens to pull that request and process it, then it's not a load balancer, it's a queue different concept, different semantics, different results
jqpabc123 4y ago
I have a simple alternative method in mind for SAAS (software as a service) apps. Manual/statistical load balancing --- assign users to a specific server based on their login credentials. A statistical model of server utilization can be maintained and users assigned or re-assigned as needed. Latency can be reduced to zero by simply forwarding the connection to the proper server once the login is complete. The obvious downside is a custom load balancer implementation is required. Does anyone have any experience using NodeJS as a load balancer for something like this?
- choult 4y ago
  That's called sharding; this can be achieved with any load balancer worth its salt.
  - lucideer 4y ago
    This is called sharding, but the question is more about the assignment algorithm(s) supported by the sharding algorithms, which are not always flexible enough to support the gp's suggestion.
- mkl95 4y ago
  Sounds like sticky sessions
  - jqpabc123 4y ago
    "Sticky" applies after a session has been assigned to a server. I'm interested in control over the assignment algorithm.
    - cett 4y ago
      Definitely doable with HAProxy + lua. I've used it extensively for load balancing stateful apps.
      - jqpabc123 4y ago
bbatchelder 4y ago
The playground simulation is pretty cool. One thing I found interesting, is it you go with PEWMA and create a scenario where the cluster is stressed, and then add 1 server, it pummels the shit out of the new server and you have a brief surge in failed requests. Not sure if that is a real world issue, or just with the simulation...
- samwho 4y ago
  This is very likely a bug in the simulation. My simplified implementation of PEWMA prioritises servers that have had no traffic, in order to send at least 1 request to all servers. There will be a window, until this new server serves its first request, where it is considered the highest priority server. I doubt very much that this would be part of any real world implementation
  - toast0 4y ago
    I'm not familiar with PEWMA, but real load balancers sometimes have this problem. Either because of dynamic weighting that slams the new server which shows zero load, or because the new server needs to do some sort of cache warming, whether that's disk or code or jit or connection establishment or ???, a lot of times early requests are handled slowly. Most load balancers should have a way to do some sort of slow start for newly added or newly healthy servers. That could be an age factor to weighting, or an age factor on max connections or ???. Some older load balancers are just not great at this, so you develop experienced based rules like 'always use round robin, leastconn will kill your servers with lumpy loads'. All that said, and a repeated theme across my comments in this thread, the more sophisticated your load balancing is, the harder your load balancer needs to work, and the sooner you need to figure out how to load balance your load balancers.
- 411111111111111 4y ago
  It should happen in the real world as well, at least that's what I've been told when I started my first job as a system admin. The reason people cited to me back then was that the balancer usually isn't particularly smart when balancing, so they only see a free node, thus every free request is routed to it. The errors (mostly timeout) will happen once the request start to actually get processed. Normally, the node gets a steady amount of requests over time, thus the load is constant (generally speaking, a request will require the most resources at the same relative time of their lifecycle). As all requests are fresh, they'll all hit the same load bottleneck at the same time, causing all the timeouts. The answer is to both aggressively scale horizontally and then quickly decommission until you're back to baseline. Or just accept the failed requests Its been over 10 years though, it mightve been improved since.
sarasaurous 4y ago
Fantastic visualizations!! This makes a complex & dry topic simple, understandable, and engaging. Very well done!
- samwho 4y ago
  Thank you for your early reviews! Genuinely couldn't do it without the people around me.
photochemsyn 4y ago
I'm going to guess the style of this excellent effort was inspired in part by this popular HN poster? Creating a post in this manner with animations does take a lot of work but it's very effective and instructional: https://ciechanow.ski/gps/ https://ciechanow.ski/gps/ Incidentally load balancing and dynamic routing in satellite networks looks like a complicated problem and is a subject of active research: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9231381/ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9231381/
- samwho 4y ago
  Yes! Bartosz Ciechanowski is a huge inspiration to me. This post was my first attempt to imbue some of his style into my writing. I'm not up to his standard by a long way, but I'm very happy with my results. :)
- mgoetzke 4y ago
  That page was indeed a masterpiece in visual communication. Math and Music curriculum teachers and educators should spend time on making all topics approachable like this. It would be a great way to supplement learning by making it interactive. Instead of using iPads as glorified PDF readers. Sadly the quality of e.g our Math Books (in Germany) is so low in many cases that I do not see this happening ever.
bbss 4y ago
Great post! I would have loved to see P2C (Power of 2 Choices) in there as well, which is typically a better alternative to Round Robin and Least Connections.
- samwho 4y ago
  Thank you! <3 P2C is really cool, but it would have meant having to talk about load balancers with incomplete information. This felt like slightly too much to add to an already-quite-long post. It also would have added an extra layer of complexity to my already-quite-complex simulation code :sweat_smile:
NKosmatos 4y ago
Excellent post, very informative and with nice animations (check the bonus interactive animation at the end of the page), my only comment is to use different colours/colors (or dashed lines) for the graphs, it’s a bit confusing having the same color for different percentiles. Also take the time to check out other posts/pages by Sam! Well done mate ;-)
- Abimelex 4y ago
  indeed, a really great post! In case you decide to change the colors or need another reason I also want to add, that in general red/green is difficult for color-blind people. About 8% of male population is affected by red/green color blindness.
  - samwho 4y ago
    The colour palette I used on the graphs is the Wong palette I found at https://davidmathlogic.com/colorblind/ https://davidmathlogic.com/colorblind/. Or are you talking about the animations? I reached out to some colourblind folks I knew before publishing and they didn’t flag those, just the graphs. Happy to change the animations as well if they’re problematic. :)
    - ricardobeat 4y ago
      The PEWMA vs LC bar graph uses red and green, and ends up looking like single set of brown bars.
jayd16 4y ago
Good post. Although, this just scratches the surface. There's also caching mechanisms involved in handling requests that might make similar requests faster when served by the same host. Now you're tempted to add sticky sessions to the mix and deal with the perks and problems that comes with that.
- samwho 4y ago
  Absolutely! I had to pick a stopping point in order to restore balance to my personal life :D I'd love to see people taking this as inspiration and covering the more advanced topics. I've already started on my next post and it's about a completely different area to load balancing. Very excited.
- mnutt 4y ago
  You could go with sticky sessions, or consistent hashing to maximize cache hit rate. Then you may run into hotspots and look at bounded-load consistent hashing, etc.
er0k 4y ago
Great visualizations. There is also a wonderful talk on this topic called Load Balancing is Impossible by Tyler McMullen https://www.youtube.com/watch?v=kpvbOzHUakA https://www.youtube.com/watch?v=kpvbOzHUakA
zokier 4y ago
Least connections is intuitively very sensible algorithm, but it has one pitfall: if backend server starts returning errors for whatever reason (e.g. load shedding) quicker than typical responses, it can lead to situation where disproportionate number of requests are directed to that one server. Also typically you'd have more than one load balancer instance, and at least naive least connections requires shared state (backend connection counts) between the instances, while with round-robin you can avoid that?
- samwho 4y ago
  Least connections doesn't need shared state between the instances, but it would need shared state between the load balancers if you had more than one for sure. You're totally right, I glossed right over errors. With PEWMA and weighted round robin you can make instances incur a "penalty" for serving errors, which can help you isolate bad servers. It would have been fun to visualise this, definitely.
  - mst 4y ago
    It also strikes me that it might be interesting to model least connections with two or three LBs with and without such shared state. My instinct is that you'd still get most of the advantages even with each LB keeping its own independent connection counts, but given the number of times I've fired up a profiler and gone "wait, seriously, -that-s the slow part?!" I'd suggest nobody believes me and measures it instead.
- sesm 4y ago
  There is a talk about Fitbit load balancer on YouTube, where their algorithm is described. They used modified least connections algorithm, which also tracks failure rate of each node, decreasing the traffic when error rate is increased. The video is called "A Frontend Server, Front to Back by Zach Tellman", timestamp 33:34.
- ed_balls 4y ago
  you can improve this be picking top 3 server with least connections and then pick one randomly from these 3 servers.
naikrovek 4y ago
Why is there not a queue system where a server can pull requests when it's ready to handle one? Why must the work to determine where to send a request go to the load balancer, when you could just pull from a queue and save yourself the trouble of finding the exact right load balancer strategy for your application?
- jmholla 4y ago
  The thread up here [0] is talking about that in case you missed it. [0]: https://news.ycombinator.com/item?id=35613454 https://news.ycombinator.com/item?id=35613454
- bityard 4y ago
  The short answer is that it's more complicated to engineer and has its own set of trade-offs. With the push-based models shown in the article, everything works regular HTTP(S), no fancy routing is needed, and the LB needs to keep very little state to do its job.
  - naikrovek 4y ago
    seems like a request could be pulled from a queue with HTTPS easily enough. and if I am misunderstanding what you're saying, I don't understand why a purely request-driven path is so vital; it's just a way to me ve data around. seems like the queue could accept the request, keep the https connection open, wait for a response from whatever server accepts the request, and pass the response to the client upon receipt just fine. I dunno. web stuff is poorly done imo. poorly designed.
cod1r 4y ago
This is an awesome blog. Learned a quite a bit! And bookmarked for future reference! <3 :)
jamespo 4y ago
Availability is briefly mentioned but it'd be nice to have a simulation where members of the LB group fail
- samwho 4y ago
  This and slow-start were on my original to-do list for this post, but I wanted to keep it to a certain length and complexity so they ended up getting cut. There's a tonne of cool stuff to visualise in this space, I was spoilt for choice. Slow start, server flapping, session stickiness, dozens more algorithms, multiple load balancers with incomplete state, multiple levels of load balancers, the list probably goes on. :D
throwaway894345 4y ago
I’ve always been more curious about how load balancers are supposed to be highly available? Presumably you run many instances, but then it seems like you need something to balance the load across your load balancer instances? Also, how do many load balancer instances listen on the same IP address (or do they use DNS to map a domain name to multiple IP addresses?)?
- samwho 4y ago
  You've got it, DNS is what's often used to solve this problem. Do a few resolutions of reddit.com, you can see them returning 4 different IP addresses in a randomised order. :)
  - c7DJTLrn 4y ago
    CDNs such as Cloudflare also do anycast routing which means you can hit the same IP in different places in the world and get a response from the nearest point-of-presence.
- toast0 4y ago
  A classical load balancer runs in an HA hot-warm pair, with IP takeover --- when the secondary senses the primary has failed, it takes over the IP and begins serving. Depending on the type of load balancing and the software involved, this could be nearly seamless, or it could end all sessions in progress. If you want to run hot-hot load balancing on a single IP, it's generally done with routing protocols. Equal cost multi-path (ECMP) will split traffic by hashing on some portion of the (source IP, dest IP, protocol, source port, dest port) 5-tuple; you'd configure your router to enable ECMP, and then your load balancers would advertise the IP via BGP or RIP or whatever is cool these days. Communication between load balancers to handle sessions that move during failover and bring-up is optional (if you don't do it, sessions will end abruptly); this setup is similar to anycast, although with anycast you may also see sessions move when external routing changes, and you really should manage that. You also should have a method to handle ICMP packets, most specificially needs-frag packets, as they will be sent from a different IP than the connection peer and will likely hash differently and may likely route differently for anycast, too. You can use DNS to direct traffic to multiple load balancers, but DNS is not a precision instrument. It's useful for geographic balancing (in addition to anycast), but resolvers have a tendancy to cache results for longer than published TTLs and it takes significant effort to understand how much request traffic a given resolver will generate from one lookup. For balancing between two load balancers where you want roughly equal traffic, you also need to consider pathologic behavior like RFC 3484 and RFC 6724. These two RFCs suggest preferentially using IPs with a larger common prefix when multiple options are available. This only makes sense when the common prefix is meaningful. If your ISP was assigned 10.1.2.0/24 and I have service IPs of 10.1.7.3 and 10.2.4.5 and return both of those as A records, your resolver shouldn't really prefer one or the other, because beyond your ISP prefix, there's no actual network closeness implied by a similar IP. 'Smart' resolvers that follow this RFC can cause large scale traffic imbalances, so fun times there.
maltris 4y ago
The visualizations are perfect, I will add this to our trainee introduction on loadbalancing.
openizr 4y ago
[dead]
AYBABTME 4y ago
I feel like something missing from people's perspective when thinking of load balancing is to consider pull models. All push load balancing algorithms try to somehow predict how busy downstreams are. Some even go as far as having downstreams send back some utilization metrics. But if you use a pull-based approach, this is all sort of moot. Downstreams will pull work when they're ready for it.
- wmf 4y ago
  For most protocols like HTTP there's no software to do this and it's not worth developing something nonstandard.
  - blipvert 4y ago
    Should be something that could quite easily be added to a uWSGI subscription router - subscribing node periodically says “I have N slots available” and the router keeps track of how many requests are in flight.
- orthecreedence 4y ago
  The pull model works beautifully for background work queues. For load balancing it seems it would take a bit of re-plumbing on the expectations of request/response. How would you envision this working with something like HTTP? It seems it would reverse the direction, which would be interesting.
  - AYBABTME 4y ago
    Very similar to background queues but the load balancer holds the request and dispatches it to a waiting worker, or waits until someone comes to serve it. While the worker handles the request, the load balancer proxies. The request serving is the same, the way the work is dispatched is just inverted.
    - bityard 4y ago
      Seems like this wouldn't work as well in situations where you care a lot about latency or resource utilization. If the workers are polling the LB every n ms, then that's an average of n / 2 ms added to _every_ request. Plus additional CPU cycles and network traffic on both ends due to the polling mechanism.
ahmadnoid 4y ago
What I don't understand is since it's the same service can't we just run a performance test, determine the ballpark of the needed resources and just have them capped like in k8s? why would some servers be more powerful than others in the first place?
- cdot2 4y ago
  Some requests may require utilizing different services than others.
  - samwho 4y ago
    Yeah, this for sure. Traffic mix changes over the life of an application. In k8s performance isolation certainly isn't a solved problem, and noisy neighbours can affect the "power" of a server. Any change to the application at all could upset the delicate balance of its performance. You would need to be doing this sort of profiling on every change, using up to date and accurate production traffic. It ends up being much easier to put some smarts in your load balancer.
- mutagen 4y ago
  ‘Noisy neighbor’ VMs and different underlying hardware specs on the ‘same’ instance configuration are two examples that come to mind.
- adql 4y ago
  One perfectly homogenous server gets 20MB POST with image that then needs to be reencoded/cropped Other gets tiny GET for CSS. Boom, now your equal servers are inequally loaded. The beauty of leastconn is that if 1st server is loaded it will just naturally get less connections than the lucky ones that only got easy jobs
chrisweekly 4y ago
Fantastic post; useful and entertaining. 10/10, bookmarked, will share. Context: perf-related webdev since 1998.
victor106 4y ago
Well written and animated!! Anyone knows what technology was used for the animation?
- samwho 4y ago
  I used https://pixijs.com/ https://pixijs.com/. This was my first project with it and it was really nice to use. I fell in to a few traps here and there, but generally it wasn't too bad to get the results I wanted with it. :)
  - talentedRed 4y ago
    I'd love to see the source code of it :)
    - samwho 4y ago
      It’s just plain JS, you can see it here: https://samwho.dev/js/load-balancers.js https://samwho.dev/js/load-balancers.js Just like the good old days :)
Nijikokun 4y ago
Interactive diagrams and visuals are worth so much with these topics. I just created documentation at ngrok (full disclosure, I work there!) for how to do load balancing with their edges product for this the other day! Now I have something to refer people to when describing these. https://ngrok.com/docs/guides/how-to-round-robin-load-balance-with-ngrok-cloud-edges/ https://ngrok.com/docs/guides/how-to-round-robin-load-balanc...
- samwho 4y ago
  Big ngrok fan, keep up the awesome work!
- strunz 4y ago
  Boy have I got the perfect site for you - https://ciechanow.ski/archives/ https://ciechanow.ski/archives/
chasd00 4y ago
iirc there was a famous case where an outage occurred at a company using some least connection or least resource algorithm in the load balancers. The load balancer queue'd up requests and when a new server was brought online it immediately dos'd it out of existence. Then another server was brought online and the same thing occurred and another and another. They eventually switched to round-robin to give the new servers coming online a fighting chance to survive. Eventually, enough were online to process the queue. the take away was complex load balancing can make problems worse when bad things happen unexpectedly.
- samwho 4y ago
  Yes! This is called a “thundering herd” problem: https://en.m.wikipedia.org/wiki/Thundering_herd_problem https://en.m.wikipedia.org/wiki/Thundering_herd_problem. The topic is definitely much more complex than what I was able to cover in a single post :)
kriz9 4y ago
It is nice to see someone writing that a single server is enough for a lot of websites/apps - if not most. Computers are insanely fast nowadays.
donalhunt 4y ago
Would love to see the following scenarios explored too: - failure of a backend node - adding additional capacity From experience both scenarios can trigger non-obvious behaviours (especially when you have backends with different power levels).
interroboink 4y ago
A small note on "least connections" load balancing. The article says: Because the load balancer sits between the server and the user, it can accurately keep track of how many outstanding requests each server has. and this is the common case. But there are some cases, such as when serving audio/video streams (looking at you, porn :) where the server will send its response straight to the user, not back through the load balancer. So, the load balancer doesn't know how busy the server is, unless that information is communicated separately, through some other channel. One variation is "least sessions", where the number of active sessions rather than connections is used, and as mentioned, that info is stored separately from the "main" connection, and available on the load balancer for its decision-making. Example: https://www.youtube.com/watch?v=tAAmZ3bz8AA&t=681s https://www.youtube.com/watch?v=tAAmZ3bz8AA&t=681s
- strunz 4y ago
  Yeah this was the most confusing part of the whole article to me, and seemed like the most important. I was like "how is it keeping track of how many connections are still being processed?"
  - jacurtis 4y ago
    In most situations (not all) the load balancer is actually a proxy. So when you type in example.com, the dns points to a load balancer. You connect to a load balancer, the load balancer opens a connection with the desired server (probably sitting in a private network somewhere), and proxies the traffic to the server. You never actually connect to the server in this case. You stay connected to the load balancer the whole time, the load balancer makes a request to the server, which processes your request, and sends it back to the load balancer, which then proxies the data back to you in the response. In this case the LB sits between you (the user) and the actual server running the application. In this case the LB knows how many connections each server has in the system because it is actually the one connected to the servers. If a server drops a connection, the LB knows because its the one that actually is losing connection. So it is fully aware of what all servers are doing in this scenario. The only thing the load balancer might still need to do is ping servers for health checks to make sure they are online when the servers are not connected, this is also how it knows latency and other metrics.
ned1010 4y ago
Thank you for this high quaility explanation of this topic. Something that no model will ever be able to generate. I enjoy reading it.
edude03 4y ago
I love this simulation it's the best visualization I've seen of load balancing concepts. One thing though - in my experience the biggest challenge I typically see is that different requests take different amounts of time for example you're running multiple instances of your monolith and there is an endpoint that returns a static response and another one that generates a huge report. This is actually something that can be handled with a load balancer that can introspect layer 7 but that's a whole other thing
- samwho 4y ago
  I do talk about variable request cost a fair bit, but I really don't think I did a good job visualising it. The rate at which each request shrinks while it's being processed by a server is meant to represent cost, but it's pretty subtle and easy to miss unless you're really watching closely. If I were to do this again, making request cost more obvious would be something I'd like to do. I had initially had requests by variable in size on screen, and moved away from that because load balancers don't typically know the cost of a request up front.
lowflyingcondor 4y ago
Would be cool to supplement this with what we know happens to all of these strategies when the load balancer's snapshot of server load is stale. https://brooker.co.za/blog/2012/01/17/two-random.html https://brooker.co.za/blog/2012/01/17/two-random.html
er4hn 4y ago
Beautiful animations! I love how they make understanding this more intuitive and can be adjusted to play with different settings. One thing that I generally felt is missing in these discussions is how TLS messes up load balancing strategies. I did my own research on what to do when you want to have TLS and not terminate at the load balancer. I covered that in a blog post available here: https://er4hn.info/blog/2023.02.18-tls-load-balancer/ https://er4hn.info/blog/2023.02.18-tls-load-balancer/
hamilyon2 4y ago
I always thought that for hundreds of backends and above 10K RPS those algorithms scale poorly. First of all, scaling beyond single load balancer becomes a problem. The cost of updating counters becomes significant. If responses are quick, the cost additional bookkeeping adds doesn't pay off. Of you use weighted random all these problems go away. Is my knowledge outdated?
- preseinger 4y ago
  updating a counter (in memory on a single host) is typically a single- or double-digit-nanoseconds operation, basically never the bottleneck in anything
- samwho 4y ago
  Weighted random is one of the algorithms available in the playground at the end. I did originally have a section talking about it but cut it for length reasons. Very few people in practice are serving 10K RPS.
- adql 4y ago
  Well, in short, yes. > I always thought that for hundreds of backends and above 10K RPS those algorithms scale poorly https://www.haproxy.com/blog/haproxy-forwards-over-2-million-http-requests-per-second-on-a-single-aws-arm-instance/ https://www.haproxy.com/blog/haproxy-forwards-over-2-million... > First of all, scaling beyond single load balancer becomes a problem. If you are in DC or have L3 access to the underlying network ECMP is VERY easy way to scale to 4-16 loadbalancers. Over that just... use multiple IPs. We use ECMPed setup of 4 nodes since forever and it works very well. There are theoretical improvements that could be made by doing L4 loadabalancing into L7 loadbalancing, but you'd need a hell lot of traffic to ever need that > The cost of updating counters becomes significant. If responses are quick, the cost additional bookkeeping adds doesn't pay off. Essentially, yes but if you have some architecture that talks very little (say just few packets per connection, let's assume some IoT garbage), you probably just want different architecture altogether; like "first request gets you assigned server, then you talk to it directly without LB". L4 balancing is also an option. In essence, if somehow performance of leastconn algorithm is your bottleneck, you're both big enough and specialized enough to go with another approach than "just dump all traffic at few loadbalancers"
xyzzy4747 4y ago
If the requests are similar (i.e. don't have unique user data in them), it's best to put a high performance reverse proxy in front that has some caching. This way you don't have to execute lots of code for every request.
- samwho 4y ago
  Caching is something I want to cover in a separate post :)
mparnisari 4y ago
i'm a visual person so i loved the animations! more like these please!
quickthrower2 4y ago
This is good teaching. You can get a concept across in a few minutes, or you can make someone struggle for hours to understand. I think classic academic teaching, leans towards the latter (imagine a latex pdf that introduces an alphabet of Greek letters), vs. this, which learns you the concept pretty quick. You can them do the Greeks letters version later.
- zamnos 4y ago
  (which teaches you the concept pretty quick.)
  - quickthrower2 4y ago
    Thanks, it was a actually subtle reference/nod to the “learn you a haskell” book.
dtjohnnymonkey 4y ago
This is so timely for me, I've been wondering how I can visualize load balancing algorithms for the last few weeks. When trying to explain why round robin is bad, I often try to describe a situation where a backend cluster with a wide variance in performance can cause a cluster of clients using round-robin load balancing to start developing a sort of harmonic resonance where all the clients slowly synchronize on which servers they are hitting. However, it's hard to explain in words and a visual simulation would help me explain. Do you think it would be easy for me to hack the source and add multiple clients to the simulation?
- zamnos 4y ago
  Shouldn't be too hard to add the clients since, in terms of the animation, they're just flipped versions of the server. The question is if this resonance is going to require some intentionality to it to demonstrate/replicate.
- samwho 4y ago
  You have my blessing to try. The source is all in one file and is just plain JS, no minification or anything. I’ll warn you: the code is a bit messy. I wrote it knowing it was just for me and was a one off :D
vivegi 4y ago
Several years ago, I implemented an application specific load balancer where the LB kept two queues. One was free_workers and the other was open_requests. Initially, upon startup, each worker registers itself with the LB and gets added to the free_workers queue. When requests arrive at the LB, the LB checks if there are free workers available. If yes, it dequeues a free worker and dispatches the request to that worker. If no free workers are available, the LB adds the request to the open_requests queue. When a worker finishes its work, it lets the LB know and the LB adds the free worker to the end of the free_workers queue and initiates another round of dispatching. The parameter to watch for is the queue size for the open_requests queue. (There were a few more nitty gritty details, but that was the concept at a high level)
- ReaLNero 4y ago
  But then your LB is a single point of failure! Even if you were to spin up duplicate copies of the LB that could be failed-over-to in real time, there is still the drawback that you are bounded by the number of requests you can store on a single machine. I think what you actually built is a message queue engine that forwards the data to the consumers, not a load balancer.
mattbillenstein 4y ago
What a great post!
hahnchen 4y ago
does a single load balancer ever get overwhelmed? what do you do when that happens?
- samwho 4y ago
  Yeah, it does! There are a few options, I’ll mention 2: 1. You can use DNS to return IP addresses to multiple load balancers. 2. You can have N load balancers that are themselves behind another, beefier load balancer. Plenty of other magical things that have been done to solve this problem, but I think those 2 are quite common and flow naturally from the ideas the post covers.
Myrmornis 4y ago
I think it might be worth adding to this some discussion of how the load balancer itself handles the load, and the related fact that _within_ some backends, the responsibility for load-balancing falls on rich clients that maintain knowledge of the server sets to which they can route requests.
- adql 4y ago
  And the fact that you should tune for loadbalancer to queue and eventually drop, not your app server. Then in case of leastconn there will be no dropped connections as long as total server capacity < incoming traffic.
adql 4y ago
Leastconn also have very nice characteristics, that if your app say gets into long GC it will near-immediately stop sending connections there Also the "overrun" of dropped connections shouldn't really happen if * incoming connections are < total capacity * loadbalancer have server limits set properly and doesn't send too many connections for app to stgart dropping * loadbalancer itself is one queuing (as it "knows" the next server that should get the connection) So that part of the description is subtly wrong; you WANT to queue on loadbalancer, not on app servers. The app server should have queue just long enough to feed all the threads but not enough to start dropping anything
dazbradbury 4y ago
AWS Application Load Balancers seem to default to round-robin, would be interested to hear how many people change this to their "least connections" equivalent called "LOR" [1]? And why they don't support any other options? I'd guess AWS default to round robin because it's the least complex, and doesn't have issues like if a worker responds extremely quickly due to an error (eg. returns a 500 immediately) then using LOR it seems it would consume all the requests until it's taken out of service by any health checks. But maybe there are other potential downsides? [1] - https://aws.amazon.com/about-aws/whats-new/2019/11/application-load-balancer-now-supports-least-outstanding-requests-algorithm-for-load-balancing-requests/ https://aws.amazon.com/about-aws/whats-new/2019/11/applicati...
- AdamN 4y ago
  You point out a good gotcha that most people don't notice - many host-specific errors are often faster than the standard response and more traffic will route to those hosts with a performance-based heuristic. A well configured LB would have hosts with responses that take them out of rotation for known fault conditions - but at scale that's hard for companies to validate.
  - zamnos 4y ago
    At scale, with also having scaled systems engineers, it's not, like, impossibly hard. A sidecar like Envoy can be configured to emit health stats which can then be read by the load balancer to consider a given server unhealthy. Again, at scale, but each team is already responsible for a dashboard with health metrics for their service, so the load balancer team doesn't have to try and determine everybodies health metrics, only their own.
- base 4y ago
  Depending on the app might not have better performance. The reason is that a host with more connections might not be using more resources than one with less connections. The busy connections might be waiting for a reply from an external service.
- zamnos 4y ago
sporn656 4y ago
[dead]
wolfcub7865 4y ago
[dead]
poemsporn75 4y ago
[dead]
mystique5784 4y ago
[dead]
justonemore65 4y ago
[dead]
able7574 4y ago
[dead]
creature63 4y ago
[dead]
spicysugar54 4y ago
[dead]
gypsysoul65 4y ago
[dead]
lustforlife451 4y ago
[dead]
wine5433 4y ago
[dead]
whatsthetea54 4y ago
[dead]
justdogs573 4y ago
[dead]
ssense74 4y ago
[dead]
gyourstory35 4y ago
[dead]
- dragontamer 4y ago
  Queuing theory is nice, but then again its completely abstract and mathematical. Real life issues get in the way. In particular: for many parallelization problems, its simply not worth the effort to ever load balance. Tasks are too small and the "time spent calculating where to go" is more expensive than just accomplishing the task to begin with. (Ex: Matrix multiplication can be seen as a parallelization of multiplies, followed by a set of additions. The multiplies are too cheap to perform any form of load-balancing, executing in just one clock tick). So in reality, we have "fine grained parallelism", and "coarse grained parallelism". Coarse grained is where load balancing is feasible (the task is "big enough" that its worth spending a bit of CPU time figuring out load balancing). "Fine grained" is very difficult, and is in the realm of CPU design (CPUs will execute your instructions out-of-order to discover parallelism)... though software also plays a role. ---------- That being said, I probably should study more queuing theory myself. The math seems less about "how to design a good parallel system" and more focused on "how to measure a parallel system" (ex: throughput * latency == state... which means you can measure latency == state/throughput, and other such mathematical tricks). The math is simple, albeit abstract. Its not there for "deeper understanding", its there for "even basic understanding" (but much much faster to calculate if you already know queuing theory).
- preseinger 4y ago
  i don't think anything claimed here requires that lbs or apps are single-tenant on their machines, or that load balancing is connection-oriented
deleted 4y ago
[deleted]
angelhearts45 4y ago
[dead]
smashfizzle754 4y ago
[dead]
thelight453 4y ago
[dead]
curioussoul46 4y ago
[dead]

1143 points by kiyanwang 4y ago

If a picture is worth a thousand words.... a well done animation is gotta be at least 10K words. Thanks for making an old topic fun to read about again!

samwho 4y ago
Thanks for your lovely words! <3
- akhayam 4y ago
  [dead]
- robocat 4y ago
  Great visual - very elegant! Although the denied requests look slightly wrong: perhaps quickly “bouncing” (less ease-in) and off the outside of the receivers would make it more understandable? But still a fantastic demo without any changes, bravo.
notyourwork 4y ago
100% agree, although I have experience and knew the material, I read this through because it was a pleasure to read and the visualizations were engaging. Well done!
- akhayam 4y ago
  [dead]

captures432 4y ago

[dead]

mystertea 4y ago

Just throwing another positive comment into the fray: Amazing work on this article. Informative, and easy to digest despite being a complex subject. Well done! I learned a lot from this article.

foxy4096 4y ago

This is so Correct! Load Balancing is essential for large websites with huge user base.

dswalter 4y ago

The simulations in this are great. It must have taken a ton of work to get this to such an apparently simple and almost self-explanatory state. Really effective as teaching material; kudos to the author!

johnorourke 4y ago
I came here to say the same thing! This is also a great tool for explaining it to non-technical customers.
samwho 4y ago
I really appreciate you saying this, you have no idea how much it means to me. I spent many evenings and weekends tweaking this asking myself "is this intuitive to someone whose only experience with this topic is everything prior in this post?" It's important to me that every section is grounded only in all of the previous sections. One of my fundamental beliefs is that anyone can learn anything, provided they're presented the material in the right order.
- alottabit 4y ago
  I mostly work on desktop tools, and this was a great presentation on a topic I'm rather unfamiliar with. It was communicated very well. Nice work!

adamch 4y ago

Really excellent simulation and explanation. Thank you!

aqibgatoo 4y ago

Very nice depiction of load balancing!

mnutt 4y ago

The simulations are really cool. I'm trying to think of a real-world situation where you'd have differently-sized backends though. I guess it might help if your server runs hourly cron jobs that take away system resources from requests.

deepfriedrice 4y ago
Had the same thought. With AWS et al. it's just too easy to use the same instances and avoid that variable.
- paulddraper 4y ago
  On the contrary, with AWS et al, it's just too easy to have noisy neighbors :)
  - samwho 4y ago
    I don't think many people are intentionally deploying their apps with replicas of different sizes, you're right. But this is it: noisy neighbours, inherent physical differences in even identical hardware, using different node sizes in your clusters. I think incidental differences in servers are very common, even within the same AWS instance category.
    - mnutt 4y ago
      I thought of another variant: with AWS autoscaling groups using spot instances you can list a number of different instance sizes and say "give me whatever is cheapest" and you'll often get a mix.

throwaway71271 4y ago

we are so stuck with this push request load balancing its crazy, if we just switch to pull instead of push things get much smoother, and resources get better utilized you cant reliably guess if the instance where you will push your request actually has capacity to handle it, even using ML to guess it will still have thrashing properties but if you just let instances pull work, things work out for themselves sadly, the whole industry is stuck on http push i was playing with it few years ago making a simple queue and wrote my ideas here: https://punkjazz.org/jack/we-got-it-all-wrong.txt https://punkjazz.org/jack/we-got-it-all-wrong.txt and some basic benchmarks https://punkjazz.org/jack/we-got-it-all-wrong-2.txt https://punkjazz.org/jack/we-got-it-all-wrong-2.txt in the same time, there is so much tooling for http, and its so natural to use it, that it is actually hard to switch to another transport layer, so now the best we have is some naive bayesian classifiers in the LB and some exponential backoff here is the difference i had in timings using synchronous io queue vs http for 2 endpoints, one fast and one slow (endpoints had the same code, just transport was different) 2019/02/19 22:26:27 synchronous QUEUE ... 20000 messages, took: 29.95s, speed: 667.74 per second - 0+10=9711 48.55% ****************************** - 10+ 5= 276 49.94% - 15+ 8= 20 50.03% - 23+12= 16 50.11% - 35+18=3398 67.11% ********** - 53+27=6549 99.85% ******************** - 80+40= 30 100.00% - 120+60= 0 100.00% - 180+90= 0 100.00% - 270+ 0= 0 100.00% 2019/02/19 22:26:56 http ... 20000 messages, took: 29.55s, speed: 676.91 per second - 0+10=3274 16.37% ******************** - 10+ 5=1523 23.98% ********* - 15+ 8=4439 46.18% **************************** - 23+12=4756 69.96% ****************************** - 35+18=3318 86.55% ******************** - 53+27=2037 96.73% ************ - 80+40= 581 99.64% *** - 120+60= 70 99.99% - 180+90= 2 100.00% - 270+ 0= 0 100.00% you can see how the fast endpoint is always fast with the queue transport, but with classic push load balancing it spills latency a lot, because the instance is sometime busy servicing the slow request PS: this post is absolutely amazing! and the animations are brilliant! thanks a lot for making it

preseinger 4y ago
if your load balancer holds on to each received request until a downstream server happens to pull that request and process it, then it's not a load balancer, it's a queue different concept, different semantics, different results

jqpabc123 4y ago

I have a simple alternative method in mind for SAAS (software as a service) apps. Manual/statistical load balancing --- assign users to a specific server based on their login credentials. A statistical model of server utilization can be maintained and users assigned or re-assigned as needed. Latency can be reduced to zero by simply forwarding the connection to the proper server once the login is complete. The obvious downside is a custom load balancer implementation is required. Does anyone have any experience using NodeJS as a load balancer for something like this?

choult 4y ago
That's called sharding; this can be achieved with any load balancer worth its salt.
- lucideer 4y ago
  This is called sharding, but the question is more about the assignment algorithm(s) supported by the sharding algorithms, which are not always flexible enough to support the gp's suggestion.
mkl95 4y ago
Sounds like sticky sessions
- jqpabc123 4y ago
  "Sticky" applies after a session has been assigned to a server. I'm interested in control over the assignment algorithm.
  - cett 4y ago
    Definitely doable with HAProxy + lua. I've used it extensively for load balancing stateful apps.
    - jqpabc123 4y ago

bbatchelder 4y ago

The playground simulation is pretty cool. One thing I found interesting, is it you go with PEWMA and create a scenario where the cluster is stressed, and then add 1 server, it pummels the shit out of the new server and you have a brief surge in failed requests. Not sure if that is a real world issue, or just with the simulation...

samwho 4y ago
This is very likely a bug in the simulation. My simplified implementation of PEWMA prioritises servers that have had no traffic, in order to send at least 1 request to all servers. There will be a window, until this new server serves its first request, where it is considered the highest priority server. I doubt very much that this would be part of any real world implementation
- toast0 4y ago
  I'm not familiar with PEWMA, but real load balancers sometimes have this problem. Either because of dynamic weighting that slams the new server which shows zero load, or because the new server needs to do some sort of cache warming, whether that's disk or code or jit or connection establishment or ???, a lot of times early requests are handled slowly. Most load balancers should have a way to do some sort of slow start for newly added or newly healthy servers. That could be an age factor to weighting, or an age factor on max connections or ???. Some older load balancers are just not great at this, so you develop experienced based rules like 'always use round robin, leastconn will kill your servers with lumpy loads'. All that said, and a repeated theme across my comments in this thread, the more sophisticated your load balancing is, the harder your load balancer needs to work, and the sooner you need to figure out how to load balance your load balancers.
411111111111111 4y ago
It should happen in the real world as well, at least that's what I've been told when I started my first job as a system admin. The reason people cited to me back then was that the balancer usually isn't particularly smart when balancing, so they only see a free node, thus every free request is routed to it. The errors (mostly timeout) will happen once the request start to actually get processed. Normally, the node gets a steady amount of requests over time, thus the load is constant (generally speaking, a request will require the most resources at the same relative time of their lifecycle). As all requests are fresh, they'll all hit the same load bottleneck at the same time, causing all the timeouts. The answer is to both aggressively scale horizontally and then quickly decommission until you're back to baseline. Or just accept the failed requests Its been over 10 years though, it mightve been improved since.

sarasaurous 4y ago

Fantastic visualizations!! This makes a complex & dry topic simple, understandable, and engaging. Very well done!

samwho 4y ago
Thank you for your early reviews! Genuinely couldn't do it without the people around me.

photochemsyn 4y ago

I'm going to guess the style of this excellent effort was inspired in part by this popular HN poster? Creating a post in this manner with animations does take a lot of work but it's very effective and instructional: https://ciechanow.ski/gps/ https://ciechanow.ski/gps/ Incidentally load balancing and dynamic routing in satellite networks looks like a complicated problem and is a subject of active research: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9231381/ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9231381/

samwho 4y ago
Yes! Bartosz Ciechanowski is a huge inspiration to me. This post was my first attempt to imbue some of his style into my writing. I'm not up to his standard by a long way, but I'm very happy with my results. :)
mgoetzke 4y ago
That page was indeed a masterpiece in visual communication. Math and Music curriculum teachers and educators should spend time on making all topics approachable like this. It would be a great way to supplement learning by making it interactive. Instead of using iPads as glorified PDF readers. Sadly the quality of e.g our Math Books (in Germany) is so low in many cases that I do not see this happening ever.

bbss 4y ago

Great post! I would have loved to see P2C (Power of 2 Choices) in there as well, which is typically a better alternative to Round Robin and Least Connections.

samwho 4y ago
Thank you! <3 P2C is really cool, but it would have meant having to talk about load balancers with incomplete information. This felt like slightly too much to add to an already-quite-long post. It also would have added an extra layer of complexity to my already-quite-complex simulation code :sweat_smile:

NKosmatos 4y ago

Excellent post, very informative and with nice animations (check the bonus interactive animation at the end of the page), my only comment is to use different colours/colors (or dashed lines) for the graphs, it’s a bit confusing having the same color for different percentiles. Also take the time to check out other posts/pages by Sam! Well done mate ;-)

Abimelex 4y ago
indeed, a really great post! In case you decide to change the colors or need another reason I also want to add, that in general red/green is difficult for color-blind people. About 8% of male population is affected by red/green color blindness.
- samwho 4y ago
  The colour palette I used on the graphs is the Wong palette I found at https://davidmathlogic.com/colorblind/ https://davidmathlogic.com/colorblind/. Or are you talking about the animations? I reached out to some colourblind folks I knew before publishing and they didn’t flag those, just the graphs. Happy to change the animations as well if they’re problematic. :)
  - ricardobeat 4y ago
    The PEWMA vs LC bar graph uses red and green, and ends up looking like single set of brown bars.

jayd16 4y ago

Good post. Although, this just scratches the surface. There's also caching mechanisms involved in handling requests that might make similar requests faster when served by the same host. Now you're tempted to add sticky sessions to the mix and deal with the perks and problems that comes with that.

samwho 4y ago
Absolutely! I had to pick a stopping point in order to restore balance to my personal life :D I'd love to see people taking this as inspiration and covering the more advanced topics. I've already started on my next post and it's about a completely different area to load balancing. Very excited.
mnutt 4y ago
You could go with sticky sessions, or consistent hashing to maximize cache hit rate. Then you may run into hotspots and look at bounded-load consistent hashing, etc.

er0k 4y ago

Great visualizations. There is also a wonderful talk on this topic called Load Balancing is Impossible by Tyler McMullen https://www.youtube.com/watch?v=kpvbOzHUakA https://www.youtube.com/watch?v=kpvbOzHUakA

zokier 4y ago

Least connections is intuitively very sensible algorithm, but it has one pitfall: if backend server starts returning errors for whatever reason (e.g. load shedding) quicker than typical responses, it can lead to situation where disproportionate number of requests are directed to that one server. Also typically you'd have more than one load balancer instance, and at least naive least connections requires shared state (backend connection counts) between the instances, while with round-robin you can avoid that?

samwho 4y ago
Least connections doesn't need shared state between the instances, but it would need shared state between the load balancers if you had more than one for sure. You're totally right, I glossed right over errors. With PEWMA and weighted round robin you can make instances incur a "penalty" for serving errors, which can help you isolate bad servers. It would have been fun to visualise this, definitely.
- mst 4y ago
  It also strikes me that it might be interesting to model least connections with two or three LBs with and without such shared state. My instinct is that you'd still get most of the advantages even with each LB keeping its own independent connection counts, but given the number of times I've fired up a profiler and gone "wait, seriously, -that-s the slow part?!" I'd suggest nobody believes me and measures it instead.
sesm 4y ago
There is a talk about Fitbit load balancer on YouTube, where their algorithm is described. They used modified least connections algorithm, which also tracks failure rate of each node, decreasing the traffic when error rate is increased. The video is called "A Frontend Server, Front to Back by Zach Tellman", timestamp 33:34.
ed_balls 4y ago
you can improve this be picking top 3 server with least connections and then pick one randomly from these 3 servers.

naikrovek 4y ago

Why is there not a queue system where a server can pull requests when it's ready to handle one? Why must the work to determine where to send a request go to the load balancer, when you could just pull from a queue and save yourself the trouble of finding the exact right load balancer strategy for your application?

jmholla 4y ago
The thread up here [0] is talking about that in case you missed it. [0]: https://news.ycombinator.com/item?id=35613454 https://news.ycombinator.com/item?id=35613454
bityard 4y ago
The short answer is that it's more complicated to engineer and has its own set of trade-offs. With the push-based models shown in the article, everything works regular HTTP(S), no fancy routing is needed, and the LB needs to keep very little state to do its job.
- naikrovek 4y ago
  seems like a request could be pulled from a queue with HTTPS easily enough. and if I am misunderstanding what you're saying, I don't understand why a purely request-driven path is so vital; it's just a way to me ve data around. seems like the queue could accept the request, keep the https connection open, wait for a response from whatever server accepts the request, and pass the response to the client upon receipt just fine. I dunno. web stuff is poorly done imo. poorly designed.

cod1r 4y ago

This is an awesome blog. Learned a quite a bit! And bookmarked for future reference! <3 :)

jamespo 4y ago

Availability is briefly mentioned but it'd be nice to have a simulation where members of the LB group fail

samwho 4y ago
This and slow-start were on my original to-do list for this post, but I wanted to keep it to a certain length and complexity so they ended up getting cut. There's a tonne of cool stuff to visualise in this space, I was spoilt for choice. Slow start, server flapping, session stickiness, dozens more algorithms, multiple load balancers with incomplete state, multiple levels of load balancers, the list probably goes on. :D

throwaway894345 4y ago

I’ve always been more curious about how load balancers are supposed to be highly available? Presumably you run many instances, but then it seems like you need something to balance the load across your load balancer instances? Also, how do many load balancer instances listen on the same IP address (or do they use DNS to map a domain name to multiple IP addresses?)?

samwho 4y ago
You've got it, DNS is what's often used to solve this problem. Do a few resolutions of reddit.com, you can see them returning 4 different IP addresses in a randomised order. :)
- c7DJTLrn 4y ago
  CDNs such as Cloudflare also do anycast routing which means you can hit the same IP in different places in the world and get a response from the nearest point-of-presence.
toast0 4y ago
A classical load balancer runs in an HA hot-warm pair, with IP takeover --- when the secondary senses the primary has failed, it takes over the IP and begins serving. Depending on the type of load balancing and the software involved, this could be nearly seamless, or it could end all sessions in progress. If you want to run hot-hot load balancing on a single IP, it's generally done with routing protocols. Equal cost multi-path (ECMP) will split traffic by hashing on some portion of the (source IP, dest IP, protocol, source port, dest port) 5-tuple; you'd configure your router to enable ECMP, and then your load balancers would advertise the IP via BGP or RIP or whatever is cool these days. Communication between load balancers to handle sessions that move during failover and bring-up is optional (if you don't do it, sessions will end abruptly); this setup is similar to anycast, although with anycast you may also see sessions move when external routing changes, and you really should manage that. You also should have a method to handle ICMP packets, most specificially needs-frag packets, as they will be sent from a different IP than the connection peer and will likely hash differently and may likely route differently for anycast, too. You can use DNS to direct traffic to multiple load balancers, but DNS is not a precision instrument. It's useful for geographic balancing (in addition to anycast), but resolvers have a tendancy to cache results for longer than published TTLs and it takes significant effort to understand how much request traffic a given resolver will generate from one lookup. For balancing between two load balancers where you want roughly equal traffic, you also need to consider pathologic behavior like RFC 3484 and RFC 6724. These two RFCs suggest preferentially using IPs with a larger common prefix when multiple options are available. This only makes sense when the common prefix is meaningful. If your ISP was assigned 10.1.2.0/24 and I have service IPs of 10.1.7.3 and 10.2.4.5 and return both of those as A records, your resolver shouldn't really prefer one or the other, because beyond your ISP prefix, there's no actual network closeness implied by a similar IP. 'Smart' resolvers that follow this RFC can cause large scale traffic imbalances, so fun times there.

maltris 4y ago

The visualizations are perfect, I will add this to our trainee introduction on loadbalancing.

openizr 4y ago

[dead]

AYBABTME 4y ago

I feel like something missing from people's perspective when thinking of load balancing is to consider pull models. All push load balancing algorithms try to somehow predict how busy downstreams are. Some even go as far as having downstreams send back some utilization metrics. But if you use a pull-based approach, this is all sort of moot. Downstreams will pull work when they're ready for it.

wmf 4y ago
For most protocols like HTTP there's no software to do this and it's not worth developing something nonstandard.
- blipvert 4y ago
  Should be something that could quite easily be added to a uWSGI subscription router - subscribing node periodically says “I have N slots available” and the router keeps track of how many requests are in flight.
orthecreedence 4y ago
The pull model works beautifully for background work queues. For load balancing it seems it would take a bit of re-plumbing on the expectations of request/response. How would you envision this working with something like HTTP? It seems it would reverse the direction, which would be interesting.
- AYBABTME 4y ago
  Very similar to background queues but the load balancer holds the request and dispatches it to a waiting worker, or waits until someone comes to serve it. While the worker handles the request, the load balancer proxies. The request serving is the same, the way the work is dispatched is just inverted.
  - bityard 4y ago
    Seems like this wouldn't work as well in situations where you care a lot about latency or resource utilization. If the workers are polling the LB every n ms, then that's an average of n / 2 ms added to _every_ request. Plus additional CPU cycles and network traffic on both ends due to the polling mechanism.

ahmadnoid 4y ago

What I don't understand is since it's the same service can't we just run a performance test, determine the ballpark of the needed resources and just have them capped like in k8s? why would some servers be more powerful than others in the first place?

cdot2 4y ago
Some requests may require utilizing different services than others.
- samwho 4y ago
  Yeah, this for sure. Traffic mix changes over the life of an application. In k8s performance isolation certainly isn't a solved problem, and noisy neighbours can affect the "power" of a server. Any change to the application at all could upset the delicate balance of its performance. You would need to be doing this sort of profiling on every change, using up to date and accurate production traffic. It ends up being much easier to put some smarts in your load balancer.
mutagen 4y ago
‘Noisy neighbor’ VMs and different underlying hardware specs on the ‘same’ instance configuration are two examples that come to mind.
adql 4y ago
One perfectly homogenous server gets 20MB POST with image that then needs to be reencoded/cropped Other gets tiny GET for CSS. Boom, now your equal servers are inequally loaded. The beauty of leastconn is that if 1st server is loaded it will just naturally get less connections than the lucky ones that only got easy jobs

chrisweekly 4y ago

Fantastic post; useful and entertaining. 10/10, bookmarked, will share. Context: perf-related webdev since 1998.

victor106 4y ago

Well written and animated!! Anyone knows what technology was used for the animation?

samwho 4y ago
I used https://pixijs.com/ https://pixijs.com/. This was my first project with it and it was really nice to use. I fell in to a few traps here and there, but generally it wasn't too bad to get the results I wanted with it. :)
- talentedRed 4y ago
  I'd love to see the source code of it :)
  - samwho 4y ago
    It’s just plain JS, you can see it here: https://samwho.dev/js/load-balancers.js https://samwho.dev/js/load-balancers.js Just like the good old days :)

Nijikokun 4y ago

Interactive diagrams and visuals are worth so much with these topics. I just created documentation at ngrok (full disclosure, I work there!) for how to do load balancing with their edges product for this the other day! Now I have something to refer people to when describing these. https://ngrok.com/docs/guides/how-to-round-robin-load-balance-with-ngrok-cloud-edges/ https://ngrok.com/docs/guides/how-to-round-robin-load-balanc...

samwho 4y ago
Big ngrok fan, keep up the awesome work!
strunz 4y ago
Boy have I got the perfect site for you - https://ciechanow.ski/archives/ https://ciechanow.ski/archives/

chasd00 4y ago

iirc there was a famous case where an outage occurred at a company using some least connection or least resource algorithm in the load balancers. The load balancer queue'd up requests and when a new server was brought online it immediately dos'd it out of existence. Then another server was brought online and the same thing occurred and another and another. They eventually switched to round-robin to give the new servers coming online a fighting chance to survive. Eventually, enough were online to process the queue. the take away was complex load balancing can make problems worse when bad things happen unexpectedly.

samwho 4y ago
Yes! This is called a “thundering herd” problem: https://en.m.wikipedia.org/wiki/Thundering_herd_problem https://en.m.wikipedia.org/wiki/Thundering_herd_problem. The topic is definitely much more complex than what I was able to cover in a single post :)

kriz9 4y ago

It is nice to see someone writing that a single server is enough for a lot of websites/apps - if not most. Computers are insanely fast nowadays.

donalhunt 4y ago

Would love to see the following scenarios explored too: - failure of a backend node - adding additional capacity From experience both scenarios can trigger non-obvious behaviours (especially when you have backends with different power levels).

interroboink 4y ago

A small note on "least connections" load balancing. The article says: Because the load balancer sits between the server and the user, it can accurately keep track of how many outstanding requests each server has. and this is the common case. But there are some cases, such as when serving audio/video streams (looking at you, porn :) where the server will send its response straight to the user, not back through the load balancer. So, the load balancer doesn't know how busy the server is, unless that information is communicated separately, through some other channel. One variation is "least sessions", where the number of active sessions rather than connections is used, and as mentioned, that info is stored separately from the "main" connection, and available on the load balancer for its decision-making. Example: https://www.youtube.com/watch?v=tAAmZ3bz8AA&t=681s https://www.youtube.com/watch?v=tAAmZ3bz8AA&t=681s

strunz 4y ago
Yeah this was the most confusing part of the whole article to me, and seemed like the most important. I was like "how is it keeping track of how many connections are still being processed?"
- jacurtis 4y ago
  In most situations (not all) the load balancer is actually a proxy. So when you type in example.com, the dns points to a load balancer. You connect to a load balancer, the load balancer opens a connection with the desired server (probably sitting in a private network somewhere), and proxies the traffic to the server. You never actually connect to the server in this case. You stay connected to the load balancer the whole time, the load balancer makes a request to the server, which processes your request, and sends it back to the load balancer, which then proxies the data back to you in the response. In this case the LB sits between you (the user) and the actual server running the application. In this case the LB knows how many connections each server has in the system because it is actually the one connected to the servers. If a server drops a connection, the LB knows because its the one that actually is losing connection. So it is fully aware of what all servers are doing in this scenario. The only thing the load balancer might still need to do is ping servers for health checks to make sure they are online when the servers are not connected, this is also how it knows latency and other metrics.

ned1010 4y ago

Thank you for this high quaility explanation of this topic. Something that no model will ever be able to generate. I enjoy reading it.

edude03 4y ago

I love this simulation it's the best visualization I've seen of load balancing concepts. One thing though - in my experience the biggest challenge I typically see is that different requests take different amounts of time for example you're running multiple instances of your monolith and there is an endpoint that returns a static response and another one that generates a huge report. This is actually something that can be handled with a load balancer that can introspect layer 7 but that's a whole other thing

samwho 4y ago
I do talk about variable request cost a fair bit, but I really don't think I did a good job visualising it. The rate at which each request shrinks while it's being processed by a server is meant to represent cost, but it's pretty subtle and easy to miss unless you're really watching closely. If I were to do this again, making request cost more obvious would be something I'd like to do. I had initially had requests by variable in size on screen, and moved away from that because load balancers don't typically know the cost of a request up front.

lowflyingcondor 4y ago

Would be cool to supplement this with what we know happens to all of these strategies when the load balancer's snapshot of server load is stale. https://brooker.co.za/blog/2012/01/17/two-random.html https://brooker.co.za/blog/2012/01/17/two-random.html

er4hn 4y ago

Beautiful animations! I love how they make understanding this more intuitive and can be adjusted to play with different settings. One thing that I generally felt is missing in these discussions is how TLS messes up load balancing strategies. I did my own research on what to do when you want to have TLS and not terminate at the load balancer. I covered that in a blog post available here: https://er4hn.info/blog/2023.02.18-tls-load-balancer/ https://er4hn.info/blog/2023.02.18-tls-load-balancer/

hamilyon2 4y ago

I always thought that for hundreds of backends and above 10K RPS those algorithms scale poorly. First of all, scaling beyond single load balancer becomes a problem. The cost of updating counters becomes significant. If responses are quick, the cost additional bookkeeping adds doesn't pay off. Of you use weighted random all these problems go away. Is my knowledge outdated?

preseinger 4y ago
updating a counter (in memory on a single host) is typically a single- or double-digit-nanoseconds operation, basically never the bottleneck in anything
samwho 4y ago
Weighted random is one of the algorithms available in the playground at the end. I did originally have a section talking about it but cut it for length reasons. Very few people in practice are serving 10K RPS.
adql 4y ago
Well, in short, yes. > I always thought that for hundreds of backends and above 10K RPS those algorithms scale poorly https://www.haproxy.com/blog/haproxy-forwards-over-2-million-http-requests-per-second-on-a-single-aws-arm-instance/ https://www.haproxy.com/blog/haproxy-forwards-over-2-million... > First of all, scaling beyond single load balancer becomes a problem. If you are in DC or have L3 access to the underlying network ECMP is VERY easy way to scale to 4-16 loadbalancers. Over that just... use multiple IPs. We use ECMPed setup of 4 nodes since forever and it works very well. There are theoretical improvements that could be made by doing L4 loadabalancing into L7 loadbalancing, but you'd need a hell lot of traffic to ever need that > The cost of updating counters becomes significant. If responses are quick, the cost additional bookkeeping adds doesn't pay off. Essentially, yes but if you have some architecture that talks very little (say just few packets per connection, let's assume some IoT garbage), you probably just want different architecture altogether; like "first request gets you assigned server, then you talk to it directly without LB". L4 balancing is also an option. In essence, if somehow performance of leastconn algorithm is your bottleneck, you're both big enough and specialized enough to go with another approach than "just dump all traffic at few loadbalancers"

xyzzy4747 4y ago

If the requests are similar (i.e. don't have unique user data in them), it's best to put a high performance reverse proxy in front that has some caching. This way you don't have to execute lots of code for every request.

samwho 4y ago
Caching is something I want to cover in a separate post :)

mparnisari 4y ago

i'm a visual person so i loved the animations! more like these please!

quickthrower2 4y ago

This is good teaching. You can get a concept across in a few minutes, or you can make someone struggle for hours to understand. I think classic academic teaching, leans towards the latter (imagine a latex pdf that introduces an alphabet of Greek letters), vs. this, which learns you the concept pretty quick. You can them do the Greeks letters version later.

zamnos 4y ago
(which teaches you the concept pretty quick.)
- quickthrower2 4y ago
  Thanks, it was a actually subtle reference/nod to the “learn you a haskell” book.

dtjohnnymonkey 4y ago

This is so timely for me, I've been wondering how I can visualize load balancing algorithms for the last few weeks. When trying to explain why round robin is bad, I often try to describe a situation where a backend cluster with a wide variance in performance can cause a cluster of clients using round-robin load balancing to start developing a sort of harmonic resonance where all the clients slowly synchronize on which servers they are hitting. However, it's hard to explain in words and a visual simulation would help me explain. Do you think it would be easy for me to hack the source and add multiple clients to the simulation?

zamnos 4y ago
Shouldn't be too hard to add the clients since, in terms of the animation, they're just flipped versions of the server. The question is if this resonance is going to require some intentionality to it to demonstrate/replicate.
samwho 4y ago
You have my blessing to try. The source is all in one file and is just plain JS, no minification or anything. I’ll warn you: the code is a bit messy. I wrote it knowing it was just for me and was a one off :D

vivegi 4y ago

Several years ago, I implemented an application specific load balancer where the LB kept two queues. One was free_workers and the other was open_requests. Initially, upon startup, each worker registers itself with the LB and gets added to the free_workers queue. When requests arrive at the LB, the LB checks if there are free workers available. If yes, it dequeues a free worker and dispatches the request to that worker. If no free workers are available, the LB adds the request to the open_requests queue. When a worker finishes its work, it lets the LB know and the LB adds the free worker to the end of the free_workers queue and initiates another round of dispatching. The parameter to watch for is the queue size for the open_requests queue. (There were a few more nitty gritty details, but that was the concept at a high level)

ReaLNero 4y ago
But then your LB is a single point of failure! Even if you were to spin up duplicate copies of the LB that could be failed-over-to in real time, there is still the drawback that you are bounded by the number of requests you can store on a single machine. I think what you actually built is a message queue engine that forwards the data to the consumers, not a load balancer.

mattbillenstein 4y ago

What a great post!

hahnchen 4y ago

does a single load balancer ever get overwhelmed? what do you do when that happens?

samwho 4y ago
Yeah, it does! There are a few options, I’ll mention 2: 1. You can use DNS to return IP addresses to multiple load balancers. 2. You can have N load balancers that are themselves behind another, beefier load balancer. Plenty of other magical things that have been done to solve this problem, but I think those 2 are quite common and flow naturally from the ideas the post covers.

Myrmornis 4y ago

I think it might be worth adding to this some discussion of how the load balancer itself handles the load, and the related fact that _within_ some backends, the responsibility for load-balancing falls on rich clients that maintain knowledge of the server sets to which they can route requests.

adql 4y ago
And the fact that you should tune for loadbalancer to queue and eventually drop, not your app server. Then in case of leastconn there will be no dropped connections as long as total server capacity < incoming traffic.

adql 4y ago

Leastconn also have very nice characteristics, that if your app say gets into long GC it will near-immediately stop sending connections there Also the "overrun" of dropped connections shouldn't really happen if * incoming connections are < total capacity * loadbalancer have server limits set properly and doesn't send too many connections for app to stgart dropping * loadbalancer itself is one queuing (as it "knows" the next server that should get the connection) So that part of the description is subtly wrong; you WANT to queue on loadbalancer, not on app servers. The app server should have queue just long enough to feed all the threads but not enough to start dropping anything

dazbradbury 4y ago

AWS Application Load Balancers seem to default to round-robin, would be interested to hear how many people change this to their "least connections" equivalent called "LOR" [1]? And why they don't support any other options? I'd guess AWS default to round robin because it's the least complex, and doesn't have issues like if a worker responds extremely quickly due to an error (eg. returns a 500 immediately) then using LOR it seems it would consume all the requests until it's taken out of service by any health checks. But maybe there are other potential downsides? [1] - https://aws.amazon.com/about-aws/whats-new/2019/11/application-load-balancer-now-supports-least-outstanding-requests-algorithm-for-load-balancing-requests/ https://aws.amazon.com/about-aws/whats-new/2019/11/applicati...

AdamN 4y ago
You point out a good gotcha that most people don't notice - many host-specific errors are often faster than the standard response and more traffic will route to those hosts with a performance-based heuristic. A well configured LB would have hosts with responses that take them out of rotation for known fault conditions - but at scale that's hard for companies to validate.
- zamnos 4y ago
  At scale, with also having scaled systems engineers, it's not, like, impossibly hard. A sidecar like Envoy can be configured to emit health stats which can then be read by the load balancer to consider a given server unhealthy. Again, at scale, but each team is already responsible for a dashboard with health metrics for their service, so the load balancer team doesn't have to try and determine everybodies health metrics, only their own.
base 4y ago
Depending on the app might not have better performance. The reason is that a host with more connections might not be using more resources than one with less connections. The busy connections might be waiting for a reply from an external service.
zamnos 4y ago

sporn656 4y ago

[dead]

wolfcub7865 4y ago

[dead]

poemsporn75 4y ago

[dead]

mystique5784 4y ago

[dead]

justonemore65 4y ago

[dead]

able7574 4y ago

[dead]

creature63 4y ago

[dead]

spicysugar54 4y ago

[dead]

gypsysoul65 4y ago

[dead]

lustforlife451 4y ago

[dead]

wine5433 4y ago

[dead]

whatsthetea54 4y ago

[dead]

justdogs573 4y ago

[dead]

ssense74 4y ago

[dead]

gyourstory35 4y ago

[dead]

dragontamer 4y ago
Queuing theory is nice, but then again its completely abstract and mathematical. Real life issues get in the way. In particular: for many parallelization problems, its simply not worth the effort to ever load balance. Tasks are too small and the "time spent calculating where to go" is more expensive than just accomplishing the task to begin with. (Ex: Matrix multiplication can be seen as a parallelization of multiplies, followed by a set of additions. The multiplies are too cheap to perform any form of load-balancing, executing in just one clock tick). So in reality, we have "fine grained parallelism", and "coarse grained parallelism". Coarse grained is where load balancing is feasible (the task is "big enough" that its worth spending a bit of CPU time figuring out load balancing). "Fine grained" is very difficult, and is in the realm of CPU design (CPUs will execute your instructions out-of-order to discover parallelism)... though software also plays a role. ---------- That being said, I probably should study more queuing theory myself. The math seems less about "how to design a good parallel system" and more focused on "how to measure a parallel system" (ex: throughput * latency == state... which means you can measure latency == state/throughput, and other such mathematical tricks). The math is simple, albeit abstract. Its not there for "deeper understanding", its there for "even basic understanding" (but much much faster to calculate if you already know queuing theory).
preseinger 4y ago
i don't think anything claimed here requires that lbs or apps are single-tenant on their machines, or that load balancing is connection-oriented

deleted 4y ago

[deleted]

angelhearts45 4y ago

[dead]

smashfizzle754 4y ago

[dead]

thelight453 4y ago

[dead]

curioussoul46 4y ago

[dead]