Design a load balancer

01 · CONTEXT AND REQUIREMENTS

What a load balancer needs to do

Um load balancer accepts incoming traffic from clients and forwards it to registered targets, such as server instances, in one or more availability zones. It also monitors the health of the targets: when it detects an unhealthy target, it stops routing traffic to it and only resumes when it detects that the target is healthy again.

The load balancer receives connections through listeners. A listener is a process that checks for connection requests, configured with a protocol and port for connections coming from clients.

For an interview, the functional requirements boil down to distributing requests among several servers, stopping traffic to servers with problems, and allowing servers to be added or removed. The non-functional ones that drive the design are high availability, including that of the load balancer itself, even load distribution, and little added latency.

1. Clients send requests to the load balancer, which receives them through a listener.

2. The load balancer node selects a healthy registered target and forwards the request to it.

3. The load balancer also periodically sends test requests to the registered targets; these are the health checks.

4. When a target fails the checks beyond the configured threshold, the load balancer takes it out of service and stops routing traffic to it.

5. After consecutive successes above the configured threshold, the load balancer returns the target to service.

02 · PICKING THE SERVER

Distribution algorithms

With the healthy servers identified, what remains is deciding which one receives each request. The NGINX documentation, which does application-layer load balancing for HTTP and HTTPS traffic, lists five methods in the open source edition: round robin, least connections, least time, IP hash, and generic hash.

Round robin, least connections, and random distribute requests according to server weights. A server marked as backup does not receive requests unless the others are unavailable.

In the AWS Application Load Balancer, the algorithm is a property of the target group and can be round_robin, least_outstanding_requests, or weighted_random. The default is round robin, and routing is done independently for each target group.

03 · HEALTH AND ZONES

Target health and availability zones

The health check keeps the load balancer from sending traffic to a broken target. On AWS, each load balancer node routes requests only to the healthy targets in the enabled zones, and the state comes from test requests sent periodically. After consecutive failures above the configured threshold the target goes out of service; after consecutive successes above the threshold, it comes back.

NGINX Plus offers slow start, which keeps a freshly recovered server from being overwhelmed by connections: the server gradually recovers its weight, from zero up to the nominal value. The documentation says this feature is only available in NGINX Plus.

Each availability zone enabled gets a load balancer node. AWS recommends enabling several zones on every load balancer and, on the Application Load Balancer, requires two or more. That way, if a zone becomes unavailable or has no healthy targets, the load balancer can route traffic to healthy targets in another zone.

1. The client resolves the load balancer's name; the DNS server returns one or more IP addresses, which are those of the load balancer nodes.

2. Each enabled zone has its own load balancer node.

3. With cross-zone off, each node distributes traffic only among the targets in its own zone.

4. With cross-zone on, each node distributes traffic among the registered targets of all enabled zones.

5. If zone A becomes unavailable or has no healthy targets, the load balancer can route traffic to healthy targets in another zone.

Cross-zone load balancing defines the scope of each node: on, the node distributes traffic among the targets of all enabled zones; off, only among the targets of its own zone. On the Application Load Balancer it is always on at the load balancer level.

In the documentation's example there are two enabled zones, with two targets in zone A and eight in zone B; with round robin, each load balancer node receives half of the client traffic.

04 · THE LOAD BALANCER FAILS TOO

Scaling without a single point of failure

A single load balancer would itself be a single point of failure and a capacity limit. That is why it is worth looking at how a large-scale load balancer replicates itself.

Maglev, Google's network load balancer described in a technical paper, is a distributed software system that runs on commodity servers, and its capacity is easily adjusted by adding or removing servers. Network routers distribute packets evenly among the Maglev machines via ECMP, short for equal-cost multipath.

Each service has one or more virtual IP addresses (VIPs), different from a physical IP: a VIP is served by several service endpoints behind Maglev. DNS assigns the user to a nearby frontend location and returns a VIP of that location.

1. The browser queries DNS, which assigns it to a nearby frontend location and returns a VIP of that location.

2. Packets for the VIP arrive at the router, which forwards them to one of the cluster's Maglev machines via ECMP.

3. The Maglev machine checks the connection table; if there is no usable entry, it consults the consistent hash and picks a new backend.

4. The packet is encapsulated with GRE and sent to the chosen endpoint; the response is sent directly to the router, so Maglev does not need to handle return packets.

5. During an update, machines are restarted in sequence with traffic drained beforehand; ECMP reshuffles traffic and connections move to other machines midstream, where the connection table entries are not correct.

6. Thanks to the consistent hash's minimal disruption property, the connection most likely keeps going to the same backend as before.

Choosing the endpoint depends on one requirement: the system must guarantee connection persistence, that is, packets of the same connection must always go to the same endpoint. Maglev stores the backend choice for recent connections in a connection table and, if there is an entry and the backend is still healthy, reuses the result.

The table alone is not enough, for two reasons pointed out in the paper. Local tracking assumes that all packets with the same five-tuple are always sent to the same Maglev machine, which stops holding when the set of machines changes; in a cluster update, for example, machines are restarted in sequence. In addition, the table has finite space and can fill up under high load or a SYN flood attack.

The second defense is local consistent hashing. Sharing connection state among all machines would be a possible approach, but it would hurt forwarding performance, and the paper prefers a local solution. Among the desired properties are load balancing, in which each backend receives a nearly equal number of connections, and minimal disruption, in which a connection likely keeps going to the same backend when the set changes.

05 · LAYERS AND WRAP-UP

Packet or request: where the load balancer decides

AWS shows two ways to decide. In the Application Load Balancer, the node evaluates the listener rules in priority order and the default algorithm is round robin. In the Network Load Balancer, the node picks the target using a flow hash algorithm and routes each TCP connection to a single target for the whole lifetime of the connection.

Two examples use a hash to pick the destination. NGINX's IP hash picks the server from the client's IP address and guarantees the same server for the same address, unless it is unavailable. The Network Load Balancer's flow hash uses, among other fields, the source IP and port.

To close an interview, put the pieces together: DNS returns the addresses of the nodes, the nodes sit in more than one zone, each node picks only among healthy targets, the algorithm depends on the type of traffic, and the load balancer layer is replicated so it does not become a single point of failure.