The problem
One server can only answer so many requests per second. When more arrive than it can handle, they wait in a queue. The queue grows, pages get slow, and in the end the server falls over.
The fix is to run several copies of the server. That raises a new question: when a request arrives, which copy should answer it?
A load balancer is the part that decides. Clients talk to one address. Behind that address, the load balancer hands each request to one of the servers.
A request arrives
The client only knows the load balancer's address. It has no idea how many servers are behind it.
The load balancer picks a server
It follows one simple rule, called the algorithm. This page covers the eight rules you will meet most often.
The server does the work
If the server is busy, the request waits in that server's queue.
The answer goes back to the client
The client never learns which server answered.
A good rule keeps every queue short. A bad rule leaves one server drowning while another sits idle.
Try it first
Pick a rule and a kind of traffic, then press play. Use Step to move one request at a time and read why each choice was made.
The rule: Take turns: A, B, C, D, A, B, ... Four equal servers. One request in five is heavy. The number on each request is the work it has left.
- Sent
- 0 / 40
- Longest queue
- 0
- Average wait
- 0.0 ticks
How to read the animation:
- Each dot is a request. The number on it is how much work it still needs.
- A server works on the dot at the front of its queue. When the number reaches 0, the request is done.
- Pink dots are heavy requests. They hold up everything queued behind them.
- A server with 4 or more dots waiting turns red.
Round robin
The rule: take turns. The first request goes to A, the second to B, then C, then D, then back to A.
Example
Six requests, three servers
Request 1 goes to A. Request 2 goes to B. Request 3 goes to C. The list is finished, so it starts again: request 4 goes to A, 5 to B, 6 to C. Every server got exactly two.
The load balancer only has to remember one thing: whose turn it is.
servers = ["A", "B", "C"]
turn = 0
def pick():
global turn
server = servers[turn % len(servers)] # 0 -> A, 1 -> B, 2 -> C, 3 -> A, ...
turn += 1
return serverWhen every server is the same and every request is the same size, this is perfect. Watch: no queue ever holds more than one request.
The rule: Take turns: A, B, C, D, A, B, ... Four equal servers. Every request is the same size. The number on each request is the work it has left.
- Sent
- 0 / 28
- Longest queue
- 0
- Average wait
- 0.0 ticks
Good at
- The simplest rule there is, and the usual default
- Every server gets the same number of requests
- Needs to know nothing about the servers
Where it bites
- Assumes all servers are equally fast
- Assumes all requests cost the same
- Keeps sending to a server that is already struggling
Weighted round robin
Real servers are not always equal. Suppose server A is four times as fast as B, C and D. Plain round robin still gives each of them a quarter of the traffic. A finishes early and waits. The small servers fall behind.
The rule: take turns, but bigger servers get more turns. Each server gets a number called its weight. A weight of 4 means "send me four requests for every one you send to a weight-1 server".
Example
Weights 4, 1, 1, 1
The weights add up to 7. So out of every 7 requests, A gets 4 and the others get 1 each. A good load balancer spreads A's turns out instead of sending four in a row: A, B, A, C, A, D, A, then the pattern repeats.
Here are both rules on the same traffic. Server A is four times as fast.
- longest queue
- 0
- avg wait
- 0.0
- longest queue
- 0
- avg wait
- 0.0
Request 0 of 36. Server A is four times as fast as the others. Every card receives the same requests in the same order. Each bar is one server's queue.
Watch one of them up close. Server A receives most of the dots and still keeps up.
The rule: Take turns, but bigger servers get more turns. Server A is four times as fast as the others. The number on each request is the work it has left.
- Sent
- 0 / 36
- Longest queue
- 0
- Average wait
- 0.0 ticks
Good at
- Makes use of bigger machines
- Still simple: the weights are set once in the configuration
Where it bites
- Somebody has to choose the weights, and keep them right
- Still blind to how busy each server is at this moment
Random
The rule: pick any server, like rolling a die.
It sounds careless, but over thousands of requests every server ends up with about the same share. It also needs no memory at all, which matters when there are many load balancers that cannot easily share a "whose turn is it" counter.
Over a short stretch, though, luck is uneven. Some server gets three in a row while another gets none. Compare this with round robin above: same servers, same requests.
The rule: Pick any server, like rolling a die. Four equal servers. Every request is the same size. The number on each request is the work it has left.
- Sent
- 0 / 28
- Longest queue
- 0
- Average wait
- 0.0 ticks
Good at
- Nothing to remember and nothing to coordinate
- Fair over a long time
Where it bites
- Uneven over a short time: queues form by bad luck
- Blind to how busy each server is
Least connections
The rules so far never look at the servers. This one does.
The rule: send the request to the server with the fewest open requests. "Open" means sent to the server and not answered yet.
Example
Who gets the next one?
A has 3 open requests, B has 1 and C has 2. The next request goes to B. Now B has 2, tied with C, and the load balancer picks either one.
open_requests = {"A": 3, "B": 1, "C": 2}
def pick():
return min(open_requests, key=open_requests.get) # "B"This is the rule that copes with heavy requests. A server stuck on a big pink one has a longer queue, so new requests are steered away from it until it catches up.
The rule: Send it to the server with the fewest open requests. Four equal servers. One request in five is heavy. The number on each request is the work it has left.
- Sent
- 0 / 40
- Longest queue
- 0
- Average wait
- 0.0 ticks
Good at
- Reacts to what is happening right now
- Handles requests of very different sizes
- Good for long-lived connections such as chats, streams and downloads
Where it bites
- The load balancer must count open requests for every server
- Counts requests, not work: three tiny requests look busier than one huge one
Weighted least connections
Least connections treats every server as equal. Combine it with weights and you get a rule for servers of different sizes.
The rule: fewest open requests for its size. Divide each server's open requests by its weight and pick the lowest result.
Example
More requests, but less loaded
A has weight 4 and 4 open requests: 4 ÷ 4 = 1. B has weight 1 and 2 open requests: 2 ÷ 1 = 2. The next request goes to A, even though A already holds more. For its size, A is half as busy as B.
The rule: Fewest open requests for its size. Server A is four times as fast as the others. The number on each request is the work it has left.
- Sent
- 0 / 36
- Longest queue
- 0
- Average wait
- 0.0 ticks
Good at
- Uses bigger machines well and reacts to live load
- A sensible choice for a mixed fleet of servers
Where it bites
- Needs both things: correct weights and live counts
Least response time
Counting open requests is a guess at how busy a server is. This rule asks the real question.
The rule: send the request to the server that would answer soonest.
A real load balancer cannot see the future, so it measures the past: it tracks how long each server took to answer recently, often together with its open requests, and picks the best. In the animation below, the load balancer adds up the work waiting in each queue, which is the same idea with perfect information.
Example
Two requests are not always more than one
A has two small requests waiting, 2 units of work each: 4 in total. B has one heavy request: 10 units. Least connections would pick B, because it has fewer requests. Least response time picks A, because A will be free sooner.
The rule: Send it to whoever would answer soonest. Four equal servers. One request in five is heavy. The number on each request is the work it has left.
- Sent
- 0 / 40
- Longest queue
- 0
- Average wait
- 0.0 ticks
Good at
- Aims at the thing users feel: how long they wait
- Notices a server that is slow for any reason, such as a full disk or a noisy neighbour
Where it bites
- Needs constant measuring
- Measurements are always slightly old, so many balancers can rush to the same fast-looking server at once
IP hash
Every rule so far may send the same user to a different server each time. Sometimes that is a problem. If server A keeps your shopping cart in its own memory, your next request must reach A again.
The rule: the same client always goes to the same server. The load balancer takes the client's IP address, runs it through a hash function to turn it into a big number, and divides by the number of servers. The remainder picks the server.
Example
From address to server
A client's address hashes to 1,234,567. There are 4 servers. 1,234,567 ÷ 4 leaves a remainder of 3, so this client goes to server number 3 (counting from 0, that is D). Tomorrow the same address gives the same number and the same remainder, so it reaches D again.
import zlib
servers = ["A", "B", "C", "D"]
def pick(client_ip):
number = zlib.crc32(client_ip.encode()) # same address in, same number out
return servers[number % len(servers)]In the animation, each client has its own colour. Notice two things: a colour always lands on the same server, and client 1 sends half of all the traffic, so its server is buried.
The rule: The same client always goes to the same server. Four equal servers. Client 1 sends half of all requests. The number on each request is the work it has left.
- Sent
- 0 / 30
- Longest queue
- 0
- Average wait
- 0.0 ticks
Good at
- A user keeps reaching the same server, with nothing to store
- Helps when servers keep per-user data or a warm cache in memory
Where it bites
- One busy client, or a whole office behind one address, overloads one server
- Add or remove a server and the remainders change, so almost every client moves
Power of two choices
Least connections works well, but checking every server for every request gets expensive with hundreds of servers. Random is cheap, but uneven. This rule sits between them, and it is surprisingly good.
The rule: look at two random servers and take the less busy one.
Example
Two looks instead of one hundred
There are 100 servers. The load balancer picks two at random, say number 17 and number 62. Server 17 has 5 open requests and server 62 has 2. The request goes to 62. The other 98 servers were never checked.
import random
def pick():
first, second = random.sample(servers, 2)
return first if open_requests[first] <= open_requests[second] else secondWhy does one extra look help so much? With one random pick, an overloaded server is just as likely to be chosen as an idle one. With two picks, the overloaded server only gets the request if the other pick is even worse, which is rare.
In the animation, the two servers being compared are outlined: the chosen one with a solid line, the other with a dashed line.
The rule: Look at two random servers, take the less busy one. Four equal servers. One request in five is heavy. The number on each request is the work it has left.
- Sent
- 0 / 40
- Longest queue
- 0
- Average wait
- 0.0 ticks
Good at
- Close to least connections at a fraction of the cost
- Works with many load balancers, because no shared counter is needed
- Does not send everyone to the same quiet server at once
Where it bites
- Slightly worse than checking every server when there are only a few
All eight on the same traffic
Here is every rule handling the same 40 requests in the same order. Four equal servers, and one request in five is heavy. When the traffic stops, the rules are ranked by how long a request waited on average.
- longest queue
- 0
- avg wait
- 0.0
- longest queue
- 0
- avg wait
- 0.0
- longest queue
- 0
- avg wait
- 0.0
- longest queue
- 0
- avg wait
- 0.0
- longest queue
- 0
- avg wait
- 0.0
- longest queue
- 0
- avg wait
- 0.0
- longest queue
- 0
- avg wait
- 0.0
- longest queue
- 0
- avg wait
- 0.0
Request 0 of 40. Four equal servers. One request in five is heavy. Every card receives the same requests in the same order. Each bar is one server's queue.
What to notice:
- Random forms the longest queues. It never looks, and its luck runs out.
- Round robin shares requests evenly but not work, so a server that draws two heavy ones falls behind.
- Power of two choices lands level with the rules that check every server, using only two looks.
- IP hash depends entirely on who is sending. Here the four clients send about the same amount, and it still does no better than taking turns.
Which one should you use?
| Your situation | A good first choice |
|---|---|
| Servers are identical and requests are quick and similar | Round robin |
| Servers have different sizes | Weighted round robin |
| Requests vary a lot, or connections stay open for a long time | Least connections |
| Different sizes and varied requests | Weighted least connections |
| You care most about how long users wait, and you can measure it | Least response time |
| A user must keep reaching the same server | IP hash |
| Many servers, or many load balancers | Power of two choices |
What the animation leaves out
The simulation is small on purpose. A real load balancer also does these things:
- Health checks. It pings each server every few seconds and stops sending to one that does not answer. No rule on this page helps if requests go to a dead server.
- Slow start. A server that has just joined is given traffic gradually, so it is not flooded while it warms up.
- Draining. Before a server is removed, it is allowed to finish the requests it already has.
- Not being the weak point itself. Load balancers run in pairs or groups, so that one of them failing does not take the site down.
Key takeaways
- A load balancer gives clients one address and spreads their requests over many servers.
- Round robin takes turns. Weighted round robin gives bigger servers more turns.
- Least connections looks at how busy servers are right now, so it copes with heavy requests.
- IP hash keeps a client on one server, at the cost of even load.
- Power of two choices checks just two random servers and gets close to checking all of them.
- No rule wins everywhere. Match the rule to your servers and your traffic.