# Load balancing algorithms: which server gets your request? URL: https://systemdesignsimple.com/which-server-gets-your-request/ Published: 2026-11-05 Category: System Design Series: System Design, simply, Part 16: Load balancing algorithms: round robin, least conn, hash Publisher: System Design Simple (https://systemdesignsimple.com) ## Short answer A load balancer picks a server per request: take turns (round robin), fewest unfinished requests (least connections), or a hash of a key such as the user ID. With mixed request costs, least connections keeps quick requests quick. In our one-machine simulation with 10.25% of requests slow, quick requests had a p99 of 150.3 ms (round robin), 22 ms (least connections) and 468.9 ms (user-ID hash). ## Key facts - **Quick-request p99, our simulation:** Round robin 150.3 ms, least connections 22 ms, user-ID hash 468.9 ms, for requests that needed only 20 ms of work - **Overall p99, same runs:** Round robin 408.1 ms, least connections 400 ms, user-ID hash 523.1 ms; the overall p99 is a slow 400 ms request, so it hides most of the difference - **Peak queue on any server:** Round robin 24, least connections 2, user-ID hash 71 - **Hot server under hashing:** The busiest server got 32.7% of requests against a fair 25% share, an offered load of 86.8% while the average was 66.2% - **Skewed users:** 2,000 users with Zipf s = 1 traffic: the top user sent 12.1% of all requests, the top 10 users 35.9% - **Control run:** Same arrivals, every request 20 ms, 22.5% load: all three rules had a p99 of 20 ms; hashing still sent 32.7% to one server, at only 29.4% load - **Setup:** Our discrete event simulation (labs/sd-16), seed 16, 4 servers x 8 slots, 20,000 Poisson arrivals, 10% target slow at 400 ms (10.25% realized), else 20 ms, 66.2% realized load. Chosen numbers, not a measurement of any real system Load balancing algorithms determine which server handles each request, and that choice decides whether a quick request finishes in 20 ms or waits behind slow work for hundreds of milliseconds. The rule that looks fair (take turns) and the rule that looks smart (keep each user on one server) can both build long queues once request costs differ or traffic is skewed. In an interview: round robin, least connections or hashing, which would you use, and why? ## Prerequisites {#prerequisites} **What a load balancer is.** It sits in front of several equivalent servers and decides which one handles each request or connection. Part 15, [load balancer vs reverse proxy](/load-balancer-vs-reverse-proxy/), covers where it sits and layer 4 vs layer 7. This part covers the choice of server. **Utilisation and queues.** A server whose 8 slots are busy 5.3 at a time on average is 66% utilised. Queues still form whenever requests bunch up, and waiting grows much faster than load near 100%. We built that intuition in [fast for you, slow for a million](/fast-alone-slow-crowded/) and in [50K fans, 5K seats](/50k-fans-5k-seats/), where the rule of thumb was to keep busy resources near 70%. **Percentiles.** The p99 latency is the time within which 99% of requests finished. A page that makes many backend calls is as slow as its slowest call, so the tail matters. [Ten lanes can still be slow](/ten-lanes-still-slow/) separates latency from throughput. Our simulation holds offered traffic fixed and drains every request, so it compares latency only. In production, placement can change sustainable throughput as well as latency: a rule that saturates one server while others idle caps what the pool can serve before timeouts and retries start. ## Definitions {#definitions} > Definition: **Load balancing algorithm**: the rule a load balancer uses to choose a server (an upstream, or backend) for each new request or connection. > Definition: **Round robin**: send each new request to the next server in a fixed cycle, 1, 2, 3, 4, 1, and so on, without looking at how busy any server is. **Weighted round robin** gives a server with weight 2 twice as many turns. > Definition: **Least connections**: send each new request to the server with the fewest open connections or unfinished requests at that moment, usually adjusted by weight. In our simulation it means the fewest running plus queued requests. > Definition: **Power of two choices**: pick two servers at random and send the request to the less loaded one. It gets most of the benefit of least connections without comparing every server. > Definition: **Hash-based balancing**: hash a key from the request (client IP, user ID, URL) and map it to a server, so the same key lands on the same server while the pool stays the same. > Definition: **Consistent hashing**: a key to server mapping, usually a ring, where adding or removing one of N servers moves only about 1/N of the keys. > Definition: **Sticky session** (session affinity): keeping a client on the server it used before, by hashing or by a cookie that names the server. > Definition: **Head-of-line blocking**: a quick request waiting because slow requests ahead of it hold the resource. It shows up as tail latency, the latency of the slowest requests. ## How load balancing algorithms pick a server {#how-it-works} [Image: A rule card above a small load balancer box lists three ways to pick a server: round robin, least connections and user-ID hash, each with a run marker underneath, and an empty results board headed p99 quick requests sits top right | Three rules, one request stream: take turns, least busy, or hash your user ID.] Every rule answers the same question with different information. The less it looks at, the cheaper it is, and the more it can be wrong about the present. **Round robin** keeps one counter: request n goes to server n mod N. It is perfectly fair in count and blind to cost, so a server stuck on four heavy reports still gets its turn. NGINX uses weighted round robin by default and spreads turns smoothly (A, B, A rather than A, A, B). HAProxy's `roundrobin` allows weights to change at run time; `static-rr` is a cheaper fixed version. Weights correct for unequal hardware; they do nothing about requests of unequal cost. **Least connections** reads live state. For each new request it compares a counter per server and picks the lowest, breaking ties in turn. The counter rises when work starts and falls when it finishes, so a server holding slow work looks busy and is skipped. **Power of two choices.** With hundreds of servers and several balancer copies, counts are partial and change between reads. Sampling two random servers and taking the lighter one shrinks the worst server's excess load far below what one random choice gives, and it avoids herding, where every copy sees the same "least loaded" server and floods it. Envoy's least request balancer uses two random choices by default when weights are equal; NGINX has `random two least_conn` and HAProxy has `random(2)`. **Hashing.** The balancer computes `hash(key) mod N`. With `ip_hash` the key is the client address; with `hash $arg_user` a query argument; HAProxy's `balance uri`, `url_param` or `hdr(...)` use the path, a parameter or a header. No shared state is needed, and every balancer copy gives the same answer. The weak point is `mod N`: from 4 to 5 servers, a key keeps its server only if its hash has the same remainder mod 4 and mod 5, about 1 in 5, so about 80% of keys move. **Consistent hashing** fixes that. Each server sits at many points on a ring of hash values (virtual nodes), and a key goes to the first server point clockwise from its hash. A fifth server takes over only the arcs just before its points, about 1/5 of the keys. NGINX's `hash ... consistent` uses the ketama method; HAProxy has `hash-type consistent`; Envoy offers ring hash and Maglev, a table-based variant with a more even spread. **Sticky sessions** name a goal rather than an algorithm. You get them with a hash of something stable about the client, or with a cookie the balancer sets (HAProxy's `cookie`). ## Why does round robin build queues when requests differ? {#round-robin-queues} [Image: A latency ruler for quick requests with most dots bunched near 20 ms and a thin tail to the right, a bracket marking p99, and below it a load balancer dealing envelopes 1, 2, 3, 4 while two server cards have most of their 8 slots filled by heavy envelopes and small envelopes stack in a queue lane | Round robin deals in turn; when a server's slots are full of slow work, the quick requests it is dealt wait in its queue.] By count, round robin is even. In our mixed run every server got exactly 25% of requests, with offered loads of 68.2%, 66.3%, 66.5% and 64%. The amount of slow work on each server at any instant is random, though, and round robin never looks at it. Take one server. It receives a quarter of 359.6 requests per second, about 89.9. About 10.25% are slow, roughly 9.2 per second, each holding a slot for 400 ms. By Little's law (L = λW: items in the system equal arrival rate times time inside), the average number of slow requests in service is 9.2 × 0.4 ≈ 3.7. That count fluctuates. In an infinite-server approximation (no 8-slot cap, quick requests ignored, so the count is Poisson with mean 3.7), the chance of 8 or more slow requests at once is about 3.5%. That is not the simulator's measured probability: the real server has only 8 slots, quick requests occupy slots too, and queued slow requests stretch busy periods. It shows only that bursts of slow work big enough to fill a whole server happen regularly. Whenever a server's slots are full, every quick request round robin hands it waits in its queue, while other servers often have free slots; the peak queue of 24 below shows that this happened. That is head-of-line blocking, and it lives in the tail of the quick requests. Most quick requests land on a free slot, so the median stayed at 20 ms for all three rules. The unlucky few percent land behind a wall of slow work. Round robin's quick-request p99 was 150.3 ms, 7.5 times the 20 ms of real work, and its peak queue on one server was 24. Load makes this worse non-linearly. In the M/M/1 model mean time in the system is the service time divided by (1 minus ρ): from 50% to 75% load it doubles, and at 90% it is ten times the service time. Round robin splits one pool of 32 slots into four pools of 8, and separate queues wait longer than one shared queue at the same load. ### Why least connections fixes it [Image: Four server cards each carry a small counter labelled demo counter running plus queued requests; the counters show different values and the load balancer steers small envelopes around the cards whose slots are full, so every queue lane stays nearly empty | Least connections reads a counter per server and sends the request to the lowest one.] Least connections reads the counters at decision time. A server with 8 slow requests running counts 8; one with 3 running counts 3, and the new request goes there. With about 21 of 32 slots busy on average, some server almost always has a free slot, and the rule finds it. That makes the four servers behave much like one shared pool. Peak queue was 2 and the quick-request p99 22 ms, 2 ms above the work itself. It barely changed the overall p99: 400 ms for least connections, 408.1 ms for round robin, 523.1 ms for hashing. With 10.25% of requests slow, the overall p99 is a slow request whose work alone is 400 ms, so round robin looks nearly as good on that metric. Split by request type or endpoint and the gap is 150.3 ms vs 22 ms, which is why the video's board reads "p99 · quick requests". ## Why does hashing by user ID create a hot server? {#hash-hot-server} [Image: Phones in a crowd are tied by strings to server cards; one card marked busiest server has a thick string, a queue lane stretching to the bottom labelled peak queue 71 requests, and a bar filled to 32.7% beside a dotted fair share mark at 25% | Hashing pins each user to one server; the server that drew the heaviest users got 32.7% of requests.] A good hash spreads keys evenly, giving each of 4 servers about 500 of 2,000 users. Traffic does not spread the same way, because users are not equal: a busy shop account or a polling integration sends far more than a typical user. We modelled that with a Zipf distribution, s = 1: the user at rank k sends traffic proportional to 1/k, so the top user's share is 1 divided by the harmonic number H(2000). ```text H(2000) = 1 + 1/2 + 1/3 + ... + 1/2000 ≈ ln(2000) + 0.5772 ≈ 8.178 expected share of rank 1 = 1 / 8.178 ≈ 12.2% (measured 12.1%) expected share of ranks 1..10 = (1 + ... + 1/10) / 8.178 = 2.929 / 8.178 ≈ 35.8% (measured 35.9%) ``` Whichever server gets the top user starts with 12.1% of all requests from that one user, nearly half a fair 25% share, before anyone else is counted. In our seed the hash (FNV-1a of "user-" plus the ID, mod 4) also put users 5, 9 and 10 there. These four users contribute about 17.25% of expected traffic: (1 + 1/5 + 1/9 + 1/10) / 8.178 = 1.411 / 8.178. The exact mapping of all other users determines the remainder; this run measured 32.7%. Turned into load, 32.7% of 359.6 requests per second is about 117.6 per second; at an average 58.95 ms of work (10.25% at 400 ms, the rest at 20 ms) that is 117.6 × 0.05895 ≈ 6.93 busy slots of 8, about 86.6%. The simulation measured 86.8%, while the other servers ran at 66.4%, 56% and 55.7%. The cluster had spare capacity overall and one server near saturation, and on the queueing curve 86.8% is far worse than 66%. Its peak queue reached 71, and the quick-request p99 under hashing was 468.9 ms, more than the 400 ms work of a slow request. A heavy user is an indivisible chunk of traffic, though not by itself an overload. The top user alone needs 359.6 × 0.121 × 0.05895 / 8 ≈ 32.1% of one server's capacity; the other users mapped alongside it decide whether that server approaches saturation. A different hash may improve this placement, but no hash can guarantee balance under skew, and the rule cannot react to 71 queued requests. The fixes are structural: hash a finer key (session, cart, room) instead of the account, or route known heavy keys to their own pool. **Bounded loads trade affinity for balance.** Consistent hashing with bounded loads (HAProxy `hash-balance-factor`, Envoy's `hash_balance_factor`) sets an admission threshold relative to the average number of concurrent requests. With 125, the target is about 1.25 times the mean in-flight count as this balancer observes it, weight-adjusted, and it is a target rather than a hard limit: [HAProxy's implementation](https://github.com/haproxy/haproxy/blob/v2.8.0/src/lb_chash.c) counts outstanding requests including the incoming one, rounds each server's allowance to whole slots, and always allows at least one slot per server, and several independent balancers each see only their own traffic, with no global count. When the preferred server is at or over its threshold, HAProxy redirects the request to the next eligible server on the ring, including requests for keys that already live on the busy server. That redirects requests, potentially breaking affinity. It is safe for a replicated cache or when state sits in a shared store, because a redirected request costs a cache miss, not an error. It is unsafe for a single-owner room or shard, where the request would reach a server without the state; those need an owner lookup, forwarding to the owner, or explicit state migration. ## What do NGINX and HAProxy actually count? {#real-balancers} Our least connections is idealized: one balancer with an exact, instant count of running plus queued requests on every server. Real balancers count something close to that. **NGINX `least_conn`** passes a request to the server with the least number of active connections, taking weights into account, with weighted round robin among ties. Without a `zone` directive each worker process keeps its own counters, so with 8 workers each sees only its own share; `zone` puts the group's run-time state in shared memory. The method must also appear before `keepalive` in the upstream block. The commercial NGINX Plus adds `least_time`, which also weighs response time. **HAProxy `leastconn`** (2.8 manual) gives the connection to the server with the lowest number of connections, performs round robin within groups of servers at the same load, and is dynamic, so weights can change at run time and slow start applies. The manual recommends it for very long sessions such as LDAP, SQL or TSE and says it is not very well suited to short-session protocols such as HTTP. The count it compares is the streams a server is currently serving (the `scur` column on the stats page), divided by weight, so idle server connections kept for reuse do not add to it. **Many copies, multiplexed connections.** Each of your two or more balancers counts only what it sent, so they can all pick the same lightly loaded server at once; randomized two choices helps. With HTTP/2 or gRPC one connection carries many requests, so a layer 4 balancer that picks per connection can pin most work to a few servers; a layer 7 balancer picks per request. ### Inside the balancer: selection cost, counters and weights Each pick runs on every request, so its cost and the counter it reads matter at scale. | Implementation | Data structure | Cost per pick | What it reads | | --- | --- | --- | --- | | NGINX weighted round robin | Linked peer records with current and effective weight (smooth WRR) | O(N): add each weight, take the max, subtract the total | Configured/current/effective weights plus peer eligibility (down, `max_fails`, `max_conns`) | | NGINX `least_conn` | Same peer list plus a `conns` counter per peer | O(N) scan, compares conns / weight by cross multiplication | Active connections, per worker unless `zone` | | HAProxy `leastconn` | Elastic binary tree keyed by served streams / weight | O(log N) to take the lightest and requeue it | Streams being served | | Envoy least request, equal weights | Host list, P2C | O(1): two random hosts, keep the one with fewer active requests | Active requests from this Envoy | | Envoy least request, unequal weights | Earliest deadline first scheduler | O(log N) | Weight and active requests | | NGINX `hash ... consistent` | Sorted ketama ring, 160 points per weight unit | O(log P) ring search plus O(N) peer scan on the normal path; unavailable candidates can require further scans. 4 servers = 640 points, about 10 comparisons for the search | Key only | | Envoy Maglev | Lookup table, default size 65,537 (prime) | O(1): one index by hash mod 65,537 | Key only | **Envoy's two modes, with numbers.** With equal weights, Envoy's least request balancer samples two hosts (the `choice_count` default) and takes the one with fewer active requests. With unequal weights it switches to weighted round robin whose weights are recomputed per pick as `weight / (active_requests + 1)^active_request_bias`, bias 1.0 by default. Host A with weight 2 and 3 active requests gets 2 / 4 = 0.5; host B with weight 1 and 0 active gets 1 / 1 = 1.0, so at that moment B receives about twice A's share despite half the weight. With bias 0 the formula reduces to plain weighted round robin; a bias above 1 punishes in-flight work harder. **Ring vs table.** A ketama ring for 4 servers holds 640 points, each a 32-bit hash plus a server reference: around 10 KB. A lookup is an O(log P) binary search of the ring, then, in the [NGINX implementation](https://github.com/nginx/nginx/blob/master/src/http/modules/ngx_http_upstream_hash_module.c), an O(N) scan of the peer list to find the eligible peer matching the selected server; if that peer is down or failed, NGINX moves to the next ring point and scans again. Envoy's ring hash defaults to at least 1,024 entries and can grow to millions for a finer spread, which grows both memory and build time. Maglev fills a fixed 65,537-entry table, roughly 0.5 MB at 8 bytes per host reference, and looks up in constant time. Envoy's documentation reports Maglev at about 10 times faster table build and 5 times faster host selection than a 256K-entry ring, at the cost of stability: about twice as many keys move when a host is removed. **Detecting imbalance and queueing.** Average utilisation hides both problems, so watch per-server numbers: - **Imbalance ratio:** busiest server's in-flight count or offered load divided by the mean. In our runs it was 68.2 / 66.2 = 1.03 for round robin and 86.8 / 66.2 = 1.31 for user-ID hashing. Sources: HAProxy `scur` per server, Envoy `rq_active` per host on the admin `/clusters` page, NGINX access logs grouped by `$upstream_addr` (open-source NGINX has no live per-peer counter). - **Queueing at the balancer:** HAProxy `qcur` and `qmax` per server and the `Tw` timer (time waiting in queues) in its logs. A rising `Tw` on one server is the hot server signature. - **Queueing in the server:** the balancer only sees `$upstream_response_time`, so have the application record time from accept to start of work per request; queue wait growing while service time stays flat means placement, not slow code. - **Per-endpoint p99:** split quick and slow endpoints, as in this article; the overall p99 hid a 150.3 vs 22 ms gap. ### Health checks and slow start Every rule picks only among servers believed healthy, so the health check decides the pool before the algorithm runs. **Passive checks** watch real traffic: in open-source NGINX, `max_fails` failures within `fail_timeout` (defaults 1 and 10 seconds) take a server out for `fail_timeout`. **Active checks** probe on a schedule: HAProxy's `check inter 2s fall 3 rise 2` probes every 2 seconds, removes a server after 3 failures and returns it after 2 successes. The failover part, [the main server dies at 3 a.m.](/main-server-dies-at-3am/), measured how the interval and failure count decide how many requests are lost before a dead server leaves the pool. The checks interact with the rule. A server that fails fast, returning errors in 1 ms, has few unfinished requests, so least connections sends it more and more traffic: a black hole. Count errors against servers so they are ejected. In NGINX, what counts as an unsuccessful attempt for `max_fails` is whatever `proxy_next_upstream` lists, and its default, `error timeout`, does not include HTTP 500 responses: a server answering 500 in 1 ms is never marked failed. List the status codes that mean "this server is broken" for that endpoint, for example `http_500 http_502 http_503 http_504`, and bound retries with `proxy_next_upstream_tries` and `proxy_next_upstream_timeout`. NGINX does not pass non-idempotent requests (POST, LOCK, PATCH) to the next server once they have been sent unless you add `non_idempotent`; keep it that way for writes without idempotency keys, or a retried payment can run twice. HTTP 403 and 404 are never counted as failures. **Slow start** covers the other direction. A server that just joined has an empty count, so least connections hands it every new request while its caches and connection pools are cold. HAProxy's `slowstart 30s` ramps its weight over 30 seconds; NGINX Plus has `slow_start`; Envoy has a slow start mode for round robin and least request. ## When do you still want hashing? {#when-hashing} [Image: The results board with rows round robin 150.3 ms, least connections 22 ms and user-ID hash 468.9 ms, a control run tag reading 22.5% load, and a fourth row reading control all three 20 ms, with an equals sign linking three 20 ms timers on the rule card | The control run: same arrivals, every request quick, 22.5% load, and all three rules tied at a p99 of 20 ms.] At light load the rule hardly matters. In the control run, with every request at 20 ms and 22.5% load, all three rules gave a p99 of 20 ms, though hashing still sent 32.7% of requests to one server. That server ran at 29.4% load. At this lighter load, queueing affected fewer than 1% of requests, so p99 stayed at 20 ms; hashing still produced a peak queue of 2 and a maximum latency of 28.6 ms, while round robin and least connections never queued. The imbalance was there in both runs; it became expensive when it pushed a server toward saturation. (The control is lighter, not equal load: only service times changed, so it does not show round robin with equal requests at 66% load.) Hashing gives you locality and costs you balance. Use it when locality is worth more: - **Cache locality.** If each server keeps an in-memory cache, hashing by URL or object ID sends repeat requests to the server that already has the object, so the distinct cached data can approach N times one server's, depending on skew and replication, instead of N copies of the same hot items. It is the same reason as routing to the right edge in why Netflix doesn't buffer in Kathmandu: a hit is cheap only if you reach the copy. - **In-memory state.** A single-owner room design (WebSocket rooms, game rooms, chat channels) routes members to the room's owner. Hash on the room ID, without a load bound: a redirected member would land on a server without the room. - **Sharded data.** If server k owns some keys, the request must go there; hot keys are then a data modelling problem, solved by splitting the key, an owner lookup with forwarding, or explicit migration, not by redirecting requests. A common pattern: least connections for stateless work; consistent hashing for paths that need locality, with a load bound only where state is replicated or shared (a cache); owner routing for single-owner state; and sessions in a shared store such as Redis so nothing else needs stickiness. ## Worked example {#worked-example} The video replays one request stream through each rule. Our lab (`labs/sd-16/run.mjs`) is a discrete event simulation on a virtual clock, seed 16, on one machine, with settings we chose; it is not a measurement of any real system. ```text assumed parameters (simulation, not production) 4 servers x 8 slots, one FIFO queue per server 20,000 requests, Poisson arrivals, the same arrival times for every rule mixed run: each request slow (400 ms) with probability 10%, else 20 ms 2,000 users, Zipf s = 1 (top user 12.1%, top 10 users 35.9%) hash = FNV-1a("user-" + id) mod 4 least connections = fewest running + queued requests, ties rotate load, mixed run realized slow share 10.25% mean work = 0.8975 x 20 + 0.1025 x 400 = 17.95 + 41 = 58.95 ms arrival rate 359.6 req/s load = 359.6 x 0.05895 / 32 slots = 0.662 measured 66.2% quick p99 overall p99 peak queue busiest share round robin 150.3 ms 408.1 ms 24 25% least connections 22 ms 400 ms 2 25.6% user-ID hash 468.9 ms 523.1 ms 71 32.7% hash, busiest server 117.6 req/s x 0.05895 s / 8 slots = 0.866 measured 86.8% control run: same arrivals, every request 20 ms load = 359.6 x 0.020 / 32 = 0.225 measured 22.5% p99 of all three rules: 20 ms hash busiest share still 32.7%, load 117.6 x 0.020 / 8 = 0.294 measured 29.4% ``` [Image: The opening layout returns: a phone, the load balancer and four servers each with a counter; the lowest counter is circled and one envelope goes to that server and comes back quickly, while row 2 of the results board pulses | In this run, sending each request to the server with the fewest unfinished ones kept quick requests quick.] Limits: one balancer with perfect, instant knowledge, no network, retries or failures, plain `mod 4` hashing; another seed or hash could make the hot server hotter or cooler. ## Code {#code} First, a short standard-library Python simulation of the same idea. It uses a different generator and hash than the lab, so its numbers differ from ours, but the order is the same. ```python # pick_lab.py: round robin vs least connections vs user-ID hash, 4 servers # Standard library only. A tiny simulation, not the lab: numbers will differ. import hashlib, heapq, random SERVERS, SLOTS, N = 4, 8, 20000 # 4 servers, 8 requests at once each FAST, SLOW, P_SLOW = 20.0, 400.0, 0.10 # ms of work; 10% of requests are slow RATE = 0.65 * SERVERS * SLOTS / (0.9 * FAST + 0.1 * SLOW) # req per ms, ~65% load USERS = 2000 rng = random.Random(16) weights = [1 / k for k in range(1, USERS + 1)] # Zipf s=1: few heavy users t, stream = 0.0, [] for user in rng.choices(range(1, USERS + 1), weights, k=N): t += rng.expovariate(RATE) # Poisson arrivals stream.append((t, user, SLOW if rng.random() < P_SLOW else FAST)) def user_hash(user): # stable across runs return int(hashlib.md5(f"user-{user}".encode()).hexdigest(), 16) % SERVERS def run(rule): slots = [[0.0] * SLOTS for _ in range(SERVERS)] # when each slot is free unfinished = [[] for _ in range(SERVERS)] # finish times, a min-heap got, quick, rr = [0] * SERVERS, [], 0 for arrive, user, work in stream: for h in unfinished: # forget finished requests while h and h[0] <= arrive: heapq.heappop(h) if rule == "round robin": s, rr = rr, (rr + 1) % SERVERS elif rule == "least conn": # fewest running + queued order = [(rr + k) % SERVERS for k in range(SERVERS)] # rotate ties s, rr = min(order, key=lambda i: len(unfinished[i])), (rr + 1) % SERVERS else: s = user_hash(user) free = slots[s] i = min(range(SLOTS), key=free.__getitem__) # FIFO: earliest free slot start = max(arrive, free[i]) free[i] = start + work heapq.heappush(unfinished[s], start + work) got[s] += 1 if work == FAST: quick.append(start + work - arrive) quick.sort() p99 = quick[int(0.99 * len(quick)) - 1] share = max(got) / N * 100 print(f"{rule:12} quick p99 {p99:6.1f} ms busiest server {share:4.1f}% of requests") for rule in ("round robin", "least conn", "hash"): run(rule) ``` Run it with `python3 pick_lab.py` (we used Python 3.14). What to observe: least connections has the lowest quick-request p99, round robin a clearly higher one with exactly 25% per server, and hashing the highest p99 with one server above 25%. Change `0.65` to `0.30` in `RATE`: all three quick p99 values fall to the 20 ms work time while the hash share stays put, the lesson of our control run. Second, NGINX (example addresses). ```nginx # /etc/nginx/conf.d/app.conf upstream api { zone api 64k; # share counters across worker processes least_conn; # fewest active connections, weighted # random two least_conn; # power of two choices instead server 10.0.0.11:8080 max_fails=3 fail_timeout=10s; server 10.0.0.12:8080 max_fails=3 fail_timeout=10s; server 10.0.0.13:8080 max_fails=3 fail_timeout=10s; server 10.0.0.14:8080 max_fails=3 fail_timeout=10s; keepalive 32; # must come after the balancing method } upstream feed_by_user { zone feed_by_user 64k; hash $arg_user consistent; # ketama ring keyed on ?user= server 10.0.0.11:8080; server 10.0.0.12:8080; server 10.0.0.13:8080; server 10.0.0.14:8080; } server { listen 80; location /api/ { proxy_pass http://api; proxy_http_version 1.1; proxy_set_header Connection ""; # count fast 5xx as failures too, so max_fails can eject a black hole proxy_next_upstream error timeout http_500 http_502 http_503 http_504; proxy_next_upstream_tries 2; # at most one retry on another server proxy_next_upstream_timeout 2s; # retry eligibility window, not a total request deadline proxy_connect_timeout 1s; # each attempt's own limits are set separately proxy_send_timeout 5s; proxy_read_timeout 5s; # POST and PATCH are not retried after sending (no non_idempotent) } location /feed/ { proxy_pass http://feed_by_user; # same user, same server, while the pool is fixed } } ``` A note on `proxy_next_upstream_timeout`: per the [NGINX proxy module documentation](https://nginx.org/en/docs/http/ngx_http_proxy_module.html#proxy_next_upstream_timeout) it limits the time during which a request may be passed to the next server. It does not interrupt an attempt already in progress at 2 seconds; that attempt is bounded only by `proxy_connect_timeout`, `proxy_send_timeout` and `proxy_read_timeout`, and the read and send timeouts apply between two successive operations, not to the whole response. With the values above, a request can still run for well over 2 seconds. If the client needs a strict total deadline, enforce it end to end: a deadline in the client or the application (a gRPC deadline, or a request context that is cancelled when time runs out), not a balancer retry setting. What to observe: `curl "http://host/feed/?user=42"` hits the same server every time in the upstream log; remove one server and only about a quarter of user IDs move. On `/api/`, a server busy with slow requests stops attracting new ones. Third, HAProxy with active health checks, slow start and a load bound on the hash. ```ini # /etc/haproxy/haproxy.cfg (excerpt) backend api balance leastconn option httpchk GET /healthz default-server check inter 2s fall 3 rise 2 slowstart 30s server app1 10.0.0.11:8080 server app2 10.0.0.12:8080 server app3 10.0.0.13:8080 server app4 10.0.0.14:8080 backend feed_by_user balance url_param user hash-type consistent hash-balance-factor 125 # admission target: ~1.25x the mean concurrent requests # (safe here only because feed is a cache) option httpchk GET /healthz default-server check inter 2s fall 3 rise 2 server app1 10.0.0.11:8080 server app2 10.0.0.12:8080 server app3 10.0.0.13:8080 server app4 10.0.0.14:8080 ``` What to observe: on the stats page, sessions per server stay close on `api`; on `feed_by_user`, while a server is at its admission threshold (about 1.25 times the weight-adjusted mean of concurrent requests this HAProxy sees, rounded to whole slots), requests that hash to it, for new and existing users alike, go to the next eligible server on the ring. That breaks affinity for those requests, which is acceptable for a per-server feed cache and not for single-owner state. ## Failure modes and edge cases {#failure-modes} **The black hole server.** A server that errors instantly looks idle, so least connections feeds it. Detect it by per-server error rate; fix it with error-based ejection and health checks that exercise real work. **Herding.** Balancers with partial counts all pick the same server. Use power of two choices. **Hot keys.** One heavy user, tenant or object overloads its server. Watch per-server share and top keys, not averages. Hash a finer key or isolate heavy keys; bound the load only for replicated or shared state. **Remapping storms.** With `mod N`, going from 4 to 5 servers invalidates locality for about 80% of uniformly hashed keys, potentially causing a miss burst against the database. Use consistent hashing and add servers one at a time. **Cold servers flooded.** An empty counter attracts every request to a cold server. Use slow start. **Long-lived connections.** WebSocket and HTTP/2 connections last hours, so per-connection balancing freezes the spread and new servers stay underused after a deploy. Close connections gradually or balance per request. ## Trade-offs {#trade-offs} | Option | Good for | Costs you | Use when | | --- | --- | --- | --- | | Round robin | Simplicity, no state, exact even counts | Blind to cost; queues on servers holding slow work | Requests cost about the same and load is moderate | | Weighted round robin | Servers of different sizes | Static weights go stale; still blind to current load | Mixed hardware with similar requests | | Least connections | Uneven request costs, long requests | Needs live counts; partial views across copies; black hole risk | Stateless services with variable latency | | Power of two choices | Large fleets, many balancer copies | Slightly less precise than a full comparison | Hundreds of servers or several balancers | | Hash, mod N | Stateless stickiness, same answer on every copy | Hot keys; most keys move when N changes | Rarely; prefer consistent hashing | | Consistent hashing | Cache locality, single-owner rooms and shards | Imbalance from skewed keys; ring search O(log P) plus an O(N) peer scan (more if candidates are unavailable), about 10 KB for 4 servers in NGINX | Per-server state is worth more than perfect balance | | Bounded-load consistent hashing | Replicated caches, shared state | Redirects requests past an admission threshold near 1.25x (or your factor) of locally observed mean concurrency, breaking affinity; more servers checked per pick at low factors | A miss on another server is cheap; never for single-owner state | | Cookie stickiness | Keeping a session on one server | Uneven load; sessions lost when a server dies | Legacy apps with in-memory sessions | ## Common mistakes {#common-mistakes} - **Mistake:** calling round robin fair because every server gets 25% of requests. **Instead:** compare work, not counts; with 10.25% slow requests, equal counts still gave a quick-request p99 of 150.3 ms in our run. - **Mistake:** judging the rule by overall p99. **Instead:** split latency by request type or endpoint; overall p99 was 408.1 vs 400 ms, quick-request p99 150.3 vs 22 ms. - **Mistake:** hashing on user ID for stickiness when the app is stateless. **Instead:** keep sessions in a shared store and use least connections; hash only when per-server state pays off. - **Mistake:** assuming a good hash function prevents hot servers. **Instead:** the hash spreads keys, not traffic. A heavy user creates an indivisible traffic contribution (12.1% of requests, about 32.1% of one server here); the other users mapped alongside it determine whether the server approaches saturation. Hash a finer key, isolate heavy keys, or bound the load where state is shared. - **Mistake:** using least connections without failure detection, or adding servers without slow start. **Instead:** eject servers on errors, and ramp a new server's weight gradually. ## In an interview {#in-an-interview} 1. **Clarify:** are requests similar in cost or very mixed? Do servers keep per-user state or caches? How many balancer copies? 2. **Assumptions:** a pool (4 servers with 8 workers each), a load (about 65%), a mix (mostly quick, some slow). 3. **Structure:** clients, two balancers, the pool, a shared session store; mark which paths are stateless and which need locality. 4. **Deep dive:** why round robin queues quick requests behind slow ones, why least connections or two choices fixes it, and what NGINX or HAProxy really count. 5. **Trade-offs:** hashing buys cache locality or session state at the cost of hot servers; consistent hashing limits remapping; bounded loads limit skew with an admission threshold, by breaking affinity, so only for shared or replicated state. 6. **Wrap up:** health checks, slow start, and per-endpoint p99 monitoring. > **A 60-second answer**For stateless HTTP services I would use least connections, or power of two choices with many servers or several balancer copies, because request costs vary and round robin keeps sending quick requests to servers stuck on slow work. In a simulation with about 10% slow requests, the quick-request p99 was 150.3 ms with round robin and 22 ms with least connections, while the overall p99 barely differed, so I would monitor p99 per endpoint. I would hash only where locality pays, such as per-server caches or chat rooms, and then with consistent hashing, adding a load bound only for cache-like state because it redirects requests, since skewed keys make hot servers: hashing on user ID put 32.7% of requests on one server. I would add health checks with error-based ejection, slow start, and keep sessions in a shared store. ## Practice {#practice} **Q (Beginner): What information does round robin use to pick a server?** Only its own counter. It never looks at how busy a server is, so counts are equal and request cost is ignored. **Q (Intermediate): Every server got exactly 25% of requests under round robin, yet quick requests had a p99 of 150.3 ms. Why?** The number of slow requests on each server fluctuates. When all 8 slots hold 400 ms requests, round robin still sends that server every fourth request, and those quick requests queue while other servers have free slots. **Q (Intermediate): Least connections cut the quick-request p99 from 150.3 to 22 ms but the overall p99 only from 408.1 to 400 ms. Why?** 10.25% of requests were slow, more than 1%, so the overall p99 is a slow request with 400 ms of work. Least connections removes waiting, not work. **Q (Intermediate): With Zipf s = 1 over 2,000 users, what share does the top user send?** 1 / H(2000), with H(2000) about ln(2000) + 0.5772 = 8.178, so about 12.2%. The simulation measured 12.1%. **Q (Advanced): A server gets 117.6 requests per second, 58.95 ms of work each on average, with 8 slots. What is its load, and why does it matter?** 117.6 x 0.05895 / 8 is about 0.866. Waiting grows sharply near full use, so this server built long queues (peak 71 in our run) while the cluster average was 66.2%. **Q (Advanced): You scale a hash(key) mod N pool from 4 to 5 servers. What fraction of keys move, and with consistent hashing?** With mod N a key stays only if its hash has the same remainder mod 4 and mod 5, about 1 in 5, so about 80% move. With consistent hashing about 1/5 move. **Q (Advanced): In the control run all three rules tied at 20 ms, yet hashing still sent 32.7% to one server. What does that tell you?** Imbalance gets expensive when it pushes a server toward saturation. At 29.4% load queueing touched fewer than 1% of requests, so p99 stayed at 20 ms, but hashing still reached a peak queue of 2 and a maximum of 28.6 ms. The control is also lighter (22.5%), so it says nothing about equal-cost requests at high load. ## Cheat sheet {#cheat-sheet} | Term or formula | Meaning | | --- | --- | | Round robin | Next server in a fixed cycle; equal counts, blind to cost | | Weighted round robin | More turns for bigger servers; static | | Least connections | Fewest open connections or unfinished requests, weighted | | Power of two choices | Pick two at random, send to the lighter one | | hash(key) mod N | Same key, same server; about 80% of keys move from 4 to 5 servers | | Consistent hashing | Ring of server points; adding one of N moves about 1/N of keys | | Bounded-load hashing | Admission threshold targets a factor (for example 1.25x) of the locally observed, weight-adjusted mean concurrent requests, subject to integer rounding; excess requests redirect, so only for shared or replicated state | | Envoy weighted least request | weight / (active + 1)^bias; 2 / 4 = 0.5 vs 1 / 1 = 1.0 | | Sticky session | Keep a client on one server, by hash or cookie | | Utilisation ρ = λ x S / slots | Share of slots busy; 359.6 x 0.05895 / 32 = 66.2% | | Little's law L = λW | Requests in system = arrival rate x time in system | | M/M/1 time in system S / (1 minus ρ) | Waiting explodes as load nears 100% | | Zipf share of rank 1 | 1 / H(users); 1 / 8.178 = about 12.2% for 2,000 users | | Health check, slow start | Who is in the pool; ramp a new server's weight gradually | ## Further reading {#further-reading} - **NGINX docs, Using nginx as HTTP load balancer:** the upstream block, round robin, least_conn, ip_hash, weights and passive health checks. - **NGINX docs, ngx_http_upstream_module, least_conn:** the exact definition and tie-breaking; the same page documents `zone`, `random` and `keepalive`. - **NGINX docs, ngx_http_upstream_module, hash:** the hash directive and its `consistent` (ketama) parameter. - **HAProxy configuration manual, balance:** every algorithm with notes on when each fits; see also `hash-type` and `hash-balance-factor`. - **Envoy docs, Supported load balancers:** weighted round robin, least request with two random choices, ring hash and Maglev. - **Dean and Barroso, The Tail at Scale:** why the slowest 1% of requests dominates user-facing latency when a page fans out to many backends. This article describes general load balancing patterns, public documentation for NGINX, HAProxy and Envoy, and our own small simulation. It does not describe any company's private systems, and the diagrams are conceptual. The simulated numbers come from settings we chose; they show the shape of the effect, not measurements of any real system. ## Frequently asked questions **Which load balancing algorithm is best?** There is no single best. When requests cost about the same and servers are identical, round robin is simple and fair. When request costs vary a lot, a rule that looks at each server's unfinished work, such as least connections or power of two choices, keeps quick requests from waiting behind slow ones. When you need the same user or key on the same server, for a local cache or session state, use consistent hashing and protect it against hot keys. **What is the difference between round robin and least connections?** Round robin sends requests to servers in a fixed cycle and never looks at how busy they are. Least connections looks at each server's current count of open connections or active requests and picks the lowest. In our simulation with 10.25% slow requests, the p99 of quick requests was 150.3 ms with round robin and 22 ms with least connections. **Why is hashing by user ID risky?** Because user traffic is usually skewed. Hashing sends all of one user's requests to one server, so a server that receives one or two heavy users carries more than its share. In our run the top user alone sent 12.1% of all requests, and the busiest server received 32.7% of requests against a fair 25%, with a peak queue of 71. **Does least connections count requests or TCP connections?** It depends on the software. NGINX's least_conn counts active connections to each upstream server, per worker process unless the upstream has a shared memory zone. HAProxy's leastconn (2.8) compares the streams each server is currently serving, divided by weight, so idle reusable connections do not count. Our simulation counts running plus queued requests on each server, the idealized version. **What is consistent hashing used for in load balancing?** It maps keys to servers so that adding or removing one server moves only about 1/N of the keys instead of nearly all of them. That keeps per-server caches warm and sessions in place during scaling. NGINX enables it with hash $key consistent; HAProxy with hash-type consistent. **Were these numbers measured on real servers?** No. They come from a discrete event simulation on a virtual clock with a fixed seed (16) and settings we chose: 4 servers with 8 slots each, 20,000 requests, about 10% taking 400 ms and the rest 20 ms. It shows the shape of the effect, not numbers for any real system. ## Sources - [NGINX docs: Using nginx as HTTP load balancer](https://nginx.org/en/docs/http/load_balancing.html) - [NGINX docs: ngx_http_upstream_module, least_conn](https://nginx.org/en/docs/http/ngx_http_upstream_module.html#least_conn) - [NGINX docs: ngx_http_upstream_module, hash](https://nginx.org/en/docs/http/ngx_http_upstream_module.html#hash) - [HAProxy configuration manual: balance](https://docs.haproxy.org/2.8/configuration.html#4.2-balance) - [Envoy docs: Supported load balancers](https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/load_balancers) - [NGINX docs: ngx_http_proxy_module, proxy_next_upstream](https://nginx.org/en/docs/http/ngx_http_proxy_module.html#proxy_next_upstream) - [Dean and Barroso: The Tail at Scale](https://research.google/pubs/the-tail-at-scale/)