The problem
"Design a load balancer." Most designs draw the load balancer as a box in front of the servers. Here the box is the system: it receives every request to the site, picks a healthy server for each one, and must keep working while servers crash or are updated, and when its own machine fails.
This practice problem reuses the pattern of Design a Key-Value Store, with the Load Balancing and Consistent Hashing lessons. Version 1 serves one data center; sending users to the nearest of several (DNS or anycast) and blocking attacks (a firewall, a rate limiter) come later.
The numbers
From the interviewer: 100,000 requests a second over 50 servers, so each server gets 100,000 ÷ 50 = 2,000 a second. If a request takes about 20 ms, each server is in the middle of about 40 at any moment.
Checks run every 5 seconds: 3 failed in a row take a server out, 2 good ones bring it back. A server that crashes just after passing one fails the checks at 5, 10 and 15 seconds, so for 15 seconds its share of the traffic fails:
check every out after failed requests
5 s 15 s 2,000 × 15 = 30,000
1 s 3 s 2,000 × 3 = 6,000Faster checks lose fewer requests, but then a healthy server that pauses for 3 seconds is thrown out.
Layer 4 or layer 7
A layer 4 balancer passes each connection on by its address and port, without reading what's inside. It is fast, works for any protocol, and can still count open connections or hash the client's address.
A layer 7 balancer reads each HTTP request: the path, the headers, the cookies. Only it can send /api/… to one group of servers and pages to another, keep a user on a server by a cookie, or retry a failed GET elsewhere. To read HTTPS it must decrypt it, so it holds the site's certificate. For a website, pick layer 7; at large scale a common design puts a layer 4 tier in front of it.
Sessions: sticky or shared
If app servers keep logins in their own memory, the app team asks the balancer to send each user back to the same server: sticky sessions. A layer 7 balancer can do it with a cookie, but when that server dies or is updated its users, 1 in 50, are logged out, and every deploy has to wait for sessions to end. Hashing the client's address is worse: an office shares one address, and a phone's address changes as it moves.
Keep the servers stateless instead: sessions go into a shared key-value store that every server reads. That costs one lookup per request, about 0.5 ms inside the data center; 100,000 lookups a second is roughly what one in-memory server answers, so run a few with copies. If something must stay on one server, like a large per-user cache, hash users onto a ring: a new server then moves only a slice of them.
Health checks: what to test
A check should fail only when this server is broken, because that is all the balancer can fix. So /health tests that the app answers an HTTP request (a machine can answer a ping while its app has hung), that it has finished starting up, and that its disk isn't full.
It should not test the parts every server shares: the session store, the database, a payment provider. If the session store stalls for 15 seconds, every server fails 3 checks in a row and the balancer takes all 50 out, although no server is broken. Watch shared parts with their own alarms; some balancers also keep sending to all servers when every one looks sick.
Deploys: drain first
Stopping server 17 and letting the health checks notice repeats the crash on purpose: its 40 open requests are cut off, and about 30,000 new ones fail before it is out. Taking it out of the list and stopping it at once still cuts off the 40.
Draining fails nothing. The balancer stops sending server 17 new requests, the other 49 take them, and the open ones finish, with a limit, say 30 seconds, for any that hang. Then the server is updated, and once it passes 2 checks in a row it gets requests again.
The balancer's own machine
Every request passes through the balancer, so its machine is a single point of failure. A bigger machine still fails, and an automatic restart that takes a minute loses about 6 million requests.
The usual design is a pair: an active balancer and a standby with the same settings, sharing one address that the active one holds. The standby checks the active one every second; after a few missed answers it claims the address, and packets start reaching it. Browsers keep the same address; requests caught in those seconds are retried. Keep the two connected by more than one link, or both may claim the address at once.
Same pattern as the Key-Value Store
The Key-Value Store refused a leader that every request passes through; a balancer can't avoid being one, so it gets a partner. Its session store is a key-value store, and its hash ring is the one that placed the store's keys. Large layer 4 tiers hash each connection the same way, so all their machines agree on its server with no shared table. From Load Balancing: round robin, or least connections.
Summary
- Scope: 100,000 requests a second over 50 servers; survive crashes, deploys and its own death.
- Numbers: 2,000 a second per server; a crash costs about 30,000 requests.
- Services: a layer 7 balancer; stateless servers, sessions in a shared key-value store.
- Health checks: the server itself only; out after 3 failed, back after 2 good.
- Deploys: drain first, then update.
- Scale: an active balancer and a standby on one shared address.