Load Balancing Algorithms: Power of Two Choices, Maglev and L4 vs L7 (2026)
Most teams pick a load balancing algorithm once, usually the default, and never look at it again. That is fine until one backend in fifty starts garbage-collecting, a deploy adds cold JVMs to the pool, or a gRPC client pins every request to a single pod. Then the algorithm is the difference between a blip in a dashboard and a paged incident.
The load balancing algorithms that matter in 2026 fall into three families: stateless spreaders such as round robin and random, load-aware pickers such as least connections and power of two choices, and hash-based schemes such as ring hash and Maglev that trade evenness for stickiness. Which one is right depends less on the algorithm than on where it runs (L4 or L7) and how fresh its view of backend load is.
What this covers: the mechanics and queueing math of each algorithm, a simulation with real numbers, Maglev table construction and measured disruption, L4 vs L7 trade-offs, health checking, slow start, draining, gRPC imbalance, locality routing, and the failure modes that bite in production.
Context and Background
A load balancer has two jobs that are easy to conflate: choosing a destination for each unit of work, and keeping that choice valid as the set of healthy destinations changes. The first is the algorithm. The second is health checking, draining and membership propagation, and it is where most real incidents originate.
The unit of work matters. An L4 (transport layer) balancer sees TCP connections or UDP flows, so the unit is a connection. An L7 (application layer) balancer parses HTTP, HTTP/2 or gRPC, so the unit is a request. With HTTP/1.1 and short connections the two behave similarly. With HTTP/2, one connection multiplexes thousands of requests, and a connection-level balancer can no longer spread load. The gRPC project’s own load balancing write-up makes this point: multiplexing makes connection-level balancing ineffective for gRPC, and an application-level balancer can distribute the streams from one client among multiple backends.
The second axis is where the decision is made. A proxy balancer sits in the data path. A client-side balancer embeds the logic in each caller and avoids the extra hop but needs a client library per language and a trusted client. A lookaside balancer moves the logic to a separate server that hands clients addresses and receives load reports. Service meshes such as Istio and Linkerd put an L7 proxy next to every workload, which turns every caller into a client-side balancer without changing application code.
Envoy, the most widely deployed open L7 data plane, documents its policies in the supported load balancers reference: weighted round robin, weighted least request, ring hash, Maglev and random. Google described the L4 side in the Maglev paper, presented at NSDI 2016. The gateway layer that fronts these policies is covered in our API gateway comparison of Kong, Envoy Gateway and Apache APISIX, and the admission control that complements balancing is covered in distributed rate limiting with token bucket and GCRA.
One framing to keep throughout: a load balancer is a controller acting on delayed, partial information. The best algorithm is rarely the one with the best average on paper. It is the one that degrades gracefully when its information is stale, when a backend lies about its health, or when the pool changes under it.
The Algorithm Families: A Reference Architecture
Direct answer: load balancing algorithms split into stateless (round robin, random, weighted variants), load-aware (least connections, least request, power of two choices, latency EWMA) and hash-based (ring hash, Maglev, rendezvous). Stateless is cheapest, load-aware gives the best tail latency, and hash-based gives affinity for caches and connection stability at some cost in evenness.
Figure 1: A typical two-tier layout. ECMP spreads flows across L4 balancers, which hash the 5-tuple to L7 proxies that balance each request across backends while health checks and outlier detection feed back membership.
Figure 1 shows how the pieces stack in a common deployment. Routers use equal-cost multipath (ECMP) to spread packets for a virtual IP across several L4 balancers. Each L4 balancer picks an L7 proxy per connection. Each proxy then picks a backend per request. Every tier has its own algorithm, its own health view and its own failure modes, and they interact: if the L4 tier hashes connections to proxies unevenly, the L7 tier’s careful per-request balancing operates on an already skewed share of traffic.
Stateless: round robin, weighted round robin, random
Round robin cycles through backends in order. It needs no state beyond a counter, it is perfectly fair in request count, and it is the default almost everywhere. Its weakness is that it balances counts, not work. If requests have a heavy-tailed cost, or one backend is slower, equal counts produce unequal queues. In an M/M/1 view with 50 servers at 90 percent average load, a server that happens to receive a run of slow requests builds a queue that round robin never corrects, because it never looks at the queue.
Weighted round robin repeats higher-weight hosts proportionally in the rotation, which is how you express heterogeneous capacity such as a mixed fleet of 8-core and 16-core nodes. The weights are static opinions. If the opinion is wrong, or the real capacity changes (noisy neighbour, throttled CPU), the balancer has no way to notice.
Random selection is statistically worse than round robin for even spread (it is the classic balls-into-bins problem, covered next) but has one real advantage that the Envoy documentation calls out: with no health checking configured, random avoids the bias of round robin toward the host that follows a failed one in the rotation. Without health checks, a dead host’s successor receives double traffic under round robin, which can cascade.
Load-aware: least connections, least request
Least connections sends each new connection to the backend with the fewest active ones. Least request does the same per request. Both assume that active count is a good proxy for load, which holds when requests are of similar cost and backends of similar speed, and holds well when it is the slow backends that accumulate active requests. A slow backend naturally holds requests longer, its count rises, and the balancer routes away. That implicit feedback is why least-request adapts to heterogeneity that static weights cannot express.
A literal implementation scans all N backends per pick, which is O(N) and requires either a lock-protected shared counter table or per-worker approximations. In a multi-threaded proxy with many workers, each worker sees only its own connections, so each worker’s view of a backend’s total load is incomplete. This is the first appearance of the stale-information problem, and it is the reason the approximation in the next section is not merely a performance trick.
Power of two choices
Power of two choices (P2C) picks two backends uniformly at random and sends the request to the one with fewer active requests. It was analysed in the balls-into-bins literature (Azar, Broder, Karlin and Upfal, 1994) and surveyed for load balancing by Michael Mitzenmacher in “The Power of Two Choices in Randomized Load Balancing” (IEEE Transactions on Parallel and Distributed Systems, 2001).
The core result is dramatic. Throw n balls into n bins uniformly at random, and the fullest bin holds about ln n / ln ln n balls. Give each ball two random candidate bins and put it in the emptier one, and the fullest bin drops to about ln ln n / ln 2 plus a constant. The hidden constants make small-n comparisons unreliable, so do not read those expressions as literal counts. What matters is the shape: going from one choice to two changes the order of growth from logarithmic to doubly logarithmic, while a third choice only improves a constant factor. In the supermarket-queue model that Mitzenmacher studies, with arrival rate lambda per server and exponential service, the tail of queue lengths under random assignment decays as lambda to the power k, while with d choices it decays as lambda to the power (d^k minus 1)/(d minus 1), doubly exponentially in k.
Figure 2: Power of two choices. Sample two hosts at random, compare their in-flight counts, send the request to the lighter one.
Figure 2 shows the loop. What makes P2C attractive in practice is not only the math but the engineering profile: O(1) work per pick, no global sorted structure, and, critically, robustness to stale data. Envoy’s least-request policy with equal weights does exactly this, sampling a configurable number of hosts (the documented default choice count is 2) and picking the one with the fewest active requests. When weights differ, Envoy switches to weighted round robin with dynamic weights computed at pick time as the configured weight divided by (active requests plus one) raised to an active-request-bias exponent that defaults to 1.0; setting the bias to 0.0 makes it behave like plain round robin.
Measuring the Algorithms: A Queue Simulation
Theory is clean; production is not. The simulation below is deliberately simple so you can read and extend it: 50 single-server FCFS queues, Poisson arrivals, exponentially distributed service times with mean 1, and a policy that picks a server for each arrival. The numbers quoted in this article come from running exactly this code once, with a fixed seed of 7 and 200,000 jobs (the first 10 percent discarded as warm-up). They are illustrative of the model, not benchmarks of any product, and a different seed will move them by a few percent.
import heapq, random, statistics
def simulate(policy, n=50, rho=0.9, jobs=200_000, seed=7, slow=None, stale=0.0):
rng = random.Random(seed)
lam = rho * n # total arrival rate
free_at = [0.0] * n # when each server drains its backlog
inflight = [[] for _ in range(n)] # completion times per server
snap, snap_t, t, rr, resp = [0] * n, 0.0, 0.0, 0, []
for _ in range(jobs):
t += rng.expovariate(lam)
for h in inflight:
while h and h[0] <= t:
heapq.heappop(h)
if stale > 0 and t - snap_t >= stale: # load info refreshed every `stale`
snap = [len(h) for h in inflight]; snap_t = t
load = snap if stale > 0 else [len(h) for h in inflight]
if policy == "random":
s = rng.randrange(n)
elif policy == "rr":
s = rr % n; rr += 1
elif policy == "p2c":
a, b = rng.sample(range(n), 2)
s = a if load[a] <= load[b] else b
else: # "least": full information
m = min(load); s = rng.choice([i for i in range(n) if load[i] == m])
mult = slow.get(s, 1.0) if slow else 1.0
done = max(t, free_at[s]) + rng.expovariate(1.0) * mult
free_at[s] = done
heapq.heappush(inflight[s], done)
resp.append(done - t)
resp = sorted(resp[jobs // 10:])
q = lambda p: resp[int(p * (len(resp) - 1))]
return statistics.fmean(resp), q(.5), q(.99), q(.999)
Response time is measured in units of mean service time, so a value of 1.0 means a request took as long as its pure service would. At 70 percent utilisation the results were:
| Policy | Mean | p50 | p99 | p99.9 |
|---|---|---|---|---|
| Random | 3.35 | 2.30 | 15.39 | 21.92 |
| Round robin | 1.89 | 1.31 | 8.76 | 12.78 |
| Power of two choices | 1.64 | 1.23 | 6.65 | 9.45 |
| Least (full information) | 1.00 | 0.69 | 4.65 | 6.93 |
Table 1: Simulated response time (service-time units) at 70 percent utilisation, 50 servers, fresh load information. Illustrative, from the code above.
At 90 percent utilisation the gaps widen sharply:
| Policy | Mean | p50 | p99 | p99.9 |
|---|---|---|---|---|
| Random | 9.91 | 6.81 | 44.58 | 64.29 |
| Round robin | 5.11 | 3.57 | 23.61 | 33.30 |
| Power of two choices | 2.71 | 2.28 | 9.14 | 12.18 |
| Least (full information) | 1.17 | 0.82 | 5.26 | 7.72 |
Table 2: Same model at 90 percent utilisation. Illustrative.
Three observations follow. First, round robin beats random by about a factor of two in this model because it removes arrival-count variance, yet it is still 2.6 times worse than P2C at p99 when the system is hot. Second, P2C captures most of the gain of full-information least-loaded: at 90 percent it cuts p99 from 23.6 to 9.1, about 61 percent, while the omniscient policy reaches 5.3. Third, the benefit grows with utilisation. At low load every policy looks fine, which is why default-algorithm choices survive for years until traffic grows.
Stale information: where full-information least-loaded breaks
The omniscient “least” policy assumes it sees every backend’s current in-flight count. Real balancers do not. A fleet of proxies each see only their own traffic, or consult a load report refreshed every few hundred milliseconds. To model this, the simulation refreshes its snapshot of queue lengths every T time units (one time unit equals one mean service time) and routes against the snapshot. Results at 90 percent utilisation:
| Snapshot age T | P2C mean / p99 | Least mean / p99 |
|---|---|---|
| 0.5 | 2.87 / 9.61 | 3.06 / 14.32 |
| 2 | 3.31 / 11.07 | 6.57 / 27.14 |
| 10 | 5.20 / 17.55 | 24.12 / 117.27 |
Table 3: Effect of stale load information at 90 percent utilisation, 50 servers. Illustrative, from the simulation above.
This is the herd effect. Every arrival during a stale window sees the same “emptiest” server and piles onto it, so the globally least-loaded policy turns into a synchronised stampede onto one backend, which then becomes the most loaded. The crossover happens quickly: at T equal to 0.5 service times, full-information least-loaded is already worse than P2C at the tail. At T equal to 10, it is roughly seven times worse at p99. P2C degrades gracefully because two random candidates spread the herd across many different “least loaded of a pair” choices. This is the practical reason Envoy, NGINX (which offers a random-two variant) and most service meshes ship P2C rather than a global minimum.
Heterogeneous backends: where round robin collapses
The last scenario uses the slow parameter: 5 of 50 servers run three times slower, and the arrival rate is 60 percent of nominal fleet capacity. Under round robin or random, each slow server still receives 0.6 requests per unit time but can only serve one third of one per unit time, so each slow server’s queue grows without bound: arrival rate 0.6 times service time 3 gives utilisation 1.8. The simulation shows mean response times near 290 for round robin and 302 for random, with p99 above 4,800. P2C held a mean of 1.78 and p99 of 10.43 on the same fleet, and the full-information policy 1.10 and 5.74. Load-aware picking is not a polish; it is the difference between a stable and an unstable system whenever any backend is slower than its peers. In production the cause might be a degraded disk, a noisy neighbour, a CPU-throttled container or a pod that is mid-compaction.
Latency-aware: EWMA and peak EWMA
Counting active requests ignores how long they have been running. Latency-aware policies track an exponentially weighted moving average (EWMA) of recent response time per backend and combine it with in-flight count, commonly as a cost of EWMA latency times (in-flight plus one). Linkerd’s load balancing documentation states that it uses an EWMA to favour faster endpoints. The peak-EWMA variant used by Finagle reacts instantly to latency spikes but decays slowly; I could not verify peak-EWMA details in Linkerd’s current documentation page, so treat that attribution as background knowledge rather than a cited fact.
Latency-aware balancing has a trap: a backend that fails fast looks fast. If a broken host returns errors in two milliseconds, its EWMA is the lowest in the pool and it attracts the most traffic, a “black hole” effect. Any latency-based policy must count errors as high-latency samples or pair with outlier ejection.
Consistent Hashing: Ring Hash and Maglev
Load-aware algorithms treat all backends as interchangeable. Sometimes they are not: a cache shard owns certain keys, a stateful session lives on one node, or an L4 balancer must send every packet of a flow to the same backend even though the balancer fleet itself changes. For these cases you need a deterministic mapping from key to backend that moves as few keys as possible when the backend set changes. That is consistent hashing.
The naive scheme, backend index equals hash modulo N, remaps almost everything when N changes. In a test over 100,000 synthetic flow keys with 100 backends, removing a single backend under modulo hashing moved 99.01 percent of keys. Consistent schemes move roughly the 1 percent that belonged to the removed backend, plus some overhead depending on the scheme.
Ring hash
Ring hash places each backend at many points on a circular hash space and assigns a key to the nearest point clockwise. Many virtual nodes per backend smooth the distribution, and weights translate into proportionally more points. Envoy’s documentation recommends setting minimum_ring_size and maximum_ring_size explicitly and monitoring the min_hashes_per_host and max_hashes_per_host gauges, which tells you the evenness in practice. Ring hash lookup is a binary search over the ring: O(log of ring size).
In my test (SHA-256 truncated to 64 bits, 100 backends, 100,000 keys, ideal 1,000 keys per backend), 100 virtual nodes per backend left the loads between 808 and 1,300, so the hottest backend carried 30 percent more than ideal. With 1,000 virtual nodes the range tightened to 901 to 1,107. Removing one backend moved 0.99 percent of keys, essentially the minimum. Ring hash is minimally disruptive but needs a big ring to be even, and bigger rings cost memory and build time.
Maglev consistent hashing
Maglev, from Google’s NSDI 2016 paper “Maglev: A Fast and Reliable Software Network Load Balancer,” takes a different approach: build a fixed-size lookup table once and make lookups a single array read. The table size M is a prime number, and the paper’s guidance (as summarised by Adrian Colyer’s review of the paper) is M greater than 100 times N for N backends, which bounds the difference in hash-space share between backends to about one percent.
Each backend derives a permutation of the table slots from two hashes of its name: an offset equal to hash1(name) mod M, and a skip equal to hash2(name) mod (M minus 1) plus 1. Slot j of the permutation is (offset plus j times skip) mod M. Because M is prime and skip is between 1 and M minus 1, the permutation visits every slot exactly once. Backends then take turns: each claims its next most-preferred slot that is still empty, until the table is full. Round-robin turns give every backend an almost equal number of slots by construction.
Figure 3: Maglev packet path. A per-thread connection tracking table keeps existing flows on their backend; new or orphaned flows use the Maglev lookup table; the packet is GRE-encapsulated and the backend replies directly to the client.
Figure 3 shows how the table fits into the data plane. The paper describes a per-packet-thread connection tracking table keyed by a hash of the 5-tuple: if the entry exists and its backend is healthy, the packet follows it; otherwise consistent hashing selects a backend and the choice is recorded. The consistent-hash table is therefore a fallback that gives different Maglev machines the same answer for a new flow even though they share no state, which is what makes ECMP spreading of packets across balancer machines safe. Selected packets are GRE-encapsulated and unpacked at the backend, and replies use direct server return (DSR), so the balancer never touches the typically larger response traffic. The paper reports a packet thread processing a packet in about 350 nanoseconds and the design target is line rate on 10 Gbps per machine.
Here is a compact implementation of the table construction and a measurement harness:
import hashlib
def h(s, salt=""):
return int.from_bytes(hashlib.sha256((salt + s).encode()).digest()[:8], "big")
def maglev_table(backends, M=65537): # M must be prime
perms = [(h(b, "o") % M, h(b, "s") % (M - 1) + 1) for b in backends]
nxt, table, filled = [0] * len(backends), [-1] * M, 0
while True:
for i in range(len(backends)):
off, skip = perms[i]
while True:
c = (off + nxt[i] * skip) % M
nxt[i] += 1
if table[c] < 0:
table[c] = i; filled += 1
break
if filled == M:
return table
def pick(table, backends, five_tuple: str):
return backends[table[h(five_tuple) % len(table)]]
With 100 backends and M equal to 65,537, every backend received 655 or 656 table entries against an ideal of 655.37: essentially perfect evenness, versus the 30 percent spread of a 100-vnode ring. Removing one backend and rebuilding moved 1.55 percent of the 100,000 test keys, against a theoretical minimum of 1.03 percent. Ring hash with 1,000 virtual nodes moved 0.99 percent. This matches the Envoy documentation’s description of the trade-off: Maglev builds faster (about 10 times) and selects faster (about 5 times) than a 256K-entry ring, but removing hosts moves roughly twice as many keys. Envoy’s Maglev uses a fixed table size of 65,537 by default, per the same documentation, and allocates entries in proportion to weight (weights of 1 and 2 give 21,846 and 43,691 entries). A larger table_size reduces disruption.
Choosing between them
Choose Maglev when lookup speed and evenness dominate and a small amount of extra remapping on membership change is tolerable, as for L4 flow steering with a connection-tracking safety net. Choose ring hash when you cannot afford to move keys, as with cache shards whose warm contents are valuable and where remapping means cold misses. Both give affinity, not load awareness: a hot key still lands on one backend. Envoy’s bounded-load variants and application-level key splitting address that; hashing alone does not.
Walk-through: L4 vs L7 Load Balancing
L4 vs L7 load balancing is the decision with the largest operational consequences, so it deserves a direct comparison before details.
Direct answer: an L4 balancer forwards TCP or UDP flows without parsing application data, so it is fast, protocol-agnostic and cheap, but can only balance connections. An L7 balancer terminates and parses HTTP or gRPC, so it can balance each request, route on headers, retry and observe, at the cost of CPU, latency and a larger failure surface.
| Dimension | L4 | L7 |
|---|---|---|
| Unit of balancing | Connection or flow | Request or stream |
| Visibility | IPs, ports, flags | Headers, paths, methods, status codes |
| Typical algorithms | Maglev, ECMP hash, least connections | P2C, weighted least request, ring hash on a header |
| TLS | Pass-through, or terminate in some products | Terminates, can re-encrypt to backends |
| Per-packet cost | Very low, often kernel bypass | Higher, parsing and buffering |
| Retries, circuit breaking | Not possible | Native |
| gRPC and HTTP/2 spreading | Poor, pins per connection | Good |
| Return path | Can use DSR | Proxy must carry responses |
Table 4: L4 vs L7 load balancing at a glance.
Direct server return and its constraints
DSR sends replies from the backend straight to the client, bypassing the balancer. It is why a Maglev machine can keep up at line rate: inbound requests are small, outbound responses are large. The cost is that the backend must accept traffic for the virtual IP (typically via a loopback alias or a tunnel decapsulation), the balancer cannot observe responses, so it cannot do passive health checking from response codes, and it cannot use any feature that needs the response path. DSR is an L4 optimisation. Once you terminate HTTP, the proxy must be in the response path.
Where each layer belongs
Most mature fleets run both: an L4 tier at the edge or cluster boundary that provides a stable virtual IP, DDoS absorption and connection-level fan-out, and an L7 tier that does request-level policy. Figure 1 showed that arrangement. The L4 tier’s job is to be boring and always available, so keep its algorithm simple (hash-based, with connection tracking). The L7 tier is where you spend complexity: P2C, retries, outlier detection, locality awareness.
Section by section, the L7 benefits are concrete. Per-request balancing makes gRPC work. Retries on a different host mask single-backend failures. Request-aware routing enables canary releases by header or weight. Per-route timeouts and circuit breakers bound the damage from a slow dependency; see the companion article on retries, backoff with jitter, circuit breakers and retry budgets for how those controls combine with balancing.
Keeping the Pool Honest: Health Checks, Slow Start and Draining
An algorithm only chooses among the hosts it believes are healthy. Membership accuracy is therefore a bigger lever than algorithm choice in most incidents.
Active versus passive health checking
Active health checking sends synthetic probes (a TCP connect, an HTTP GET to a health endpoint, a gRPC health RPC) on an interval and ejects a host after a threshold of failures. It detects dead hosts with no traffic, and it can gate readmission: a host must pass several probes before receiving load. Its weaknesses are cost (N balancers times M backends probes per interval, which becomes real traffic at large fan-out) and fidelity: a shallow /healthz that returns 200 while the database connection pool is exhausted lies convincingly.
Passive health checking, called outlier detection in Envoy, watches real traffic and ejects hosts that return consecutive 5xx responses or exhibit statistical anomalies in success rate. It reacts to what users experience and costs nothing extra. Its weakness is that it needs failing traffic to learn anything, so the first few requests pay the price, and a low-traffic backend may never accumulate enough samples. Envoy’s outlier detection ejects for a base time that grows with repeated ejections and caps the share of the cluster that may be ejected at once, because ejecting everything is worse than serving from bad hosts. I recall the defaults as five consecutive 5xx, a 10-second analysis interval, a 30-second base ejection time and a 10 percent maximum ejection, but defaults change between releases, so confirm them against the documentation for your version.
The strongest configuration uses both: active checks for liveness and readmission, passive ejection for gray failures that the probe cannot see. A related protection is the panic threshold. When the share of healthy hosts falls below a threshold, Envoy’s documentation describes it as ignoring health status and balancing across all hosts, on the reasoning that if most of the pool looks unhealthy, health information is more likely wrong than right. Know your threshold, because it determines whether a partial outage becomes a total one.
Slow start
A newly started instance has cold caches, an unwarmed JIT, empty connection pools and lazy-initialised dependencies. A least-request balancer sees zero active requests on the new host and sends it a disproportionate share immediately, exactly when it is slowest. Latency rises, requests queue, health probes begin failing, the host is ejected, restarts its warm-up from zero, and the cycle repeats. This is the cold-backend thundering herd.
Slow start fixes it by ramping the host’s effective weight from a small fraction to its full weight over a configured window. Envoy supports slow start through its SlowStartConfig for round robin and least request policies, and for the client-side weighted round robin policy. The principle is portable: during the ramp, the host’s weight is multiplied by a growing factor, so a host that is 30 seconds into a 120-second window gets a fraction of its share. Choose the window from measurement: take the time for p99 latency of a fresh instance to converge to that of a warm one, and add margin. Slow start interacts with autoscaling: if every new pod ramps for two minutes, a scale-up in response to a spike delivers capacity two minutes late, so ramp windows belong in capacity planning.
Figure 4: Backend lifecycle at the balancer. A new backend passes health checks and ramps through slow start; the old one stops receiving new requests and drains in-flight work until a timeout.
Connection draining
Draining is slow start’s mirror. Removing a backend by killing it drops in-flight requests and resets connections. Graceful removal has an ordering, shown in the lower half of Figure 4: first stop sending new requests to the host (mark it draining or failing the readiness probe), then wait for in-flight requests to complete, up to a maximum drain time, and only then terminate. In Kubernetes the classic mistake is a race between endpoint removal propagating to every proxy and the container receiving SIGTERM. Proxies learn about removal asynchronously, so a pod that exits immediately will still receive new requests for seconds. The remedy is a preStop sleep or a drain period longer than the propagation delay, and an application that keeps serving until its listener is told to close.
Long-lived connections complicate this. A WebSocket or gRPC stream can last hours, and draining must either wait for it, or signal the client to reconnect elsewhere (HTTP/2 GOAWAY, for example). Set a hard maximum drain time and make clients tolerate reconnects.
HTTP/2, gRPC and the Long-Lived Connection Problem
The most common production surprise with Kubernetes is gRPC traffic that arrives on a single pod. A Kubernetes Service of the default ClusterIP type balances at L4: kube-proxy picks a backend when a connection opens. A gRPC client opens one HTTP/2 connection and multiplexes every call over it, so every call lands on the one pod chosen at connect time. Scaling the deployment from 3 to 30 pods changes nothing for existing clients. The Linkerd documentation notes that Kubernetes’ default balancing is not effective for gRPC and HTTP/2, which is why meshes balance at the request level.
There are three standard remedies, each with different costs:
- L7 proxy balancing. Route through Envoy, NGINX or a mesh sidecar that balances each stream. Simple for clients and suited to untrusted ones, but adds a hop and puts the proxy in the data path.
- Client-side balancing. Use the gRPC library’s built-in policies (such as round robin) with a resolver that returns all backend addresses, typically via a headless Service. No extra hop, but each language needs a correct implementation, and clients must refresh addresses or they drift from the real pool.
- Lookaside balancing. A separate server holds load information and tells clients where to go; backends report load. It supports sophisticated policies without a data-path proxy but adds a component to operate. The gRPC write-up notes that clients can layer simple algorithms on top of the lookaside balancer’s choices.
A subtler problem remains after you balance per request. Connection churn: even with per-request balancing, a pool that was scaled up will show new pods underused if existing connections are never recycled, because a client-side balancer that opened subconnections to the old set will not use new ones until it re-resolves. Set a maximum connection age at the server (with a jittered value so clients do not all reconnect at once) so the system reshuffles itself every few minutes.
Client-Side, Proxy and Mesh Balancing Compared
The same algorithm behaves differently depending on who runs it, because the number of independent deciders determines how stale their view of load is.
With a central proxy fleet of, say, 10 balancers, each sees about one tenth of the traffic and its in-flight counters reflect only its own requests. A backend can look idle to every balancer while receiving a combined load from all of them. With P2C this is acceptable because random pairs spread the effect. With a global minimum it produces the herd behaviour measured in Table 3.
In a sidecar mesh with, say, 500 callers of one service, there are 500 independent deciders, each with a tiny sample of traffic. Each sidecar’s local view of a backend’s in-flight count is often 0 or 1, so least-request degenerates to nearly random selection with a slight bias away from busy hosts. Latency EWMA recovers some signal because response times reflect load from all callers, not only the local one. This is a reason to prefer latency-aware policies, or server-reported load such as Envoy’s client-side weighted round robin that consumes ORCA load reports, in large meshes. The Envoy documentation describes its weights as derived from queries per second divided by utilisation with an error penalty, drawn from backend-reported metrics, which gives each client a global signal it could never derive locally.
| Model | Extra hop | Load view | Best for | Main risk |
|---|---|---|---|---|
| Central proxy | Yes | Partial, per proxy | Untrusted clients, simple clients | Proxy is a bottleneck and failure domain |
| Client-side | No | Very partial, per client | Trusted internal RPC, low latency | Per-language bugs, stale endpoint lists |
| Lookaside | No | Global, delayed | Large fleets needing smart policy | Extra control component |
| Sidecar mesh | Local hop | Partial, per sidecar | Uniform policy without code changes | Resource overhead, config complexity |
Table 5: Where the decision is made and what it can see.
Locality and Zone-Aware Routing
Cross-zone traffic costs latency (typically a millisecond or more rather than hundreds of microseconds within a zone) and, on major clouds, money per gigabyte. Locality-aware balancing prefers backends in the caller’s zone when they have capacity and spills over only when needed.
The naive version breaks easily. If zone A has 2 backends and zone B has 8 and traffic originates equally from both, preferring local sends five times more load per backend in zone A. Envoy’s zone-aware routing therefore compares the share of upstream capacity in the local zone against the share of originating traffic and sends only the excess across zones; it also falls back to global balancing when too few hosts are healthy locally. Locality can also be configured with explicit priorities and weights for failover between regions.
Two design rules follow. Keep zones balanced in capacity, because locality preference amplifies imbalance. And treat zone-aware routing as an optimisation that must fail open: when a zone loses most of its backends, traffic must spill over rather than hammer the survivors.
Trade-offs, Gotchas, and What Goes Wrong
Health check flapping. A host oscillating between pass and fail causes constant membership changes. With hash-based schemes each flap remaps keys and invalidates caches; with ring hash it moves roughly one backend’s share each time. Use hysteresis: require several consecutive successes to readmit and a longer ejection for repeat offenders.
Retry amplification. A balancer that retries on another host doubles load on the remaining pool when failures are correlated. Cap retries with a budget. Retries combined with a slow shared dependency can create a retry storm; the earlier-linked article on retry budgets covers that.
Black-holing. A host that fails quickly attracts traffic under least-request and latency-aware policies because its in-flight count and latency are both low. Count errors against a host’s score, or enable outlier detection that ejects on consecutive errors.
Hash skew and hot keys. Consistent hashing gives affinity, not balance. One celebrity key can saturate one shard. Mitigate with replication of hot keys, request coalescing, bounded-load hashing or a two-level scheme.
Weights that rot. Static weights express capacity at the moment someone set them. After a hardware refresh or a noisy-neighbour event they are wrong, and nothing alerts you. Prefer weights derived from live signals, or audit them.
Config propagation skew. During a rollout, different proxies hold different membership versions. A removed pod may receive traffic for seconds; a new one may receive none. Plan for it with drain periods and with idempotent retries.
Connection-count conflation. Least connections at L4 treats an idle keep-alive connection and a connection streaming a large download as equal. If your connections are heterogeneous, least connections can balance counts while load stays skewed.
Over-trusting the simulation. My model has exponential service times, infinite queues and independent servers. Real services have heavy tails, correlated slowdowns, finite thread pools and queue limits. Use the simulation to understand the direction and magnitude of effects, then test your own workload with a replay.
Practical Recommendations
For a general-purpose HTTP or gRPC service, default to P2C (least request with two choices) at L7 and keep the choice count at two. Raising it moves you toward the herd-prone global minimum with little benefit. Use hash-based balancing only where affinity pays for itself: caches, stateful shards, and L4 flow steering. At L4, use a hash with connection tracking and DSR where your network permits it. Prefer Maglev-style tables when evenness and lookup speed matter, and ring hash when minimal remapping matters more.
Spend your effort on membership: combine active and passive health checks, configure slow start from measured warm-up time, and drain gracefully. Measure per-backend load distribution continuously, because the maximum-to-mean ratio of requests per backend is the single best indicator of balancing health.
Checklist:
- [ ] Identify the unit of balancing: confirm HTTP/2 and gRPC traffic is balanced per request, not per connection.
- [ ] Choose P2C or weighted least request for stateless services; reserve hashing for affinity needs.
- [ ] Set explicit ring size or Maglev table size and monitor min and max entries per host.
- [ ] Enable both active health checks and outlier detection; count errors in latency-aware scoring.
- [ ] Configure slow start with a window derived from measured warm-up, and account for it in autoscaling.
- [ ] Implement graceful draining with a preStop delay longer than endpoint propagation.
- [ ] Set maximum connection age with jitter so clients re-balance.
- [ ] Cap retries with a budget and make retried calls idempotent.
- [ ] Alert on max-to-mean requests per backend and on healthy-host percentage near the panic threshold.
- [ ] Keep zone capacity balanced before enabling locality preference.
Frequently Asked Questions
What is the best load balancing algorithm?
There is no universal best, but for stateless request-based services power of two choices is the strongest default. It is O(1) per decision, needs only in-flight counts, and degrades gracefully when load information is stale. In the simulation here it cut p99 latency by roughly 61 percent versus round robin at 90 percent utilisation. Use hashing instead when you need affinity, and round robin when requests and backends are truly uniform and you want simplicity.
What is the difference between round robin and least connections?
Round robin cycles through backends and equalises request counts, ignoring how busy each backend is. Least connections sends each new connection to the backend with the fewest active ones, so slower backends, which hold connections longer, naturally receive less. Round robin is cheaper and fine for uniform work. Least connections adapts to heterogeneous speed and variable request cost, but counts connections rather than work and can suffer from stale counts across multiple balancers.
How does power of two choices work?
For each request the balancer samples two backends at random and sends the request to the one with fewer active requests. Randomness spreads decisions and avoids herding, while the comparison avoids the worst of two random choices. The theory shows that two choices reduce the maximum load from logarithmic to doubly logarithmic growth, and a third choice only improves a constant. Envoy implements it as least request with a default choice count of two.
What is Maglev consistent hashing?
Maglev hashing is the algorithm in Google’s software network load balancer. It builds a prime-sized lookup table by letting each backend claim slots in its own pseudo-random permutation order, giving near-equal shares, then maps a flow hash to a table entry in one read. When backends change, only a small fraction of flows move. Envoy offers it with a default table size of 65,537 as a faster alternative to ring hash.
When should I use L4 instead of L7 load balancing?
Use L4 when you need raw throughput, non-HTTP protocols, pass-through TLS or a stable virtual IP at the edge, and when DSR can offload response traffic. Use L7 when you need per-request balancing (essential for gRPC and HTTP/2), header or path routing, retries, rate limiting or detailed metrics. Many architectures use both: an L4 tier for flow distribution in front of an L7 tier for request policy.
Why does gRPC traffic go to only one pod?
gRPC multiplexes all calls over one long-lived HTTP/2 connection. A Kubernetes ClusterIP Service balances at connection time, so the client’s single connection pins to one pod and later scale-up does not help. Fix it with an L7 proxy or mesh that balances each request, client-side balancing with a headless Service, or lookaside balancing. Also set a jittered maximum connection age so clients periodically reconnect and discover new pods.
Further Reading
- API gateway comparison: Kong vs Envoy Gateway vs Apache APISIX for how gateways expose balancing policies.
- Distributed rate limiting: token bucket, GCRA, Redis and Envoy for the admission-control half of load management.
- Cilium 1.20 ExternalAuth vs oauth2-proxy vs Istio for the mesh and data-plane context.
- Envoy: supported load balancers (official documentation).
- gRPC load balancing (official gRPC project).
- Eisenbud et al., “Maglev: A Fast and Reliable Software Network Load Balancer,” NSDI 2016, and Mitzenmacher, “The Power of Two Choices in Randomized Load Balancing,” IEEE TPDS 2001.
By Riju — about
