When people talk about load balancing algorithms, three names come up first: Round Robin, Least Connection, Weighted Round Robin. The textbook trio. Yet the algorithm that modern LBs like Envoy and AWS ALB (Application Load Balancer) ship as their headline option — and that RPC (Remote Procedure Call) stacks like Finagle pick as their default — is none of them. It is Least Outstanding Requests, and its practical implementation is Power of Two Choices.

The shift is not simply “a faster algorithm came along.” Cloud environments — wide variance in request processing time, autoscaling that constantly reshapes the backend pool, long-lived connections on top of HTTP/2 multiplexing — broke the assumptions behind RR and LC. So the unit of routing decisions moved from connection to request.

The Routing Problem

Routing is the load balancer deciding which instance in the backend pool a request goes to. Two things are needed for that decision. A load signal — how to tell which backend is less busy. A decision cost — whether there is room to compare N backends on every request.

The unit of routing depends on the layer. An L4 load balancer routes per TCP connection. Once a connection is open, every packet on it goes to the same backend. An L7 load balancer can route per HTTP request. Two requests on the same connection can go to different backends. This difference bounds the choice of algorithm — a connection-level signal works at both L4 and L7, but a request-level signal is only possible at L7.

sequenceDiagram
    participant C as Client
    participant LB as Load Balancer
    participant A as backend A
    participant B as backend B

    Note over C,B: L4 — same connection always to the same backend
    C->>LB: TCP conn 1 (req 1)
    LB->>A: req 1
    C->>LB: TCP conn 1 (req 2)
    LB->>A: req 2

    Note over C,B: L7 — different requests on the same connection can split
    C->>LB: HTTP req 1 (stream 1)
    LB->>A: req 1
    C->>LB: HTTP req 2 (stream 3)
    LB->>B: req 2

Round Robin

The simplest routing algorithm. Cycle through the backend pool and assign in turn. First request goes to A, second to B, third to C, fourth back to A.

If the backends are equal, RR is enough. Every backend receives the same count of requests, and load evens out over time. The implementation is light and the load balancer does not have to track backend state.

When backends are not equal — say a larger instance is mixed in, or some backends run on faster machines — RR extends to Weighted Round Robin. Each backend gets a weight, and the cycle distributes proportionally. Weights of 3:1:1 send A three times, then B once, then C once.

RR rests on two assumptions. Backends are equal (WRR partly resolves this). Request processing time is uniform. The second assumption breaks easily in cloud environments.

A request that misses cache and one that hits can differ in processing time by 10x or more. Even if RR sends requests evenly, a backend that happens to receive several heavy requests in a row builds up a queue. On the next RR cycle, that backend receives a new request just the same. RR does not use the backend’s current state as a signal.

The moment a new backend is added by autoscaling is another weak spot for RR. The new backend has a cold cache and no JIT warmup, so it responds slowly for the first few minutes. RR sends it requests at the same rate, oblivious.

Least Connection

LC patches RR’s limitation — not using backend state as a signal. The load balancer tracks each backend’s current active connection count and, on a new request, picks the backend with the fewest connections.

A backend under load accumulates connections; a quieter backend’s count drops as connections close. LC reflects this difference immediately. A slow-responding backend naturally receives fewer new requests.

LC works on the premise that connection count is the load signal. In an HTTP/1.1 world this is mostly true. Since one connection processes one request at a time, connection count ≈ requests in flight.

An environment came along that broke this premise: HTTP/2 multiplexing. Dozens of streams run concurrently on a single connection. gRPC pours large numbers of RPCs over long-lived connections. In this world connection count is no longer the load signal.

graph TB
    subgraph view["What LC sees — connection count only"]
        LCa["backend A: 1 connection"]
        LCb["backend B: 1 connection"]
    end
    subgraph reality["Actual load under HTTP/2"]
        Ra["backend A — 1 conn / 50 streams"]
        Rb["backend B — 1 conn / 3 streams"]
    end
    view -->|conclusion| same["both backends look equal"]
    reality -->|actual| diff["A is about 16x busier"]

    style same fill:#FFCDD2
    style diff fill:#C8E6C9

LC has another trap. If health checking is inaccurate, a dead backend’s connection count appears as zero. LC then keeps picking that backend as the “quietest” candidate and routes new requests to it. In cloud environments, backends drop into a dead state quickly — instance termination, network partitions, OOMs — and a long health-check interval stretches the window in which LC picks wrong.

Least Outstanding Requests

LOR addresses both of LC’s limitations. It moves the unit of the routing signal from connection to outstanding request — an in-flight request still waiting for a response.

LOR tracks the count of currently processing requests per backend. On a new request, it picks the backend with the fewest outstanding. The signal stays accurate even on HTTP/2 multiplexing — a backend with 1 connection but 50 outstanding is busy. A dead backend either accumulates outstanding (responses stop returning) or gets removed from the pool by a circuit breaker.

The signal itself is one step more precise than LC. But LOR carries a cost. Every request has to compare the outstanding values across N backends. With 100 backends, every decision walks 100 entries. Decision cost grows linearly with the pool size.

The cost is negligible for small pools, but in microservice environments, where a service’s backend count reaches the tens to hundreds, it stops being negligible.

Power of Two Choices

P2C is the variant that almost preserves LOR’s accuracy while dropping decision cost to O(1). The algorithm is short. Pick two random backends from the pool and send the request to the one with fewer outstanding.

flowchart TD
    Start["new request arrives"] --> Pick["pick 2 random backends from the pool"]
    Pool["backend pool (N)"] -.->|look at only 2| Pick
    Pick --> Compare["choose the one with fewer outstanding"]
    Compare --> Done["route the request"]

    style Pick fill:#FFF3E0
    style Compare fill:#C8E6C9

Intuitively one might worry: “isn’t it inaccurate to skip finding the global minimum?” Mitzenmacher’s analysis (2001) pushes back. The worst-case load under purely random routing — the largest count among backends — grows roughly as log N. With just two comparisons per decision, that worst case shrinks to log log N. So jumping from 1 to 2 random picks is an exponential improvement, and going further from 2 to N adds little.

That result made P2C a “good enough approximation” of LOR. The comparison cost is always 2, independent of pool size — whether the pool holds 100 backends or 1000, the decision cost stays the same. Envoy’s LEAST_REQUEST policy is exactly P2C (the number of random hosts to pick defaults to 2), and AWS ALB’s least_outstanding_requests option, gRPC’s weighted_round_robin policy, and Finagle’s default are all variants of the same family.

The Unit of the Load Signal

The evolution of routing algorithms is the story of the load signal’s unit shrinking. RR has no unit — it does not look at backend state at all. LC’s unit is connection. LOR’s unit is request. P2C keeps the same unit (request) and brings down the decision cost.

Modern LBs picked up P2C as the headline option not because a faster algorithm arrived. Cloud environments — HTTP/2 multiplexing, autoscaling, inaccurate health checks, wide variance in request time — made connection unusable as a load signal. The unit had to drop from connection to request, and P2C made that drop practical.