Load Balancing

The problem: one address, many servers

Say your app gets about 3,000 requests a second at busy hours, and one app server handles about 1,000. So you scale out to three identical, stateless servers. But a browser knows one address. If that address is server A's, all 3,000 requests a second land on A, three times what it can handle, while B and C sit idle.

A load balancer solves this. It owns the one public address, receives every request, and passes each one to a server behind it. Browsers never learn the servers' addresses, so you can add, remove or replace servers without anyone noticing. Passing requests on is light work, so one balancer carries far more traffic than one app server.

Two shortcuts work less well. Listing all three servers in DNS lets browsers pick one, but browsers and DNS caches keep an address for minutes or hours, so a dead server keeps getting users. Having A forward its extra requests still sends all 3,000 a second to A first.

Round robin: take turns

The simplest rule is round robin: send each new request to the next server in the list, then start over. It needs to know nothing about the servers.

request   1  2  3  4  5  6  7  8  9  10  11  12
server    A  B  C  A  B  C  A  B  C  A   B   C

Twelve requests, four for each server; at 3,000 requests a second, about 1,000 each. Round robin works well when requests cost about the same and the servers are the same size. When one server is twice as big, weighted round robin gives it two turns for each turn of the others.

Least connections: look at who is busy

Round robin counts turns; it never looks at how busy a server is, and real requests are rarely equal. Say requests 1, 4 and 7 are report exports that keep a server busy for 30 seconds, and the others take a few milliseconds:

request             1     2      3      4     5      6      7
kind                slow  quick  quick  slow  quick  quick  slow
round robin         A     B      C      A     B      C      A
least connections   A     B      C      B     C      C      C

Round robin ends with all three slow requests on A while B and C sit idle. Least connections sends each request to the server with the fewest requests still open (servers that tie take turns). When request 4 arrives, A is still busy with request 1, so it goes to B, and request 7 finds C with nothing open: one slow request on each server.

The cost is small: the balancer counts open requests per server, which is easy because every request passes through it. It's a good choice whenever request times vary: uploads, reports, long-lived connections.

Health checks: finding dead servers

When a server's machine crashes, nothing tells the balancer. Round robin keeps giving the dead server its turn, so every third request fails: about 1,000 a second of the 3,000.

So the balancer asks. A health check is a small request, such as GET /health, that the balancer sends to every server every few seconds. Say it checks every 5 seconds, takes a server out after 3 misses in a row, and puts it back after 2 passes in a row:

0 s    C crashes, just after passing a check
5 s    miss 1: C stays in (one miss could be a hiccup)
10 s   miss 2: C stays in
15 s   miss 3 in a row: C is out; requests go to A and B only
later  C is restarted, passes 2 checks in a row (within about 10 s), and is put back

Waiting for 3 misses keeps one slow answer from throwing a healthy server out, but for up to 15 seconds C still gets a third of the traffic: at 3,000 requests a second, about 15,000 failed requests. So check often, and let the balancer retry a failed request on another server when it's safe to repeat, such as a GET.

Plan for one server down

Once C is out, A and B share all 3,000 requests a second: 1,500 each, half again what one server handles, so they slow down too. The fix is a spare: run 4 servers when 3 are enough, so losing one still leaves the capacity you need. This is called N + 1: the servers you need, plus one.

The balancer must not be a single point of failure

Every request passes through the balancer, so if its machine dies, the whole site is down however healthy the servers are. Health checks can't help (the balancer runs them), and browser retries go to the same dead address.

The usual setup is two balancers sharing one address. The standby checks the active one every second or so and, when it stops answering, takes over the address within a few seconds. Cloud providers' managed load balancers are already built redundant, so in an interview it's enough to say so.

Other choices and their trade-offs

• Hashing and sticky sessions: hash the user's ID or a cookie so the same user always lands on the same server. It helps when a server keeps something in memory for that user, but when that server dies its users lose it, and load can turn uneven. Prefer stateless servers with sessions in a shared store. When a request must reach the server that owns a key, as with cache servers, use consistent hashing (its own lesson).
• Layer 4 or layer 7: a layer 4 balancer forwards connections by IP address and port without reading them: very fast, and it works for any protocol. A layer 7 balancer reads the HTTP request (path, headers, cookies), so it can send /api to one group of servers and /images to another, end HTTPS and retry, at more work per request. Most web designs draw a layer 7 balancer.

Where it shows up in design interviews

Almost every design has a load balancer. Draw one in front of each tier of stateless servers: web servers, API servers, each service of a split design, read-only copies of a database. Then say which rule it uses (round robin, or least connections when request times vary) and how it finds dead servers (health checks, plus a spare server to carry the load). If the interviewer pushes on reliability, add that the balancer itself runs as a pair.

Not every tier needs one. The one database leader that takes every write has nothing to spread; cache servers each hold their own keys, so requests are routed by hashing the key; and workers pull jobs from a queue, which already spreads the work.

Common interview questions

What happens when a server behind the balancer dies?

The balancer's health checks notice: after a few failed checks in a row, it stops sending that server requests, and the others share its load. When the server passes a few checks in a row, it is put back. Requests caught in between can be retried on another server.

Round robin or least connections?

Round robin when requests cost about the same: it's simple and keeps no state. Least connections when request times vary, because it sends new work to the server with the fewest requests open.

How do you keep a user's session when requests go to different servers?

Keep the servers stateless and put sessions in a shared store every server can read, such as a cache or a database. Sticky sessions also work, but a server's death logs its users out.

Summary

• A load balancer gives many servers one address and spreads requests over them.
• Round robin takes turns: simple, but blind to how busy a server is.
• Least connections picks the server with the fewest open requests: better when request times vary.
• Health checks find dead servers: say every 5 seconds, out after 3 misses, back after 2 passes.
• Keep a spare server (N + 1), so losing one doesn't overload the rest.
• Run the balancer as a pair, so it isn't a single point of failure.
• In an interview, draw one in front of every stateless tier and say how it finds dead servers.