Least Connections

The load balancer keeps count of how many requests each server is still working on, and sends each new request to the server with the fewest. Unlike round robin, it reacts to what the servers are doing. Below, switch between least connections and round robin on the same traffic and see where they differ.

Users463 req/sLoad balancerleast connections1234last sent toServer 1Server 2Server 3Server 4

Each server drawn stands for one of your servers, and each dot for 100 real requests. Only the speed is slowed, so you can follow single requests. "In progress" under the balancer is what least connections compares: requests sent to each server and not yet answered. Switching the algorithm restarts the run with the same traffic.

Sizing the fleet
x average

Busiest hour vs the daily average. The book's estimate uses 2x.

req/s

Measured by load testing one server until it cannot go faster.

% busy

Headroom for spikes, slow requests and a failed server. 50 to 70% is common.

x planned peak

  1. 1. Average requests per second

    DAU x requests per user per day / 86,400
    = 1,000,000 x 50 / 86,400 = 579 req/s

  2. 2. Peak requests per second

    average x peak factor = 579 x 2 = 1,157 req/s

  3. 3. Servers needed n

    n = peak / (one server x target load) = 1,157 / (200 x 60%), rounded up = 10

  4. 4. Load on each server

    traffic now / (n x one server) = 58%
    With identical servers and requests, both algorithms give every server this load.

  5. 5. One server half as fast

    round robin still gives it 1/n: load / 0.5 = 116%
    least connections moves work away from it; a perfect split would give every server load x n / (n - 0.5) = 61%. In practice it gets close, with the slow server somewhat busier.

  6. 6. About one request in five taking 4x as long

    both: load x 1.6 = 93% on average. Least connections steers new requests away from servers stuck on heavy ones, which lowers the average response; the worst cases improve less.

  7. 7. One server fails

    the rest share its traffic: load x n / (n - 1) = 64%
  8. Least connections cannot create capacity, but it uses what there is: a slow server costs the fleet about half a server, instead of becoming one overloaded server. Any value in red above is over 100%.
Where these formulas come from

Steps 1 and 2 are the estimation method from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1, including its 2x peak. The rest is standard capacity planning. The perfect split in step 5 is the same traffic spread over n - 1 full servers and one half server. Least connections only approaches it, because it evens out requests in progress, not how busy each server is.

Limits of least connections

Errors look like free capacity

A server that fails requests at once never has any in progress, so least connections keeps choosing it. Set Server 4 to Errors with health checks off. The fix is to take failing servers out, with health checks or by counting errors.

A new server gets flooded

A server that has just started has nothing in progress, so it gets every new request until it catches up, often while its caches are still cold. Slow start, where a new server's share ramps up over time, exists for this; AWS notes it cannot be combined with its least outstanding requests algorithm.

It counts requests, not their cost

Two cheap requests and two expensive ones count the same until they finish. It still adapts, because expensive requests stay in progress longer, but only after the fact.

Each balancer sees only its own requests

With several load balancers in front of the same servers, each one counts only the requests it sent. They can all pick the same quiet server at once. Picking the better of two random servers (Power of Two Choices, later in this list) copes with that well.

How NGINX and AWS use least connections

Both offer it as an alternative to their round robin default, for traffic where requests differ.

NGINX: least_conn

With least_conn in an upstream block, "a request is passed to the server with the least number of active connections, taking into account weights of servers." On ties: "If there are several such servers, they are tried in turn using a weighted round-robin balancing method." Its load balancing guide gives the reason to use it: it is fairer "in a situation when some of the requests take longer to complete."

AWS: least outstanding requests

An Application Load Balancer target group can use the least outstanding requests algorithm, which "routes requests to the targets with the lowest number of in progress requests." AWS describes it as commonly used when requests "vary in complexity" or targets "vary in processing capability". It "can not be used with slow start mode", which is the new-server problem above.
Sources and credibility

Both are the vendors' own documentation (primary sources). Quoted phrases are short attributed quotations; everything else is described in our words. Check the pages for current behaviour.