Load Balancing

Now, you didn’t buy this book to learn about throwing balls into bins. However, this concept is used in various distribution algorithms. One common use case is load balancing. Load balancing is a concept commonly used for Internet servers and similar networks. If you’re not familiar with load balancing, here’s the gist of it, using Internet usage as a basic example.

When you open your Internet browser and visit a website, your browser makes a request to a server to receive the web page content, as illustrated in the following figure:

A server is simply a computer dedicated to delivering content to your computer; it “serves” the content to you.

Now, a server can only handle a finite amount of traffic at a given moment. If a website is so popular that thousands of people visit it each second, a single server may not be enough to deliver content to everyone in a timely manner. Because of this, many websites are delivered using a system made up of multiple servers. Each server is capable of delivering the same content, so no matter which server your laptop talks to, it will receive the same web page.

However, a laptop doesn’t choose which server it wants to make a request from. If it did, and one million users of the website decided to all make requests from the same server, we haven’t accomplished anything by adding multiple servers.

To make this setup work, a device known as a load balancer is used to direct all traffic. That is, each laptop makes a request of the load balancer, and the load balancer routes the request to one of the servers, like so:

Even though this example system has a bottleneck of having only one load balancer, it’s still a win. This is because a load balancer can generally act much faster than a server since all it does is route requests, as opposed to the server that interacts with databases and performs more time-intensive tasks. So, even though all the traffic may be flowing to that one load balancer, the load balancer may still be able to direct all the requests quickly enough.

Now, here’s the crucial thing. For this setup to be effective, the load balancer needs to distribute the traffic uniformly among all the available servers. Certainly, if the load balancer sends all the traffic to one server, we’ve truly accomplished nothing. We want all the servers to take on an equal share of the load.

And this is where the balls-in-bins analogy becomes relevant because directing requests to servers is essentially the same concept.

Fortunately, there are numerous algorithms that load balancers can use to ensure that the traffic is distributed evenly.

Round-Robin Load Balancing

One of the simplest and most common load balancing algorithms is called round-robin load balancing. We rotate between all the servers and send each request to the next server as illustrated in the .

In this image, we send the first request to the first server, the second request to the next server, and the third request to the next server.

With subsequent requests, we repeat the same pattern as shown here:

And so on. As with balls-in-bins, round-robin load balancing distributes the requests perfectly evenly, and the algorithm is as easy as pie.

However, the round-robin approach isn’t always the best one. This is because servers don’t always deliver responses at the same speed. This can happen for a variety of reasons, among them that one user made a request that is complex and requires that request’s server to do a lot more work.

Least-Time Load Balancing

A potentially “smarter” load balancing algorithm, called least-time load balancing, is one in which the load balancer detects how quickly each server is currently taking to process requests. Once the load balancer is aware of how speedy each server is in the moment, the load balancer sends the next request to the fastest server.

However, this works best when we’re only dealing with a single load balancer. Some setups, though, include multiple load balancers, which can be necessary when we have a lot of traffic, as shown in the .

But here’s the gotcha when dealing with multiple load balancers. In that diagram, we have two load balancers, but imagine we have 10.

Let’s also say that the 10 load balancers all receive requests at the same time. With the least-time load balancing scheme, the load balancers will all find the fastest server, and send all 10 requests to it. What a moment ago was the fastest server may now become the slowest by far, as we’ve clogged it with a slew of 10 requests simultaneously!

So, least-time balancing can fall apart when dealing with multiple load balancers. Luckily, there’s yet another load balancing algorithm that works well even under these conditions, and it involves randomization.

Randomized Load Balancing with the Power of Two Choices

Indeed, we can use randomization as the basis of a load-balancing algorithm. The simplest way to do this is to have the load balancer send each request to a random server. As you saw with balls in bins, distributing balls into random buckets is an effective way to distribute the balls pretty evenly. This distribution won’t be as uniform as round-robin load balancing, but it’ll be uniform enough. We’ll call this approach the “purely random” load-balancing algorithm. However, purely randomized load balancing runs into the same pitfalls as the round-robin approach: if there’s one slow server, we’re going to keep sending requests to it even though we should be avoiding it until it speeds up again.

However, a randomization algorithm known as the power of two choices works astonishingly well. This approach is almost as simple as the purely random algorithm, but with a twist: each load balancer chooses two random servers, checks which one is faster in the moment, and sends the request to that faster server.

Again, the problem with the purely random approach was that we may end up sending requests to the slowest server. But with the power of two choices, this is impossible to do. Even if our randomly chosen servers happen to be the slowest server and the second-slowest server, we still avoid sending the request to the slowest server.

The power of two choices is beneficial even if we randomly pick the fastest and second-fastest servers. After all, we’ll shave off some extra time by sending the request to the fastest server instead of the second-to-fastest one.

In theory, we could also have a power of three choices algorithm, which randomly chooses three servers and sends the request to the fastest one. However, the more servers we choose from, the more likely it is that we have multiple load balancers sending requests to the same server at once. Ultimately, these numbers may vary depending on the number of load balancers and servers our system has. However, as a general rule, the power of two choices algorithm has held up in many cases and has been shown to be effective.

Power of Two Choices for Balls in Bins

To see the power of two choices in action, let’s go back to our balls-in-bins code. Let’s change it up so that instead of throwing each ball into a random bin, we choose two random bins, and throw the ball into the emptier bin. This is analogous to a load balancer sending a request to the faster of two servers. Just as we want each server to have an equal load of web requests, we want each bin to contain the same number of balls. Here’s our updated code:

No matter how many times I run this code, I get results along these lines:

Wow! That’s pretty close to perfect distribution. And that, my friends, is the power of two choices—and randomization.

The Probability Theory Caveat

Some of the randomization concepts we’ve looked at are intuitive, while others are less so. It’s important to remember that probability and statistics are an entire subject, nay, an entire field, and I can’t do justice to it in these pages.

With that in mind, if you are developing your own randomization algorithm, you’ll often need to check its effectiveness using established probability theory. Sometimes it may seem that randomization will produce fantastic results, but when you run your idea through statistical formulas, you may discover that it’s not so hot after all. Remember when I thought that naïve shuffling was a good idea?

That being said, benchmarking is also your friend, and you may be able to demonstrate the power of your algorithm using the techniques outlined in the previous chapter.