Load Balancing

Past a certain point, web applications outgrow a single server deployment. Companies either want to increase their availability, scalability, or both! To do this, they deploy their application across multiple servers with a load balancer in front to distribute incoming requests. Big companies may need thousands of servers running their web application to handle the load.

In this post we're going to focus on the ways that a single load balancer might distribute HTTP requests to a set of servers. We'll start from the bottom and work our way up to modern load balancing algorithms.

# Visualising the problem

Let's start at the beginning: a single load balancer sending requests to a single server. I'm going to send the server 1 request per second (rps), and each request takes the server half a second to process.

When you're ready, press play. Drag the slider to make the demo go faster or slower.

For a lot of websites, this setup works just fine. Modern servers are powerful and can handle a lot of requests. But what happens when they can't keep up? The demo below sends requests at a rate of 3 rps.

The faster rate causes some requests to get dropped. If a request arrives at the server while another request is being processed, the server will drop it. This will result in an error being shown to the user and is something we want to avoid. We can add another server to our load balancer to fix this.

No more dropped requests! The way our load balancer is behaving here, sending a request to each server in turn, is called "round robin" load balancing. It's one of the simplest forms of load balancing, and works well when either your servers are all equally powerful and your requests are all equally expensive, or you have plenty of headroom to absorb imbalances.

# When round robin doesn't cut it

In the real world, it's rare for servers to be equally powerful and requests to be equally expensive. Even if you use the exact same hardware, performance can differ. Applications often service many different types of requests, and these have different performance characteristics. Fetching a list of 10 items will take less time than fetching a list of 1000.

Let's see what happens when we vary request cost. In the following simulation, requests aren't equally expensive. You'll be able to see this by some requests taking longer to disappear than others.

While most requests get served successfully, we do drop some. One of the ways we can mitigate this is to have a "request queue." In this next simulation I've introduced a reset button you can press to start again from the beginning if you want to.

Queues help us deal with uncertainty, but it's a trade-off. We will drop fewer requests, but at the cost of some requests having a higher latency. You'll also notice that thanks to the request cost variance, servers start to exhibit an imbalance. Queues will get backed up on servers that get unlucky and have to serve multiple expensive requests in a row.

If a queue is full when a request arrives, we drop the request even if another queue has space. Some real world load balancers will try to send the request to another server before dropping it, but others don't.

Everything said above about request variance applies equally to servers that vary in power. In the next simulation we also vary the power of each server, which is represented visually shades of grey. Darker greys are more powerful, and process requests faster.

The less powerful servers quickly start to drop requests, while the more powerful servers sit idle much of the time. This scenario shows the key weakness of round robin: variance. Despite its flaws, though, round robin is the default HTTP load balancing method for nginx.

# Improving on round robin

It's possible to tweak round robin to perform better with variance. There's an algorithm called "weighted round robin" which involves getting humans to tag each server with a weight that controls how many requests to send to it.

In this next simulation, we use each server's known power value as its weight, and we give more powerful servers more requests as we loop through them. The number below each server shows how many requests it gets before we move on to the next one.

While this handles the variance of server power better than vanilla round robin, boiling server performance down to a single number is hard. It requires careful load testing with real workloads. No one really does this, so another variant of weighted round robin calculates weights dynamically by using a proxy metric: latency.

It stands to reason that if one server serves requests 3 times faster than another server on average, it should probably receive 3 times as many requests. In the next simulation that's exactly what we're going to do. The number below each server is its average latency from recent requests, and we'll use that to send fast servers more requests.

The result is very similar to the initial weighted round robin simulation, but there's no need to specify the weight of each server up front. This algorithm will also be able to adapt to changes in server performance over time. This is called "dynamic weighted round robin."

Let's see this new algorithm in practice, with high variance in both server power and request cost. You can change the power of all of the servers, even when the simulation is playing, by pressing shuffle. I've made the number below each server show how many requests the server will get per round robin loop, but it's still using latency to calculate this.

If you pick a server that's particularly strong, and then click shuffle until it becomes really weak, you should notice the number of requests it gets sent is corrected very quickly. Much better than relying on humans to do good load testing and keep weights up to date by hand!

# Moving away from round robin

Dynamic weighted round robin seems to account well for variance in both server power and request cost. But what if I told you we could do even better, and with a simpler algorithm? Watch this next simulation for a little while and see how well it distributes requests.

This is an algorithm called "least connections".

Because the load balancer sits between the server and the user, it can accurately keep track of how many outstanding requests each server has. Then when a new request arrives, it knows which servers have the least work to do and prioritises those.

This algorithm performs well regardless how much variance exists. It cuts through uncertainty by keeping track of what each server is doing right now. It also has the benefit of being very simple to implement.

Let's see this in action with the same parameters we gave the dynamic weighted round robin algorithm above. Again, these parameters are randomised. Press shuffle to give the servers new power values while it runs.

While this algorithm is a great balance between simplicity and performance, it's not immune to dropping requests. However, it only drops requests when all of the servers have full queues. Least connections is a great default choice for most workloads, better than round robin in my opinion.

# Optimizing for latency

So far we've focused on not dropping requests. This is a good goal, but it's not the only thing we can optimise for.

People want websites to load fast, so optimising for lower latencies is beneficial to most businesses. To measure latency, it's common to look at different "percentiles." For example, the 50th percentile, also called the "median," is defined as the duration for which 50% of requests are below, and 50% are above.

I ran 3 simulations with identical parameters for 60 seconds and took a variety of measurements every second. Each simulation varied only by the load balancing algorithm used. Let's compare the medians for each of the 3 simulations:

You might not have expected it, but round robin has the best median latency. If we weren't looking at any other data points, we'd miss the full story. Let's take a look at the 95th and 99th percentiles. Remember, 95th percentile is the latency value where only 5% of requests had a higher latency. 95th and 99th percentile represent the slower end of the distribution.

Note: there's no colour difference between the different percentiles for each load balancing algorithm. Higher percentiles will always be higher on the graph.

We see that round robin doesn't perform well in the higher percentiles. How can it be that round robin has a great median, but bad 95th and 99th percentiles?

In round robin, the state of each server isn't considered, so you'll get quite a lot of requests going to servers that are idle. This is how we get the low 50th percentile. On the flip side, we'll also happily send requests to servers that are overloaded, hence the bad 95th and 99th percentiles.

We can take a look at the full data in histogram form:

I chose the parameters for these simulations to avoid dropping any requests. This guarantees we compare the same number of data points for all 3 algorithms. Let's run the simulations again but with an increased RPS value, designed to push all of the algorithms past what they can handle. The following is a graph of cumulative requests dropped over time.

Least connections handles overload much better, but the cost of doing that is slightly higher 95th and 99th percentile latencies. Depending on your use-case, this might be a worthwhile trade-off.

# One last algorithm

Below is a simulation using an algorithm called "peak exponentially weighted moving average" (or PEWMA). It's a mouthful, isn't it? It uses the latency for each server to decide which server to send the next request to, not just a weight for it. It doesn't use an average latency, it uses an "exponentially weighted moving average" (EWMA), which just means more recent data gets a higher weight.

Press play below to watch it at watch. I've set the numbers below each server to be the weighted average latency.

I set the parameters for this simulation very carefully in order to show you something. Did you notice that the leftmost server stops receiving requests? This happens because PEWMA figures out that all of the other servers are faster, and there's no need to send requests to the slowest one. Doing so would result in requests with a higher latency.

It's difficult to see how the EWMA works by just looking at the current value. You have to see it change over time.

The visual below shows a single server receiving 1 request per second. You can control how long it takes to serve that request by moving the slider. The blue line on the graph shows the EWMA over time. Move the slider to watch how the EWMA updates.

It gradually converges toward whatever new latency value you've set. It takes big steps at first, but the steps get smaller as it gets closer. Calculating it this way helps avoid big swings if you have a mix of fast and slow requests. You wouldn't want a couple of back-to-back fast requests to cause one server to suddenly get all of the traffic.

Each server's EWMA is tracked individually, and gets multiplied by queued_requests + 1 before being used to make a load balancing decision. The server with the lowest ewma * (queued_requests + 1) gets the next request.

The visual below shows a more full example, with 5 servers being load balanced with PEWMA. By default, the graph just shows EWMA for each server. Check "With queued_requests" to multiply the EWMAs by the queued_requests + 1 to see the actual score used to choose a server. Press shuffle a few times to watch the algorithm adapt.

PEWMA adapts dynamically to make sure requests are routed to servers that are fast, and have the capacity to process them. It's more complicated than least connections, and it would be fair to ask if this extra complexity is worth it. Let's take a look at the 50th, 95th, and 99th percentile latencies when compared against the least connections data from earlier.

An improvement across the board! It's more pronounced at the higher percentiles, but consistently present for the median as well. Here we can see the same data in histogram form.

The PEWMA distribution is consistently shifted further left, toward lower latency, than least connections.

How about dropped requests?

It starts out performing better, but over time performs worse than least connections. This makes sense. PEWMA is opportunistic in that it tries to get the best latency, and this means it may sometimes leave a server less than fully loaded.

I want to add here that PEWMA has a lot of parameters that can be tweaked. The implementation I wrote for this post uses a configuration that seemed to work well for the situations I tested it in, but further tweaking could get you better results vs least connections. This is one of the downsides of PEWMA vs least connections: extra complexity.

# Conclusion

I spent a long time on this post. It was difficult to balance realism against ease of understanding, but I feel good about where I landed. I'm hopeful that being able to see how these complex systems behave in practice, in ideal and less-than-ideal scenarios, helps you grow an intuitive understanding of when they would best apply to your workloads.

Obligatory disclaimer: You must always benchmark your own workloads over taking advice from the Internet as gospel. My simulations here ignore some real life constraints (server slow start, network latency), and are set up to display specific properties of each algorithm. They aren't realistic benchmarks to be taken at face value.

To round this out, I leave you with a version of the simulation that lets you tweak most of the parameters in real time. Have fun!

EDIT: Thanks to everyone who participated in the discussions on Hacker News, Twitter and Lobste.rs!

You all had a tonne of great questions and I tried to answer all of them. Some of the common themes were about missing things, either algorithms (like "power of 2 choices") or downsides of algorithms covered (like how "least connections" handles errors from servers).

I tried to strike a balance between post length and complexity of the simulations. I'm quite happy with where I landed, but like you I also wish I could have covered more. I'd love to see people taking inspiration from this and covering more topics in this space in a visual way. Please ping me if you do!

The other common theme was "how did you make this?" The original version used PixiJS. The current version uses a Lit component with SVG for the live simulations and charts. If writing visual explanations like this is something you're interested in, I recommend it!

Wanna tell me what you thought of the post? This form sends a notification directly to my phone.

# Playground