Load balancer simulator

Requests arrive at random moments at the chosen rate, and each needs a random amount of work, as in most real services where some requests are quick and some are slow. All four load balancers see exactly the same requests; only the choice of server differs. The table beside the panels shows the median and 99th-percentile response times over the last ten seconds, which is the part of the picture users notice.

Try these:

• At 80% traffic with all servers normal, compare the 99th percentiles. Round robin and random leave some servers with queues while others are idle; the two algorithms that look at load keep queues short.
• Press Make S3 three times slower. Round robin and random keep sending S3 a quarter of the requests, more than it can handle, so its queue grows without limit and the 99th percentile climbs. Least connections and power of two choices send S3 far fewer requests.
• Press Stop S4, first with health checks on, then off. With them on, a few requests fail before S4 is removed. With them off, failures continue, and least connections sends a large share of all traffic to the stopped server.
• Raise traffic to 95%. Near full capacity, small imbalances turn into long queues, and the differences between the algorithms grow.

The simulation runs in real time and keeps every request, so the response times are measured, not modelled. Because arrivals are random (Poisson) and work per request is exponentially distributed, the healthy case can be checked against queueing theory. With Random, each server behaves as an M/M/4 queue, whose average response time Erlang's C formula gives exactly; no balancer can beat one shared queue feeding all 16 workers (M/M/16). In 1,000-second test runs of this code, Random landed within about 2% of its formula at every load below, and least connections stayed just above the shared-queue figure.

These are averages; the panel shows the median and 99th percentile, so its numbers differ, but the ordering holds: the gap between random placement and a shared queue widens sharply as traffic approaches capacity.

Load balancing is the spreading of incoming work, such as HTTP requests or network connections, across a group of servers that can each do it. The component that does this, a load balancer, sits between clients and the servers: clients connect to one address, and the load balancer forwards each request or connection to one of the servers behind it.

Load balancing serves two purposes. It lets a service handle more traffic than one machine can, by adding servers. And it keeps the service up when servers fail or are taken out for maintenance, because the load balancer stops sending traffic to servers that are not healthy.

A load balancer has to decide, for each request, which server gets it. That choice matters most when servers or requests are not all alike, which in practice they rarely are.

Round robin

Servers take turns: the first request goes to server 1, the next to server 2, and so on, starting again after the last. It needs no information about the servers and spreads the number of requests evenly. It does not spread the work evenly if requests differ in cost or servers differ in speed. Weighted round robin gives larger servers more turns.

Random

Each request goes to a server chosen at random. Over many requests the spread is even, but over short periods some servers get noticeably more than others. Its advantage is that many independent load balancers can use it without coordinating.

Least connections

Each request goes to the server with the fewest requests or connections in progress. Because a slow server finishes requests slowly, it keeps more in progress and automatically receives less new work. A known weakness is a server that fails requests instantly: it always looks idle and attracts more traffic, which the simulator shows when S4 is stopped without health checks. Variants weight the count by server capacity, or choose by measured response time.

Hashing

The server is chosen from a hash of something in the request, such as the client's IP address or a session ID, so the same client keeps reaching the same server. Plain hash mod N moves most clients when a server is added or removed, so load balancers use consistent hashing or Google's Maglev hashing instead. Hashing is used for caches and sessions, not to even out load.

Always picking the least loaded server needs up-to-date load figures for every server, and when several load balancers do it independently they can all pick the same quiet server at once and overload it. The power of two choices avoids both problems: pick two servers at random, then send the request to the less loaded of the two.

The result is surprisingly strong. In the classic analysis of placing n balls into n bins, choosing one bin at random gives a fullest bin of about ln n / ln ln n balls, while choosing the emptier of two random bins gives about ln ln n / ln 2, an exponential improvement. Going from two choices to three adds little. Yossi Azar, Andrei Broder, Anna Karlin and Eli Upfal published this result in 1994, and Michael Mitzenmacher's 1996 PhD thesis analysed it for load balancing over time.

Envoy's least-request algorithm and HAProxy's random algorithm with two draws use this idea, and it works well with many independent load balancers sharing the same servers.

A load balancer needs to know which servers can take traffic. Active health checks send each server a test request, such as a TCP connection or an HTTP request to a path like /health, at a fixed interval. A server that fails a set number of checks in a row is removed from rotation and returns after passing a set number. Passive health checks, also called outlier detection, watch real traffic instead and remove a server that returns too many errors.

The settings are a trade-off. Checking often and removing after one failure reacts fast, but can remove a healthy server that was briefly slow. Checking rarely means clients see errors for longer after a real failure; the simulator removes a server after two failed checks one second apart. A health check endpoint should test what the server needs to serve traffic, but checking shared dependencies such as the database from every server can take all of them out of rotation at once when that dependency has a problem.

When a server is taken out deliberately, for example during a deployment, the load balancer stops sending it new requests but lets requests in progress finish. This is called connection draining.

Load balancers are often described by the layer of the network model they work at.

• A layer 4 load balancer works with TCP connections or UDP packets. It chooses a server when a connection opens, then forwards its packets without reading the contents. It is fast and works with any protocol, but every request on a long-lived connection goes to the same server.
• A layer 7 load balancer understands the application protocol, usually HTTP. It ends the client's connection, reads each request, and can choose a server for each request based on its path, host name, headers or cookies. It can also terminate TLS, retry failed requests, add headers and compress responses. This costs more processing per request.

HTTP/2 and gRPC send many requests over one long-lived connection, so a layer 4 load balancer can leave one server with most of the traffic. Balancing them evenly needs a layer 7 load balancer, or clients that open connections to several servers.

Some applications keep data about a user in a server's memory, so later requests from that user must reach the same server. Session affinity, or sticky sessions, does this by hashing the client's address or by setting a cookie that names the server. It has costs: load is spread less evenly, and when a server fails its users lose their sessions. Many services avoid the need by keeping session data in a shared store such as Redis.

A service that runs in several regions also has to choose a region for each user. DNS-based load balancing returns different IP addresses to different users, usually the nearest healthy region. Anycast advertises the same IP address from many locations, and internet routing delivers each user's packets to the nearest one; CDNs and Google's front ends work this way. Inside each region, an ordinary load balancer then spreads traffic across servers.

Early web sites spread load with round-robin DNS, giving out the addresses of several servers in rotation; it is simple but cannot react to failures, because clients and resolvers cache the answers. Dedicated hardware load balancers appeared in the late 1990s, such as F5 Networks' BIG-IP in 1997. The open-source Linux Virtual Server project, started by Wensong Zhang in 1998, brought layer 4 balancing into the Linux kernel as IPVS.

Software layer 7 load balancers followed: HAProxy, written by Willy Tarreau and first released in 2001, and NGINX, first released by Igor Sysoev in 2004. Large services later built their own: Google described Maglev, its software network load balancer, in 2016, the year Lyft released Envoy as open source. Cloud providers now offer load balancing as a managed service.