C05 hands-on — Load shedding and the utilisation knee

Why 95% utilisation is not 95% as fast, what to shed on, and what to drop.

Source: handson/c05_load_shedding.py --- run it with python3 handson/c05_load_shedding.py
Full project spec: d05 — Load Shedding Gateway

Load shedding is the reliability primitive every other design leans on, and it is the one people reason about worst --- because the intuition that a system at 95% utilisation is almost as good as one at 50% is wrong by an order of magnitude, and nothing about the code says so.

This page is a discrete-event simulation of one server: 10 ms mean service time, so 100 requests per second of capacity. It measures the latency knee against the M/M/1 closed form, bounds the queue, compares the three signals people shed on, runs FIFO against LIFO under sustained overload, drops work whose deadline has already passed, and finishes with reserved floors versus strict priority. Every number came from running the simulation.

Run it

cd swe-interview-prep/handson

python3 c05_load_shedding.py            # every block, then the assembly
python3 c05_load_shedding.py --block 3  # block 3 and its prerequisites only
python3 c05_load_shedding.py --quiet    # the assembly only
python3 c05_load_shedding.py --verify   # re-derive and assert every claim below

What to expect. A full run takes under a second and prints 6 blocks followed by the assembly. There are no dependencies beyond the Python standard library and nothing touches the network or the filesystem.

Every seed is fixed, so the numbers you get are the numbers on this page --- character for character. If yours differ, the code changed, not the machine. --verify re-derives 14 claims from scratch and exits non-zero if any of them stops holding, which is what makes the prose here checkable rather than assertable.

Predict before you read

Worth two minutes with a pen, because the gap between your answer and the measurement is the entire value of the page. Write down a number for each:

1. One server, 10 ms mean service, so 100 rps of capacity. At 50% utilisation, what is p99 latency? At 95%?
2. By what factor does p99 rise between those two points? (Most people guess under 3x.)
3. 110 rps offered against 100 rps capacity, unbounded queue. What is p50?
4. 120 rps offered, capacity 100, queue capped at 200. FIFO versus LIFO: which completes more requests, and what fraction of each finishes inside 100 ms?
5. Clients time out at 250 ms. Of the requests a FIFO server completes under that overload, what fraction arrive before the caller has gone?
6. Strict priority protects premium traffic. What completion rate does the free tier get?

Then run it, or read on --- the answers are in the blocks, and the ones most people get wrong are called out where they land.

Contents

• Run it
• Predict before you read
• Block 1 — The unbounded queue
• Block 2 — Bounding the queue
• Block 3 — Which signal to shed on
• Block 4 — FIFO versus LIFO under overload
• Block 5 — Dropping doomed work
• Block 6 — Priority with a floor
• The assembly
• Verify the claims
• The design space
• The mathematics you should be able to derive at a whiteboard
• Where the numbers come from in production
• Advanced
• How this connects to the rest of the program
• Failure modes at scale
• Primary sources
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — The unbounded queue

Teaches: latency does not degrade gracefully, it has a knee

The problem. Everyone knows a queue gets slower as it fills. Almost nobody has the shape of the curve, and the shape is the whole argument: it is not a slope, it is a hyperbola, and the difference decides how much headroom a service needs. This block measures it and checks the measurement against the closed form, because a simulation that has not been validated is a drawing.

@block(1, "The unbounded queue", "latency does not degrade gracefully, it has a knee")
def b1(s, show):
    if show:
        print("  One server, 10 ms mean service -> capacity 100 rps. Poisson arrivals.")
        print("  No queue bound, no timeout, no shedding: just let it queue.")
        print(f"  {'offered':>9}{'rho':>7}{'mean':>9}{'M/M/1':>9}{'p50':>9}"
              f"{'p99':>10}{'p99 vs rho=.5':>15}")
        base = None
        for rate in (50, 80, 90, 95, 99):
            lat, *_ = simulate(rate, n=20_000)
            mean = sum(lat) / len(lat) * 1000
            theory = 1000 / (100 - rate)          # M/M/1: W = 1/(mu - lambda)
            p50, p99 = pct(lat, .50) * 1000, pct(lat, .99) * 1000
            if base is None: base = p99
            print(f"  {rate:>8}r{rate/100:>7.2f}{mean:>8.0f}m{theory:>8.0f}m"
                  f"{p50:>8.0f}m{p99:>9.0f}m{p99/base:>14.1f}x")
        print("  The M/M/1 column is the closed form W = 1/(mu-lambda). Simulated")
        print("  mean tracks it to within 7% up to rho=0.95 -- which is the check")
        print("  that this model measures what it claims to.")
        print("  At rho=0.99 it does NOT: 520ms simulated against 1000ms predicted.")
        print("  That gap is the simulation being too short, not the theory being")
        print("  wrong. Relaxation time grows as 1/(1-rho)^2, so 20,000 requests")
        print("  never reaches steady state at rho=0.99 and the run is still filling")
        print("  its queue when it ends. The real knee is SHARPER than this table")
        print("  shows, and a benchmark that stops early always flatters the tail.")
        print("  From 50% to 95% utilisation the offered load not even doubles and")
        print("  p99 goes up 8.7x. This is the utilisation knee: queueing delay")
        print("  scales as 1/(1-rho), so the last few percent of capacity cost more")
        print("  latency than all the rest combined. You cannot run a queueing")
        print("  system at 95% utilisation and be fast; that is arithmetic, not")
        print("  tuning.")
    return {}

Reading the implementation

• rng.expovariate(1 / SERVICE) — service times are exponential, not constant. That matters: with constant service times an M/D/1 queue has exactly half the waiting time of M/M/1 at the same utilisation. Variability is what creates queueing, and assuming constant service is the most common way to under-predict a tail.
• The event loop advances to min(next arrival, next completion) rather than stepping a clock. Discrete-event rather than time-stepped, so there is no timestep to tune and no resolution artifact — the simulation is exact given the arrival and service draws.
• free_at = max(free_at, t) on the arrival path is what makes the server idle correctly. Without it an arrival to an empty system would be scheduled from a stale free_at in the past and the queue would appear to have work it does not.
• Latency is measured as completion - enqueue, so it includes queueing and service. That is what a client experiences; measuring only service time is how a dashboard shows 10 ms while users see two seconds.

What the numbers say

Output:

  One server, 10 ms mean service -> capacity 100 rps. Poisson arrivals.
  No queue bound, no timeout, no shedding: just let it queue.
    offered    rho     mean    M/M/1      p50       p99  p99 vs rho=.5
        50r   0.50      20m      20m      14m       93m           1.0x
        80r   0.80      51m      50m      35m      211m           2.3x
        90r   0.90     107m     100m      71m      503m           5.4x
        95r   0.95     202m     200m     148m      803m           8.7x
        99r   0.99     520m    1000m     417m     1635m          17.6x
  The M/M/1 column is the closed form W = 1/(mu-lambda). Simulated
  mean tracks it to within 7% up to rho=0.95 -- which is the check
  that this model measures what it claims to.
  At rho=0.99 it does NOT: 520ms simulated against 1000ms predicted.
  That gap is the simulation being too short, not the theory being
  wrong. Relaxation time grows as 1/(1-rho)^2, so 20,000 requests
  never reaches steady state at rho=0.99 and the run is still filling
  its queue when it ends. The real knee is SHARPER than this table
  shows, and a benchmark that stops early always flatters the tail.
  From 50% to 95% utilisation the offered load not even doubles and
  p99 goes up 8.7x. This is the utilisation knee: queueing delay
  scales as 1/(1-rho), so the last few percent of capacity cost more
  latency than all the rest combined. You cannot run a queueing
  system at 95% utilisation and be fast; that is arithmetic, not
  tuning.

Two things, and the second is the more useful one.

The knee is real and it is steep. Offered load rises from 50 to 95 requests per second — less than double — and p99 rises 8.7×. The mean tracks the closed form \(W = 1/(\mu - \lambda)\) within 7% up to ρ=0.95, which is the check that this simulation measures what it claims to.

At ρ=0.99 the simulation disagrees with theory, and the simulation is wrong. 520 ms measured against 1000 ms predicted. The queue's relaxation time scales as \(1/(1-\rho)^2\), so at ρ=0.99 twenty thousand requests never reaches steady state — the run ends while the queue is still filling. The real knee is sharper than this table shows.

That is worth more than the knee itself: a benchmark that stops early always flatters the tail, and at high utilisation "early" can mean hours. Any load test that reports a p99 without stating its duration relative to \(1/(1-\rho)^2\) has probably measured the transient.

Try it yourself

The knee is a formula before it is a measurement. Derive it, then check it:

from c05_load_shedding import simulate, pct, SERVICE

MU = 1 / SERVICE                      # 100 requests/second of capacity
print(f"  {'rho':>6}{'W = 1/(mu-lam)':>17}{'simulated mean':>16}{'error':>8}"
      f"{'p99':>9}")
for rate in (50, 70, 80, 90, 95, 98):
    lat, *_ = simulate(rate, n=20_000)
    mean, theory = sum(lat) / len(lat), 1.0 / (MU - rate)
    print(f"  {rate/100:>6.2f}{theory*1000:>14.0f} ms{mean*1000:>13.0f} ms"
          f"{(mean/theory - 1)*100:>7.0f}%{pct(lat,.99)*1000:>8.0f}ms")
print()
print("  Doubling the load from 0.5 to 0.98 multiplies mean latency by "
      f"{(1/(MU-98))/(1/(MU-50)):.0f}x.")

     rho   W = 1/(mu-lam)  simulated mean   error      p99
    0.50            20 ms           20 ms      1%      93ms
    0.70            33 ms           33 ms      0%     144ms
    0.80            50 ms           51 ms      2%     211ms
    0.90           100 ms          107 ms      7%     503ms
    0.95           200 ms          202 ms      1%     803ms
    0.98           500 ms          377 ms    -25%    1158ms

  Doubling the load from 0.5 to 0.98 multiplies mean latency by 25x.

Two things fall out. The closed form and the simulation agree closely enough to trust the model — and the error column grows with ρ, which is the finite-run artifact the block calls out: at high utilisation the run ends before the queue reaches steady state, so the simulation understates the tail. A load test that stops early always flatters you.

Beyond the toy

One server is the pessimistic case, and the correction goes the helpful way: with \(c\) servers sharing one queue (M/M/c), the same total capacity gives much lower delay, because a single long request blocks only one server. Concretely, at ρ=0.9, going from one server to ten at the same ρ cuts mean queueing delay by roughly an order of magnitude. This is the argument for a shared queue over per-worker queues, and it is the same reason a single supermarket line beats one line per till.

What breaks the model, in the direction that makes reality worse:

• Service times are not exponential, they are heavy-tailed. Real request distributions have a long tail (a p99 that is 100× the median is normal), and heavier tails produce worse queueing than M/M/1 at equal mean.
• Arrivals are not Poisson, they are bursty and correlated — retries, cron, and client-side batching all cluster arrivals, which is worse than independent.
• Capacity is not constant. GC, cache misses, and a noisy neighbour all move μ during the run.

All three push the same way, which is why the practical rule of thumb — target 60–70% utilisation for a latency-sensitive service — is well below where the arithmetic alone says the knee starts.

Block 2 — Bounding the queue

Teaches: you cannot avoid dropping; you can only choose when

The problem. Block 1's queue is unbounded, which means latency is unbounded, which means a request can sit for thirty seconds behind work whose callers have all gone home. Bounding the queue is the fix, and the interesting part is what the bound actually buys — because it does not create capacity.

@block(2, "Bounding the queue", "you cannot avoid dropping; you can only choose when")
def b2(s, show):
    if show:
        print("  110 rps offered against 100 rps capacity -- sustained overload,")
        print("  so an unbounded queue grows without limit. Cap it and drop.")
        print(f"  {'queue cap':>10}{'p50':>9}{'p99':>10}{'dropped':>10}{'goodput':>10}")
        for cap in (None, 1000, 100, 10, 2):
            lat, dropped, *_ = simulate(110, n=20_000, capacity=cap)
            p50, p99 = pct(lat, .50) * 1000, pct(lat, .99) * 1000
            served = len(lat)
            print(f"  {str(cap):>10}{p50:>8.1f}m{p99:>9.1f}m{dropped:>10}"
                  f"{served/20000*100:>9.1f}%")
        print("  A bound converts an unbounded LATENCY problem into a bounded one")
        print("  plus a visible DROP RATE. Nothing was gained or lost in aggregate:")
        print("  the work that does not fit does not fit either way. The difference")
        print("  is that a drop is a fast, countable, actionable failure and a")
        print("  30-second queue wait is an invisible one that also holds a socket,")
        print("  a thread and a chunk of memory the whole time.")
    return {}

Reading the implementation

• if len(pending) >= capacity: dropped += 1; continue — the drop happens at arrival, before any resource is committed. A request that is going to be refused should be refused before it gets a thread, a buffer, or a database connection, and the earlier in the stack that happens the cheaper the overload is to survive.
• The offered rate is 110 rps against 100 rps of capacity. That is deliberate: at ρ<1 the unbounded queue is stable and the caps rarely bind, so the block would demonstrate nothing. Sustained overload is the regime where bounding matters, and it is the regime a shedding page is about.

What the numbers say

Output:

  110 rps offered against 100 rps capacity -- sustained overload,
  so an unbounded queue grows without limit. Cap it and drop.
   queue cap      p50       p99   dropped   goodput
        None  7996.4m  18628.5m         0    100.0%
        1000  7721.3m  10771.4m       757     96.2%
         100   892.0m   1206.3m      1657     91.7%
          10    65.8m    169.2m      2663     86.7%
           2    16.5m     73.0m      5564     72.2%
  A bound converts an unbounded LATENCY problem into a bounded one
  plus a visible DROP RATE. Nothing was gained or lost in aggregate:
  the work that does not fit does not fit either way. The difference
  is that a drop is a fast, countable, actionable failure and a
  30-second queue wait is an invisible one that also holds a socket,
  a thread and a chunk of memory the whole time.

Read the None row first: p50 is 8 seconds and p99 is 18.6 seconds, and the queue is still growing when the run ends. Every one of those requests is holding a connection and a buffer the whole time.

Now read down the table. Nothing in the goodput column is created by bounding — 110 rps of demand against 100 rps of capacity means about 9% cannot be served under any policy, and the caps mostly trade drop rate against latency along that line. What changes is the form of the failure:

A drop is a fast, countable, actionable failure. A thirty-second queue wait is an invisible one that also consumes the resources you need to serve everyone else. That is the whole argument for the bound and it is not about throughput.

Try it yourself

Derive the queue cap from an SLO instead of guessing it, then check the guess:

from c05_load_shedding import simulate, pct

CAPACITY, BUDGET = 100, 0.200          # 100 rps, a 200 ms latency budget
littles_law = CAPACITY * BUDGET        # L = lambda x W
print(f"  Little's law says the cap should be ~{littles_law:.0f} requests\n")

print(f"  {'cap':>6}{'p50':>9}{'p99':>9}{'dropped':>10}{'p99 vs budget':>16}")
for cap in (5, 10, 20, 40, 100, 400):
    lat, dropped, *_ = simulate(110, n=20_000, capacity=cap)
    p99 = pct(lat, .99)
    verdict = "within" if p99 <= BUDGET else f"{p99/BUDGET:.1f}x OVER"
    print(f"  {cap:>6}{pct(lat,.50)*1000:>7.0f}ms{p99*1000:>7.0f}ms"
          f"{dropped:>10}{verdict:>16}")

  Little's law says the cap should be ~20 requests

     cap      p50      p99   dropped   p99 vs budget
       5     33ms    110ms      3657          within
      10     66ms    169ms      2663          within
      20    145ms    292ms      2039       1.5x OVER
      40    311ms    522ms      1735       2.6x OVER
     100    892ms   1206ms      1657       6.0x OVER
     400   3818ms   4444ms      1357      22.2x OVER

Read that carefully, because it does not say what I expected it to say.

Little's law gives a cap of 20, and a cap of 20 misses the budget by 1.5×. The cap that actually holds a 200 ms p99 is 10 — half the derived figure.

The reason is that \(L = \lambda W\) relates the mean queue length to the mean wait, and the SLO is a p99. Sizing a queue from Little's law and then measuring a tail is a units error, and it is a common one: the derivation is correct and the conclusion is wrong by roughly 2× because the two ends of it are different statistics.

So the usable rule is compute the Little's-law cap, then halve it for a p99 budget — and verify, because the ratio between mean and p99 depends on the service-time distribution, which is exactly what the block's M/G/1 note is about.

What survives intact is the framing: the queue depth is not a capacity knob, it is a latency knob. Anyone who picks 1000 because it sounds safe has chosen a 4.4-second p99 without noticing — that is the last row.

Beyond the toy

Choosing the bound is the follow-up, and the good answer is not a number — it is a latency budget converted into a queue length by Little's law:

\[ L = \lambda W \implies \text{queue cap} = \text{capacity} \times \text{latency budget} \]

At 100 rps and a 200 ms budget, the cap is 20. Derive the queue depth from the SLO rather than picking it, and you can defend it; pick 1000 because it sounds safe and you have chosen an 10-second p99 without noticing.

Production refinements worth naming:

• CoDel (controlled delay), from network AQM and used in Facebook's request queues: rather than bounding length, bound the sojourn time — drop when the minimum queueing delay over a window exceeds a target. It adapts automatically when capacity changes, which a fixed length cannot.
• Distinguish "full" from "over quota". A queue-full drop is a 503 (capacity — the client cannot fix it), a quota rejection is a 429 (the client can). C03 makes the same distinction, and collapsing them hides your capacity problem inside a metric that looks like client misbehaviour.

Block 3 — Which signal to shed on

Teaches: CPU is the intuitive answer and the wrong one

The problem. Having decided to shed, you need a signal that says when. The intuitive one is CPU utilisation, it is the one on every dashboard, and it is unusable for this — for a reason that is obvious once measured and invisible otherwise.

@block(3, "Which signal to shed on", "CPU is the intuitive answer and the wrong one")
def b3(s, show):
    if show:
        print("  Three candidate signals, evaluated at a range of offered loads.")
        print("  'utilisation' here is the server's busy fraction -- what CPU% is.")
        print(f"  {'offered':>9}{'utilisation':>13}{'mean queue':>12}{'p99 latency':>13}")
        for rate in (50, 80, 90, 95, 99, 120):
            lat, dropped, *_ = simulate(rate, n=20_000, capacity=100_000)
            served = len(lat)
            util = min(1.0, rate / 100)
            mq = (sum(lat) / len(lat) - SERVICE) / SERVICE if lat else 0
            print(f"  {rate:>8}r{util*100:>12.0f}%{mq:>12.1f}{pct(lat,.99)*1000:>11.1f}ms")
        print("  Utilisation saturates at 100% and stops moving. Everything past")
        print("  that -- the entire overload regime -- looks IDENTICAL on a CPU")
        print("  graph, while queue depth and latency keep climbing without bound.")
        print("  A signal that is flat exactly where you need to act is not a")
        print("  signal. Shed on QUEUE DEPTH or on measured WAIT TIME, both of")
        print("  which are unbounded above and lead latency rather than trailing it.")
    return {}

Reading the implementation

• util = min(1.0, rate / 100) — utilisation is defined as busy fraction, and a busy fraction cannot exceed 1. The min is not a simplification; it is what the metric genuinely does.
• Mean queue depth is derived as (mean latency - service) / service, which is Little's law rearranged: mean number waiting equals arrival rate times mean wait. Deriving it rather than counting it directly is a small check that the simulator's numbers are mutually consistent.
• The 120 rps row runs with capacity=100_000 so the queue is effectively unbounded and the overload regime is visible rather than clipped.

What the numbers say

Output:

  Three candidate signals, evaluated at a range of offered loads.
  'utilisation' here is the server's busy fraction -- what CPU% is.
    offered  utilisation  mean queue  p99 latency
        50r          50%         1.0       92.7ms
        80r          80%         4.1      210.8ms
        90r          90%         9.7      503.3ms
        95r          95%        19.2      803.2ms
        99r          99%        51.0     1635.2ms
       120r         100%      1617.4    33544.0ms
  Utilisation saturates at 100% and stops moving. Everything past
  that -- the entire overload regime -- looks IDENTICAL on a CPU
  graph, while queue depth and latency keep climbing without bound.
  A signal that is flat exactly where you need to act is not a
  signal. Shed on QUEUE DEPTH or on measured WAIT TIME, both of
  which are unbounded above and lead latency rather than trailing it.

The utilisation column reaches 100% and stops. Between 99 rps and 120 rps — an entire regime, the one where the system is failing — utilisation moves by one percentage point while mean queue depth goes from 51 to 1,617 and p99 from 1.6 s to 33.5 s.

A signal that is flat exactly where you need to act is not a signal. CPU saturation tells you the server is busy; it cannot distinguish "busy and keeping up" from "busy and falling behind by 20%", and those need opposite responses.

Try it yourself

Put the three candidate signals side by side and look for the one that is still moving where you need to act:

from c05_load_shedding import simulate, pct, SERVICE

print(f"  {'offered':>9}{'CPU%':>7}{'errors%':>9}{'queue':>8}{'wait p99':>11}")
for rate in (50, 90, 99, 110, 130, 200):
    lat, dropped, *_ = simulate(rate, n=20_000, capacity=100_000)
    cpu = min(100, rate)
    errors = 0.0                       # nothing is failing yet -- that is the point
    q = (sum(lat)/len(lat) - SERVICE) / SERVICE
    print(f"  {rate:>8}r{cpu:>6.0f}%{errors:>8.1f}%{q:>8.0f}{pct(lat,.99):>9.1f}s")
print()
print("  CPU stops moving at 100. Errors are still zero -- the requests are all")
print("  succeeding, just far too late. Only queue depth and wait time carry")
print("  information across the whole range.")

    offered   CPU%  errors%   queue   wait p99
        50r    50%     0.0%       1      0.1s
        90r    90%     0.0%      10      0.5s
        99r    99%     0.0%      51      1.6s
       110r   100%     0.0%     869     18.6s
       130r   100%     0.0%    2254     46.2s
       200r   100%     0.0%    4926     99.4s

  CPU stops moving at 100. Errors are still zero -- the requests are all
  succeeding, just far too late. Only queue depth and wait time carry
  information across the whole range.

The errors% column is the one worth staring at. A service in this state is 100% available and completely useless, so any alerting built on error rate is silent throughout. That is why availability and latency SLOs are different things, and why an SLO without a latency term is not an SLO.

Beyond the toy

The general property to look for: a shedding signal must be unbounded above and must lead rather than trail. Queue depth and measured wait time are both; utilisation and error rate are neither (error rate trails — by the time it moves you have already failed).

Two production systems worth naming because they encode exactly this: Netflix concurrency-limits infers the limit from measured latency using a TCP-congestion- control algorithm (Vegas/Gradient) rather than a configured number, and CoDel uses sojourn time directly. Both replace a threshold nobody can tune with a control loop on a signal that keeps moving.

And the same finding appears one substrate over: in m01, GPU utilisation reads ~100% during a batch-1 decode that uses 1/295th of the machine's compute. Same failure, different metric — the utilisation of a resource is not the scarcity of that resource.

Block 4 — FIFO versus LIFO under overload

Teaches: the counterintuitive one, and it is worth knowing

The problem. With a bounded queue you must choose what order to serve it in, and FIFO is so obviously fair that most systems never make the choice consciously. Under sustained overload FIFO has a property that is worth measuring, because it can deliver a service that is 100% available and 0% useful.

@block(4, "FIFO versus LIFO under overload", "the counterintuitive one, and it is worth knowing")
def b4(s, show):
    if show:
        print("  120 rps offered against 100 rps capacity: 20% more work than the")
        print("  server can ever do. Queue capped at 200. Same arrivals both rows.")
        print(f"  {'policy':>8}{'served':>9}{'p50':>10}{'p99':>11}{'under 100ms':>13}")
        for policy in ("fifo", "lifo"):
            lat, dropped, *_ = simulate(120, n=20_000, capacity=200, policy=policy)
            fast = sum(1 for x in lat if x < 0.100) / 20_000 * 100
            print(f"  {policy:>8}{len(lat):>9}{pct(lat,.50)*1000:>9.1f}m"
                  f"{pct(lat,.99)*1000:>10.1f}m{fast:>12.1f}%")
        print("  Same throughput -- the server does the same amount of work either")
        print("  way. But FIFO serves everyone slowly and LIFO serves the newest")
        print("  arrivals fast while the old ones rot. Under sustained overload")
        print("  where the client has a timeout, FIFO can deliver ZERO useful")
        print("  responses: every request is answered after the caller gave up.")
        print("  LIFO is unfair and delivers a working service to a subset. That")
        print("  is the argument, and it is why adaptive LIFO exists -- FIFO when")
        print("  healthy, LIFO only once the queue indicates overload.")
    return {}

Reading the implementation

• pending.pop(0) if policy == "fifo" else pending.pop() — the entire difference, one index. Everything else about the two runs is identical, including the arrival stream and the service-time draws, so the comparison is clean.
• fast = sum(1 for x in lat if x < 0.100) — the metric is the fraction of requests answered inside 100 ms, not the mean or the p99. Under overload the aggregate statistics hide the finding entirely, and choosing the right metric is the block.

What the numbers say

Output:

  120 rps offered against 100 rps capacity: 20% more work than the
  server can ever do. Queue capped at 200. Same arrivals both rows.
    policy   served       p50        p99  under 100ms
      fifo    16968   1911.0m    2366.9m         0.4%
      lifo    16968     22.9m  123654.3m        70.7%
  Same throughput -- the server does the same amount of work either
  way. But FIFO serves everyone slowly and LIFO serves the newest
  arrivals fast while the old ones rot. Under sustained overload
  where the client has a timeout, FIFO can deliver ZERO useful
  responses: every request is answered after the caller gave up.
  LIFO is unfair and delivers a working service to a subset. That
  is the argument, and it is why adaptive LIFO exists -- FIFO when
  healthy, LIFO only once the queue indicates overload.

Identical throughput — 16,968 completed either way, because the server does the same amount of work regardless of order. Then:

• FIFO: p50 is 1.9 s, and 0.4% of requests complete within 100 ms.
• LIFO: p50 is 23 ms, and 70.7% complete within 100 ms — with a p99 of 123 seconds, because the requests at the bottom of the stack rot there.

If clients time out at one second, FIFO delivers almost nothing useful while appearing to serve every request, and LIFO delivers a working service to 70% of them. The server is equally busy in both cases; only the distribution of who gets served changed.

Try it yourself

The choice only matters under overload. Sweep across the boundary and watch it switch from irrelevant to decisive:

from c05_load_shedding import simulate

DEADLINE = 0.100
print(f"  {'offered':>9}{'FIFO useful':>13}{'LIFO useful':>13}{'advantage':>12}")
for rate in (60, 90, 100, 120, 160):
    f, *_ = simulate(rate, n=20_000, capacity=200, policy="fifo")
    l, *_ = simulate(rate, n=20_000, capacity=200, policy="lifo")
    uf = sum(1 for x in f if x < DEADLINE)
    ul = sum(1 for x in l if x < DEADLINE)
    print(f"  {rate:>8}r{uf:>13,}{ul:>13,}{(ul/max(uf,1)):>11.1f}x")

    offered  FIFO useful  LIFO useful   advantage
        60r       19,624       19,225        1.0x
        90r       12,162       17,245        1.4x
       100r        1,788       16,286        9.1x
       120r           82       14,136      172.4x
       160r           35       11,028      315.1x

Below capacity the two are identical, because there is no queue to order. The advantage appears exactly when the queue becomes persistent, which is the argument for adaptive LIFO rather than always-LIFO: FIFO's fairness costs nothing while it is affordable, and costs everything once it is not.

Beyond the toy

The reasoning generalises: under overload, FIFO maximises the number of responses that arrive too late to matter. Every request waits behind the entire backlog, and the backlog is by definition longer than the deadline. LIFO serves the requests whose callers are most likely still present.

The obvious objection is correct and is the reason nobody runs pure LIFO: it is unfair, and the starved tail is unbounded. The production answer is adaptive LIFO — FIFO while healthy, switch to LIFO only when the queue signals overload (Facebook's Thrift servers do exactly this, paired with CoDel). Fairness when fairness is affordable; usefulness when it is not.

Two related mechanisms in the same family:

• Shortest-job-first minimises mean latency but needs a size estimate and starves long requests.
• The single-queue-versus-per-worker choice from block 1's Beyond the toy is the same class of decision: how work is assigned changes the latency distribution without changing throughput.

Block 5 — Dropping doomed work

Teaches: the queue is full of requests nobody is waiting for

The problem. Block 4 shows FIFO answering requests after the caller has given up. That work was not merely late — it was waste, and it consumed capacity that a still-waiting request needed. This block measures how much, and the answer is large enough that the fix is the cheapest intervention on the page.

@block(5, "Dropping doomed work", "the queue is full of requests nobody is waiting for")
def b5(s, show):
    if show:
        print("  120 rps offered, 100 rps capacity, client timeout 250 ms.")
        print("  Work whose queue wait already exceeds the deadline is pure waste:")
        print("  the caller has gone, and serving it delays someone still present.")
        print(f"  {'policy':>26}{'completed':>11}{'useful':>9}{'wasted':>9}"
              f"{'p99 of useful':>15}")
        for name, kw in (("serve everything (FIFO)", dict(policy="fifo")),
                         ("drop expired at dequeue", dict(policy="fifo", timeout=0.250)),
                         ("drop expired + LIFO", dict(policy="lifo", timeout=0.250))):
            lat, dropped, expired, _ = simulate(120, n=20_000, capacity=200, **kw)
            useful = [x for x in lat if x <= 0.250]
            waste = len(lat) - len(useful)
            print(f"  {name:>26}{len(lat):>11}{len(useful):>9}{waste:>9}"
                  f"{pct(useful,.99)*1000:>13.1f}ms")
        print("  Row 1 completes the most requests and most of them are useless --")
        print("  answered after the client timed out. Checking the deadline at")
        print("  DEQUEUE time (not at enqueue) converts that wasted service into")
        print("  capacity for requests still worth serving. This is the cheapest")
        print("  intervention on this page and almost nobody implements it.")
    return {}

Reading the implementation

• The deadline is checked at dequeue, not at enqueue: if timeout is not None and wait > timeout. Checking at enqueue is useless — nothing has waited yet. The check must happen at the moment the server is about to spend capacity, which is the only moment the answer can be known.
• free_at = max(free_at, enq) on the expired path, and no service time is consumed: discarding a doomed request is free, which is exactly why it is worth doing.
• useful = [x for x in lat if x <= 0.250] scores completions against the deadline afterwards, so the "serve everything" row is judged by the same standard as the others rather than being flattered by its higher completion count.

What the numbers say

Output:

  120 rps offered, 100 rps capacity, client timeout 250 ms.
  Work whose queue wait already exceeds the deadline is pure waste:
  the caller has gone, and serving it delays someone still present.
                      policy  completed   useful   wasted  p99 of useful
     serve everything (FIFO)      16968      225    16743        248.5ms
     drop expired at dequeue      16662    13898     2764        249.5ms
         drop expired + LIFO      16059    16030       29        204.3ms
  Row 1 completes the most requests and most of them are useless --
  answered after the client timed out. Checking the deadline at
  DEQUEUE time (not at enqueue) converts that wasted service into
  capacity for requests still worth serving. This is the cheapest
  intervention on this page and almost nobody implements it.

The first row completes 16,968 requests, of which 225 arrive in time. 98.7% of the server's work produced nothing. Adding a dequeue-time deadline check takes useful completions from 225 to 13,898 — a 62× improvement — using the same hardware, the same arrival stream, and about four lines of code.

Combining it with LIFO reaches 16,030 useful, with a p99 of the useful set of 204 ms, comfortably inside the deadline.

Try it yourself

Sweep the deadline and watch where the intervention stops paying:

from c05_load_shedding import simulate

print(f"  {'client deadline':>16}{'no check':>10}{'with check':>12}{'gain':>8}")
for deadline in (0.05, 0.10, 0.25, 0.50, 1.00, 2.00):
    plain, *_ = simulate(120, n=20_000, capacity=200, policy="fifo")
    drop, *_ = simulate(120, n=20_000, capacity=200, policy="fifo", timeout=deadline)
    u_plain = sum(1 for x in plain if x <= deadline)
    u_drop = sum(1 for x in drop if x <= deadline)
    print(f"  {deadline*1000:>13.0f} ms{u_plain:>10,}{u_drop:>12,}"
          f"{u_drop/max(u_plain,1):>7.1f}x")

   client deadline  no check  with check    gain
             50 ms        25      11,761  470.4x
            100 ms        82      13,186  160.8x
            250 ms       225      13,898   61.8x
            500 ms       370      13,870   37.5x
           1000 ms       623      13,955   22.4x
           2000 ms    11,615      16,423    1.4x

The gain is largest for tight deadlines, which is the opposite of the intuition that a strict deadline makes things hopeless. A tight deadline means more of the queue is already doomed, so more capacity is recoverable by refusing to spend it. As the deadline loosens past the queueing delay the check stops firing and the two converge.

Beyond the toy

Nothing on this page has a better ratio of value to effort, and almost no system implements it, because the deadline is usually not available at the point where it would be checked. Making it available is deadline propagation: the client's remaining budget travels with the request, every hop subtracts its own elapsed time, and any hop may abandon work whose budget is exhausted.

• gRPC has this built in — context.WithTimeout propagates a deadline across service boundaries, and a well-behaved server checks ctx.Err() before doing expensive work.
• The failure without it is death by a thousand timeouts: each service has its own fixed timeout, so a request that has already burned its client budget in service A is still processed at full cost by services B, C and D.

The subtle version, worth mentioning if the interview goes there: a request whose deadline expires during service should usually be completed anyway if it has side effects, because abandoning it halfway can leave state inconsistent. The cheap win is dropping work that has not started; abandoning work in flight is a different and much harder decision.

Block 6 — Priority with a floor

Teaches: strict priority starves; a reserved floor does not

The problem. Shedding decides how much to drop. It does not decide whose requests, and once there are paying and non-paying tiers that is a product question with a measurable answer. The obvious policy — always serve the paying tier first — has a failure mode that costs money in a way that does not appear on any latency graph.

@block(6, "Priority with a floor", "strict priority starves; a reserved floor does not")
def b6(s, show):
    def run(strategy, rate=140, n=20_000, seed=9, cap=200, floor=0.15):
        """Two classes: 70% premium, 30% free. Which do we admit at the cap?"""
        rng = random.Random(seed)
        ts, _ = arrivals(rate, n, seed)
        cls = [("premium" if rng.random() < 0.7 else "free") for _ in ts]
        pending, free_at, done = [], 0.0, {"premium": 0, "free": 0}
        i = 0
        while i < len(ts) or pending:
            if pending and (i >= len(ts) or free_at <= ts[i]):
                enq, c = pending.pop(0)
                free_at = max(free_at, enq) + rng.expovariate(1 / SERVICE)
                done[c] += 1
                continue
            t, c = ts[i], cls[i]; i += 1
            n_free = sum(1 for _, cc in pending if cc == "free")
            if len(pending) >= cap:
                continue                                   # hard cap
            if strategy == "strict" and c == "free" and len(pending) >= cap * 0.2:
                continue                                   # free shed first, hard
            if strategy == "floor" and c == "free" \
               and n_free >= cap * floor and len(pending) >= cap * 0.2:
                continue                    # free may always use `floor` of the queue
            pending.append((t, c))
            free_at = max(free_at, t)
        return done, sum(1 for c in cls if c == "premium"), sum(1 for c in cls if c == "free")

    if show:
        print("  140 rps against 100 rps capacity. 70% premium, 30% free tier.")
        print(f"  {'strategy':>22}{'premium served':>16}{'free served':>13}"
              f"{'free completion':>17}")
        for strat in ("none", "strict", "floor"):
            done, np_, nf = run(strat)
            print(f"  {strat:>22}{done['premium']:>16}{done['free']:>13}"
                  f"{done['free']/nf*100:>16.1f}%")
        print("  With no policy both classes degrade together. Strict priority")
        print("  protects premium by starving free almost completely -- and free")
        print("  tier users are prospective customers evaluating you, so a 503 is")
        print("  a lost sale, not a saved millisecond. The reserved floor keeps a")
        print("  fixed slice of the queue available to free traffic no matter how")
        print("  much premium arrives: premium is still protected, free still")
        print("  works, and the guarantee is a number you can put in writing.")
    return {}

Reading the implementation

• n_free = sum(1 for _, cc in pending if cc == "free") — the floor policy counts free requests currently queued, not total queue depth. That is what makes it a floor rather than a threshold: free traffic may always occupy up to floor of the queue no matter how much premium traffic is arriving.
• The strict policy sheds free traffic as soon as the queue passes 20% of its cap; the floor policy sheds it only once free traffic is also above its own reservation. One extra condition, and it is the whole difference.
• Both policies keep the same hard cap, so premium is never allowed to fill the queue without limit either.

What the numbers say

Output:

  140 rps against 100 rps capacity. 70% premium, 30% free tier.
                strategy  premium served  free served  free completion
                    none            9257         5305            89.4%
                  strict           14069          345             5.8%
                   floor           12232         2326            39.2%
  With no policy both classes degrade together. Strict priority
  protects premium by starving free almost completely -- and free
  tier users are prospective customers evaluating you, so a 503 is
  a lost sale, not a saved millisecond. The reserved floor keeps a
  fixed slice of the queue available to free traffic no matter how
  much premium arrives: premium is still protected, free still
  works, and the guarantee is a number you can put in writing.

Strict priority does its job: premium completions rise from 9,257 to 14,069. It also takes free-tier completion to 5.8% — effectively an outage for that class, indefinitely, for as long as premium demand exceeds capacity.

The floor recovers most of the premium gain (12,232, or 87% of what strict achieved) while keeping free tier at 39% rather than 6%.

Try it yourself

Tune the floor and watch the frontier between the two classes:

from c05_load_shedding import arrivals, SERVICE
import random

def run(floor, rate=140, n=20_000, seed=9, cap=200):
    rng = random.Random(seed)
    ts, _ = arrivals(rate, n, seed)
    cls = ["premium" if rng.random() < 0.7 else "free" for _ in ts]
    pending, free_at, done, i = [], 0.0, {"premium": 0, "free": 0}, 0
    while i < len(ts) or pending:
        if pending and (i >= len(ts) or free_at <= ts[i]):
            enq, c = pending.pop(0)
            free_at = max(free_at, enq) + rng.expovariate(1 / SERVICE)
            done[c] += 1; continue
        t, c = ts[i], cls[i]; i += 1
        n_free = sum(1 for _, cc in pending if cc == "free")
        if len(pending) >= cap: continue
        if c == "free" and n_free >= cap * floor and len(pending) >= cap * 0.2:
            continue
        pending.append((t, c)); free_at = max(free_at, t)
    return done, cls.count("free")

print(f"  {'free floor':>11}{'premium':>10}{'free':>8}{'free rate':>11}")
for floor in (0.0, 0.05, 0.15, 0.30, 0.60, 1.0):
    done, nf = run(floor)
    print(f"  {floor*100:>10.0f}%{done['premium']:>10,}{done['free']:>8,}"
          f"{done['free']/nf*100:>10.1f}%")

   free floor   premium    free  free rate
           0%    14,069     345       5.8%
           5%    13,571     952      16.1%
          15%    12,232   2,326      39.2%
          30%    10,236   4,326      72.9%
          60%     9,257   5,305      89.4%
         100%     9,257   5,305      89.4%

The frontier is unusually gentle: going from a 0% floor (strict priority) to 15% costs premium a few percent and takes free tier from near-zero to nearly 40%. That shape is the argument — if the trade were steep, strict priority would be defensible; because it is shallow, starving the bottom class buys almost nothing.

Beyond the toy

The argument for the floor is commercial and worth making in those terms: free-tier users are prospective customers evaluating the product, so a sustained 94% failure rate for them is a lost sales pipeline, not a saved millisecond. Strict priority optimises a latency metric by damaging a funnel nobody is measuring in the same dashboard.

The engineering form of the same argument: strict priority makes the bottom class's availability a function of the top class's demand, which is not a guarantee at all — it is an unbounded coupling. A floor converts it into a number you can write in a contract.

This is the fourth independent arrival at reserved floors in this program, and that recurrence is the point:

• d05 — shed classes.
• d12 — fair queueing across tenants.
• m01 — the enterprise reserved token floor, where the revision's finding is that a floor must guarantee latency, not merely admission.
• m07 — reserved batch slots for long-tail adapters.

Whenever a design reaches for priority, ask what the bottom class is guaranteed. If the answer is "nothing", it will eventually get nothing.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nOne overloaded service, five policies, same arrivals throughout.\n")
    rate, cap, deadline = 130, 200, 0.250
    rows = [
        ("no bound, FIFO",            dict(policy="fifo")),
        ("bounded queue, FIFO",       dict(policy="fifo", capacity=cap)),
        ("bounded + deadline drop",   dict(policy="fifo", capacity=cap, timeout=deadline)),
        ("bounded + LIFO",            dict(policy="lifo", capacity=cap)),
        ("bounded + LIFO + deadline", dict(policy="lifo", capacity=cap, timeout=deadline)),
    ]
    print(f"  {'policy':<26}{'p50':>9}{'p99':>10}{'useful':>9}{'wasted':>8}"
          f"{'shed':>7}")
    for name, kw in rows:
        lat, dropped, expired, _ = simulate(rate, n=20_000, **kw)
        useful = [x for x in lat if x <= deadline]
        print(f"  {name:<26}{pct(lat,.50)*1000:>8.0f}m{pct(lat,.99)*1000:>9.0f}m"
              f"{len(useful):>9}{len(lat)-len(useful):>8}{dropped+expired:>7}")

    print("\n  130 rps offered against 100 rps capacity, so 23% of the work cannot")
    print("  be done by anyone under any policy. The columns that move are which")
    print("  requests get served and how fast -- 'useful' counts responses that")
    print("  arrived before the 250 ms deadline, which is the only column a user")
    print("  can perceive.")
    print("\n  The order to say it in: you cannot run at high utilisation and be")
    print("  fast, because delay goes as 1/(1-rho) and the knee is real. So you")
    print("  bound the queue, which converts unbounded latency into a countable")
    print("  drop rate. You shed on queue depth or wait time, never on CPU, which")
    print("  is flat across the whole overload regime. You drop work whose")
    print("  deadline has already passed, because serving it costs capacity and")
    print("  delivers nothing. And you protect classes with a reserved floor")
    print("  rather than strict priority, because strict priority starves the")
    print("  bottom class to zero.")
    print("\n  Built: the knee -> bounded queue -> the shed signal -> FIFO vs LIFO")
    print("  -> deadline propagation -> reserved floors.")
    print("  Not built, worth ten more minutes: circuit breakers between services,")
    print("  retry budgets (a retry storm is offered load you generated), and")
    print("  the recovery ramp -- a service that comes back at full traffic goes")
    print("  straight back down.")


def parts():
    """Every mechanism this page builds, ready to import.

        >>> from c05_load_shedding import parts
        >>> p = parts()
        >>> sorted(p)                      # doctest: +ELLIPSIS
        [...]
    """
    return collect()


def verify():
    """Re-derive every headline claim on this page from scratch."""
    # B1 -- the simulator agrees with the M/M/1 closed form below rho=0.95.
    for rate in (50, 80, 90, 95):
        lat, *_ = simulate(rate, n=20_000)
        mean = sum(lat) / len(lat)
        theory = 1.0 / (100 - rate)
        check(f"B1  simulated mean matches M/M/1 at rho={rate/100:.2f}",
              approx(mean, theory, 0.10),
              f"{mean*1000:.0f} ms measured vs {theory*1000:.0f} ms predicted")

    # B1 -- and it does NOT at rho=0.99, because the run is too short.
    lat, *_ = simulate(99, n=20_000)
    mean99 = sum(lat) / len(lat)
    check("B1  at rho=0.99 the run is too short and UNDERSTATES the tail",
          mean99 < 1.0 * 0.8,
          f"{mean99*1000:.0f} ms vs 1000 ms predicted -- relaxation ~1/(1-rho)^2")

    # B1 -- the knee: p99 rises ~9x between rho=0.5 and rho=0.95.
    p50_lo = pct(simulate(50, n=20_000)[0], .99)
    p99_hi = pct(simulate(95, n=20_000)[0], .99)
    knee = p99_hi / p50_lo
    check("B1  p99 rises ~9x from 50% to 95% utilisation",
          8.0 <= knee <= 10.0, f"{knee:.1f}x")

    # B2 -- bounding the queue trades unbounded latency for a countable drop rate.
    unb, _, _, _ = simulate(110, n=20_000)
    cap, dropped, _, _ = simulate(110, n=20_000, capacity=10)
    check("B2  an unbounded queue at rho>1 produces multi-second latency",
          pct(unb, .99) > 5.0, f"p99 {pct(unb,.99):.1f} s")
    check("B2  a bound converts it into a bounded latency plus visible drops",
          pct(cap, .99) < 0.5 and dropped > 0,
          f"p99 {pct(cap,.99)*1000:.0f} ms, {dropped} dropped")

    # B3 -- utilisation saturates while queue depth keeps climbing.
    q99 = (sum(simulate(99, n=20_000, capacity=100_000)[0]) /
           len(simulate(99, n=20_000, capacity=100_000)[0]) - SERVICE) / SERVICE
    q120 = (sum(simulate(120, n=20_000, capacity=100_000)[0]) /
            len(simulate(120, n=20_000, capacity=100_000)[0]) - SERVICE) / SERVICE
    check("B3  utilisation is pinned at 100% across the whole overload regime",
          min(1.0, 99/100) < 1.0 and min(1.0, 120/100) == 1.0,
          "99 rps -> 99%, 120 rps -> 100%: one point of movement")
    check("B3  ...while mean queue depth grows by more than an order of magnitude",
          q120 / q99 > 10, f"{q99:.0f} -> {q120:.0f} deep")

    # B4 -- FIFO and LIFO do the SAME work; only the distribution differs.
    f_lat, *_ = simulate(120, n=20_000, capacity=200, policy="fifo")
    l_lat, *_ = simulate(120, n=20_000, capacity=200, policy="lifo")
    fast_f = sum(1 for x in f_lat if x < 0.100)
    fast_l = sum(1 for x in l_lat if x < 0.100)
    check("B4  FIFO and LIFO complete the same number of requests",
          len(f_lat) == len(l_lat), f"{len(f_lat)} either way")
    check("B4  ...but LIFO serves vastly more of them inside 100 ms",
          fast_l > 50 * fast_f, f"{fast_l} vs {fast_f} under 100 ms")

    # B5 -- dropping doomed work multiplies USEFUL completions.
    all_lat, *_ = simulate(120, n=20_000, capacity=200, policy="fifo")
    dl_lat, *_ = simulate(120, n=20_000, capacity=200, policy="fifo", timeout=0.250)
    u_all = sum(1 for x in all_lat if x <= 0.250)
    u_dl = sum(1 for x in dl_lat if x <= 0.250)
    check("B5  serving everything FIFO wastes almost all of the work",
          u_all / len(all_lat) < 0.05,
          f"{u_all} of {len(all_lat)} completions arrived in time")
    check("B5  dropping expired work at dequeue is a >10x goodput win",
          u_dl / max(u_all, 1) > 10, f"{u_all} -> {u_dl} useful completions")

Output:

One overloaded service, five policies, same arrivals throughout.

  policy                          p50       p99   useful  wasted   shed
  no bound, FIFO               21893m    46192m      117   19883      0
  bounded queue, FIFO           1926m     2368m      117   15590   4293
  bounded + deadline drop        235m      283m    11809    3571   4620
  bounded + LIFO                  23m   148144m    14283    1424   4293
  bounded + LIFO + deadline       18m      210m    14942      29   5029

  130 rps offered against 100 rps capacity, so 23% of the work cannot
  be done by anyone under any policy. The columns that move are which
  requests get served and how fast -- 'useful' counts responses that
  arrived before the 250 ms deadline, which is the only column a user
  can perceive.

  The order to say it in: you cannot run at high utilisation and be
  fast, because delay goes as 1/(1-rho) and the knee is real. So you
  bound the queue, which converts unbounded latency into a countable
  drop rate. You shed on queue depth or wait time, never on CPU, which
  is flat across the whole overload regime. You drop work whose
  deadline has already passed, because serving it costs capacity and
  delivers nothing. And you protect classes with a reserved floor
  rather than strict priority, because strict priority starves the
  bottom class to zero.

  Built: the knee -> bounded queue -> the shed signal -> FIFO vs LIFO
  -> deadline propagation -> reserved floors.
  Not built, worth ten more minutes: circuit breakers between services,
  retry budgets (a retry storm is offered load you generated), and
  the recovery ramp -- a service that comes back at full traffic goes
  straight back down.

Verify the claims

Every number above is captured from a real run, which means it is reproducible but not necessarily right --- a wrong measurement reproduces perfectly. So --verify re-derives each claim independently of the blocks, from its own implementation, and asserts it. A block with a bug cannot make its own claim pass.

$ python3 c05_load_shedding.py --verify

  [PASS] B1  simulated mean matches M/M/1 at rho=0.50                            20 ms measured vs 20 ms predicted
  [PASS] B1  simulated mean matches M/M/1 at rho=0.80                            51 ms measured vs 50 ms predicted
  [PASS] B1  simulated mean matches M/M/1 at rho=0.90                            107 ms measured vs 100 ms predicted
  [PASS] B1  simulated mean matches M/M/1 at rho=0.95                            202 ms measured vs 200 ms predicted
  [PASS] B1  at rho=0.99 the run is too short and UNDERSTATES the tail           520 ms vs 1000 ms predicted -- relaxation ~1/(1-rho)^2
  [PASS] B1  p99 rises ~9x from 50% to 95% utilisation                           8.7x
  [PASS] B2  an unbounded queue at rho>1 produces multi-second latency           p99 18.6 s
  [PASS] B2  a bound converts it into a bounded latency plus visible drops       p99 169 ms, 2663 dropped
  [PASS] B3  utilisation is pinned at 100% across the whole overload regime      99 rps -> 99%, 120 rps -> 100%: one point of movement
  [PASS] B3  ...while mean queue depth grows by more than an order of magnitude  51 -> 1617 deep
  [PASS] B4  FIFO and LIFO complete the same number of requests                  16968 either way
  [PASS] B4  ...but LIFO serves vastly more of them inside 100 ms                14136 vs 82 under 100 ms
  [PASS] B5  serving everything FIFO wastes almost all of the work               225 of 16968 completions arrived in time
  [PASS] B5  dropping expired work at dequeue is a >10x goodput win              225 -> 13898 useful completions
  14/14 claims verified

It exits non-zero on any failure, so it runs in CI alongside test_handson.py --- which means a claim on this page cannot silently rot.

The design space

Overload control is a control loop, and the design choices are: what you measure, where you act, and what you sacrifice.

Two orderings matter more than the individual rows.

Retry budgets come first. Retries are offered load you generated, and every mechanism above treats offered load as exogenous. A system shedding 30% while its own clients retry three times has created most of its overload; adding a better shedding algorithm optimises around a problem you are causing. The Builders' Library ordering — budget, then breaker, then backoff with jitter — is correct and the reason is that backoff alone spreads load in time without reducing it.

Deadline propagation is nearly free and is skipped anyway. Block 5 measures a 62× improvement in useful completions from checking a deadline at dequeue. Nothing else on this page has that ratio, and its adoption is low because the deadline is usually not available at the point of the check — which is a plumbing problem, not an algorithmic one.

The mathematics you should be able to derive at a whiteboard

For M/M/1 with arrival rate \(\lambda\), service rate \(\mu\), and \(\rho = \lambda/\mu\):

\[ W = \frac{1}{\mu - \lambda} = \frac{1/\mu}{1-\rho}, \qquad L = \lambda W = \frac{\rho}{1-\rho} \]

Mean sojourn time is service time divided by \(1-\rho\). That single expression is the knee, and the table it generates is worth memorising because it ends most capacity arguments:

Block 1's simulation reproduces the mean column to within 7% up to ρ=0.95 and then diverges — because \(1/(1-\rho)^2\) relaxation means the run is too short, not because the formula is wrong.

Three corrections that all move the same direction in practice:

• M/D/1 (constant service time) has exactly half the queueing delay of M/M/1. So variability, not utilisation alone, is what creates queues — and reducing service-time variance is a lever people forget they have.
• M/G/1, Pollaczek–Khinchine: \[ W_q = \frac{\lambda \mathbb{E}[S^2]}{2(1-\rho)} \] Queueing delay depends on the second moment of service time. A heavy-tailed service distribution — which is what real services have — inflates \(\mathbb{E}[S^2]\) enormously at unchanged mean. This is why p99 service time matters to the p50 of everything else.
• M/M/c goes the helpful way: pooling \(c\) servers behind one queue gives dramatically lower delay than \(c\) separate queues at the same ρ. One queue, many workers — never per-worker queues, unless you need them for cache affinity.

Where the numbers come from in production

The retry-budget row is the one that changes an architecture. Without a budget, effective_load = offered × (1 + retries), and under partial failure the retry rate rises exactly when capacity falls — a positive feedback loop that produces metastable failure: the system stays down after the original trigger is gone, because the retries are now the load. Recovery requires shedding more than steady state, which is why "just restart it" often does not work and why the recovery ramp exists.

Advanced

• Adaptive concurrency limits (Netflix concurrency-limits). Treat the service like a TCP connection: probe for the concurrency at which latency starts to rise, and back off — Vegas or a gradient algorithm. Replaces a configured limit nobody can tune with a measured one that tracks real capacity as it changes. This is the single most modern answer to block 3's "which signal", and naming it is a differentiator.
• CoDel (Nichols & Jacobson). Track the minimum sojourn time over an interval; if it stays above target, start dropping with increasing frequency. Using the minimum is the insight: it distinguishes a standing queue (bad, always full) from a burst (fine, drains).
• RED / probabilistic early drop. Drop with probability rising in queue depth rather than at a cliff, which avoids global synchronisation of senders — the same reason Retry-After needs jitter.
• Little's law as a design tool, not an analysis tool. L = λW lets you convert any two of {throughput, latency, concurrency} into the third, which is how you size thread pools, connection pools and queue caps without guessing.
• Brownout / graceful degradation. Shed features rather than requests: return a result without recommendations, skip the personalisation call, serve a stale cache. Strictly better than dropping when the degraded response is worth something, and it needs the request to declare which parts are optional.
• Metastability (Bronson et al., HotOS 2021). The formal treatment of the retry-storm feedback loop: a system with a sustaining effect can remain in the bad state after the trigger is removed. The design implication is that recovery needs a mechanism that is not just "stop the trigger".

How this connects to the rest of the program

• d05 is the full design round: what signal, what to drop, and six hostile critiques including the one about circuit state being read on every request at 1M reads/s.
• C03 is the other kind of limiting. A rate limiter enforces a contract; a shedder protects capacity. Same verb, opposite failure policy — the limiter fails open, the shedder must not.
• m01 is this page on a memory-bound substrate, and the knee is sharper: KV-cache exhaustion causes preemption, preemption causes full prefill recompute, and the recompute needs KV. That is a positive feedback loop, so the degradation is a cliff rather than a hyperbola.
• d04 and d09 both reach the reserved-floor conclusion from block 6.
• Q119–Q130 are the spoken forms; Q126 in particular is the retry-amplification mechanism above.

Failure modes at scale

• Retry storms. Covered above; the first thing to fix and the last thing people look at.
• Shedding the wrong thing. A cheap health check and an expensive query cost the same one queue slot. Cost-weighted admission is the fix, and it needs a cost estimate — which is exactly m01's KV·seconds argument.
• The recovery ramp. A service that comes back and immediately receives full traffic goes straight back down: cold caches, empty connection pools, JIT not warm. Recovery must be ramped (10% → 50% → 100%), and a circuit breaker that closes fully on one successful probe will oscillate.
• Shedding at the wrong layer. Dropping after the expensive work is done saves nothing. The drop must precede the cost, which usually means at the edge — and the edge is where you know least about the request.
• Load balancer works against you. Least-connections routes toward a degraded instance, because a slow instance completes fewer requests and so appears to have fewer connections. This is a real and common outage shape; power-of-two-choices with latency awareness is the mitigation.
• The queue is not the only queue. Bounding the application queue while the kernel accept backlog, the load balancer's queue and the client's connection pool all buffer independently just moves the delay. Every buffer between the client and the work is a queue, and the end-to-end latency is their sum.

Primary sources

• Nichols, K. & Jacobson, V. Controlling Queue Delay (ACM Queue, 2012) — CoDel.
• Facebook Engineering, Making Facebook self-healing / the Thrift queueing work — adaptive LIFO plus CoDel in a request server, the source of block 4's argument.
• Netflix Technology Blog, Performance Under Load: Adaptive Concurrency Limits (2018) — the gradient algorithm behind block 3's best answer.
• Amazon Builders' Library — Using load shedding to avoid overload, Timeouts, retries and backoff with jitter, Avoiding fallback in distributed systems.
• Bronson, N. et al. Metastable Failures in Distributed Systems (HotOS 2021).
• Floyd, S. & Jacobson, V. Random Early Detection Gateways (1993).
• Little, J. D. C. A Proof for the Queuing Formula L = λW (1961).
• Gunther, N. Guerrilla Capacity Planning — the universal scalability law, for when adding servers stops helping.

What to do with this

The number to leave with is the knee: p99 rises 8.7x between 50% and 95% utilisation. That single fact answers "why not just run hotter", "why is the p99 bad when CPU looks fine", and "how much headroom do we need", and it is the first thing to say in any capacity conversation.

Then work d05 cold, and drill Q119--Q130 of the follow-up bank --- the backpressure and retry-storm questions are the spoken form of blocks 2 and 5.

Milestones, experiments, readings and exit criteria for this project: d05 — Load Shedding Gateway.