Load Balancing Algorithms

This is the answer when your servers are not the same size. The cost is that you set the weights by hand, and you have to change them when the hardware changes.

Least Connections

Send the next request to the server that has the fewest open connections at this moment.

This rule reacts to real load, and it needs no configuration from you. If one server is stuck with slow requests, its connection count stays high, and it stops receiving new work.

It has one important weakness. It counts connections, not capacity. A small server and a large server that both hold 10 connections look the same to it. The small server then gets an equal share and runs out of resources first.

It works best when connections stay open for a while and their length varies, such as WebSocket traffic or long API calls.

Weighted Least Connections

Divide each server's connection count by its weight, and pick the smallest result.

This fixes the weakness above. It looks at the current load like Least Connections, and it knows the size of each server like Weighted Round Robin. The cost is that you again have to set and maintain the weights.

Least Response Time

Send the request to the server that has been answering fastest in the recent past.

This sounds like the best rule, and it has two traps.

The first trap is that response times move quickly. A short slow moment can push all new traffic to another server, and the choice can jump around.

The second trap is that failing is fast. A server that returns an error in 2 milliseconds looks faster than a healthy server that does real work in 50 milliseconds. Without a health check that looks at the status code, the broken server attracts all the traffic.

Least Bandwidth

Send the request to the server that is currently sending the fewest megabits per second.

This is about the size of the responses, not about speed. It only makes sense when responses are large, for example video or file downloads. For normal API traffic it tells you almost nothing.

IP Hash

Take the client's IP address, run it through a hash function, and use the result to choose the server. The same client address then always reaches the same server.

The purpose of this rule is stickiness. It keeps one user on one server without any shared session storage.

Two things about it are often stated wrongly.

It does not send users to a server near them. The hash of an IP address has no connection to the location of that address. Sending users to a nearby data center is done with DNS or anycast routing, not with IP hash.

It also does not spread the load evenly. Many users can share one address, for example a whole office or a mobile network, and they all land on the same server.

The bigger problem is what happens when the number of servers changes. The choice is normally hash(IP) % number_of_servers. Add one server to a group of three, and that number changes from 3 to 4. Almost every client then moves to a different server. Every session built on stickiness is lost at the same moment.

Consistent hashing is the fix. It is a different way of mapping keys to servers. When you add or remove one server, only a small share of the keys move. It is covered in Consistent Hashing.

Random, and Random of Two

Pick a server at random. With enough requests the spread is even, and the rule costs nothing.

There is a better version of it. Pick two servers at random, then send the request to whichever of the two has fewer connections. This gets very close to the result of Least Connections, and the load balancer only has to compare two numbers instead of tracking every server. NGINX offers it as random two.

Custom Rules

Most cloud load balancers and modern proxies let you write your own rule, using CPU, memory, queue length, or a number your application reports.

This is powerful, and it moves the responsibility to you. You now own the monitoring, and a wrong metric sends traffic to the wrong place.

How to Choose

For most systems the honest answer is that round robin or least connections is enough.

• Servers are the same size and requests are short: round robin.
• Servers are different sizes: weighted round robin.
• Requests take very different amounts of time, or connections stay open: least connections.
• Different sizes and uneven requests: weighted least connections.
• Responses are large files or video: least bandwidth.
• The same user must reach the same server: IP hash. It is usually better to move the session into a shared cache instead, and remove the need for stickiness.

In an interview, name the algorithm, then say what it does not know. That second part is what shows you understand it.

Key Takeaways

• The algorithm only picks between healthy servers. Health checks are a separate mechanism, so "ignores server health" is not a weakness of any algorithm.
• Round robin is simple and counts requests, not work. Weighted round robin adds server size, which you must configure by hand.
• Least connections reacts to real load with no configuration, but it is blind to server capacity. Weighted least connections fixes that.
• Least response time can be fooled by a server that fails quickly, because an error is fast.
• Least bandwidth measures the size of responses, not speed. It is for large downloads and video.
• IP hash gives stickiness. It does not route by location, it spreads load unevenly, and adding a server moves almost every client. Consistent hashing solves the last problem.
• Random of two choices is nearly as good as least connections and much cheaper to run.

The algorithm matters less than most people expect. Uneven load usually comes from somewhere else. Sessions kept in server memory, one very popular item, or requests that cost very different amounts. Fix those first.