How to Spread Requests Across Servers in Python With the Power of Two Choices and Avoid the Herd Effect of Least-Loaded Routing
A hands-on tutorial that builds a queueing simulator and an asyncio balancer in Python, shows why picking the lighter of two random servers cuts the average time in system 3.7 times against random...
Imagine ten identical servers behind one entry point and a steady stream of requests. Every request has to go to exactly one server, and the rule that picks the server decides whether your users get fast answers or slow ones from the same hardware. The two obvious rules, pick a server at random or pick the server that looks least busy, each hide a flaw. This tutorial builds a small experiment in Python, shows each flaw with numbers, and then shows a rule that avoids both: choose two servers at random and send the request to the one that is less busy. The rule is called the power of two choices.
Table Of Content
- The terms used in this tutorial
- Prerequisites
- Set up the lab folder
- Step 1: See the idea in 20 lines with balls and bins
- Step 2: Build the server of the simulator
- What the code does
- A gotcha to remember
- Step 3: Write the routing rules
- What each policy does
- Step 4: Write the simulation loop
- How it works
- Step 5: Check the simulator against a formula before you trust it
- Step 6: Compare the five rules
- Reading the table
- Check that it worked
- Step 7: See why two choices are enough
- Reading the table
- Step 8: Take away the fresh numbers and watch the herd form
- Reading the table
- Why the herd forms
- Turn T into your own numbers
- Step 9: Run several balancers that cannot see each other
- Reading the table
- Step 10: Put one sick server in the fleet
- Reading the table
- The limit of this signal
- Step 11: Notice when counting requests is the wrong measure
- Reading the table
- Step 12: Put the idea into an asyncio program
- What the code does
- Run it against a slow backend
- Reading the table
- Step 13: Test it, then break it on purpose
- What the tests check
- Plant seven bugs and see whether the tests notice
- Step 14: Meet three bugs that look harmless
- Mistake 1: choosing with replacement
- Mistake 2: breaking ties toward the lowest index
- Mistake 3: forgetting to count a request down when it is cancelled
- Step 15: Use the same idea in nginx, HAProxy and Envoy
- nginx
- Reading the table
- A gotcha I hit
- One more caution about worker processes
- HAProxy and Envoy
- Verify the whole thing end to end
- What to take away
- Where to go next
It is not an academic curiosity. nginx has a directive for it, HAProxy has an option for it, and Envoy’s least request balancer uses it when all hosts have equal weight. You will read the documentation of all three in Step 15 and run the nginx version against real backends.
By the end you will have built, run and tested these things yourself:
- a queueing simulator of about 180 lines that you can point at any routing rule, together with a check that it reproduces a textbook formula before you trust it;
- five routing rules (random, round robin, shortest queue, two choices and three choices) and a measured comparison of how long requests spend in the system under each;
- three experiments that break the obvious rules: load numbers that are out of date, many independent balancers, and one sick server;
- a small asyncio balancer class you can put in front of real calls, with 12 tests and a mutation check that proves the tests notice seven planted bugs;
- a run of the same idea through nginx 1.30.6 with one slow backend.
Everything below was run on Python 3.13.14 on Windows 11 on November 5, 2026, with pytest 9.1.1 and nothing else installed. Every output block is copied from those runs. The simulation numbers use fixed seeds, so you should see the same digits on Python 3.13; other Python versions may differ in the last digit. The two experiments that use real time (asyncio and nginx) depend on your machine, so compare the ratios and not the exact milliseconds.
One caution before you start. The simulator is a model. Requests arrive at random, each one takes a random amount of time, and a server handles one request at a time. Real traffic is burstier and real servers often work on many requests at once. The simulation shows what each rule does in this model, and the asyncio and nginx runs show the same direction with real software, but nothing here is a benchmark of any product.
The terms used in this tutorial
- Server (or backend). One machine or process that handles requests. In the model a server handles one request at a time and the others wait in line.
- Request (or job). One unit of work. Its work is how long it takes on a server running at normal speed. The average work is 1, so one time unit in this tutorial is the average time a request needs.
- Queue. The waiting line at one server, served first come, first served.
- Load. The number of requests at a server, waiting or in service. A balancer that counts them calls the number the in-flight count.
- Utilization. The share of capacity in use. At 0.9, requests arrive at 90 percent of the rate the servers can handle on average. High utilization is where small imbalances become long waits.
- Time in system. From the moment a request arrives until it is finished: waiting plus service. This is what a user feels.
- p99. The time that 99 of 100 requests beat. It describes the slow end that users complain about, and it moves much more than the average does.
- Balancer. The code that picks a server for each request.
- Herd effect. Many requests choosing the same server because it looked best a moment ago.
Prerequisites
- Python 3.13, which is what I used. The code needs at least Python 3.11 because of
asyncio.timeout, but I did not test older versions. - A terminal and an empty folder. The commands work on Windows, macOS and Linux; I show both forms of the one command that differs.
- pip, to install pytest. No other package is needed.
- You should know what a function, a class and a list are. You do not need queueing theory: I explain each formula when it first appears.
- Optional, for Step 15: nginx 1.15.1 or newer, the release that added the
randomdirective. I used 1.30.6.
Set up the lab folder
Each code block below starts with a docstring or a comment that names its file. Save the block under that name in one folder. A block whose first line ends with (continued) belongs at the end of the same file as the block before it. These commands create the folder and an isolated Python environment, so nothing you install here touches the rest of your machine:
mkdir lb-lab
cd lb-lab
python -m venv .venv
.venv\Scripts\activate (macOS and Linux: source .venv/bin/activate)
python -m pip install pytest==9.1.1The venv command creates a private copy of Python in .venv. Activating it makes python and pip use that copy. Check that it worked by running python -m pytest --version; it should print pytest 9.1.1.
Step 1: See the idea in 20 lines with balls and bins
Before queues, here is the idea in its simplest form. Throw n balls into n bins one at a time. Each ball may look at d randomly chosen bins and drops into the emptiest of them. The fullest bin at the end is the worst-treated server. With d equal to 1 the ball has no choice, which is random routing.
"""step01_balls.py: throw n balls into n bins and look at the fullest bin."""
import random
def fullest(n, d, seed):
rng = random.Random(seed)
loads = [0] * n
for _ in range(n):
if d == 1:
i = rng.randrange(n)
else:
i = min((rng.randrange(n) for _ in range(d)), key=loads.__getitem__)
loads[i] += 1
return max(loads), loads.count(0) / n
if __name__ == "__main__":
n = 1_000_000
print(f"{n:,} balls into {n:,} bins, five runs each")
print(f"{'choices per ball':<18}{'fullest bin in each run':<28}{'empty bins':>10}")
for d in (1, 2, 3):
runs = [fullest(n, d, seed) for seed in range(1, 6)]
label = f"{d} (random)" if d == 1 else str(d)
print(f"{label:<18}{str([r[0] for r in runs]):<28}{runs[0][1]:>10.1%}")Run it with python step01_balls.py. It takes under 10 seconds, even though it throws a million balls fifteen times.
1,000,000 balls into 1,000,000 bins, five runs each
choices per ball fullest bin in each run empty bins
1 (random) [8, 9, 9, 9, 8] 36.8%
2 [4, 4, 4, 4, 4] 23.9%
3 [3, 3, 3, 3, 3] 17.7%With random placement the fullest bin held 8 or 9 balls, although the average bin holds exactly 1, and about 37 percent of the bins stayed empty. Letting each ball look at just one more bin cut the fullest bin to 4, and a third look cut it to 3. This is the whole story in miniature: random choice wastes capacity (empty bins) and overloads others (the fullest bin) at the same time, and one extra look repairs most of it.
Mitzenmacher’s 2001 paper The Power of Two Choices in Randomized Load Balancing studies the version of this problem with queues, where requests also leave. Its abstract says that having two choices “leads to exponential improvements in the expected time a customer spends in the system over” having one, and that a third choice “is only a constant factor better than” two. You will check both statements with numbers in Step 6. The paper’s Theorem 6 adds that, with two or more choices, the longest queue grows only like log log n divided by log d plus a constant, where n is the number of servers. That is an extremely slow growth.
Step 2: Build the server of the simulator
Now the real experiment. A queue is a waiting line: if a server is busy, a new request waits behind the ones already there. The simulator needs servers that behave like that, and it needs them to be fast, because you will push hundreds of thousands of requests through them.
The trick that keeps the code short is that a first-come, first-served server’s future is settled the moment a request arrives. The request starts when the server finishes everything it already accepted (or right away if it is idle), and it ends after its work divided by the server’s speed. So a server only has to remember the finish time of each request it holds, and nobody has to schedule an event called “request finished”. To ask how many requests are in the system at time t, forget the finish times that are at or before t and count the rest.
Create sim.py with this first block:
"""sim.py: a small queueing simulator for comparing request-routing policies.
Every server is a FIFO queue and requests arrive as a Poisson stream.
A routing policy looks at some view of the servers and picks one of them.
Python 3.13, standard library only.
"""
import random
from collections import deque
from dataclasses import dataclass
class Server:
"""A FIFO server that remembers when each job it accepted will finish."""
def __init__(self, speed=1.0):
self.speed = speed
self.free_at = 0.0 # the moment it finishes everything accepted so far
self.finish_times = deque() # finish time of every job still in the system
def jobs_in_system(self, now):
done = self.finish_times
while done and done[0] <= now: # forget jobs that finished before now
done.popleft()
return len(done)
def work_left(self, now):
return max(0.0, self.free_at - now)
def accept(self, now, work):
finish = max(now, self.free_at) + work / self.speed
self.free_at = finish
self.finish_times.append(finish)
return finishWhat the code does
free_atis the moment the server finishes everything it has accepted so far.acceptuses it to decide when a new request starts.finish_timesholds one finish time per request still in the system. It is adeque, a list that is cheap to shorten from the left, because finished requests are always the oldest ones.jobs_in_system(now)drops the finished requests and returns how many remain. This is the load number a balancer would see.work_left(now)returns how much work is still queued. It is used once, in Step 11, to show what a better load signal would do.speedis 1.0 for a normal server. A server with speed 0.2 needs five times as long for the same work. Step 10 uses one.
A gotcha to remember
The clock only moves forward. jobs_in_system deletes information, so asking about time 5 and then about time 3 gives a wrong answer for time 3. The simulator always asks in time order, and the unit test in Step 13 does too.
Step 3: Write the routing rules
A routing rule, which I will call a policy, is a function. It receives the number of servers n, a function load(i) that returns the load number it is allowed to see for server i, and a random number generator. It returns the index of the chosen server. Keeping the policy this small is what lets the same rule run against fresh numbers, old numbers or a single balancer’s private counts. Add this to sim.py:
# sim.py (continued)
# A policy is a function policy(n, load, rng) -> index of the chosen server.
# `load(i)` returns the load number the policy is allowed to see for server i.
def random_server(n, load, rng):
return rng.randrange(n)
class RoundRobin:
def __init__(self):
self.last = -1
def __call__(self, n, load, rng):
self.last = (self.last + 1) % n
return self.last
def shortest(n, load, rng):
"""Join the shortest queue: look at every server, break ties at random."""
best, ties = None, []
for i in range(n):
value = load(i)
if best is None or value < best:
best, ties = value, [i]
elif value == best:
ties.append(i)
return rng.choice(ties)
def choices(d):
"""Power of d choices: look at d different random servers, take the lightest."""
def pick(n, load, rng):
picks = rng.sample(range(n), d) # d different servers, in random order
return min(picks, key=load) # min keeps the first of equals: a random tie-break
pick.__name__ = f"choices{d}"
return pick
two_choices = choices(2)What each policy does
random_serverignores load and picks any server with equal probability.RoundRobingoes through the servers in order. It is a class because it has to remember where it is. It also ignores load.shortestlooks at every server and picks the one with the smallest load number, choosing at random among ties. A tie is common: when many servers are idle they all show 0.choices(d)builds the power ofdchoices.rng.sample(range(n), d)drawsddifferent servers. The Python documentation says thatrandom.samplewill “Return a k length list of unique elements chosen from the population sequence. Used for random sampling without replacement.” Thenmin(picks, key=load)keeps the one with the smallest load number. When two servers tie,minkeeps the first, and becausesamplereturns them in random order that is a fair coin flip.
Choosing different servers matters, and so does the tie-break. Step 14 plants both mistakes on purpose and measures what each costs.
Step 4: Write the simulation loop
The loop makes requests arrive, asks the policy where each one goes, and records how long each one spends in the system. Add this to sim.py:
# sim.py (continued)
def lognormal_work(sigma):
"""Job sizes with mean exactly 1 whose spread grows with sigma."""
mu = -sigma * sigma / 2
return lambda rng: rng.lognormvariate(mu, sigma)
@dataclass
class Result:
mean: float
p50: float
p99: float
p999: float
peak: int # most jobs ever queued at one server (right after accepting a job)
share0: float # share of all requests that went to server 0
tails: list # fraction of servers holding at least k jobs, k = 1..10
jobs: int
def simulate(policy, n=100, rho=0.9, warmup=500.0, horizon=2500.0, seed=1, speeds=None,
work=None, view="fresh", refresh=1.0, dispatchers=1, metric="count",
probe_every=0):
"""Run one simulation and return a Result.
view "fresh": exact live numbers. "stale": a board refreshed every `refresh` time units.
"local": each of `dispatchers` balancers counts only the requests it sent itself.
metric "count": jobs in the system. "work": time of work left (needs foresight).
"""
rng_a = random.Random(seed) # arrivals and job sizes
rng_p = random.Random(seed + 1_000_003) # the policy's own coin flips
work = work or (lambda r: r.expovariate(1.0))
servers = [Server(s) for s in (speeds or [1.0] * n)]
rate = rho * n # arrivals per time unit (mean work is 1)
board, next_refresh = [0] * n, 0.0
local = [[deque() for _ in range(n)] for _ in range(dispatchers)]
times, sent, peak = [], [0] * n, 0
tail_sum, probes, arrivals, t = [0] * 10, 0, 0, 0.0
while True:
t += rng_a.expovariate(rate)
if t > horizon:
break
arrivals += 1
job = work(rng_a)
if view == "stale":
if t >= next_refresh:
stamp = (t // refresh) * refresh
board = [s.jobs_in_system(stamp) for s in servers]
next_refresh = stamp + refresh
load = board.__getitem__
elif view == "local":
mine = local[rng_a.randrange(dispatchers)]
def load(i):
q = mine[i]
while q and q[0] <= t:
q.popleft()
return len(q)
elif metric == "work":
def load(i):
return servers[i].work_left(t)
else:
def load(i):
return servers[i].jobs_in_system(t)
if probe_every and t > warmup and arrivals % probe_every == 0:
counts = [s.jobs_in_system(t) for s in servers]
for k in range(10):
tail_sum[k] += sum(1 for c in counts if c >= k + 1)
probes += 1
i = policy(n, load, rng_p)
finish = servers[i].accept(t, job)
if view == "local":
mine[i].append(finish)
if t > warmup:
times.append(finish - t)
sent[i] += 1
peak = max(peak, servers[i].jobs_in_system(t))
times.sort()
def q(p):
return times[min(len(times) - 1, int(p * len(times)))]
return Result(mean=sum(times) / len(times), p50=q(0.5), p99=q(0.99), p999=q(0.999),
peak=peak, share0=sent[0] / max(1, sum(sent)),
tails=[x / (probes * n) if probes else 0.0 for x in tail_sum],
jobs=len(times))How it works
- Arrivals. Gaps between arrivals are drawn with
expovariate(rate), which makes arrivals a Poisson stream, the standard model for independent users. The rate isrho * n, so withrhoat 0.9 and 100 servers, 90 requests arrive per time unit. - Job sizes. The default work is exponential with mean 1.
lognormal_workmakes sizes that vary much more; Step 11 uses it. - Two random generators.
rng_adraws arrivals and sizes, andrng_pis for the policy’s own coin flips. Every policy therefore faces exactly the same requests for a given seed, so a difference between two policies comes from the policy and not from luck. - Warm-up. The system starts empty, so the first requests are unrealistically fast. Requests that arrive before
warmupare not counted. - Views. A view decides what numbers the policy may see.
freshis the live truth.staleis a board that is refreshed everyrefreshtime units.localgives each of several balancers only the requests it sent itself. Steps 8 and 9 use the last two. - Result. The function returns the mean, the median, p99, p99.9, the longest queue it ever saw, the share of requests that went to server 0, and, when
probe_everyis set, the share of servers that held at least k requests (Step 7).
The last block of sim.py holds small helpers: averages over seeds and two formulas you will meet in Step 5 and Step 7.
# sim.py (continued)
def avg(results, field):
return sum(getattr(r, field) for r in results) / len(results)
def span(results, field):
values = [getattr(r, field) for r in results]
return min(values), max(values)
def mean_field_time(d, rho, terms=12):
"""Expected time in system for n -> infinity servers with d choices (exponential jobs)."""
if d == 1:
return 1 / (1 - rho)
return sum(rho ** ((d ** i - d) // (d - 1)) for i in range(1, terms))
def mean_field_tail(d, rho, k):
"""Fraction of servers holding at least k jobs when n -> infinity."""
return rho ** ((d ** k - 1) // (d - 1)) if d > 1 else rho ** kStep 5: Check the simulator against a formula before you trust it
A simulator that is wrong looks exactly like one that is right: it prints numbers. The cure is to make it reproduce something you can calculate by hand. Random routing is the one case with an exact answer. If every request goes to a uniformly random server, each server sees its own Poisson stream of requests with an average work of 1. That is the textbook M/M/1 queue: Markovian (Poisson) arrivals, Markovian (exponential) service, one server. For it, Wikipedia’s M/M/1 queue article says that the average response time “does not depend on scheduling discipline and can be computed using Little’s law” as 1 / (mu - lambda). With a service rate of 1 and a utilization of rho that is 1 / (1 - rho). For first-come, first-served service the same article gives the density of the time a request spends in the system as (mu - lambda) * exp(-(mu - lambda) * t). That is an exponential distribution with rate mu - lambda, so its 99th percentile is ln(100) / (1 - rho).
"""step02_validate.py: does random routing match the textbook M/M/1 formulas?"""
import math
import sim
SEEDS = (1, 2, 3)
if __name__ == "__main__":
print("random routing, 50 servers, mean work 1.0, three seeds")
print(f"{'utilization':<13}{'mean (sim)':>11}{'mean (formula)':>16}{'p99 (sim)':>11}{'p99 (formula)':>15}")
for rho in (0.5, 0.9):
rs = [sim.simulate(sim.random_server, n=50, rho=rho, warmup=1000.0, horizon=6000.0, seed=s)
for s in SEEDS]
mean_theory = 1 / (1 - rho)
p99_theory = math.log(100) / (1 - rho)
print(f"{rho:<13}{sim.avg(rs, 'mean'):>11.2f}{mean_theory:>16.2f}"
f"{sim.avg(rs, 'p99'):>11.1f}{p99_theory:>15.1f}")Run python step02_validate.py. It simulates 50 servers for 6,000 time units with three seeds and throws away the first 1,000:
random routing, 50 servers, mean work 1.0, three seeds
utilization mean (sim) mean (formula) p99 (sim) p99 (formula)
0.5 2.00 2.00 9.2 9.2
0.9 9.81 10.00 46.4 46.1At 50 percent utilization the simulation and the formula agree to the digit. At 90 percent the mean is 9.81 against 10.00, within 2 percent, and the p99 is 46.4 against 46.1. I treat that as a pass: at 90 percent the queues are long and slow to settle after the empty start, so a small deviation in either direction is normal. If you ever change the simulator and this table moves by more than a few percent, stop and find out why before looking at any other result.
Step 6: Compare the five rules
Now the main experiment: 100 servers at 90 percent utilization, five policies, three seeds each. The last line prints what the theory says for very many servers. Mitzenmacher’s analysis gives the share of servers that hold at least k requests when each request joins the shortest of d random queues (Step 7 shows it), and Little’s law turns that into an average time in system. The helper mean_field_time in sim.py adds it up.
"""step03_policies.py: five routing policies on 100 servers at 90 percent utilization."""
import sim
SEEDS = (1, 2, 3)
POLICIES = [
("random", lambda: sim.random_server),
("round robin", sim.RoundRobin),
("2 choices", lambda: sim.choices(2)),
("3 choices", lambda: sim.choices(3)),
("shortest queue", lambda: sim.shortest),
]
if __name__ == "__main__":
print("100 servers, utilization 0.9, mean work 1.0, three seeds")
print(f"{'policy':<16}{'mean time':>10}{'seed range':>13}{'p99':>8}{'p99.9':>8}{'fullest queue':>15}")
for name, make in POLICIES:
rs = [sim.simulate(make(), seed=s) for s in SEEDS]
lo, hi = sim.span(rs, "mean")
print(f"{name:<16}{sim.avg(rs, 'mean'):>10.2f}{f'{lo:.2f}-{hi:.2f}':>13}"
f"{sim.avg(rs, 'p99'):>8.1f}{sim.avg(rs, 'p999'):>8.1f}{max(r.peak for r in rs):>15d}")
print("limit for very many servers: "
+ ", ".join(f"d={d}: {sim.mean_field_time(d, 0.9):.3f}" for d in (1, 2, 3)))Run python step03_policies.py. It takes about 10 seconds, most of it spent on the shortest queue rule, which has to look at 100 servers for every request.
100 servers, utilization 0.9, mean work 1.0, three seeds
policy mean time seed range p99 p99.9 fullest queue
random 9.80 9.59-9.99 43.3 57.8 69
round robin 5.20 5.14-5.25 24.8 38.8 55
2 choices 2.64 2.62-2.67 8.9 12.1 7
3 choices 2.07 2.05-2.09 7.4 10.2 5
shortest queue 1.07 1.06-1.08 4.9 7.3 2
limit for very many servers: d=1: 10.000, d=2: 2.614, d=3: 2.028Reading the table
- Random averages 9.80 time units, close to the 10.00 the formula predicts, with a p99 of 43.3. The fullest queue ever seen held 69 requests.
- Round robin averages 5.20, about half of random. It deals requests out evenly, so no server gets an unlucky burst. It still ignores load completely, and Step 10 shows what that costs.
- Two choices averages 2.64, which is 3.7 times lower than random, and the p99 falls from 43.3 to 8.9. The fullest queue ever seen held 7 requests instead of 69. The theory for very many servers says 2.614, so the simulation with 100 servers matches it closely. Mitzenmacher’s paper reports the same: for 100 queues the predictions are “within a few percent of the simulation results”.
- Three choices averages 2.07, a further 22 percent lower, and the theory says 2.028. Going from one choice to two cut the average by a factor of 3.7, while going from two to three cut it by a further 22 percent. That is the abstract’s “exponential improvement” followed by “only a constant factor”.
- Shortest queue averages 1.07 and has the best p99, 4.9. With perfect live numbers and a look at every server, nothing beats it. It is 2.5 times better than two choices on the mean.
That last line deserves care. Envoy’s documentation says the research “has shown that this approach is nearly as good as an O(N) full scan”. In this model, with perfect and instant numbers, the full scan is clearly better than two choices (1.07 against 2.64), so I would describe two choices as most of the benefit at constant cost, not as equally good. Whether the full scan keeps its lead depends on whether the numbers it looks at are perfect and instant. In a real system they never are, and the next three steps take that perfection away.
Check that it worked
Your table should show the same ordering (random, then round robin, then two choices, then three choices, then shortest queue, from slowest to fastest) and the random row within a few percent of 10. If random is far from 10, re-run Step 5 first.
Step 7: See why two choices are enough
The mean hides how the improvement happens, so look at the queues themselves. The simulator can count, at moments chosen as a request arrives, how many servers hold at least k requests. Random arrivals see the same average state as the system has over time, so sampling at arrivals (every 20th one here) is a fair sample. Mitzenmacher’s analysis gives a clean answer for very many servers: with random routing the share of servers holding at least k requests is rho ** k, and with two choices it is rho ** (2 ** k - 1). In general, for d choices, it is rho ** ((d ** k - 1) / (d - 1)). The helper mean_field_tail computes it.
"""step04_tails.py: how many servers hold at least k jobs?"""
import sim
if __name__ == "__main__":
rho = 0.9
one = sim.simulate(sim.random_server, rho=rho, probe_every=20, seed=1)
two = sim.simulate(sim.two_choices, rho=rho, probe_every=20, seed=1)
print("100 servers, utilization 0.9: share of servers holding at least k jobs")
print(f"{'k':<4}{'random':>9}{'rho^k':>9} {'2 choices':>10}{'rho^(2^k-1)':>13}")
for k in range(1, 9):
print(f"{k:<4}{one.tails[k - 1]:>9.4f}{sim.mean_field_tail(1, rho, k):>9.4f} "
f"{two.tails[k - 1]:>10.4f}{sim.mean_field_tail(2, rho, k):>13.4f}")Run python step04_tails.py:
100 servers, utilization 0.9: share of servers holding at least k jobs
k random rho^k 2 choices rho^(2^k-1)
1 0.9009 0.9000 0.9014 0.9000
2 0.8120 0.8100 0.7338 0.7290
3 0.7329 0.7290 0.4884 0.4783
4 0.6619 0.6561 0.2222 0.2059
5 0.5974 0.5905 0.0531 0.0382
6 0.5399 0.5314 0.0048 0.0013
7 0.4875 0.4783 0.0002 0.0000
8 0.4395 0.4305 0.0000 0.0000Reading the table
Random routing gives a geometric decline: each extra request in the queue is 90 percent as likely as the one before. Even 6 or more requests at one server is normal, at 54 percent of the servers. With two choices the decline speeds up with every step. At k = 5 the share is 0.0531 against 0.5974 (11 times fewer servers), and at k = 6 it is 0.0048 against 0.5399 (more than 100 times fewer). The paper’s words for this are that the tails “decrease doubly exponentially” for two or more choices, while with one choice they decrease “only geometrically (or singly exponentially)”.
Here is the intuition. A request can make a queue longer than k only if both of the servers it looked at already hold k requests. That takes two unlucky draws instead of one, and so the tail at each level is roughly the square of the level before, times rho. Squaring repeatedly is what turns a gentle slope into a cliff.
The measured two-choice values sit a little above the formula (0.0531 against 0.0382 at k = 5). That is expected: the formula is the limit for infinitely many servers and this run has 100, and the paper says accuracy improves with more servers and worsens at higher utilization. If your column for random does not follow rho ** k closely, the simulator has a bug.
Step 8: Take away the fresh numbers and watch the herd form
So far the policies saw perfect, live numbers. A real balancer almost never does. It reads a dashboard, a metrics endpoint polled every few seconds, or the last health check. Model that with a board of queue lengths that is refreshed every T time units. Between refreshes every request is routed by the same old numbers.
The experiment runs two policies on the board for each T: shortest queue, which looks at every server, and two choices. Random routing needs no numbers, so it is the fixed reference.
"""step05_stale.py: what happens when the load numbers a balancer sees are old?"""
import sim
SEEDS = (1, 2)
REFRESH = [0.1, 0.5, 1, 2, 5, 10, 20]
if __name__ == "__main__":
print("100 servers, utilization 0.9; the board of queue lengths is refreshed every T time units")
print(f"{'T':<8}{'shortest mean':>14}{'p99':>8} {'2 choices mean':>15}{'p99':>8}")
for T in [None] + REFRESH:
kw = {"view": "fresh"} if T is None else {"view": "stale", "refresh": T}
a = [sim.simulate(sim.shortest, seed=s, **kw) for s in SEEDS]
b = [sim.simulate(sim.two_choices, seed=s, **kw) for s in SEEDS]
label = "live" if T is None else str(T)
print(f"{label:<8}{sim.avg(a, 'mean'):>14.2f}{sim.avg(a, 'p99'):>8.1f} "
f"{sim.avg(b, 'mean'):>15.2f}{sim.avg(b, 'p99'):>8.1f}")
r = [sim.simulate(sim.random_server, seed=s) for s in SEEDS]
print(f"random routing for reference: mean {sim.avg(r, 'mean'):.2f}, p99 {sim.avg(r, 'p99'):.1f}")Run python step05_stale.py. It takes about 30 seconds:
100 servers, utilization 0.9; the board of queue lengths is refreshed every T time units
T shortest mean p99 2 choices mean p99
live 1.07 4.9 2.65 8.9
0.1 1.56 7.2 2.69 9.0
0.5 2.84 11.5 2.82 9.4
1 4.06 15.5 2.99 9.9
2 6.20 22.1 3.27 10.8
5 12.28 41.3 4.04 13.3
10 23.22 83.1 5.12 17.3
20 63.93 506.1 7.12 25.0
random routing for reference: mean 9.90, p99 45.0Reading the table
- With live numbers, shortest queue is far ahead (1.07 against 2.65).
- A board that is only 0.1 time units old, which is nine requests of traffic, already costs shortest queue 46 percent (1.56). Two choices barely notices (2.69).
- At
Tequal to 0.5 the full scan has lost its whole lead: 2.84 against 2.82. At 1.0 it is behind: 4.06 against 2.99. - At 5 time units shortest queue averages 12.28, which is worse than not using the numbers at all (random routing gives 9.90). At 20 its mean is 63.93 and its p99 is 506. Two choices reaches 4.04 at 5 and 7.12 at 20, and it stays better than random across the whole table.
Why the herd forms
After each refresh, a few servers look emptiest. Every balancer decision until the next refresh sees the same picture, so all of the roughly 90 requests per time unit pour into those few servers. Their queues grow, nothing tells the balancer, and the servers that were busy a moment ago drain and sit idle. Shortest queue hunts for the single best server, so it suffers most from the stampede. Two choices herd far less, because each request looks at two servers that it picked at random, so different requests look at different servers and spread out even when the numbers are old. Envoy’s documentation says the same about its P2C mode: it is “particularly useful for load balancer implementations due to its resistance to herding behavior”.
Turn T into your own numbers
Divide the age of your load numbers by the average time a request takes. A metrics poll every 5 seconds against requests that average 100 milliseconds is T equal to 50, far beyond the end of this table. A health check that reports in-flight counts with every response is much fresher, which is one reason balancers that count their own in-flight requests (Step 12) are popular.
Step 9: Run several balancers that cannot see each other
A balancer that counts its own in-flight requests has exact numbers, but only about its own traffic. That is fine with one balancer. In a real system there are often many: one per application instance, one per sidecar proxy, one per region. Each of them sees only the requests it sent. The local view of the simulator models this: each arriving request goes to a random one of k balancers, and each balancer counts only what it sent.
"""step06_dispatchers.py: many balancers, each counting only its own requests."""
import sim
KS = [1, 2, 4, 8, 16, 32, 64]
if __name__ == "__main__":
print("100 servers, utilization 0.9; k balancers share the traffic, each sees only its own requests")
print(f"{'k':<6}{'shortest mean':>14}{'p99':>8} {'2 choices mean':>15}{'p99':>8}")
for k in KS:
a = sim.simulate(sim.shortest, view="local", dispatchers=k, seed=1)
b = sim.simulate(sim.two_choices, view="local", dispatchers=k, seed=1)
print(f"{k:<6}{a.mean:>14.2f}{a.p99:>8.1f} {b.mean:>15.2f}{b.p99:>8.1f}")
r = sim.simulate(sim.random_server, seed=1)
print(f"random routing for reference: mean {r.mean:.2f}, p99 {r.p99:.1f}")Run python step06_dispatchers.py. It takes about 20 seconds:
100 servers, utilization 0.9; k balancers share the traffic, each sees only its own requests
k shortest mean p99 2 choices mean p99
1 1.07 4.9 2.66 8.8
2 1.65 6.2 2.98 9.9
4 2.42 8.2 3.42 11.2
8 3.32 10.9 4.02 13.1
16 4.29 13.9 4.71 15.5
32 5.37 18.0 5.58 19.0
64 6.43 21.6 6.51 22.7
random routing for reference: mean 9.99, p99 44.3Reading the table
- With
kequal to 1 the local view is the live view, and the numbers match Step 6. - Both rules get steadily worse as
kgrows, because each balancer knows less about the whole picture. At 64 balancers each one sends about 1.4 requests per time unit, and with a mean time in system of about 6.4 that leaves only about 9 of its own requests in flight spread over 100 servers (my arithmetic: 90 divided by 64, times 6.43). Its counts are mostly small numbers that say little. - The gap between the two rules shrinks until it vanishes. At 8 balancers it is 3.32 against 4.02; at 64 it is 6.43 against 6.51. When each balancer sees a thin slice of the traffic, how cleverly the rule searches matters less than how little information it has.
- Both stay well below random routing (9.99) even at 64 balancers.
The practical lesson is to keep the number of independent balancers as small as your design allows, or to let the servers report their own load so that every balancer sees the same truth. I did not test either idea here; the table only shows the cost of not doing them.
Step 10: Put one sick server in the fleet
Now a failure that every operator meets. One server in ten is sick: it still answers, but at one fifth of the normal speed. Maybe it has a noisy neighbour, a full disk or a stuck garbage collector. The experiment uses 10 servers at 70 percent utilization by nominal speed, so the fleet as a whole has plenty of spare capacity, and gives server 0 a speed of 0.2.
"""step07_sick.py: one backend runs five times slower than the rest."""
import sim
SEEDS = (1, 2, 3)
KW = dict(n=10, rho=0.7, warmup=100.0, horizon=2000.0)
POLICIES = [
("random", lambda: sim.random_server),
("round robin", sim.RoundRobin),
("2 choices", lambda: sim.choices(2)),
("shortest queue", lambda: sim.shortest),
]
if __name__ == "__main__":
print("10 servers, utilization 0.7 by nominal speed; server 0 runs at speed 0.2")
print(f"{'policy':<16}{'mean':>8}{'p99':>9}{'sick queue peak':>17}{'sent to sick':>14}")
for name, make in POLICIES:
rs = [sim.simulate(make(), speeds=[0.2] + [1.0] * 9, seed=s, **KW) for s in SEEDS]
print(f"{name:<16}{sim.avg(rs, 'mean'):>8.2f}{sim.avg(rs, 'p99'):>9.1f}"
f"{max(r.peak for r in rs):>17d}{sim.avg(rs, 'share0'):>14.1%}")
healthy = [sim.simulate(sim.two_choices, seed=s, **KW) for s in SEEDS]
print(f"2 choices with no sick server: mean {sim.avg(healthy, 'mean'):.2f}, "
f"p99 {sim.avg(healthy, 'p99'):.1f}")Run python step07_sick.py. It takes about a second:
10 servers, utilization 0.7 by nominal speed; server 0 runs at speed 0.2
policy mean p99 sick queue peak sent to sick
random 261.70 4502.2 1019 9.9%
round robin 260.49 4433.9 1029 10.0%
2 choices 2.29 16.5 7 2.9%
shortest queue 1.42 8.4 4 2.7%
2 choices with no sick server: mean 1.65, p99 6.8Reading the table
Random routing and round robin are both a disaster, and for the same reason. They send the sick server a tenth of the traffic (9.9 and 10.0 percent), which is 0.7 requests per time unit, while it can finish only 0.2. The difference piles up at 0.5 requests per time unit, so over the 2,000 time units of the run about 1,000 requests are waiting there, and the table shows peak queues above 1,000 and a p99 above 4,000. This is not a statistic that settles down. It is a ramp: a longer run gives a worse number, and in production the queue would only stop growing when something timed out or crashed.
Two choices and shortest queue never let that happen. The sick server’s queue peaked at 7 and 4 requests, and it received only 2.9 and 2.7 percent of the traffic, because its queue was usually longer than that of the server it was compared with. Nothing in the rule knows that the server is sick. It only counts requests, and a slow server’s count rises faster.
The limit of this signal
The last line of the table is the honest one. With no sick server at all, two choices gives a mean of 1.65 and a p99 of 6.8. With the sick server it gives 2.29 and 16.5. Why does the sick server still cost something? A request that lands on an empty sick server looks just as attractive as one that lands on an empty healthy server, since both show a queue length of zero, but it takes five times as long. A queue length cannot see slowness until a queue forms. That is why production setups usually add health checks and automatic ejection on top of the picking rule (nginx, for example, can mark a server unavailable after failed attempts, as the max_fails and fail_timeout parameters of its upstream module describe), and why some balancers also weigh recent latency. This tutorial adds an ejection list to the asyncio balancer in Step 12, but it does not build latency weighting.
Step 11: Notice when counting requests is the wrong measure
A request count treats all requests as equal. If job sizes vary a lot, one server with three huge requests is busier than another with three tiny ones, but both show a load of 3. The last simulation uses job sizes that vary much more than before: lognormal_work(1.2) still has a mean of 1, but its squared coefficient of variation (the variance divided by the square of the mean) is 3.22, so the standard deviation is 1.8 times the mean. The experiment lets two choices and shortest queue look at either the request count or the work left, which is the one place work_left from Step 2 is used.
"""step08_heavy.py: when jobs differ a lot in size, a job count is a poor measure of load."""
import math
import sim
SEEDS = (1, 2)
SIGMA = 1.2
KW = dict(rho=0.8, work=sim.lognormal_work(SIGMA))
if __name__ == "__main__":
cv2 = math.exp(SIGMA ** 2) - 1
print(f"100 servers, utilization 0.8, job sizes lognormal (mean 1, squared variation {cv2:.2f})")
print(f"{'policy':<28}{'mean':>8}{'p99':>8}")
rows = [
("random", sim.random_server, "count"),
("2 choices, job count", sim.two_choices, "count"),
("2 choices, work left", sim.two_choices, "work"),
("shortest queue, job count", sim.shortest, "count"),
("shortest queue, work left", sim.shortest, "work"),
]
for name, policy, metric in rows:
rs = [sim.simulate(policy, metric=metric, seed=s, **KW) for s in SEEDS]
print(f"{name:<28}{sim.avg(rs, 'mean'):>8.2f}{sim.avg(rs, 'p99'):>8.1f}")Run python step08_heavy.py. It takes about 10 seconds:
100 servers, utilization 0.8, job sizes lognormal (mean 1, squared variation 3.22)
policy mean p99
random 9.25 59.2
2 choices, job count 2.50 16.3
2 choices, work left 1.83 9.9
shortest queue, job count 1.01 8.1
shortest queue, work left 1.00 8.0Reading the table
Two choices improves from a mean of 2.50 to 1.83 (27 percent lower) and from a p99 of 16.3 to 9.9 (39 percent lower) when it can see the work left instead of the request count. Shortest queue barely changes, because at 80 percent utilization a scan over 100 servers almost always finds an idle one, so the count and the work agree on the answer.
Be careful with what this shows. The simulator knows each job’s size the moment the job arrives, and a real balancer does not. A real system can only estimate: for example from the size of the request body, or from a per-route average. So the takeaway is not a recipe. It is that when sizes vary a lot, a better load signal than a plain count is worth looking for, and that the cheap rule benefits more from a better signal than the expensive one does.
Step 12: Put the idea into an asyncio program
A simulator is for understanding. Code that serves real traffic needs a balancer object it can ask for a backend. In an asyncio program the cleanest shape is a class with two methods: pick() chooses a backend, and lease() is an async context manager, the thing you use with async with. It picks a backend, counts the request as in flight, and counts it down again when the block ends. The count-down sits in a finally clause, so it runs even when the call fails or a timeout cancels it. The Python documentation says that Task.cancel() “arranges for a CancelledError exception to be thrown into the wrapped coroutine on the next cycle of the event loop” and that the coroutine “has a chance to clean up”. A finally clause is that chance.
Create balancer.py:
"""balancer.py: client-side balancers for asyncio programs.
A balancer chooses a backend for each request and counts the requests in flight.
Python 3.13, standard library only.
"""
import contextlib
import random
class Balancer:
"""Base class: keeps the in-flight counts and the list of ejected backends."""
def __init__(self, backends, d=2, rng=None):
self.backends = list(backends)
self.d = d
self.rng = rng or random.Random()
self.inflight = {b: 0 for b in self.backends}
self.ejected = set() # backends a health check has taken out of rotation
self.turn = -1
def choose(self, pool):
raise NotImplementedError
def pick(self):
pool = [b for b in self.backends if b not in self.ejected]
if not pool:
raise RuntimeError("no backend is available")
return self.choose(pool)
@contextlib.asynccontextmanager
async def lease(self):
"""Pick a backend and count the request as in flight until the block ends."""
backend = self.pick()
self.inflight[backend] += 1
try:
yield backend
finally:
self.inflight[backend] -= 1
class PowerOfD(Balancer):
def choose(self, pool):
picks = self.rng.sample(pool, min(self.d, len(pool))) # different backends
return min(picks, key=self.inflight.__getitem__)
class RoundRobin(Balancer):
def choose(self, pool):
self.turn += 1
return pool[self.turn % len(pool)]
class RandomPick(Balancer):
def choose(self, pool):
return self.rng.choice(pool)What the code does
- The base class keeps the in-flight count of every backend and a set of ejected backends, which a health checker would fill.
pick()removes ejected backends first and refuses to continue when none is left, because an empty list should be a loud error and not a quietIndexErrordeeper in. PowerOfD.chooseis Step 3’s rule.min(self.d, len(pool))lets it keep working when only one or two backends are left.RoundRobinandRandomPickare here only for the comparison below.- asyncio runs your code on one thread and only switches at an
await, soself.inflight[backend] += 1cannot be interrupted halfway. If you use threads instead, protect the counts with a lock; this class is written for asyncio only.
Run it against a slow backend
The next script is the real-time version of Step 10. Eight fake backends each handle one request at a time, using an asyncio.Lock. The documentation says that “Acquiring a lock is fair: the coroutine that proceeds will be the first coroutine that started waiting on the lock”, which is first come, first served, as in the simulator. h7 is five times slower. 400 requests arrive at 50 per second with an average work of 0.1 seconds. Arrival times are computed as absolute offsets from the start, because a loop that sleeps for each gap tends to drift: each asyncio.sleep usually returns slightly late and the delays add up.
"""step09_asyncio.py: the same idea in a real asyncio program with one slow backend."""
import asyncio
import random
import time
from balancer import PowerOfD, RandomPick, RoundRobin
SPEEDS = [1.0] * 7 + [0.2] # backend h7 is five times slower
MEAN_WORK, RATE, REQUESTS = 0.1, 50.0, 400
class FakeBackend:
def __init__(self, speed):
self.speed = speed
self.lock = asyncio.Lock() # one request at a time, first come first served
async def handle(self, work):
async with self.lock:
await asyncio.sleep(work / self.speed)
async def run(make_balancer, seed=7):
rng = random.Random(seed)
names = [f"h{i}" for i in range(len(SPEEDS))]
backends = {name: FakeBackend(s) for name, s in zip(names, SPEEDS)}
balancer = make_balancer(names)
latencies, served = [], dict.fromkeys(names, 0)
async def one_request(work):
start = time.perf_counter()
async with balancer.lease() as name:
served[name] += 1
await backends[name].handle(work)
latencies.append(time.perf_counter() - start)
t0, at, tasks = time.perf_counter(), 0.0, []
for _ in range(REQUESTS):
at += rng.expovariate(RATE) # absolute arrival times: no drift
await asyncio.sleep(max(0.0, at - (time.perf_counter() - t0)))
tasks.append(asyncio.create_task(one_request(rng.expovariate(1.0 / MEAN_WORK))))
await asyncio.gather(*tasks)
latencies.sort()
return latencies, served
def report(label, latencies, served):
q = lambda p: latencies[int(p * (len(latencies) - 1))]
print(f"{label:<14}{q(0.5) * 1000:>9.0f}{q(0.99) * 1000:>9.0f}{latencies[-1] * 1000:>9.0f}"
f"{served['h7'] / REQUESTS:>13.1%}")
if __name__ == "__main__":
print(f"{REQUESTS} requests, {RATE:.0f} per second, 8 backends, h7 five times slower (times in ms)")
print(f"{'policy':<14}{'p50':>9}{'p99':>9}{'slowest':>9}{'sent to h7':>13}")
makers = [
("random", lambda names: RandomPick(names, rng=random.Random(1))),
("round robin", lambda names: RoundRobin(names)),
("2 choices", lambda names: PowerOfD(names, d=2, rng=random.Random(1))),
]
for label, make in makers:
lat, served = asyncio.run(run(make))
report(label, lat, served)Run python step09_asyncio.py. It takes about a minute, because the real clock is running and the first two policies leave a long queue behind on h7:
400 requests, 50 per second, 8 backends, h7 five times slower (times in ms)
policy p50 p99 slowest sent to h7
random 305 16484 18777 11.2%
round robin 208 16619 17454 12.5%
2 choices 177 1703 2342 4.5%Reading the table
The pattern of Step 10 is back, in real time. Random routing and round robin both send h7 its fair share or more (11.2 and 12.5 percent), and its queue grows for as long as the test runs, so the p99 is about 16.5 seconds and the slowest request waited more than 17 seconds. Two choices sent it only 4.5 percent, and its p99 is 1.7 seconds, about ten times lower. Your digits will differ by some percent from run to run, because they depend on the timers of your machine, but the gap between the rows that are close to 16 seconds and the row that is close to 2 seconds should hold. If it does not, run the script again before suspecting the code.
Step 13: Test it, then break it on purpose
Balancing bugs are quiet. The system keeps answering requests, only a bit worse, and nothing crashes to tell you. That is the situation where tests earn their keep, and also the situation where tests can lie by passing for the wrong reason. So this step has two halves: write the tests, then plant bugs and check that the tests notice.
Create test_routing.py:
"""test_routing.py: unit tests for the policies, the simulator and the asyncio balancer."""
import asyncio
import random
import pytest
import sim
from balancer import PowerOfD
def view(values):
return values.__getitem__
def test_two_choices_uses_two_different_servers_and_takes_the_lighter():
rng = random.Random(1)
for _ in range(300):
assert sim.two_choices(2, view([5, 1]), rng) == 1
assert sim.two_choices(2, view([1, 5]), rng) == 0
def test_two_choices_breaks_ties_at_random():
rng = random.Random(2)
counts = [0, 0]
for _ in range(2000):
counts[sim.two_choices(2, view([3, 3]), rng)] += 1
assert 800 < counts[0] < 1200
def test_shortest_picks_the_minimum_and_breaks_ties_at_random():
rng = random.Random(3)
assert sim.shortest(4, view([3, 0, 2, 5]), rng) == 1
assert {sim.shortest(4, view([0, 0, 0, 0]), rng) for _ in range(200)} == {0, 1, 2, 3}
def test_round_robin_visits_every_server_in_turn():
rr = sim.RoundRobin()
assert [rr(3, view([0, 0, 0]), None) for _ in range(7)] == [0, 1, 2, 0, 1, 2, 0]
def test_server_finish_times_follow_arrival_order():
s = sim.Server()
assert s.accept(0.0, 2.0) == 2.0
assert s.accept(1.0, 1.0) == 3.0 # waits for the first job
assert s.jobs_in_system(1.5) == 2 # ask in time order: the clock only moves forward
assert s.jobs_in_system(2.5) == 1
assert s.jobs_in_system(3.5) == 0
assert s.accept(5.0, 1.0) == 6.0 # arrives after the server went idle
assert s.work_left(5.5) == pytest.approx(0.5)
def test_a_slow_server_stretches_the_work():
assert sim.Server(speed=0.5).accept(0.0, 1.0) == 2.0
def test_balancer_prefers_the_lighter_backend():
b = PowerOfD(["a", "b"], rng=random.Random(5))
b.inflight["a"] = 7
assert {b.pick() for _ in range(100)} == {"b"}
def test_balancer_never_picks_an_ejected_backend():
b = PowerOfD(["a", "b", "c"], rng=random.Random(6))
b.ejected.add("c")
assert "c" not in {b.pick() for _ in range(200)}
def test_inflight_count_returns_to_zero_after_an_exception():
async def main():
b = PowerOfD(["a", "b", "c"], rng=random.Random(1))
with pytest.raises(RuntimeError):
async with b.lease():
raise RuntimeError("boom")
assert sum(b.inflight.values()) == 0
asyncio.run(main())
def test_inflight_count_returns_to_zero_after_cancellation():
async def main():
b = PowerOfD(["a", "b"], rng=random.Random(1))
async def call():
async with b.lease():
await asyncio.sleep(10)
task = asyncio.create_task(call())
await asyncio.sleep(0.05)
assert sum(b.inflight.values()) == 1
task.cancel()
with pytest.raises(asyncio.CancelledError):
await task
assert sum(b.inflight.values()) == 0
asyncio.run(main())
def test_random_routing_matches_the_mm1_formula():
r = sim.simulate(sim.random_server, n=20, rho=0.5, warmup=500.0, horizon=4000.0, seed=7)
assert r.mean == pytest.approx(2.0, rel=0.08)
def test_two_choices_beats_random_by_a_wide_margin_at_high_load():
r = sim.simulate(sim.two_choices, n=50, rho=0.9, warmup=300.0, horizon=1500.0, seed=3)
assert r.mean < 4.0 # random routing would give about 10What the tests check
- The policy tests use tiny cases where the right answer is certain. With two servers,
two_choicesmust always look at both, so it must always return the lighter one. Ties must split about evenly.shortestmust find the minimum and reach every server when all are tied. - The server test checks finish times by hand: a job that waits behind another, and a job that arrives after the server went idle. It asks about times in increasing order, as the gotcha in Step 2 requires.
- The balancer tests cover the rules a real program depends on: the lighter backend wins, ejected backends are never picked, and the in-flight count returns to zero after an exception and after a cancellation.
- Two slower tests tie the simulator to the theory: random routing must match the M/M/1 formula within 8 percent, and two choices must beat 4.0 where random routing would give about 10.
Run python -m pytest -q:
............ [100%]
12 passed in 0.24sPlant seven bugs and see whether the tests notice
A test suite that cannot fail proves nothing. Mutation testing checks the tests by changing the code a little, one bug at a time, and running the tests against the broken copy. Every broken copy should fail at least one test. The script below copies three files to a temporary folder, applies one text replacement, runs pytest, and reports whether it failed. It asserts that each pattern occurs exactly once, so a typo in the script cannot pass quietly.
"""mutations.py: plant one bug at a time and check that the tests notice."""
import pathlib
import shutil
import subprocess
import sys
import tempfile
HERE = pathlib.Path(__file__).parent
FILES = ["sim.py", "balancer.py", "test_routing.py"]
MUTANTS = [
("sample with replacement (the same server can be drawn twice)", "sim.py",
"picks = rng.sample(range(n), d) ", "picks = [rng.randrange(n) for _ in range(d)] "),
("take the heavier of the two choices", "sim.py",
"return min(picks, key=load) ", "return max(picks, key=load) "),
("break ties toward the lowest index", "sim.py",
"return rng.choice(ties)", "return ties[0]"),
("ignore idle time when a job arrives", "sim.py",
"finish = max(now, self.free_at) + work / self.speed", "finish = self.free_at + work / self.speed"),
("never decrement the in-flight count on error or cancel", "balancer.py",
" try:\n yield backend\n finally:\n self.inflight[backend] -= 1",
" yield backend\n self.inflight[backend] -= 1"),
("route to ejected backends", "balancer.py",
"pool = [b for b in self.backends if b not in self.ejected]", "pool = list(self.backends)"),
("ignore the in-flight counts", "balancer.py",
"return min(picks, key=self.inflight.__getitem__)", "return picks[0]"),
]
if __name__ == "__main__":
caught = 0
for number, (label, name, old, new) in enumerate(MUTANTS, 1):
with tempfile.TemporaryDirectory() as tmp:
for f in FILES:
shutil.copy(HERE / f, tmp)
path = pathlib.Path(tmp) / name
text = path.read_text(encoding="utf-8")
assert text.count(old) == 1, f"mutant {number}: pattern must occur once"
path.write_text(text.replace(old, new), encoding="utf-8")
run = subprocess.run([sys.executable, "-m", "pytest", "-x", "-q", "-p", "no:cacheprovider",
"test_routing.py"], cwd=tmp, capture_output=True, text=True)
failed = run.returncode != 0
caught += failed
print(f"mutant {number}: {'caught' if failed else 'MISSED'} {label}")
print(f"caught {caught} of {len(MUTANTS)}")Run python mutations.py:
mutant 1: caught sample with replacement (the same server can be drawn twice)
mutant 2: caught take the heavier of the two choices
mutant 3: caught break ties toward the lowest index
mutant 4: caught ignore idle time when a job arrives
mutant 5: caught never decrement the in-flight count on error or cancel
mutant 6: caught route to ejected backends
mutant 7: caught ignore the in-flight counts
caught 7 of 7All seven bugs were caught. If you add a rule or change one, add a mutant for it as well. A mutant that survives means a test is missing, and that is information you did not have before.
Step 14: Meet three bugs that look harmless
Three of the mutants deserve a closer look, because each is the kind of mistake that survives code review. The script below measures what each one costs. It reuses the simulator for the first two and the real PowerOfD class for the third.
"""step10_mistakes.py: three bugs that look harmless, and what each one costs."""
import asyncio
import contextlib
import random
import sim
from balancer import PowerOfD
def with_replacement(d):
def pick(n, load, rng):
picks = [rng.randrange(n) for _ in range(d)] # the same server can come up twice
return min(picks, key=load)
return pick
def lowest_index_ties(n, load, rng):
return min(range(n), key=load) # min keeps the first of equals
def counted(policy, tally):
def wrapped(n, load, rng):
i = policy(n, load, rng)
tally[i] += 1
return i
return wrapped
class LeakyBalancer(PowerOfD):
@contextlib.asynccontextmanager
async def lease(self):
backend = self.pick()
self.inflight[backend] += 1
yield backend # no try/finally: a cancelled call never reaches the next line
self.inflight[backend] -= 1
async def drive(balancer, requests=1000, stuck_for=200):
hits = {"stuck": 0, "recovered": 0}
for k in range(requests):
phase = "stuck" if k < stuck_for else "recovered"
try:
async with asyncio.timeout(0.02):
async with balancer.lease() as name:
if name == "h3":
hits[phase] += 1
if phase == "stuck":
await asyncio.sleep(1) # the timeout cancels this call
except TimeoutError:
pass
return hits
if __name__ == "__main__":
print("Mistake 1: choose with replacement (utilization 0.9, mean time in system, 3 seeds)")
print(f"{'servers':<9}{'two different':>14}{'with replacement':>18}")
for n, horizon in ((4, 20000.0), (10, 8000.0), (100, 2500.0)):
kw = dict(n=n, warmup=horizon / 5, horizon=horizon)
a = [sim.simulate(sim.two_choices, seed=s, **kw) for s in (1, 2, 3)]
b = [sim.simulate(with_replacement(2), seed=s, **kw) for s in (1, 2, 3)]
print(f"{n:<9}{sim.avg(a, 'mean'):>14.2f}{sim.avg(b, 'mean'):>18.2f}")
print("\nMistake 2: break ties toward the lowest index (shortest queue, 100 servers, utilization 0.3)")
for label, policy in (("random ties", sim.shortest), ("lowest index", lowest_index_ties)):
tally = [0] * 100
r = sim.simulate(counted(policy, tally), rho=0.3, seed=1)
total = sum(tally)
print(f"{label:<14} server 0 gets {tally[0] / total:.2%}, server 99 gets {tally[99] / total:.2%}"
f" (fair share 1.00%), mean {r.mean:.2f}, fullest queue {r.peak}")
print("\nMistake 3: forget to count a request down when it is cancelled")
for label, cls in (("with try/finally", PowerOfD), ("without", LeakyBalancer)):
balancer = cls(["h0", "h1", "h2", "h3"], rng=random.Random(1))
hits = asyncio.run(drive(balancer))
print(f"{label:<17} h3 got {hits['stuck']:>3} of the first 200 requests while it was stuck, "
f"{hits['recovered']:>3} of the next 800 after it recovered; in flight now: {balancer.inflight}")Run python step10_mistakes.py:
Mistake 1: choose with replacement (utilization 0.9, mean time in system, 3 seeds)
servers two different with replacement
4 3.71 4.01
10 2.96 3.11
100 2.64 2.66
Mistake 2: break ties toward the lowest index (shortest queue, 100 servers, utilization 0.3)
random ties server 0 gets 1.01%, server 99 gets 1.01% (fair share 1.00%), mean 1.01, fullest queue 1
lowest index server 0 gets 3.20%, server 99 gets 0.00% (fair share 1.00%), mean 1.01, fullest queue 1
Mistake 3: forget to count a request down when it is cancelled
with try/finally h3 got 43 of the first 200 requests while it was stuck, 197 of the next 800 after it recovered; in flight now: {'h0': 0, 'h1': 0, 'h2': 0, 'h3': 0}
without h3 got 1 of the first 200 requests while it was stuck, 0 of the next 800 after it recovered; in flight now: {'h0': 0, 'h1': 0, 'h2': 0, 'h3': 1}Mistake 1: choosing with replacement
Drawing the two servers independently, so that the same server can come up twice, is the easy way to write the code. In that case the “choice” is no choice at all. With 4 servers it happens a quarter of the time and the mean time in system is 8 percent worse (4.01 against 3.71). With 10 servers it is 5 percent worse, and with 100 servers it is 1 percent. Fleets of 4 to 10 backends are common, so this is not a rounding error. Mitzenmacher’s model draws with replacement and the paper states that “our results also hold with minor variations if the d queues are chosen without replacement”, but for its own simulations it says that “choices were made without replacement as this method is more likely to be used in practice”. Do the same: rng.sample instead of repeated randrange.
Mistake 2: breaking ties toward the lowest index
When several servers show the same load, the easy tie-break is the first one in the list. At 30 percent utilization many servers are idle at any moment, so ties are everywhere. With random tie-breaking every server gets 1 percent of the requests. With lowest-index tie-breaking server 0 gets 3.20 percent and server 99 gets 0.00 percent. At 30 requests per time unit in total, 3.20 percent means server 0 receives 0.96 requests per time unit, so it is busy about 96 percent of the time while the end of the list sits idle (my arithmetic). The mean time does not change, which is why nobody notices. What does change is that the same few servers do all the work and the others never warm their caches. The nginx documentation handles ties on purpose: for least_conn it says “If there are several such servers, they are tried in turn using a weighted round-robin balancing method.”
Mistake 3: forgetting to count a request down when it is cancelled
The leaky balancer in the script is PowerOfD with the try and finally removed. The driver sends requests one at a time through four backends and wraps each in a 20 millisecond timeout. For the first 200 requests backend h3 is stuck and every request that reaches it times out. Then it recovers. The correct balancer gave h3 43 of the first 200 requests, wasting a timeout on each, and then 197 of the next 800 once it recovered, about a quarter, which is its fair share. The leaky balancer gave it 1 of the first 200 and none of the next 800. One cancelled request left the count of h3 at 1 forever, every other backend sat at 0, and in every comparison h3 looked busier. One leaked count was enough to take a healthy backend out of rotation for good, with no error anywhere. The fix is the finally clause, and the test for it is test_inflight_count_returns_to_zero_after_cancellation from Step 13.
Step 15: Use the same idea in nginx, HAProxy and Envoy
You rarely write the balancer yourself. The popular proxies already have the rule, and each documents it.
nginx
The nginx upstream module documents random [two [method]] and says that the directive appeared in version 1.15.1. “The optional two parameter instructs nginx to randomly select two servers and then choose a server using the specified method. The default method is least_conn which passes a request to a server with the least number of active connections.” The config below is the one I tested on nginx 1.30.6 (the stable release at the time of writing), Windows build. It defines the same four backends three times: with the default round robin, with least_conn (which looks at every server) and with random two least_conn (the power of two choices).
worker_processes 1;
error_log logs/error.log;
pid logs/nginx.pid;
events {
worker_connections 256;
}
http {
access_log off;
upstream round_robin { # the default method
server 127.0.0.1:18081;
server 127.0.0.1:18082;
server 127.0.0.1:18083;
server 127.0.0.1:18084;
}
upstream fewest { # every server is checked
least_conn;
server 127.0.0.1:18081;
server 127.0.0.1:18082;
server 127.0.0.1:18083;
server 127.0.0.1:18084;
}
upstream two_choices { # two random servers, then the one with fewer active connections
random two least_conn;
server 127.0.0.1:18081;
server 127.0.0.1:18082;
server 127.0.0.1:18083;
server 127.0.0.1:18084;
}
server {
listen 127.0.0.1:18080;
location /round_robin/ { proxy_pass http://round_robin/; }
location /fewest/ { proxy_pass http://fewest/; }
location /two_choices/ { proxy_pass http://two_choices/; }
}
}The test script starts four real backends on ports 18081 to 18084, each handling one request at a time, as the servers in the simulator do. The first three need 0.05 seconds per request and the fourth needs 0.2 seconds. It copies the config, asks nginx to check it with nginx -t, starts nginx, and lets 16 client threads send 200 requests through each of the three upstream groups.
"""nginx_test.py: try the three upstream methods of nginx.conf against four real backends.
Usage: python nginx_test.py C:/path/to/nginx-1.30.6
Backends 1 to 3 take 0.05 s per request, backend 4 takes 0.2 s. Each backend serves one
request at a time, like the servers in the simulator. Sixteen clients keep 16 requests going.
"""
import http.server
import pathlib
import shutil
import subprocess
import sys
import threading
import time
import urllib.request
from concurrent.futures import ThreadPoolExecutor
HERE = pathlib.Path(__file__).parent
DELAYS = {18081: 0.05, 18082: 0.05, 18083: 0.05, 18084: 0.2}
REQUESTS, CLIENTS = 200, 16
class OneAtATime(http.server.HTTPServer):
request_queue_size = 128 # a long waiting line, so the OS never refuses a connection
def start_backend(port, delay):
class Handler(http.server.BaseHTTPRequestHandler):
protocol_version = "HTTP/1.0"
def do_GET(self):
time.sleep(delay)
body = f"backend {port}".encode()
self.send_response(200)
self.send_header("Content-Length", str(len(body)))
self.end_headers()
self.wfile.write(body)
def log_message(self, *args):
pass
server = OneAtATime(("127.0.0.1", port), Handler) # one request at a time
threading.Thread(target=server.serve_forever, daemon=True).start()
def one_request(path):
start = time.perf_counter()
with urllib.request.urlopen(f"http://127.0.0.1:18080/{path}/", timeout=60) as r:
who = r.read().decode()
return who, time.perf_counter() - start
if __name__ == "__main__":
nginx_dir = pathlib.Path(sys.argv[1])
prefix = HERE / "nginx_run"
shutil.rmtree(prefix, ignore_errors=True)
for sub in ("conf", "logs", "temp"):
(prefix / sub).mkdir(parents=True)
shutil.copy(HERE / "nginx.conf", prefix / "conf" / "nginx.conf")
exe = str(nginx_dir / "nginx.exe")
print(subprocess.run([exe, "-v"], capture_output=True, text=True).stderr.strip())
check = subprocess.run([exe, "-t", "-p", str(prefix), "-c", "conf/nginx.conf"],
capture_output=True, text=True)
print((check.stdout + check.stderr).strip().replace(str(prefix), "<prefix>"))
for port, delay in DELAYS.items():
start_backend(port, delay)
proc = subprocess.Popen([exe, "-p", str(prefix), "-c", "conf/nginx.conf"])
time.sleep(1.0)
try:
print(f"\n{REQUESTS} requests, {CLIENTS} clients at a time; backend 18084 is four times slower")
print(f"{'upstream method':<22}{'sent to 18084':>14}{'seconds':>9}{'p50 ms':>9}{'p99 ms':>9}")
for path in ("round_robin", "fewest", "two_choices"):
t0 = time.perf_counter()
with ThreadPoolExecutor(CLIENTS) as pool:
results = list(pool.map(one_request, [path] * REQUESTS))
total = time.perf_counter() - t0
lat = sorted(r[1] for r in results)
slow = sum(1 for who, _ in results if who.endswith("18084")) / REQUESTS
print(f"{path:<22}{slow:>14.1%}{total:>9.1f}{lat[len(lat) // 2] * 1000:>9.0f}"
f"{lat[int(0.99 * (len(lat) - 1))] * 1000:>9.0f}")
finally:
subprocess.run([exe, "-s", "stop", "-p", str(prefix), "-c", "conf/nginx.conf"], capture_output=True)
proc.terminate()Run it with the folder of your unpacked nginx, for example python nginx_test.py C:/tools/nginx-1.30.6:
nginx version: nginx/1.30.6
nginx: the configuration file <prefix>/conf/nginx.conf syntax is ok
nginx: configuration file <prefix>/conf/nginx.conf test is successful
200 requests, 16 clients at a time; backend 18084 is four times slower
upstream method sent to 18084 seconds p50 ms p99 ms
round_robin 25.0% 10.1 84 3046
fewest 9.0% 3.6 206 819
two_choices 9.5% 3.8 205 988Reading the table
nginx -taccepted the config, includingrandom two least_conn;.- Round robin sent a quarter of the requests (25.0 percent) to the slow backend, exactly its share by count. The slow backend alone needed 50 requests times 0.2 seconds, which is 10 seconds, and the run took 10.1 seconds. The p99 was 3,046 milliseconds.
least_connandrandom two least_connsent it 9.0 and 9.5 percent, finished in 3.6 and 3.8 seconds (about 2.7 times faster than round robin), and cut the p99 to 819 and 988 milliseconds. Two choices finished within 6 percent of the full scan’s time (3.8 against 3.6 seconds), with a somewhat higher p99 (988 against 819 milliseconds).- The medians say the opposite: 84 milliseconds for round robin against 206 and 205. This is a property of a test in which 16 clients wait for answers. With round robin, many of the clients are stuck in the slow backend’s line at any moment, so the three fast backends are mostly idle. The load-aware methods spread the 16 requests in flight over all four backends, roughly four each, so a typical request waits behind about three others on a fast backend (my reading of the medians). What users feel is the tail and the total time, where the load-aware methods win clearly. This is also a reminder to look at p99 and not only at the median.
- Even at 9 percent, the slow backend’s 18 or 19 requests took 3.6 to 3.8 seconds, which is exactly how long each run took. Counting connections cannot keep a slow backend out of the rotation entirely, which is the limit that Step 10 showed.
A gotcha I hit
In my first run, round robin sent only about 10 percent of the requests to the slow backend instead of 25. Python’s HTTPServer keeps a waiting line of usually 5 connections (the socketserver documentation says “The default value is usually 5” and that once the queue is full, further requests from clients get a “Connection denied” error), and the slow backend’s waiting line grew longer than that. The nginx error log showed the symptom, one line for each refused connection to the slow backend: connect() failed (10061: No connection could be made because the target machine actively refused it) while connecting to upstream. The upstream documentation says that a server is considered unavailable for fail_timeout (10 seconds by default) once max_fails unsuccessful attempts (1 by default) have happened. My reading of the log and of those defaults is that nginx took the slow backend out of rotation for stretches of 10 seconds and sent its requests elsewhere, which is how it ended up with 10 percent and not 25, but I did not confirm that beyond the log. Setting request_queue_size = 128 on the backend gave the expected 25 percent, and the comment in the script says why. If your own test gives a share that does not match the algorithm, check the error log and the backends before you blame the policy.
One more caution about worker processes
nginx on Linux normally runs several worker processes, and the docs for zone describe it as “the shared memory zone that keeps the group’s configuration and run-time state that are shared between worker processes”. My test config sets worker_processes 1;, so I tested a single worker only. Read the documentation for zone and test your own worker count before you rely on connection counts across workers.
HAProxy and Envoy
I did not run these two, so what follows is the documentation, not a measurement. The HAProxy 3.2 configuration manual documents balance random(<draws>). It says that when the argument is present it is “indicating the number of draws before selecting the least loaded of these servers”, and that “picking the least loaded of two servers is enough to significantly improve the fairness of the algorithm”. So balance random(2) in a backend section is the power of two choices.
Envoy’s load balancer overview says that when all weights are equal, the weighted least request balancer uses “an O(1) algorithm which selects N random available hosts as specified in the configuration (2 by default) and picks the host which has the fewest active requests”. That is the same rule with the same default.
Verify the whole thing end to end
The last script runs every step, saves each output in an out folder, then runs the tests, the mutants and, if you pass the nginx folder, the nginx test. The simulations are independent, so it starts them together. The two real-time experiments run one at a time afterwards so that they do not compete for the processor.
"""run_all.py: run every step, save the outputs in out/, then the tests and the mutants."""
import pathlib
import subprocess
import sys
HERE = pathlib.Path(__file__).parent
OUT = HERE / "out"
OUT.mkdir(exist_ok=True)
PARALLEL = ["step01_balls", "step02_validate", "step03_policies", "step04_tails",
"step05_stale", "step06_dispatchers", "step07_sick", "step08_heavy"]
def run(name, args, outfile):
with open(OUT / outfile, "w", encoding="utf-8") as fh:
return subprocess.Popen([sys.executable, *args], stdout=fh, stderr=subprocess.STDOUT, cwd=HERE)
if __name__ == "__main__":
procs = {s: run(s, [f"{s}.py"], f"{s}.txt") for s in PARALLEL} # simulations are independent
for name, p in procs.items():
print(name, "exit", p.wait())
later = [("step09_asyncio", ["step09_asyncio.py"], "step09_asyncio.txt"),
("step10_mistakes", ["step10_mistakes.py"], "step10_mistakes.txt"),
("pytest", ["-m", "pytest", "-q", "-p", "no:cacheprovider"], "pytest.txt"),
("mutations", ["mutations.py"], "mutations.txt")]
if len(sys.argv) > 1: # folder of an unpacked nginx
later.append(("nginx_test", ["nginx_test.py", sys.argv[1]], "nginx_test.txt"))
for name, args, outfile in later:
print(name, "exit", run(name, args, outfile).wait()) # timing-sensitive: one at a timeRun python run_all.py C:/tools/nginx-1.30.6 (leave the argument out to skip nginx). It prints one line per step and takes a few minutes. Success looks like this:
- every line ends with
exit 0; out/step02_validate.txtshows the simulation within a few percent of the formula (Step 5);out/step03_policies.txtshows the five policies in the order random, round robin, two choices, three choices, shortest queue, from slowest to fastest;out/step05_stale.txtshows shortest queue overtaking random routing somewhere betweenTequal to 2 and 5, while two choices stays below it;out/pytest.txtshows 12 passed andout/mutations.txtshowscaught 7 of 7;out/nginx_test.txtshowstest is successfuland about 25 percent for round robin against under 10 percent for the other two.
What to take away
- Random routing wastes capacity: in the model about one server in ten was empty at any moment, while the fullest queue reached 69 requests. Two random choices cut the average time in system by 3.7 times and the p99 by 4.9 times at 90 percent utilization.
- The full scan is better only when its numbers are fresh and complete. A board that was 0.5 time units old erased its lead, and one that was 5 time units old made it worse than random. Two choices degraded gracefully through the whole table.
- With many balancers that cannot see each other, both rules decay towards random, and the cleverness of the rule matters less than how much information each balancer has.
- Queue length cannot see slowness in an empty queue, and a request count cannot see job size. Add health checks and ejection for the first and a better signal for the second.
- Bugs in a balancer are silent. Draw without replacement, break ties fairly, count down in
finally, and keep the tests and mutants from Step 13.
Where to go next
- Add ejection that reacts to failures, then slow starts for backends that rejoin. The sibling tutorial on failure detectors builds the part that decides who is dead.
- When traffic exceeds capacity no routing rule helps. Backpressure and load shedding covers what to do instead.
- If requests must reach the server that already holds their data, load-aware picking is the wrong tool and hashing is the right one. See rendezvous hashing and consistent hashing.
- Try your own workload in
sim.py: giveworka function that matches your request sizes, givespeedsa list that matches your fleet, and see where the rules in this tutorial stop being good enough.
No Comment! Be the first one.