Load Balancing Beyond Round-Robin

Hey everyone, welcome to the fifty-first issue of The Main Thread.

Imagine an API behind an L7 load balancer and four identical servers. Normal reads usually take 40ms. But a request that exports a year of data might take 20s.

Let’s say server 2 receives one of those export requests. If the chosen load-balancing algorithm is Round-robin, then every fourth new request still goes to server 2 while the export is running. The request count is still 25% on every server, but server 2 is under more load than the others.

Soon, its queue will grow, while the other three servers still have room. Round-robin is not at fault. We asked it to divide request counts, and it does so faithfully. However, the system needs the “unfinished work” to be divided.

This insight steers us toward the decision framework for this whole topic. Each load-balancing algorithm spreads a different signal:

The right choice depends on which signal represents cost in the service. Before choosing one, we also have to separate four decisions that often get hidden under the word “load balancing”.

Let’s look at one request from a user in Mumbai.

Global routing may choose the Mumbai region because it is close to the user and has enough capacity. Suppose that region has four servers and server 3’s health check is failing. The health filter removes server 3, leaving only three servers to serve requests.

If the request has a session cookie for server 2, and server 2 is still healthy, affinity sends it back there. Otherwise, round-robin or least-request chooses from the three servers left. For a new session, a cookie can record that choice for later requests. With hash-based affinity, the balancer calculates the same choice again from the same user or session key.

Each decision has access to different information:

Round-robin only chooses a server inside the selected region. If every server in Mumbai is already busy, any local policy will still send the request to a busy server. Global routing has to send new requests to another region.

Imagine three healthy servers behind a load balancer. It sends a new request to the next server in the list. After server C, it starts again from server A.

The load balancer only remembers which server comes next. It does not check how much work each server is already doing. If server B is still processing request 2 when request 5 comes, server B gets request 5 anyway because its turn has come again.

Round-robin works well when three conditions hold:

A stateless JSON API running on three identical servers often fits these conditions. If its requests take between 8 and 10 milliseconds, giving every server the same number of requests will usually give them a similar amount of work.

The 20s export from the example given in the beginning breaks condition 2. It takes 500 times as long as a 40ms read. If the export lands on server B, server B stays busy while round-robin continues to give it new requests. Request duration is never part of the decision.

Where round-robin runs also matters. An HTTP (L7) load balancer can choose a server for every request. A TCP (L4) load balancer usually chooses a server when the connection opens, and that connection stays attached to the same server.

If one client sends 1,000 HTTP requests through one long-lived connection, all 1,000 may reach the same server. The number of connections can look evenly spread while the requests are uneven.

Round-robin assumes that the same number of assignments produces roughly the same amount of work. Measure request duration and work in progress per server. If those numbers differ widely, equal turns are no longer equal work.

Suppose server A can process 200 requests/second at the target latency. Servers B and C can process 100 request/second each.

At 400 requests/second, ordinary round-robin sends about 133 requests per second to every server. B and C can only process 100, so requests start waiting there while A still has room for 67 more.

Weighted round-robin lets us match the traffic to the measured capacity:

The weights form a ratio. A ratio of 2:1:1 gives server A 2 out of every 4 requests over time. Servers B and C get 1 each.

The two common uses are:

The weight is set before requests arrive. The load balancer keeps using 2:1:1 until someone or some system changes it.

If server A runs out of DB connections, it still receives 50% of the traffic. The same thing happens if another process takes half of its CPU. Requests start waiting on A while B and C may still have room, because A's weight describes the capacity measured earlier.

Measure these numbers for each server:

If A receives 50% of the traffic while its queue and latency keep growing, its configured weight no longer matches its current capacity.

Some load balancers combine weights with a live count of active requests. Server A can receive more work while all three servers have room. As A gets busy, the active-request count moves new requests toward B and C. If capacity changes faster than the weights can be updated, the balancer needs that live signal.

Let’s go back to our example of a 20-second export. Suppose it lands on server 2 and keeps its TCP connection open until the export finishes. During those 20 seconds, server 2 has one more open connection than the other servers.

Least-connections sends each new connection to the server with the lowest open-connection count. While the export is running, new connections go to the other servers. The long request stays visible to the load balancer until its connection closes.

This approach works when an open connection is a useful estimate of work. Long-lived TCP sessions, database proxy connections, and uploads often come close because the connection stays open while the server is busy with it.

But a connection count doesn’t give a clue about the work happening inside each connection.

Imagine server A has 500 idle WebSocket connections. Server B has 1 connection carrying a large upload. Least-connections chooses server B because 1 is smaller than 500, even if that upload is using more bandwidth than all 500 idle connections.

HTTP/2 widens this gap because one TCP connection can carry many requests at the same time. Server A may have 2 connections carrying 100 active requests each, while server B has 10 connections carrying 1 request each. Least-connections chooses server A because 2 is smaller than 10, even though server A is already processing 200 requests.

An HTTP (L7) load balancer can see those individual requests. It can use least-request, which sends the next request to the server with the fewest requests that have started and have not finished. Least-request still counts every request as 1. A server processing 2 cached reads and a server processing 2 large exports both have a count of 2, even though the exports need far more work.

A latency-aware policy can also consider how long recent requests took. That signal comes from requests that have already finished, so it takes time to reflect a sudden change in traffic.

Comparing every server's active-request count can become expensive when the pool is large. The power-of-2 choices read only 2 counts:

The load balancer avoids comparing the whole pool for every request. A busy server is also likely to lose whenever it is sampled against a less busy one.

Better information needs more bookkeeping. Least-request updates a counter when every request starts and finishes. A latency-aware policy must also record request duration and maintain recent history.

Plot the signal used by the load balancer next to queue time and latency for each server. If connection counts stay even while queue time differs widely, connection count is the wrong signal for that service.

Let’s consider a chat service that keeps conversation context in server memory. The first request for conversation 29 lands on server A, so server A loads that context. Round-robin and least-request do not use the conversation ID when choosing a server, so the next request may land on server B. Server B then has to load the same context again.

We can use conversation_id as a key and hash it to a server. The same conversation ID produces the same hash, so its requests return to the same server while the server list stays unchanged.

A direct way to choose the server is:

With 3 servers, the result is 0, 1, or 2. When server D joins, the divisor changes from 3 to 4. That changes the result for about 3 out of every 4 conversation IDs.

Those conversations now reach servers that do not have their context in memory. Each server has to load that context again. If the local state is a cache, thousands of keys can miss at once and send a sudden wave of reads to the database.

Consistent hashing keeps the hash range fixed when a server joins or leaves. It hashes both servers and keys into that range, then connects the end of the range back to the beginning to form a ring. Each key belongs to the first server found while moving clockwise.

When server D joins, it takes only the keys between the previous point on the ring and its own position. With 4 evenly placed servers, that is about 25% of the keys. The other 75% stay on the same servers. One position per server can still split the ring unevenly. A server that comes after a large empty part of the ring owns that whole part and receives more keys.

Virtual nodes place each physical server at many positions on the ring. Each server then owns many small parts spread around the ring, which makes its total share more even. A faster server can be given more virtual nodes so that it owns a larger share. Virtual nodes distribute keys. Request volume can still be uneven because some keys receive far more traffic than others. If conversation 29 produces 30% of all requests, every request for that conversation still goes to one server.

Handling that hot conversation needs another rule:

Consistent hashing also does not copy state. If server C fails, the ring can send its keys to server D, but server D does not automatically have the state that was stored on C. Server D needs a replicated copy or must load that state again.

A production policy needs 4 parts:

The fallback may have to load the state again, which costs time. That cost is still better than waiting on a preferred server that has stopped making progress.

Imagine server 3 can accept a TCP connection, but its database connection pool is full. Its /health endpoint still returns 200 OK because that endpoint only checks whether the process is running. Every request that needs the database fails. Server 3 remains in the ready list, so round-robin or least-request may keep sending traffic to it. The balancing algorithm can only choose from the servers that passed the health check.

Health checks serve 3 different purposes:

An active health check calls a test endpoint on a schedule. It may find a dead server before a user reaches it, but it only tests the path implemented by that endpoint. Passive health watches the path used by real requests, but some requests have to fail before the load balancer can detect the problem.

Readiness needs care when every server depends on the same service. If one shared database fails and all 10 application servers leave the ready list, the load balancer has nowhere to send traffic. If the application can still serve cached or limited responses, the readiness check should test that ability. If every request needs the database, the service should reject new work early while the database recovers.

A single failed probe may come from a short network delay. Removing a server after one failure and restoring it after one success can make that server repeatedly enter and leave the pool. Require several failures before removal and several successes before recovery. A small random delay in the schedule prevents every load balancer from probing the same server at the same instant.

Passive health also needs a limit on how many servers it can remove. Suppose 8 of 10 servers become slow. If all 8 are removed, the same traffic is sent to the remaining 2 servers. Each of those 2 servers now receives 5 times its previous share and may fail from the added load.

Once that removal limit is reached, the system has to choose between sending some traffic to slow servers or rejecting some requests to protect the capacity left. Every removal is also a capacity change. At the same traffic level, removing 5 of 10 servers doubles the work sent to every server that remains. Monitor the number of ready servers next to queue time and request latency.

Let’s say one client opens a TCP connection and sends 100 HTTP requests through it. An L4 load balancer sees the source and destination IP addresses, ports, protocol, and the TCP connection. It usually chooses a server when that connection opens. All 100 requests may stay on that server because L4 does not read the HTTP requests inside the connection. This is enough for TCP, UDP, and private protocols. An L4 load balancer can also forward packets without terminating HTTP or TLS.

An L7 load balancer understands the application protocol. For HTTP, it can read the hostname, path, method, headers, and cookies. It can choose a server for each of the 100 requests, even though they arrived through one client connection. That allows /exports to go to servers built for long jobs while /profile goes to the normal API servers. It also allows the load balancer to keep requests with the same session cookie on one server.

To read an HTTPS request, the L7 load balancer must terminate TLS or receive traffic that has already been decrypted. It then parses each request and opens its own connections to the application servers. That requires more CPU, memory, and connection management than forwarding packets at L4.

HTTP retries also affect correctness. Suppose the load balancer sends POST /charge to server A and times out while the response is on its way back. Server A may have completed the charge. If the load balancer retries the request on server B, the customer may be charged twice. Writes need an idempotency key or another way to make a retry safe.

Choose the layer that can see the information used by the routing rule. L4 is enough when the decision is based on a TCP connection or UDP flow. Routing /exports differently, or balancing each HTTP request requires L7 because those details exist inside HTTP.

Consider a shopping cart stored in server A's memory. A user adds an item, then the next request lands on server B. Server B has no copy of that cart, so the user sees an empty one.

Session affinity keeps later requests from that session on server A. The load balancer can do this in 2 ways:

The cookie is usually the better identifier because it follows the browser session. An IP address does not identify one user. Thousands of employees behind one company network may share one public IP address and all land on server A. A phone can also change IP addresses while moving between Wi-Fi and mobile data, which sends the next request to another server.

Affinity solves the empty-cart problem, but it limits what the load balancer can move:

Consistent hashing and session affinity both try to preserve locality, but they keep different promises. Consistent hashing calculates an owner from a key and limits how many keys move when the server list changes. Session affinity keeps one client session attached to the server chosen earlier.

If the cart lives in a shared store, any server can handle the next request. Affinity can then be a preference: use server A while it is healthy and has room, then choose another server during failure or overload.

Imagine a user in Mumbai sends a request. Before round-robin or least-request can choose a server, global routing must choose which region receives that request.

DNS can return the address of the Mumbai region based on location, measured network latency, configured weights, and health. The client then connects to that address, so DNS is no longer involved in the request.

DNS answers are cached for their time to live (TTL). If the Frankfurt region fails after a resolver caches its address, clients using that cached answer may keep trying Frankfurt until the TTL expires. A shorter TTL allows the answer to change sooner, but it also creates more DNS lookups. Changing DNS also does not move a TCP connection that is already open.

Anycast advertises the same IP address from several regions. Internet routing sends the client toward the region whose network route is preferred.

Internet routing chooses based on network reachability and routing policy. Application capacity, data location, and write-leader ownership are outside that decision. A route that looks shorter to the network may still lead to a slower or overloaded application.

Route changes also matter for long TCP connections. If later packets reach a different region, that region may not have the connection state and the connection can break. Anycast works best at a stateless edge that can pass longer work to another layer.

A global L7 proxy accepts the client connection at an edge, reads the HTTP request, and sends it to a region. It can use application health, available capacity, data location, and request details when making that choice.

The proxy now carries every request and usually terminates TLS. If its global routing service or configuration fails, users may lose access even while the regional application servers are healthy.

Region choice should be evaluated in this order:

Network distance comes after correctness and capacity. A fast route to a full region still sends the request into a queue.

Suppose Mumbai and Frankfurt each run at 70% of their maximum capacity. If Mumbai fails, Frankfurt receives the traffic from both regions. Frankfurt now needs 140% of its capacity, so it fails too. The health system moved the traffic correctly, but the spare capacity was never there.

Test regional failover at the traffic level expected during an outage. If the surviving regions cannot absorb that load, the routing policy also needs a plan to reject lower-priority requests.

The service from the opening split request counts evenly, but server 2 still built a queue. Round-robin measured how many requests each server received. The service paid for how long those requests stayed unfinished.

Start with the property that best describes the service:

These policies can be combined:

For one service, put these 5 graphs beside each other:

For consistent hashing or affinity, add cache hit rate, remaps, and fallback rate.

Read the graphs together. Even request rate with uneven active work means request count is a poor estimate of cost. Even active work with uneven queue time or latency means each active request costs a different amount. A high cache hit rate beside one overloaded key means locality is keeping too much work on one server.

Before shipping a policy, write down the measurement that would make it wrong. Keep that measurement on the dashboard as the service and its traffic change.

If the gateway and the slowest server have different owners, send this to both. The routing decision and the work inside the server create the same queue. The Main Thread covers one practical systems problem each week.