Premium Video

This video is available to premium subscribers only

Unlock Full Access

A load balancer sits in front of a group of servers and decides which server should handle each incoming request. The rule it uses to make that decision is called a load balancing algorithm.

In this chapter, we will look at the most common load balancing algorithms, how each one picks a server, where each one works well, and how to choose between them.

There are two main categories of load balancing algorithms: static and dynamic.

Static algorithms follow a fixed rule without considering how busy the servers are. For example, they might send requests to servers in a fixed order or choose a server at random.

Dynamic algorithms, on the other hand, look at the current state of the servers before making a decision. They might check how many active connections each server has or how quickly each server is responding.

Static algorithms are simple and have very little overhead, but they can't adapt when some servers become overloaded. Dynamic algorithms can respond to changing conditions, but they rely on server metrics that may not always be up to date.

What the Load Balancer Can See

A dynamic algorithm can only use the signals available where the load balancer runs. A DNS-based balancer sees much less than one that reads HTTP requests.

So an algorithm is only as good as the signal behind it. Least connections helps only if connection count says something useful about load. Least response time helps only if recent latency is a good hint about what will happen next.

No algorithm can make up for missing health checks, bad timeouts, or not enough capacity.

With that distinction in mind, let's start with the simplest algorithm.

Suppose we have three servers: A, B, and C. With round robin, the load balancer sends the first request to A, the second to B, and the third to C. The fourth request goes back to A, and the cycle continues in the same order.

The load balancer only needs to keep track of which server it selected last. This makes round robin simple to implement and easy to understand.

Round robin is a common default in load balancers like NGINX and HAProxy.

When It Works

Round robin works well when two conditions are met:

For example, if you have a pool of identical stateless API servers handling short requests, round robin is often a good choice.

Where Round Robin Breaks Down

The problem with round robin is that it distributes requests equally, but not all requests require the same amount of work.

For example, imagine most requests to your service finish in 10 milliseconds, but generating a report takes 5 seconds. Round robin treats both types of requests the same.

If several report requests happen to reach Server A, it continues receiving its normal share of new requests, even though it's already busy. As a result, requests start queuing up on Server A, while Servers B and C still have spare capacity.

So even though all three servers receive the same number of requests, the actual workload is not evenly distributed.

Another problem arises when servers have different capacities. Suppose Server A has 16 CPU cores, while Servers B and C have only 4 cores each. Round robin still sends one-third of the traffic to each server. This means Server A may be underutilized while the smaller servers struggle to keep up.

Simple Implementation

A round robin picker is just a counter and a remainder operation. The code below shows the same idea in six languages.

In production, the list should contain only healthy servers that are ready for traffic.

We can address the second problem, servers with different capacities, with a small modification to round robin.

Weighted round robin addresses this problem by assigning each server a weight based on its capacity. A server with a weight of 4 receives four times as many requests as a server with a weight of 1.

For example, suppose Server A has a weight of 4, while B and C each have a weight of 1. Out of every 6 requests, A receives 4, while B and C receive 1 each.

Weights are also useful when you want to control traffic on purpose. You can send a small share of traffic to a canary release, or slowly ramp up a new region.

Smooth Weighted Round Robin

The simplest way to implement weights is to send 4 requests to A, followed by 1 to B and 1 to C. This gives us the correct ratio, but it also sends requests to A in bursts.

To avoid this, load balancers like NGINX use a variation called smooth weighted round robin. It keeps the same ratio but spreads each server's turns across the cycle. Server A still receives 4 out of every 6 requests, but B and C get their turns in between.

The implementation below gives each server a running score. On every pick, each score grows by the server's weight, the highest score wins, and the winner's score drops by the total weight.

Where It Falls Short

Weighted round robin still has a limitation. The weights are fixed based on how much traffic we expect each server to handle, not how busy it actually is.

If a server suddenly slows down because of a long garbage collection pause or another process competing for resources, its weight doesn't change. It continues receiving the same share of traffic, even though it may no longer have the capacity to handle it.

Before moving on to dynamic algorithms, let's look at one more static approach: random selection.

With this algorithm, the load balancer picks a server at random for each incoming request. Over a small number of requests, the distribution might be uneven. But as the number of requests increases, traffic tends to spread more evenly across the servers.

The main advantage of random selection is its simplicity. There's no counter or shared state to maintain, so multiple load balancer instances can make decisions independently without coordinating with each other.

Simple Implementation

There is not much to random selection in code: pick an index in the server list with a random number.

Where It Falls Short

Just like round robin, random selection doesn't consider how busy each server is. A server that's already overloaded can still receive new requests while other servers have spare capacity.

To handle this, the load balancer has to look at the current load on each server. That's what dynamic algorithms do.

One of the most common dynamic load balancing algorithms is least connections. With this approach, the load balancer keeps track of how many active connections each server has. When a new request arrives, it sends it to the server with the fewest active connections.

Let's go back to our report example. Suppose Server A is handling three slow report requests, so it has three active connections, while Servers B and C have only one each. With least connections, the next request goes to B or C instead of A.

Since the slow requests keep their connections open longer, Server A's connection count stays high, and new traffic goes to the less busy servers.

This makes least connections a good choice for workloads where requests or connections can have very different durations, such as file uploads, database connections, or WebSockets.

There's also a weighted version that considers server capacity, allowing more powerful servers to handle a larger share of connections.

Least Requests for HTTP/2 and gRPC

Connections and requests aren't always the same thing. With protocols like HTTP/2 or gRPC, a single connection can carry multiple requests at the same time. In these cases, counting connections alone can be misleading.

Instead, load balancers can track active requests. Envoy, for example, supports an algorithm called least request, which uses this approach.

Basic Implementation

To pick the least-loaded server, keep a count of active requests per server and choose the lowest count. The code below shows that bookkeeping, including the increment when a request starts and the release when it finishes.

Production implementations also have to handle server removal, failed requests, timeouts, and concurrent updates safely.

The Problem with New Servers

Least connections has one important problem to watch out for. When you add a new server to the pool, it starts with zero active connections. To the load balancer, that makes it look like the least busy server, so it may receive a large burst of new traffic.

The problem is that a newly started server may not be ready to handle that much traffic. Its caches are still empty, its connection pools haven't been created yet, and if the application uses a JIT compiler, its code may not be fully optimized yet.

To avoid this, load balancers use a technique called slow start. Instead of sending a large amount of traffic to the new server immediately, the load balancer starts with a small share and gradually increases it over a period of time, such as 30 or 60 seconds.

Load balancers like HAProxy, NGINX Plus, and AWS Application Load Balancer support this feature. It's particularly useful when you're using least connections, as it gives new servers time to warm up before handling their full share of traffic.

Connection count tells us how many connections a server is handling, but it doesn't tell us how quickly the server is processing them.

For example, two servers might each have 10 active connections, but one responds in 20 milliseconds while the other takes 200 milliseconds because of a slow disk or a garbage collection pause.

Least response time tries to account for this difference. The load balancer measures how long each server takes to respond and prefers servers with lower response times. Some implementations also consider active connections, so they can choose a server that is both fast and not overloaded.

Smoothing with a Moving Average

Using the response time of the most recent request isn't always reliable. A single slow request, perhaps caused by a large database query, could make an otherwise healthy server appear slow.

To avoid this, load balancers use an exponentially weighted moving average. This maintains a running average of response times, giving more weight to recent measurements while smoothing out sudden fluctuations.

So one unusually slow response has a limited effect on the average, but if a server consistently responds slowly, its average increases, and the load balancer gradually directs traffic elsewhere.

The code below keeps a moving average for each server and picks the one with the lowest average.

This example is intentionally incomplete. A production version should also send an occasional request to quiet servers, so their latency data does not go stale.

Where It Falls Short

Response time depends not just on the server, but also on the type of request being processed. For example, a request that runs a heavy database query might be slow regardless of which server handles it.

If several such requests happen to reach the same server, its average response time increases. The load balancer may then move traffic away from that server, even though the server itself may be healthy.

Least connections and least response time both rely on the load balancer having reasonably accurate information about how busy each server is. But in large systems, that information isn't always available.

You might have multiple load balancer instances, and each one only sees the traffic passing through it. This means each instance has a slightly different and potentially outdated view of the servers.

This can lead to a problem called herding. For example, suppose ten load balancer instances all see that Server C has the fewest active connections. They might all send their next requests to C at roughly the same time, suddenly overloading it. When they check again, they might all switch to another server, creating the same problem there.

An algorithm called power of two choices helps avoid this problem with a simple approach. Instead of comparing every server, the load balancer randomly selects two servers and sends the request to whichever one is less busy.

The random selection reduces the chance of multiple load balancers choosing the same server, while the comparison helps avoid sending requests to servers that are already overloaded.

Research has shown that comparing just two randomly selected servers distributes load much more evenly than choosing a single server at random. Comparing more than two can improve the distribution further, but the additional benefit is usually much smaller.

It's also efficient, because the load balancer only needs to compare two servers for each request, regardless of how many servers are in the pool.

Envoy uses power of two choices by default for its least request algorithm, and NGINX supports a similar approach through its random two option.

Simple Implementation

In code, power of two choices is short: sample two servers at random, then return whichever has fewer active requests.

If server weights differ, compare a weighted score instead of raw active counts.

So far, we've assumed that any server can handle any incoming request. But sometimes, we want certain requests to keep going to the same server.

For example, if each server maintains a local cache, sending requests for the same data to the same server improves cache hit rates. Similarly, if a user's session is stored in a server's memory, we want that user's requests to keep reaching the same server.

This is what hash-based routing is for. The load balancer takes some value from the request and passes it through a hash function. It then uses the result to decide which server should handle the request.

The value can be anything that identifies the traffic you want to keep together:

Source IP Hashing

The simplest approach is source IP hashing. The load balancer hashes the client's IP address and takes the result modulo the number of servers. As long as the server pool doesn't change, requests from the same IP address always go to the same server.

However, this approach has two important problems.

First, multiple users can share the same public IP address. For example, everyone in a large office or behind a mobile carrier's network might appear to have the same IP address. As a result, all their requests could end up on the same server, creating an uneven distribution of traffic.

The second problem occurs when the number of servers changes. Suppose we have four servers and decide to add a fifth. Now, instead of taking each hash modulo 4, we take it modulo 5. This changes the mapping for most keys, causing roughly 80 percent of them to move to different servers.

If we're using hash-based routing to take advantage of local caches, this becomes a serious problem. Most requests suddenly reach different servers, where the required data may not be cached. As a result, cache hit rates can drop significantly, even though we only added one server.

Clients' IP addresses can also change, for example when a phone moves between networks. Hashing a session cookie, user ID, or another application key is often more reliable than hashing the IP.

Consistent hashing solves this problem by reducing the number of keys that need to move when servers are added or removed.

Instead of using modulo, it places both servers and keys on a circle, commonly called a hash ring. Each server is hashed to a position on the ring, and each key is hashed in the same way. To find which server should handle a key, we start at the key's position and move clockwise until we reach the first server.

Now, suppose we add a new server. It gets placed somewhere on the ring and takes over the keys between its position and the previous server. All other keys continue going to their existing servers.

In our earlier example, when we go from 4 servers to 5, only about 20 percent of the keys need to move, assuming an even distribution, compared to roughly 80 percent with modulo hashing.

Removing a server works similarly. Only the keys assigned to that server need to move, and they go to the next server on the ring.

In practice, servers are usually placed at multiple positions on the ring using virtual nodes. This helps distribute keys more evenly and keeps any one server from owning a large section of the ring by chance.

Rendezvous Hashing

Rendezvous hashing reaches the same goal without a ring. For each key, it gives every server a score and picks the server with the highest score. When a server is added or removed, only the keys that prefer that server move. Google's Maglev hashing is another variant used in large load balancers.

The code below implements rendezvous hashing, since it is the shortest to write.

Where It Falls Short

Hash-based routing still has one important limitation: it doesn't consider how busy each server is.

If a particular key receives a lot of traffic, such as a popular product page, all those requests may go to the same server. That server can become overloaded while others still have plenty of spare capacity.

So far, we've focused on choosing a server based on factors like load, response time, or request characteristics. But there's another important factor to consider: where the server is located.

In real-world systems, servers are often spread across multiple availability zones and regions. Sending requests to another zone can increase latency, and cloud providers may also charge for data transferred between zones.

Locality-aware routing helps reduce these costs by preferring servers that are closer to the load balancer. For example, if a load balancer is running in zone A, it first tries to send requests to servers in that same zone. Within the zone, it can still use an algorithm like round robin or least requests to choose a server.

Falling Back to Other Zones

But what happens if the local servers can't handle all the traffic?

If too many servers in zone A become unhealthy or overloaded, the load balancer can start directing some requests to servers in other zones. This fallback is important because it allows the system to keep serving requests even when the local zone doesn't have enough capacity.

Envoy supports this approach through zone-aware routing.

Where It Falls Short

Traffic and server capacity may not be evenly distributed across zones. For example, suppose most requests arrive in zone A, but most of your servers are in zone B. If the load balancer always prefers local servers, those in zone A could become overloaded while servers in zone B remain underutilized.

That's why locality-aware routing needs to consider not just how close the servers are, but also how much traffic and capacity each zone has.

If your data has to stay in a specific region for legal reasons, the fallback rules also need to respect that.

The final approach takes this a step further. Instead of estimating how busy a server is based on connection counts or response times, the load balancer gets load information directly from the servers.

Each server reports metrics such as CPU usage, memory usage, queue depth, or request rate. These metrics can be sent through response headers or a separate reporting channel.

The load balancer then uses this information to continuously adjust how much traffic each server receives. For example, a server running at 90 percent CPU might receive fewer requests, while a server at 30 percent gets a larger share.

gRPC supports a form of this through its weighted round robin policy. Backend servers report metrics like CPU utilization and request rate, and the client uses those measurements to calculate routing weights.

This approach is particularly useful when servers with identical specifications perform differently. For example, one server might be sharing hardware with another resource-intensive workload, causing it to process requests more slowly.

Where It Falls Short

Adaptive routing introduces a new challenge: instability.

If routing weights change too quickly, multiple load balancers might suddenly direct more traffic to the server reporting the lowest load. That server then becomes busy, causing traffic to shift away again. Instead of distributing traffic smoothly, the system keeps shifting load back and forth between servers.

To prevent this, adaptive routing needs to smooth out load measurements, limit how quickly weights can change, and provide a sensible fallback when a server stops reporting its metrics.

With so many algorithms available, how do you decide which one to use? The best choice depends on your workload and how your servers are configured.

The table below maps some common workloads to a sensible starting point.

In practice, real systems often combine several of these approaches. For example, a request might first be routed to a nearby zone, then assigned to a server using power of two choices, with slow start applied to newly added servers.

Regardless of which algorithm you choose, make sure the load balancer uses health checks to avoid sending traffic to unhealthy servers.

A load balancing algorithm is the rule a load balancer uses to pick a server. Static algorithms follow a fixed rule. Dynamic algorithms look at the current state of the servers.

Round robin is simple and works well when servers and requests are similar. Weighted round robin handles servers with different capacities, but its weights are fixed and don't react to live load. Random selection needs no shared state, but it also ignores load.

Least connections handles requests with very different durations, and least requests is the better signal for HTTP/2 and gRPC. Use slow start so new servers aren't flooded. Least response time follows latency, but it needs a moving average to stay stable.

Power of two choices avoids herding when many load balancer instances share the same pool, and it only compares two servers per request.

Hash-based routing keeps the same key on the same server. Consistent hashing moves far fewer keys than modulo hashing when servers change, but a hot key can still overload one server.

Locality-aware routing keeps traffic close, with a fallback to other zones. Adaptive routing uses load reported by the servers, but it needs smoothing to avoid shifting traffic back and forth.

Real systems often combine several of these. Whatever you choose, keep health checks in place so traffic only goes to healthy servers.