Load balancing

In lesson 15 you worked out how many servers a system needs. The next question is simple. A request arrives. Which of the servers gets it? And what happens when one server stops?

In lesson 2, the drawing had "a part that shares the requests between the servers". Interviewers want you to name that part and say how it works.

A weak answer draws one box and says "it spreads the load". A strong answer says how the box picks a server and how it finds a broken server. It also says what happens if the box itself breaks.

At SDE-1 level you should explain what the part does. At SDE-2 level you should compare two ways of picking a server and plan a spare. At SDE-3 level you should also find every part whose failure stops the whole system.

Think about a bank with five counters and one person at the door. The person at the door sends each customer to a free counter. If a counter closes, the person stops sending customers there. But if the person at the door is absent, nobody can enter.

You met this part in lesson 2. It is called a load balancer. The load is the requests that arrive (lesson 14). A load balancer is a server that sits in front of your other servers. Clients send every request to it. It passes each request to one of the servers behind it. It does three jobs:

1. One address. Clients know only the address of the load balancer. You can add or remove servers behind it, and clients notice nothing.
2. Sharing. It uses a rule to choose a server for each request.
3. Avoiding broken servers. It checks the servers and sends no requests to a broken one.

The flow is: Client -> Load balancer -> Server 1, 2 or 3 -> Database.

Layer 4 and layer 7

Network messages are built in layers, and the layers have numbers. Two layers matter here. Layer 4 is the connection: the TCP link between two computers (lesson 7). Layer 7 is the application: the HTTP request with its path, headers and cookies (lesson 7).

An L4 load balancer works on connections. When a client opens a TCP connection, it picks a server and passes all the data of that connection to it. It sees only IP addresses and port numbers. A port is a number that names one program on a computer. It cannot see the path of the request.

An L7 load balancer reads each HTTP request. It sees the path, the host name, the headers and the cookies. So it can send /images/... to file servers and /api/... to app servers. To read an HTTPS request, it must first remove the lock (lesson 7).

Ways to pick a server

• Round robin. Send request 1 to server A, request 2 to server B, request 3 to server C, then start again. It is simple. It works well when servers are equal and requests cost about the same.
• Weighted round robin. Give each server a weight, a number for its size. A server with weight 2 gets twice as many requests as a server with weight 1. Use it when servers have different sizes.
• Least connections. Send the request to the server with the fewest open connections. Use it when some requests take much longer than others.
• Same client, same server (sticky). A hash turns the client IP address into a number. The same address always gives the same number, so the same client always reaches the same server. Many phone users can share one IP address, so the load can become uneven.

Sticky choice exists because of records that a server keeps. In lesson 7, a cookie holds only an ID, and the server looks up that ID in its own records. If the records live in one server's memory, another server cannot find them. A sticky rule sends the user back to the same server. The cost is uneven load, and when that server stops, its users lose their records. A safer design keeps the records where every server can read them.

Health checks

A health check is a small request that the load balancer sends to each server on a timer, for example GET /health. The server is healthy if it answers in time with a success status code, such as 200 (lesson 7). The settings are:

• Interval: the time between checks.
• Failure count: how many failed checks in a row make a server unhealthy. The load balancer then stops sending it requests.
• Pass count: how many passed checks in a row bring it back.

Detection is not instant. The load balancer must see the failure count of failed checks, one interval apart. Until then, requests to the dead server fail.

Keep the check simple. It should show only that this server can answer. If it also fails when the database is slow, every server fails the check together, and no server is left.

Single points of failure

A single point of failure is a part that, when it stops, stops the whole system. To find one, ask of each box in your drawing: "If only this box stops, can users still be served?" Five servers pass the test. One load balancer does not. The one database box in a drawing also fails this test. A load balancer in front of the servers cannot fix that, so say it aloud in the interview.

The fix is to run two load balancers. The second one takes over the address when the first one stops, or both are used at the same time. A load balancer is also a machine with a limit. Check that its capacity is above your peak. A load balancer from a cloud provider can run on several machines in several data centres, if you switch that on (see Sources). Say this aloud in the interview.

A shop app has a sale. We size the servers, then break one.

Assumptions (made up to teach with, not real traffic):

• Peak load is 1,400 requests per second.
• A server has 4 cores and uses 8 ms of CPU per request (lesson 15). We plan for 70% busy, and one spare server.
• The health check runs every 2 seconds. Two failed checks in a row make a server unhealthy.
• Each load balancer is up 99.9% of the time. Failures are independent, which means one failing does not make the other fail.

Step 1: how many servers.

• One server at full load = 4 x 1,000 / 8 = 500 requests per second.
• At 70% busy: 500 x 0.7 = 350.
• Servers = 1,400 / 350 = 4. Plus 1 spare = 5 servers.

Step 2: round robin. The load balancer gives each server 1,400 / 5 = 280 requests per second. That is 280 / 500 = 56% busy.

Step 3: one server crashes. Detection takes between 2 and 4 seconds. At best, the crash happens just before a check: the failed checks come at about 0 and 2 seconds. At worst, it happens just after a check: they come at 2 and 4 seconds. Before detection, the dead server still gets 1,400 / 5 = 280 requests per second, and each of them fails.

• Failed requests, best case = 280 x 2 = 560.
• Failed requests, worst case = 280 x 4 = 1,120.
• Total requests in 4 seconds = 1,400 x 4 = 5,600, so the worst case loses 1,120 / 5,600 = 20%.

After detection, 4 servers share the load: 1,400 / 4 = 350 each, which is 350 / 500 = 70% busy. This answers the predict box. The spare server was planned for exactly this.

A second crash leaves 3 servers. Each gets 1,400 / 3 = 467 (rounded from 466.7), which is 467 / 500 = 93% busy. That is close to the limit.

Step 4: weights. Assumption: server A has 4 cores (500 requests per second) and server B has 2 cores (250). The load is 600 per second.

• Round robin gives 300 each. A is at 300 / 500 = 60%. B is at 300 / 250 = 120%, which is too much.
• Weights 2 : 1 give A 400 and B 200. A is at 400 / 500 = 80%. B is at 200 / 250 = 80%.

Step 5: least connections. Assumption: two servers, and four requests arrive at 0, 1, 20 and 21 ms. They take 1,000, 10, 1,000 and 10 ms.

• Round robin sends requests 1 and 3 to server A, and 2 and 4 to server B. A gets 1,000 + 1,000 = 2,000 ms of work. B gets 10 + 10 = 20 ms.
• Least connections sends request 1 to A. At 1 ms, A has 1 open connection and B has 0, so request 2 goes to B. (When both have the same number, the choice does not matter for this example.) At 20 ms, B has finished, so request 3 goes to B. At 21 ms, both have 1 open, so request 4 goes to A. Each server gets 1,010 ms of work.

Step 6: the load balancer itself. With one load balancer, downtime = 0.001 x 43,200 minutes in a 30-day month = 43.2 minutes (lesson 4). With two, both must be down together: 0.001 x 0.001 = 0.000001. That is 0.000001 x 43,200 = 0.043 minutes, about 2.6 seconds a month. This is the best case. Switching takes time, and two machines can fail for the same reason.

Simulator Level 2 shows this: after the crash twist it notices in 5 seconds, and requests to the dead server fail meanwhile.

• A load balancer solves one address, sharing, and a broken server. It costs one more box to run, and one more step for each request (1 ms in Level 2). It is a new single point of failure until you run two. I would add it as soon as there are two servers.
• L4 solves speed and simplicity. It costs the ability to route by path. I would change to L7 when I need to send different paths to different servers.
• Round robin solves simplicity. It costs fairness when requests differ in length. I would change to least connections when some requests are much slower than the rest.
• Sticky rules solve records held in one server's memory. They cost even sharing. I would move the records out of the servers instead.

"A load balancer keeps the whole system up." It protects only the servers behind it. In the example, one load balancer allows 43.2 minutes of downtime a month. Run two.

"Round robin is always fair." It shares requests equally, not work. With requests of 1,000 ms and 10 ms, one server got 2,000 ms of work and the other 20 ms.

"The load balancer knows at once when a server dies." It knows after the failure count of checks. With checks every 2 seconds and two failures, up to 4 seconds of requests to that server fail.

1. What is the difference between an L4 and an L7 load balancer? Name one thing only L7 can do.
2. A system has a peak of 2,100 requests per second. One server does 600 requests per second at full load. You plan for 70% busy and one spare. (a) How many servers? (b) After one crash, how busy is each remaining server?
3. Health checks run every 5 seconds, and three failed checks in a row make a server unhealthy. One of 4 servers crashes. The load is 800 requests per second. In the worst case, how many requests fail before the load balancer reacts? What would you change?