d05 — Load Shedding and Admission Control Gateway

A fully worked design. The reliability primitive every other design leans on. Where d03 enforces a contract, this protects capacity — and conflating the two is the most common error in this problem.

Run it first. A companion page builds this as numbered, independently runnable blocks: the knee against the M/M/1 closed form, FIFO against LIFO under sustained overload, and the cost of serving work whose deadline has passed: Hands-On — The Utilisation Knee, Block by Block. Every number on it was produced by running the code.

Table of Contents

The Prompt

"Our service falls over under load. Not gracefully — it goes from fine to completely down over a couple of minutes, and it takes twenty minutes to come back even after traffic drops. Design something that stops that."

"Twenty minutes to come back even after traffic drops" is the diagnostic. A system that recovers as soon as load falls is merely overloaded. A system that stays down is in congestion collapse — it is spending its capacity on work that will never complete: requests whose clients have already timed out, retries stacking on retries, queues full of items that are older than anyone's patience.

That reframing is the answer to the whole question. You are not building a rate limiter. You are building something that keeps the system doing useful work under overload.

1. Requirements and Scope

Clarifying questions asked

"Is the overload from more requests, or from each request getting more expensive?" Both happen and they need different responses. A traffic spike wants shedding; a slow dependency making each request expensive wants concurrency limiting and timeouts. Assumed: both.

"Do all requests have equal value?" Assumed no — there are paying tiers, internal health/control traffic, and best-effort. That is what makes prioritized shedding possible, and without it shedding is just random failure.

"Can clients retry?" Assumed yes, which is a hazard as much as a mitigation — see §6.

"What's the current p99 and what's the SLO?" Assumed p99 200 ms SLO, currently 180 ms healthy.

Functional

  1. Admit or reject each request, in microseconds, before it consumes a worker.
  2. Prioritize by class when capacity is short.
  3. Discover the capacity limit rather than have it configured.
  4. Propagate deadlines so no hop starts work it cannot finish.
  5. Expose why a request was rejected, to the client and to us.

Non-functional

PropertyTarget
Added latency when admitting< 50 µs — it is on every request
Rejection latency< 1 ms — a fast failure is the entire point
Behaviour at 2× capacitygoodput stays at ~100% of capacity; does not collapse
Recoveryreturns to healthy within seconds of load dropping, not minutes
Availabilitymust not itself be a failure mode — in-process, no external dependency on the hot path

Explicitly out of scope

  • Per-customer contractual quotas — that is d03. This protects capacity, that enforces a contract. Both exist; they are not the same component.
  • Autoscaling. Shedding is what you do because scaling takes minutes; they are the same control problem at different time scales.
  • Client-side load balancing.

2. Scale Numbers

The curve that justifies everything. For an M/M/1 queue, response time is W_s / (1 - ρ):

ρ0.50.70.80.90.950.99
× service time2.03.35.01020100

Latency is hyperbolic in utilization, not linear. 50% → 80% costs 2.5×. 90% → 95% costs another 2×. That is why a service at 85% looks fine on a dashboard and falls over at 92%. Real traffic is burstier than Poisson, so the true knee arrives earlier than this table.

The collapse arithmetic. Service at 10,000 rps capacity, 10 ms service time, 30 s client timeout. Load rises to 15,000 rps:

Excess arrivals      = 5,000/s
Queue growth         = 5,000/s
After 60 s           = 300,000 queued
Wait for a new item  = 300,000 / 10,000 = 30 s   ← exactly the client timeout

Every request now completes after its client has given up. Goodput is zero while utilization reads 100%. And retries have tripled the offered load, so it does not recover when the spike ends. That is the twenty minutes.

The bound that prevents it. By Little's law, to keep queue wait under a 200 ms SLO at 10,000 rps: L = λW = 10,000 × 0.2 = 2,000. So the queue must be bounded at ~2,000, not unbounded. That single number is the fix, and it comes from arithmetic rather than from taste.

Cost of rejection. ~50 µs to reject vs 10 ms to serve — 200× cheaper. So rejecting 50% of a 2× overload costs 0.25% of capacity. Shedding is nearly free; that is why it works.

3. API Surface

# In-process library on the request path. Not a service — see below.
admit(request) -> Admission(ok: bool, reason: str, retry_after: float | None)

# Control plane
PUT /shedding/policy   {classes: [...], slo_ms, min_admit_rate}   -> 204
GET /shedding/state                                               -> {limit, inflight,
                                                                      shed_rate_by_class,
                                                                      p99_ms, mode}

Why in-process. A shedding service adds a network hop to every request, which is 0.5 ms against a 50 µs budget — 10× the thing it is measuring. Worse, it becomes a dependency that can itself be overloaded, which is a shedding component that fails under load. Every serious implementation (Envoy's adaptive concurrency, Netflix's concurrency-limits, gRPC) is a filter in the request path.

On the rejection response: 503 with Retry-After, and a header naming the class that was shed. Without Retry-After clients retry immediately and you have converted shedding into amplification — the exact failure you are preventing.

4. Data Model

Almost none, deliberately. State lives in-process because anything else is on the hot path.

Per process, in memory:
  inflight              atomic counter
  limit                 float, adapted by AIMD
  latency_window        a bounded ring of recent latencies (for percentiles)
  per_class:            {inflight, admitted, shed, reserved_floor}
  queue                 bounded, priority-ordered, LIFO-under-load

Pushed config (never polled on the hot path):
  class definitions, weights, floors, SLO target

Why a ring buffer for latency, not a histogram: we need a recent p99 that reacts within seconds, and an ever-growing histogram is dominated by history. A ring of the last N (say 2,000) observations gives a percentile over roughly the last second at 10k rps, which is the right time constant for a control loop.

5. High-Level Architecture

   request
      │
      ▼
 ┌────────────────────────────────────────────────────────┐
 │  Admission filter (in-process, ~50 µs)                 │
 │                                                        │
 │  1. Deadline check  — is there time left to finish?    │
 │  2. Class lookup    — priority + reserved floor        │
 │  3. Concurrency     — inflight < adaptive limit?       │
 │  4. Queue admit     — bounded, priority, LIFO-on-load  │
 │                                                        │
 │        admit ──────────────────────┐   reject → 503    │
 └────────────────────────────────────┼──────────────────┘
                                      ▼
                              ┌───────────────┐
                              │  Handler      │──▶ downstream
                              └───────┬───────┘    (deadline passed on)
                                      │ latency + outcome
                                      ▼
                        ┌──────────────────────────────┐
                        │  AIMD controller             │
                        │  +1 when healthy             │
                        │  ×0.8 on failure / latency   │
                        └──────────────────────────────┘

The two hard parts — say these at minute 10:

  1. What signal do you shed on? Every obvious choice is wrong in a specific way.
  2. What do you drop? Random shedding is barely better than collapse.

6. Deep Dive A: What Signal Do You Shed On

Four candidate signals, three of which are traps.

CPU utilization — wrong

The reflex answer. It fails for a specific reason: an I/O-bound service under overload has low CPU and unbounded queues. Threads are blocked on a slow dependency; CPU reads 20%; the service is completely down. Shedding on CPU would admit everything right up to the collapse.

It is also lagging — by the time CPU is saturated the queue is already deep.

Request rate — wrong

You cannot set a threshold, because capacity is not a constant. It changes with request mix, with downstream health, with cache hit rate, with a noisy neighbour on the same host. A static rps threshold is either too low (you shed when healthy) or too high (you never shed) and it is always wrong after the next deploy.

Latency — necessary but insufficient

Rising p99 is real evidence of queueing. But it is lagging: latency only rises after the queue is deep, and by then you are already serving requests nobody wants. Good as a trigger, bad as the only input.

Queue depth and wait time — the right primary signal

Queue wait time is the direct measurement of unmet demand, and it is leading rather than lagging: an item's time-in-queue is known the instant you dequeue it, before you spend anything on it.

def admit(request):
    if request.deadline_remaining() <= expected_service_time:
        return reject("deadline_exceeded")          # cannot finish it anyway

    if queue.wait_estimate() > slo_budget * 0.5:
        if not request.class_.has_reserved_capacity():
            return reject("queue_wait")

    if inflight >= limit:
        return reject("concurrency")

    return admit_to_queue(request)

And the limit itself must be discovered, not configured

A static concurrency limit is wrong the same way a static rps threshold is wrong. AIMD — the same control law as TCP congestion control, and for the same reason: the correct limit is discovered from feedback.

def on_complete(latency, failed):
    if failed or latency > target * 2:
        limit = max(MIN, limit * 0.8)        # multiplicative decrease: back off hard
    elif latency < target and inflight >= limit * 0.9:
        limit = min(MAX, limit + 1)          # additive increase: probe gently, and
                                             # only when actually saturated

The inflight >= limit * 0.9 guard is the part people miss. Without it the limit grows without bound during quiet periods, so when a spike arrives the limit is enormous and admits everything. You only learn about capacity when you are near it.

Why gradient-based (Netflix's approach) is better still: compare current latency to the minimum observed latency — gradient = rtt_noload / rtt_current — and set the limit proportionally. It distinguishes "slow because queued" from "slow because the work is genuinely heavier", which pure AIMD cannot. Worth naming as the refinement.

Say the summary: shed on queue wait, adapt the limit with AIMD, use latency as the health signal for the controller, and never use CPU or a static rps threshold.

7. Deep Dive B: Choosing What to Drop

Shedding randomly is barely better than collapsing — you fail 50% of every customer's requests instead of 100% of everyone's. Three decisions.

1. Priority classes with reserved floors

critical    health checks, control plane, cache invalidation   never shed
paid-tier   revenue traffic                                    floor 60%
free-tier   best effort                                        floor 5%
batch       async, deadline-tolerant                           shed first

Floors, not just priorities. Pure priority ordering starves the low class completely under sustained overload, and a free tier that is 100% down is a product outage even if it is not a paid one. A floor guarantees each class some capacity; the surplus goes by priority.

Critical must genuinely never be shed — and this is the one that saves you. If health checks get shed, your load balancer marks every instance unhealthy and removes them all, converting an overload into a total outage. That has happened to real systems and it is the most important row in the table.

2. Shed the OLDEST queued item — LIFO under load

Counter-intuitive until you see the arithmetic. Under sustained overload with FIFO:

Queue 300,000 deep, 10,000/s service rate.
The item at the head has waited 30 s — its client timed out at 30 s.
So FIFO serves EXCLUSIVELY requests nobody is waiting for. Goodput = 0.

LIFO under load serves the newest first, which are the ones whose clients are still there. Goodput goes from 0 to ~100% of capacity while the same number of requests fail. Unfair by arrival order, dramatically better by outcome — and the requests it starves would have timed out under FIFO anyway.

The refinement: FIFO when healthy, LIFO when the queue exceeds a threshold. Fairness when it is free, goodput when it is not.

3. Deadline propagation

The client sends its deadline; every hop passes the remaining budget downstream; any service that sees insufficient time fails immediately rather than starting work it cannot finish.

Client: deadline = now + 500ms
  → Gateway:  480ms left → ok
    → Service A: 460ms left, needs ~200ms → ok
      → Service B: 30ms left, needs ~200ms → REJECT IMMEDIATELY

Without it, service B does 200 ms of work that is thrown away — and under overload every hop is doing that, which is precisely how capacity is consumed by nothing. gRPC deadlines work this way, and it converts wasted capacity into fast failures across the whole call graph, which is a much stronger property than any single service can achieve alone.

4. And bound the retries

Shedding produces 503s, and 503s produce retries. With 3 attempts at a 95% shed rate you get 2.85× the offered load — the shedding causes the overload it is shedding.

The fix order, and most people get it backwards: retry budget (cap retries at ~10% of base traffic, so amplification is bounded at 1.1× no matter what) → circuit breaker → jitter. Plus Retry-After on every 503, so clients back off correctly rather than immediately.

8. Failure and Recovery

FailureDetectionContainmentRecovery
Traffic spikequeue wait risesshed by class, floors honouredlimit re-probes upward via AIMD within seconds
Slow downstreamlatency rises, inflight climbsAIMD cuts the limit; timeouts bound each requestlimit recovers as latency does
Downstream downerror ratecircuit breaker opens; fail fast; degraded response if one existshalf-open probe
Retry stormrequest rate up while success rate fallsretry budget bounds amplification at 1.1×breaker + Retry-After
Congestion collapse in progressgoodput ≪ throughputLIFO + deadline checks discard doomed workgoodput recovers in seconds
Health checks shed—structurally impossible — critical class is never shed—
AIMD limit collapses to MINlimit metric floorMIN is nonzero, so some traffic always flows and the controller can learnprobes upward
Clock skew affecting deadlines—deadlines carried as remaining duration, not absolute timestampsimmune by construction
Config push failsconfig version metrickeep the last known policy — stale shedding beats no sheddingretry; alarm
Shedding masks a real regressionshed rate + p99 both elevated for hoursalarm on sustained shedding, not instantaneousit is a capacity conversation

Deliberately accepted: under sustained 2× overload, free-tier traffic sees ~95% rejection. I accept that because the alternative is everyone at 100% rejection, and because the floor guarantees the tier is degraded rather than dead. If the business needs better, that is a capacity decision, not a shedding one — and the metric makes the conversation possible.

The deadline-as-duration row is worth calling out. Carrying an absolute deadline timestamp across services makes correctness depend on clock synchronization; carrying remaining milliseconds and decrementing at each hop is immune to skew entirely. It is a small choice that removes a whole failure class.

9. Bottlenecks and Evolution

1. Percentile computation on the hot path. Computing p99 per request from a ring buffer is O(n log n) if you sort. Fix: a fixed-bucket histogram with atomic increments (O(1) per observation) and periodic percentile extraction on a background tick. This is the kind of thing that is fine at 1k rps and is 30% of your CPU at 100k.

2. Contention on the inflight counter. One atomic counter incremented and decremented per request, on every core. At high rates this cacheline is the hottest thing in the process. Fix: per-core counters summed periodically, accepting a slightly stale total — the controller does not need exactness.

3. Coordination across instances — the real limit. Each process sheds independently based on its own view, which is correct for its own capacity but blind to shared downstream capacity. Ten instances each admitting to their own limit can still collectively overwhelm one database. Fix: gossip the aggregate downstream concurrency, or push the limit to where the contention is (a concurrency limit on the database client, not on the HTTP handler).

4. It cannot fix a fundamentally undersized system. Shedding converts an outage into degradation; it does not create capacity. Sustained shedding is a signal to scale, and the design must make that visible rather than hiding the problem — hence alarming on sustained shed rate.

At 100×: the design does not change much, which is a good sign. What changes is where the limit is enforced: with enough instances you want cell-based isolation so a single cell's overload cannot spread, and the shedding decision moves to the cell router.

10. Tradeoffs Explicitly Rejected

Rejected: a static concurrency limit. Simple and testable. Rejected because capacity is not constant — it varies with request mix, downstream health, and cache warmth, and the correct value changes with every deploy. Flip condition: for a service with genuinely homogeneous requests and a fixed downstream, a static limit measured by load testing is simpler and adequate.

Rejected: shedding on CPU. Rejected because an I/O-bound service under overload has low CPU and unbounded queues, so CPU would admit everything right up to collapse. Flip condition: a purely CPU-bound service — video transcoding, say — where CPU genuinely is the capacity.

Rejected: an unbounded queue. The default in most frameworks. Rejected on Little's law: a queue deeper than λ × SLO guarantees that dequeued items are already past their deadline. An unbounded queue does not absorb overload, it converts a throughput problem into a latency problem and then an OOM.

Rejected: FIFO under overload. Fairer by arrival order. Rejected because under sustained overload FIFO serves exclusively requests whose clients have already timed out — goodput zero. Flip condition: if clients did not time out (a batch pipeline), FIFO is correct and LIFO would be actively unfair.

Rejected: pure priority without floors. Rejected because it starves the lowest class to exactly zero, which is a product outage for that tier. Floors make it degradation.

Rejected: a shedding microservice. Rejected because it adds 0.5 ms to a 50 µs budget and introduces a dependency that can itself be overloaded — a load-shedder that fails under load. Flip condition: an API gateway you already traverse (Envoy) is the right place, because the hop already exists.

Rejected: shedding at the load balancer only. The LB can shed by rate but has no view of queue depth, downstream latency, or request class. Flip condition: for a volumetric DDoS, the LB (or the CDN) is exactly right and the application layer is too late.

The Hostile Critique

C1. "AIMD probes upward with +1 per healthy request. After a five-minute quiet period at 100 rps, what is your limit? Then a spike arrives. Walk me through the first two seconds."

C2. "You shed on queue wait exceeding half the SLO budget. Where does the SLO budget come from for a request that has already spent 400 ms in three upstream hops? Your service sees a 200 ms SLO and 100 ms of actual budget."

C3. "LIFO under load. A customer's request arrives during a 90-second overload and sits at the bottom of the stack the entire time, then gets shed. From their perspective you held their connection open for 90 seconds and then failed. Is that better than failing fast?"

C4. "Your critical class is never shed. A bug makes a health check expensive — it starts doing a full dependency check taking 2 seconds. Now the unsheddable class is consuming your whole fleet. What happens?"

C5. "Each instance sheds on its own view. You have 200 instances behind a load balancer and one database with 500 connections. Each instance's AIMD independently discovers it can do 50 concurrent. Do the arithmetic."

C6. "You alarm on sustained shedding. During Black Friday you shed 30% of free tier for six hours and it was correct. Your alarm fired for six hours. What did the on-call do at hour two?"

The Revision

R1 — Cap the limit's growth and decay it when idle (answers C1)

The critique is exactly right and it is a real, well-known AIMD failure. At 100 rps for five minutes, the inflight >= limit * 0.9 guard should prevent growth — but if the limit ever drifted below the idle inflight, it grows unbounded. And even correctly guarded, the limit remembers a capacity measured under different conditions.

Change, three parts:

  1. A hard ceiling from arithmetic, not from probing: MAX = target_rps × slo_seconds × 1.5, derived from Little's law. The controller may never exceed what the SLO can support.
  2. Decay toward the observed concurrency when idle: limit = max(MIN, limit × 0.99) per second when inflight < limit × 0.5. So a long quiet period returns the limit to something near recent reality rather than a stale high-water mark.
  3. Fast initial descent. The first latency violation after a quiet period cuts by 0.5 rather than 0.8, because a stale limit is likely to be badly wrong. Subsequent cuts use 0.8.

Cost: after a genuine capacity increase (a bigger instance type), the limit takes longer to find it. Acceptable — under-admitting briefly is far cheaper than the two seconds of collapse the critique describes.

R2 — Deadline is the budget; SLO is only a fallback (answers C2)

The critique identifies a genuine conflation. The SLO is our target; the deadline is what the caller actually has.

Change: the admission decision uses, in order of preference:

  1. The propagated remaining deadline, if present. That is the truth.
  2. The SLO budget minus observed upstream latency, if the caller sends an X-Request-Start.
  3. The SLO budget, only if neither is available.
budget = request.deadline_remaining() or (slo - request.upstream_elapsed()) or slo
if queue.wait_estimate() + expected_service > budget:
    return reject("insufficient_budget")

And make deadline propagation mandatory at the edge: the gateway stamps a deadline on every inbound request if the client did not supply one. Then every internal hop has a real budget rather than a guess.

Cost: requests from clients that do not propagate deadlines get the conservative fallback and may be shed slightly more eagerly. That is the correct direction to err, and it creates pressure to adopt propagation.

R3 — Reject at admission, not after queueing (answers C3)

The critique is right, and it exposes that I described the queue as if it were the only place to shed.

Change: the decision is made at admission, before the request enters the queue, using the predicted wait. Nothing that will be shed should ever be enqueued.

predicted_wait = queue.depth / current_service_rate
if predicted_wait + expected_service > budget:
    return reject_immediately("predicted_wait")     # < 1 ms, connection released

LIFO then applies only to already-admitted work, as a hedge against the prediction being wrong — a request whose deadline expires while queued is dropped at dequeue with a cheap check, not served.

So the answer to the critique is: the customer gets a fast 503 with Retry-After in under a millisecond, not a 90-second hang. Holding a connection you intend to fail is strictly worse than failing immediately — it consumes a socket, a client thread, and their patience, and it teaches clients nothing about backing off.

R4 — Critical means unsheddable, not unbounded (answers C4)

The critique found a genuine hole: "never shed" is not the same as "cannot consume the fleet", and an expensive critical request is a self-inflicted denial of service through a path I declared exempt.

Change:

  1. Every class, including critical, has a concurrency ceiling. Critical is exempt from shedding by pressure, not from bounds. Ceiling set generously — say 5% of the fleet — but finite.
  2. Health checks get a hard timeout well below their ceiling (100 ms). A health check that cannot answer in 100 ms is a failure, and reporting it as such is more correct than waiting 2 seconds for it.
  3. Health checks must be cheap by construction — a shallow liveness check, with the deep dependency check on a separate, lower-priority endpoint that the LB does not use for eviction. This is the actual root-cause fix.
  4. Alarm on critical-class share of total concurrency. If it exceeds a few percent, something is wrong with the definition of critical.

Cost: a genuine burst of legitimate critical traffic could hit its ceiling. Given that critical is health and control-plane traffic, that burst is itself a symptom worth alarming on.

R5 — Limit where the contention is (answers C5)

The arithmetic in the critique is damning: 200 instances × 50 concurrent = 10,000 concurrent against 500 database connections, a 20× oversubscription that no per-instance limiter can see.

Change: the concurrency limit belongs at the resource, not at the entry point.

  1. A separate AIMD limiter per downstream dependency, inside the client for that dependency. Its feedback signal is that dependency's latency and errors. Now each instance discovers its share of the database's capacity, not of its own.
  2. Bound it explicitly by the dependency's known limit: per_instance_max = db_connection_limit / instance_count × safety_factor, with instance_count from service discovery.
  3. The HTTP admission filter and the dependency limiter compose: a request is admitted only if the entry-point limit and every dependency limit it will need have room. A request that will certainly block on an exhausted database connection pool should be rejected at the door, not admitted and then blocked.

Cost: more limiters and more configuration, and the dependency limiters need to know which dependencies a request will touch (which is often static per endpoint). Worth it — this is the difference between shedding that works in a single-instance test and shedding that works in production.

The general lesson worth saying: a limiter that cannot see the contended resource is guessing. Put the limit where the contention is.

R6 — Alarm on the anomaly, not the level (answers C6)

The critique describes exactly how a good alarm becomes noise, and then becomes ignored — which is worse than no alarm.

Change: three signals instead of one.

SignalFires onSeverity
Critical/paid shedding > 0any shedding of a class with a floor above best-effortpage
Shed rate anomalous vs baselineshed rate outside the band for this hour-of-weekticket
Goodput droppingadmitted-and-completed-within-SLO falling, regardless of shed ratepage

Shedding 30% of free tier on Black Friday matches the seasonal baseline and paid tier is unaffected → no page, and it appears on a dashboard as expected behaviour. Shedding 5% of paid tier on a Tuesday → page immediately.

And the metric that should have been primary all along: goodput — requests admitted and completed within their deadline. Throughput can look healthy while goodput is zero, which is exactly the collapse this whole design exists to prevent. Alarming on shed rate measures the mechanism; alarming on goodput measures the outcome.

Cost: seasonal baselines need enough history to be meaningful, and they are wrong for a genuinely novel traffic pattern. Mitigated by keeping the paid-tier and goodput alarms threshold-based and unconditional — those two never depend on a learned baseline.

References