Load Balancer Algorithms

Load balancing distributes incoming network traffic across a pool of backend servers. It ensures high availability, improves response time, and enables horizontal scaling. This page details the core algorithms used in load balancers—how requests are routed, what decisions are made, and what happens when things go wrong. The focus is on the mechanics of routing, not on infrastructure setup or orchestration. The reader should be able to implement, debug, and tune any of these algorithms using standard tools and protocols.

Round Robin

Round robin is the simplest load balancing algorithm: each request is assigned to the next server in a fixed list, cycling through the list on each new request.

It works over HTTP, TCP, or UDP, and is implemented in all major load balancers: nginx, HAProxy, Envoy, and AWS ELB.

Basic Configuration

In nginx, round robin is enabled by default. To configure a server group:

upstream backend {
    server 10.0.0.10:8080;
    server 10.0.0.11:8080;
    server 10.0.0.12:8080;
}

server {
    location / {
        proxy_pass http://backend;
    }
}

Each request to / is routed to 10.0.0.10, then 10.0.0.11, then 10.0.0.12, then back to 10.0.0.10, and so on.

Edge Cases and Failure Modes

• If a server is unavailable, the load balancer marks it as down and skips it during the round robin cycle.
• A server can be marked down using down keyword:

  upstream backend {
      server 10.0.0.10:8080 weight=2;
      server 10.0.0.11:8080 down;
      server 10.0.0.12:8080;
  }

• Requests are not distributed evenly when servers have different weights. A weight of 2 means the server receives twice as many requests as a weight-1 server.

Common Pitfalls

• Sticky sessions with round robin fail silently: if session data is stored on the backend server, and the load balancer sends requests to different servers without affinity, clients lose session state. A client making two requests can be served by two different servers, leading to inconsistent state.
• Backends with long-lived connections: TCP keepalive settings can cause the load balancer to believe a server is up, but the server may be overloaded or unresponsive. The load balancer does not detect the backend’s internal state.
• Server drift: if the list of servers changes during operation (e.g., new server added), the load balancer does not re-synchronize the round robin index across all nodes. Clients may receive requests from servers that were not in the pool at the time they were assigned.

Weighted Round Robin

Weighted round robin extends basic round robin by assigning a weight to each server, determining how many requests it receives per cycle.

The algorithm maintains a counter per server. Each time a request is assigned, the counter is incremented by the server’s weight. The server with the highest counter is selected, and its counter is reset to zero (or decremented by the total sum of all weights).

Implementation in HAProxy

HAProxy supports weighted round robin via the weight directive:

backend web-servers
    balance roundrobin
    server web1 10.0.0.10:8080 weight 3 maxconn 100
    server web2 10.0.0.11:8080 weight 2 maxconn 50
    server web3 10.0.0.12:8080 weight 1 maxconn 25

With this configuration:

• web1 receives 3 of every 6 requests,
• web2 receives 2,
• web3 receives 1.

Performance and Failure Modes

• If a server becomes overloaded, its maxconn limit is reached. HAProxy stops sending new connections to it, but continues to route requests to it via existing connections.
• When a server is marked as backup, it only receives traffic when all primary servers are full.

Sharp Edges

• Weight assignment is static: changes to weights require reload or reconfiguration. A dynamic adjustment (e.g., based on CPU or response time) must be implemented externally.
• Weight values are integers: fractional weights are not supported. To simulate a weight of 1.5, one must use multiple servers or a proxy layer.
• Load balancer state is not shared: in a cluster of load balancers, each node maintains its own round robin index. Requests may be distributed differently across nodes, leading to inconsistent load distribution.

Least Connections

Least connections selects the server with the fewest active connections. It is especially effective when connection durations vary significantly across backends.

Configuration

In nginx, use least_conn:

upstream backend {
    least_conn;
    server 10.0.0.10:8080;
    server 10.0.0.11:8080;
    server 10.0.0.12:8080;
}

The load balancer tracks the number of active connections per server and routes each new request to the one with the smallest count.

Key Features

• Active connection tracking: the load balancer counts established TCP connections, including those in ESTABLISHED state.
• Persistent tracking: each server maintains its connection count, which is updated on every new connection and every connection close.
• Connection aging: some implementations (like HAProxy) support conn_timeout and check directives to detect failed servers.

Failure Modes

• Slow server detection: if a server becomes unresponsive, the load balancer does not immediately detect it. The server continues to receive new requests even though it is slow or dead.
• Connection count drift: when a server is restarted, the connection count resets, but old connections may still be active. The load balancer may over-estimate the number of active connections.

Best Practices

• Combine with maxconn to avoid overloading a server:

  server 10.0.0.10:8080 maxconn 100;

• Use check to monitor server health:

  server web1 10.0.0.10:8080 check interval 5000 rise 2 fall 3

This sends a health check every 5 seconds. A server is marked up after two successful checks, down after three failures.

Least Time

Least time combines response time and connection count into a single metric: least_time(response_time, active_connections).

The algorithm selects the server with the smallest response_time + (active_connections / weight), where weight is the server’s capacity.

Implementation in Envoy

Envoy supports least time via the least_request load balancing strategy:

clusters:
  - name: backend
    type: STRICT_DNS
    lb_policy: LEAST_REQUEST
    load_assignment:
      cluster_name: backend
      endpoints:
        - lb_endpoints:
            - endpoint:
                address:
                  socket_address:
                    address: 10.0.0.10
                    port_value: 8080
            - endpoint:
                address:
                  socket_address:
                    address: 10.0.0.11
                    port_value: 8080
            - endpoint:
                address:
                  socket_address:
                    address: 10.0.0.12
                    port_value: 8080

Envoy measures:

• Time from request start to response completion (RTT),
• Number of active connections per server.

It computes the least time metric and selects the server with the smallest value.

Subtleties

• Response time measurement: Envoy uses the x-envoy-upstream-service-time header to record the time taken by the backend to process a request.
• Weighted least time: servers with higher weight receive more weight in the calculation. A server with weight 2 contributes half its active connections to the total time.
• Dynamic updates: Envoy can update server metrics in real time via gRPC or via a control plane.

Common Failure Modes

• Inaccurate RTT: if the backend does not set x-envoy-upstream-service-time, the load balancer uses a default value, leading to suboptimal routing.
• Stale metrics: a server may be updated in the backend, but the load balancer does not receive the latest metrics. The least time algorithm becomes stale.
• High variance in response times: when backends have widely varying RTTs, the load balancer may shift traffic rapidly between servers, leading to oscillation.

Random

Random load balancing selects a server uniformly at random from the pool.

It is simple to implement and works well when:

• Backend servers have similar performance,
• Request sizes are variable,
• The load balancer is stateless or distributed.

Configuration

In HAProxy, use balance random:

backend web-servers
    balance random
    server web1 10.0.0.10:8080
    server web2 10.0.0.11:8080
    server web3 10.0.0.12:8080

Each new request is assigned to a server chosen via a random number generator.

Advanced Usage

• Weighted random: servers can be assigned different probabilities:

  server web1 10.0.0.10:8080 weight 3
  server web2 10.0.0.11:8080 weight 2
  server web3 10.0.0.12:8080 weight 1

This generates a probability distribution where web1 is selected 3/6 = 50% of the time, web2 33%, web3 17%.

• Consistent hashing with random selection: to reduce the number of requests that change servers when the pool grows, use consistent hashing in conjunction with random selection.

Sharp Edges

• Random seed initialization: if the load balancer is restarted, the random number generator starts from a fixed seed. This leads to the same sequence of selections across restarts, causing predictable load distribution but also potential hot spots.
• No state retention: each request is independent. A client making multiple requests may be routed to different servers, breaking session affinity.
• Load imbalance under burst traffic: in a sudden spike, the random algorithm may assign many requests to a few servers, while others remain underutilized.

Session Affinity (Sticky Sessions)

Session affinity routes all requests from a client to the same backend server. It is implemented using:

• Client IP hashing,
• Cookie-based routing,
• Header-based routing.

Client IP Hashing

The load balancer computes a hash of the client’s IP address and uses it to select a server.

In nginx:

upstream backend {
    ip_hash;
    server 10.0.0.10:8080;
    server 10.0.0.11:8080;
    server 10.0.0.12:8080;
}

The ip_hash directive uses the first 32 bits of the client’s IP address to compute a hash, which maps to a server.

Cookie-Based Affinity

The load balancer sets a cookie on the first request and uses it on subsequent requests.

Example:

• First request: GET /api/users
• Backend returns: Set-Cookie: balancer=web1; Path=/
• Subsequent requests include: Cookie: balancer=web1

The load balancer reads the cookie and routes the request to the specified server.

Header-Based Affinity

The load balancer reads a header (e.g., X-Client-ID) and uses it as the key.

In HAProxy:

balance source
    hash-type consistent
    server web1 10.0.0.10:8080
    server web2 10.0.0.11:8080

The source algorithm uses the client’s IP as the key, and hash-type consistent improves performance when the server list changes.

Failure Modes

• IP changes: a client moving from Wi-Fi to cellular may change IP address, causing a session break.
• Cookie expiration: if the cookie expires or is cleared, the client loses affinity.
• Load balancer restart: if the load balancer uses a random seed, it may reassign clients to different servers after a restart.

Best Practices

• Combine session affinity with least connections: use ip_hash with least_conn to balance load while maintaining affinity.
• Use consistent hashing to minimize the number of reassignments when servers are added or removed.

Summary: Choosing the Right Algorithm

• Use round robin for uniform workloads and minimal configuration.
• Use weighted round robin when servers have different capacities.
• Use least connections when connection durations vary significantly.
• Use least time when response time is critical and servers differ in performance.
• Use random for simplicity and high burst tolerance.
• Use session affinity to maintain client state across requests.

No algorithm is perfect. The choice depends on the characteristics of the backend, the traffic pattern, and the tolerance for session loss.

This page was rewritten on 18 October 2026. It replaced a templated version that was not specific to its own title. How these pages are written and checked. If anything here is wrong, tell us at [email protected] and we will correct it.