Load Balancing
samwho.dev
samwho.dev
But if you use a pull-based approach, this is all sort of moot. Downstreams will pull work when they're ready for it.
Other than the fact that randomization avoids pathological cases, nothing I know about distributed computing or queuing theory really gets to the bottom of it. It feels like there should be more to it than that.
and
> Best of 2 is good because it combines the best of both worlds: it uses real information about load to pick a host (unlike random), but rejects herd behavior much more strongly than the other two approaches. https://brooker.co.za/blog/2012/01/17/two-random.html
I think Node 12 introduced LIFO queuing for connection pools because they found the cost of silent disconnects from the server to be too high. They got much better histograms by using the most recently freed connection instead of round robin of available sockets.
For node's situation that sounds probably workable but I think a lot of the time I'd prefer to send periodic keepalives to the idle pool connections. However, you can't exactly bake -that- into the runtime so I can see their argument and perhaps the best thing would be "both, plus periodically do a clean shutdown on excess pool members until you need them again."
They KNOW how busy they are. They are the ones tracking and forwarding connections to them. That's why leastconn works in the first palce
But, for example HAProxy have option to directly back-feed weights via healthchecks from app, so there is an option for app to signal back-pressure in RR balancing
Well, they do when they're the only ones sending work to the workers.
The article uses a literal black box for the load balancer, but there are workloads that are too heavy for a single machine, so in those cases (and others, like HA) you have to have a pool of load balancers. You can try to make those load balancers know everything about what's happening in the whole system but it can be hard and expensive.
Or, you can have them operate on less-than-perfect knowledge. This is what the round-robin strategy does, and just like round-robin, has its tradeoffs (much simpler, worse 95%ile latency).
All of this is assuming the load balancers and workers servicing connections are the only things running on those machines. In real world usage there can often be other loads on the same hardware, belonging to tenants your team doesn't even have a relationship with, which can complicate things quite a bit.
The request serving is the same, the way the work is dispatched is just inverted.
Also there's no reason to poll the LB/queue/etc., you just tell it "I'm ready" and it sends you something to handle when it's got something.
Pull/push here is about who decides when a server is ready to receive another request.
So ... I'm not an expert on actually implementing it, but I've seen systems in practice that -were- in such situations and it worked out extremely well.
I believe push/pull are the two faces of the same coin. You might physically initiate a connection one way or the other. You might in abstract push or pull information.
Ultimately you are trying build an oracle that predicts the future.
Difficult to do much with as so many request/response load balancing software is inherently push based, but it's a great eye opener.
That's why leastconn works in the first place. And leastconn is almost always one you want. It's almost magical. GC stall on one server ? That means it isn't processing, which means every new request will go to other servers.
One server processing 2x as fast as the other ? Well, it keeps its connection count low, so it gets more of them
It would be great if such a mechanism was part of the http standard, so you could easily connect compliant tools.
Not sure HTTP is the best approach to the suggested method. Since you control both ends, there are surely better protocols to use, like QUIC or something similar (or just straight up UDP).
The latency of round-tripping "finished a request, give me another" is probably also best-case ever so slightly worse than "finished one of my requests, loading the next from the buffer" (the HTTP load balanced apps I've worked on have had request queues on the workers too (framework-level, usually)).
Moreso if you had multiple load balancers involved...
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?
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.
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.
Also take the time to check out other posts/pages by Sam! Well done mate ;-)
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. :)
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 and some basic benchmarks 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%
PS: this post is absolutely amazing! and the animations are brilliant! thanks a lot for making it
Streaming requests or responses is out the window! Now you're storing the full request and response blobs in your infrastructure instead of chunks at a time in the network layer. Is a whole Netflix movie queued? If we're talking about queued chunks then its just UDP you're describing.
Connection oriented designs tend to more transparency end to end. The synchronous nature means a failed call can be bubbled back through the remote call chain. Failed async calls can be dropped, which leaves ambiguity. The callers need to resort to timeouts instead of closed connection signals.
Not to mention the issue that this doesn't work for client calls. The response handling from the client is more complex. The async callback would need to be demuxed such that a response can be associated with a call. There's no open connection so you'd need to punch the firewall somehow...honestly its very messy.
the truth is that sync calls (in normal aws + k8s example) have like 50 queues between the user's kernel and your program actually doing the work, just considering the listen(2) queues, and the network card queues, and the reality is that every one of them can just drop packets on the floor whenever it wants
so in reality, network programming is hard, and even sync things are just a collection of many async pieces from the network card to the userspace
tl;dr The difference is internal queue vs external queue.
As another commenter points out, AWS Lambda operates this way.
- GET events from ${AWS_LAMBDA_RUNTIME_API}/2018-06-01/runtime/invocation/next
- process it (run your handler)
- POST the response to /runtime/invocation/AwsRequestId/response
https://docs.aws.amazon.com/lambda/latest/dg/runtimes-api.ht...
Once you consider that, IDK if someone can really claim "more complicated."
1. It can be more tolerant of failures, since an unresponsive server doesn't mean failed requests.
2. Hooking up your server scaling system to HAProxy, etc. isn't the easiest thing in the world anyway.
it can't be known by the server itself, as (among many other reasons) the server can't know about network issues between itself and any upstream caller
it can't be determined by out-of-band health check queries, because those queries don't represent actual traffic, the simplifying assumption that they _do_ introduces many common failure modes that any seasoned engineer can speak at length about
health checks can be a nice additional signal on top of monitoring actual prod traffic, but they can't be used by themselves, they just don't capture enough relevant information
a server can return 200 OK to every health check query and 5xx to every production request, is that server up or down? hopefully clear it is down
similarly, if it returns 5xx to every health check query but 200 to every prod request, is it up or down? hopefully clear it is up
if you want to monitor the status of a server (or application) for internal purposes, that's fine, but that's (at best) supplementary signal for the decisions made by a load balancer, not something you can make load balancing decisions on in isolation
> One of the nicest things about pull load balancing is that it completely replaces the need for a separate registration + health check system.
"Jeff, stop taking random advice off HN as gospel, that shit is stuck in GC for last week ,we told you we still need monitoring"
But the load balancers/brokers are usually far less dynamic. I've never seen a worker health check a RabbitMQ broker.
I could imagine a dynamic upstream module that receives UDP or TCP packets from backends with a number estimating how many connections it can handle at that time. The module then tells the reverse proxy which upstream has the highest number and the reverse proxy selects it.
Request/response on the other hand is much simpler to configure and operate.
the lb puts a request where it has some reply_to (ip:port) where it waits (blockingly) for response from whoever picked up the request, it just does now know who that is until a reply comes
As an example of a failure scenario, how does your system distinguish between a request timeout, a response that didn’t get sent back because of network failure and the consumer crashing and losing the message?
for {
select {
case reply := <-replyChannel:
if reply.Uuid == r.message.Uuid {
return reply
}
case <-timeout:
return makeError(r.message, MessageType_ERROR_CONSUMER_TIMEOUT, "consumer timed out")
}
}
also, queue does not mean async model, it means a queue, there are many queues in http requests responses (e.g. the listen(2) backlog queue itself) and it does not make it async :)
“Message queues implement an asynchronous communication pattern between two or more processes/threads whereby the sending and receiving party do not need to interact with the message queue at the same time.”
and it is not a message queue in the sense you mean, it is a request response queue, it just happens to be using messages
when people think of message queue they are thinking of async event driven communication, and this is not it
You would almost never actually wait for host machines to dial in. You would have a list of hosts that are ready or not ready as they would almost always be ready for more. You want to assume readiness (as this lowers latency) and feed the fire hose.
But in this interpretation, in a world where an LB would be using an existing connection to host machines with HTTP/3 we're basically already there. I suppose its trivial and standard to signal unreadiness to the LB from the host with a 429 Too Many Requests response code.
Off the top of my head I'm trying to think how a host could actively signal to an LB that's its ready for more requests... I suppose its trivial and common to use a health check. Is it even a change to say that these need to be updated to achieve your goal of host to LB pulling?
Pull model just adds unnecesary RTT.
> Off the top of my head I'm trying to think how a host could actively signal to an LB that's its ready for more requests... I suppose its trivial and common to use a health check. Is it even a change to say that these need to be updated to achieve your goal of host to LB pulling?
Like this.
There is rarely a case where you decide to not serve the next request after serving previous one so push is most optimal for short ones. And if it doesn't want to it can just signal that via healthcheck.
Pull makes more sense for latency-insensitive jobs like "take a task from queue, do it, and put the results back", as if you say make video encoding service that dynamically scales itself in the background and "just do one encode and exit" is commonplace.
readiness is not knowable by a receiver, it is a function of many variables, some of which are only knowable to a sender, one obvious example is a network fault between sender and receiver, there are many more
even the concept of "load" reported by a receiving application isn't particularly relevant, what matters is the latency (and other) properties of requests sent to that application as observed by the sender
health is fundamentally a property that is relative to each sender, not something that is objective for a given receiver
The biggest benefit from pull model is not having to update backend server list every time you add/remove one but outside of that it isn't really all that beneficial.
You also get added latency, unless each backend server is actively listening and connected but if it is, you're just wasting extra RTT to say "hey, there is a request in queue, do you want it?"
Some of these protocols are a good improvement when looking for the ultimate in speed and I used them where applicable, but as a first order approximation a simple load balancer approach is quite good enough. Especially when you do not have dedicated people vested in that domain for maintenance.
Here is an example where it would not work well: lets imagine workers are doing a CPU bound task and each worker has one cpu (for simplicity), but we have also identified that we can handle up to 10 requests concurrently on one worker, but they will be just slower (because they will get smaller slices of cpu). Ideally we'd wish the requests to be divided equally between the workers, but with naive pull model one worker could greedily grab requests up until its at capacity while the other workers stay idle, making the response times worse than they need to be.
So if you can handle every incoming request with one worker that worker gets them all. Otherwise each worker pops off the stack as it becomes free. And if you can service more concurrent requests you just add more workers.
As I alluded, that works great if "can handle" and "being free" are clear-cut binary properties. But for complex applications when you are driving for high utilization while keeping latency down those questions become complicated; a worker might have some free capacity to handle requests but it doesn't mean that it would produce response as quickly as some other (more idle) worker.
In other words, the problem is not just assigning requests to workers that can handle them but assigning requests to workers that can handle them with lowest latency.
"handling a request" is something that is defined at the application layer
Multithreading-based work stealing à la Cilk relies on extremely cheap thread mechanisms and implementation to minimize communication.
In another similar situation, HPC switches are credit based so that until you hit congestion, you can “instantaneously” know if a remote is ready to receive.
This isn't a formal explanation, of course.
Edit: after some thought, that's not really the distinction that is made for load balancing. There's already knowledge of the remote state required for pushing to the last loaded queue. So the difference between pull and push is about having one queue vs several. In that sense it is like supermarkets that implement the more efficient one queue to every cashier Vs the more traditional one queue per cashier. In supermarkets there is a choice to make because there's other constraints, but just optimising for load balancing it's strictly better to have a single queue, if you only have one input.
The article does nicely mention that simple round Robin actually has lower latency, because some traffic gets lucky & goes to under-utilized machines. Unfairness helps some traffic go faster. The queue is probably going to eliminate this, but the unfairness advantage comes at the cost of a lot of other traffic getting put into long queues on workers, so it wasn't really a good thing anyways. The p90+ is usually awful.
In small setups, you may just have one layer with a single load balancer (well, hopefully at least a hot-warm pair), but larger setups often have multiple levels. There may be a network level traffic split to multiple frontend load balancers via something like ECMP; those frontends may connect directly to the origin hosts, or maybe there are frontends in many locations and they connect to backend load balancers near the origins.
In this bigger case, managing pull requests becomes difficult, because balancing may be unequal at earlier layers --- if your origin can handle N concurrent requests, so it sends N pulls, how many should it send to which of the upstreams, and if some upstreams get many requests and some get zero, those many requests will have unnecessary delay.
There's also unnecessary delay when at capacity between when one request finishes and the round trip of sending a pull and getting the next request.
But, it's always tradeoffs. It depends on the volume of requests, the typical time to process a request, behavior at or near capacity, etc.
I also think a pull based system is more work for the load balancer, and load balancers are harder to scale --- I prefer to move the work to the origins as much as possible, because it's typically easy to add more of those --- that's what the load balancer enables. But, that doesn't seem to be a commonly held opinion, direct server return is rarely available, load balancers commonly do TLS termination, and often intense traffic inspection and manipulation; again, there's tradeoffs.
TLS session establishment is expensive, so why would I want my load balancers to do it anyway? :P
Put that in front of some HAProxy servers to do TLS termination and farm out requests to another layer of NGINX/uWSGI boxes and Robert is your cousins father.
Now that we have hundreds of Gbps ethernet and TB of memory the idea has more merit, can scale pretty absurdly high with mundane systems. Or maybe you have sharding, which means now you have a load balancing problem again, of picking which work queue to take work from.
The HA bit is still hard. You have to to figure out if there's a netsplit (some folks can't connect to one server) or if one server really is gone. Probably just multicast to each queue all the incoming work & all the incoming pulls. Ideally each queue could also hear all the outgoing traffic. If ethernet capacity were unidirectional this would be great, box #2 could autonomously detect faults & take over. But ethernet is bidirectional, and now it needs all box #1's incoming traffic and it's outgoing traffic too. So instead maybe have the clients fail over. We can iterate on resign but HA is non-trivial.
i think the retries are a bit strange, and debugging was weirder as well, but its probably just me not used to it
even though i had multiple chances to use it in prod, i always go for http somehow, it just feels so familiar
also because of the way the REPLY_TO address:port worked in my experiments, sometimes having half open tcp connections really messes up things
different concept, different semantics, different results
https://ngrok.com/docs/guides/how-to-round-robin-load-balanc...
Incidentally load balancing and dynamic routing in satellite networks looks like a complicated problem and is a subject of active research:
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.
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)
I think what you actually built is a message queue engine that forwards the data to the consumers, not a load balancer.
Because the load balancer sits between the server and the user, it can accurately keep track of how many outstanding requests each server has.
Loadbalancer can still see it's an incoming connection as long as user is sending something (even if returning traffic goes directly) so at the very least it can keep number of connections same.
Of course one might stream 240p while other user streams 4k but for example in HAProxy there is an option to use external agent for health checks, that also have option to modify traffic weights and cut traffic to ones that are being swamped
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.
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:
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...
I doubt very much that this would be part of any real world implementation
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.
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.
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
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/
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?
https://www.haproxy.com/blog/enable-sticky-sessions-in-hapro... https://www.haproxy.com/blog/load-balancing-affinity-persist...
"Persistence" is more what I want but digging this out of HAProxy configuration and making changes on the fly looks troublesome.
> Manual/statistical load balancing --- assign users to a specific server based on their login credentials.
What happens when that specific server goes down? Needs an upgrade/deployment? You'll have to failover to a different server, which brings you back to an automatic load balancing strategy.
> Latency can be reduced to zero by simply forwarding the connection to the proper server once the login is complete.
Modern load balancers add a meaningless amount of latency per request. If you're truly forwarding it in the networking sense, then a load balancer/reverse proxy is still involved.
If you mean something like redirecting them to an endpoint that points directly at an individual server, you get back to the first problem. What happens when that server goes down?
> A statistical model of server utilization can be maintained and users assigned or re-assigned as needed.
This is one of those things that sounds _very simple_, but in practice is incredibly complicated.
Good point.
You'll have to failover to a different server, which brings you back to an automatic load balancing strategy.
Or to a manual load balancing strategy. What I have in mind is being able to easily re-direct users from one server to another using a simple CLI utility. This won't entirely eliminate downtime issues but it will (hopefully) mitigate effects to a manageable level.
In the era of cloud computing, downtime has become less of an issue.
This is one of those things that sounds _very simple_, but in practice is incredibly complicated.
I like attempting to simplify supposedly complicated issues. What I have in mind is simply counting the requests each server handles and using this as a simple measure to compare utilization. It's true that all requests are not equal but statistically, over time, with all servers being similar, the differences will tend to balance out.
In practice, this means that each time a server goes down someone has to be on-call to run a command to redirect them. It's also breaking your utilization-based sharding scheme.
> In the era of cloud computing, downtime has become less of an issue.
Well, yes and no. Downtime is less frequent because of robust, automated load balancing. Individual servers, whether VMs or containers or whatever you prefer, are far less reliable. That's intentional. It's cheap commodity hardware, designed to die, and 'cloud native' applications are supposed to handle that properly via things like automated load balancing.
> I like attempting to simplify supposedly complicated issues ... It's true that all requests are not equal but statistically, over time, with all servers being similar, the differences will tend to balance out.
This is an example of one of those simplifications that seems intuitive but just doesn't work. It is completely normal for there to be multiple orders of magnitude differences in request cost, between customers, and at different times. Even if you assume that your application is static (which it hopefully isn't), customer workloads are not. Their behavior will change, which means your sharding needs to change. This is already solved by existing load balancing algorithms described in the linked article.
What problem do you see with existing solutions that you're trying to solve?
The 12-factor app describes this well: https://12factor.net/processes
What I have in mind isn't really a "proxy" but more of a login/redirection server.
A "proxy" is middleware which directs all communication through a single server which adds to latency.
What I have in mind will run logins through a single server. But once the login is complete, any further communication is redirected to the proper work server to continue without any proxy middleware involved.
This won't entirely eliminate downtime issues but it does limit the effects to a reasonable level while offering increased efficiency and decreased latency.
https://github.com/haproxy/spoa-example
https://www.haproxy.com/blog/extending-haproxy-with-the-stre...
We used that to make an SSO login site that works independently on what is on the backend. Logic was basically:
* if there is no/invalid SSO cookie, SPOA set a flag which made haproxy redirect to the SSO app * if there is valid cookie, decode it and send the data (usually just logged user name) to the app in header
Once cookie is correct it doesn't need SSO server so it is pretty fast for users that already logged in.
It can be also used for blocking requests based on external engine, it's pretty flexible overall
https://docs.fastly.com/signalsciences/install-guides/other-...
User's 1 through 50 (light users) log in and their profile says they go to app-1.myapp.com. User's 51 through 60 (heavy users) log in and their profile says they go to app-2.myapp.com.
A specific user may pay extra to have a non-shared environment, and this supports that as well.
I had a simple lookup table in mind so it can be easily changed and adjusted as required without affecting the user's profile.
Really effective as teaching material; kudos to the author!
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.
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/applicati...
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.
Context: perf-related webdev since 1998.
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?
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
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
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.
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.
VRRP, philosophically,
must ipso facto standard be
But standard it
needs to be free
vis-à-vis
the IETF
you see?
But can VRRP
be said to be
or not to be
a standard, see,
when VRRP can not be free,
due to some Cisco patentry..Of you use weighted random all these problems go away.
Is my knowledge outdated?
> 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...
> 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"
Very few people in practice are serving 10K RPS.
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?
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.
Then in case of leastconn there will be no dropped connections as long as total server capacity < incoming traffic.
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
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.
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.
the take away was complex load balancing can make problems worse when bad things happen unexpectedly.
The topic is definitely much more complex than what I was able to cover in a single post :)
- 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).
Anyone knows what technology was used for the animation?
Just like the good old days :)
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.
Load Balancing is essential for large websites with huge user base.