Load shedding: why overloaded servers should reject requests

Load shedding means a server deliberately rejects some requests when it has more work than it can finish in time, so it can complete the rest quickly. An overloaded server that accepts everything doesn't serve more people. It builds a queue, every request waits longer than the client is willing to wait, and the server spends its capacity on answers nobody will read.

The fix is to decide, early and cheaply, which work you will not do.

What happens to a server under overload?

Overload is any stretch where requests arrive faster than the server can complete them. Capacity is a rate: if one request takes 10 ms of exclusive work, a single worker finishes about 100 per second, no matter how many are waiting.

When 120 requests per second arrive at that worker, 20 extra per second have nowhere to go but a queue. The queue grows by roughly 20 entries every second, and each entry adds 10 ms of wait for everyone behind it. After a minute, a new request is waiting behind over a thousand others.

The damage comes from timeouts. Clients, load balancers and upstream services all give up after some deadline. Once the queue wait exceeds that deadline, the server is still dutifully working through requests whose callers have already left. CPU stays at 100%, the dashboards say the server is busy, and almost nothing useful comes out. This is sometimes called congestion collapse: throughput looks high while goodput, the number of responses that actually arrive in time, falls toward zero.

How much does an unbounded queue cost?

A short simulation makes the shape clear. One worker, 10 ms per request, 120 requests per second arriving randomly for 60 seconds, and a 1 second client timeout. A response counts as useful only if it finishes within that timeout.

import random, collections

def run(policy, seconds=60, rate=120, service=0.010, timeout=1.0, max_queue=50):
    rnd = random.Random(1)
    t, arrivals = 0.0, []
    while t < seconds:
        t += rnd.expovariate(rate)
        arrivals.append(t)
    q, free_at = collections.deque(), 0.0
    stats = collections.Counter()
    for a in arrivals + [float("inf")]:
        while q and free_at <= a:
            arr = q.popleft()
            start = max(free_at, arr)
            if policy == "deadline" and start + service - arr > timeout:
                stats["expired"] += 1          # caller already gave up; skip it
                continue
            free_at = start + service
            stats["useful" if free_at - arr <= timeout else "wasted"] += 1
        if a == float("inf"):
            break
        if policy == "bounded" and len(q) >= max_queue:
            stats["rejected"] += 1              # fail fast
            continue
        q.append(a)
    return dict(stats)

for p in ("unbounded", "bounded", "deadline"):
    print(p, run(p))

Out of about 7,150 requests, the results look like this:

The unbounded queue kept the worker busy the entire time and still delivered about a tenth of the useful responses. Rejecting roughly 15% of requests up front let the bounded queue serve about ten times as many people, each faster.

How does a bounded queue shed load?

A bounded queue has a maximum length. When it is full, new requests are rejected immediately instead of waiting. The rejection is cheap: no database call, no rendering, just a status code.

The useful property is that the bound caps the wait. With 50 slots and 10 ms per request, nothing waits much more than half a second, which is why the p99 in the table sits around 510 ms. To pick a size, work backwards from your latency budget: maximum acceptable wait divided by typical service time, times the number of workers. A queue longer than that only stores requests that will time out.

Pair the queue with a limit on concurrency, the number of requests being worked on at once. Without one, a server under load starts more work than it can finish, and everything slows down together through contention on CPU, memory, connections and locks. A small Node.js version:

const MAX_IN_FLIGHT = 64;   // requests being processed at once
const MAX_WAITING = 128;    // bounded queue behind them
let inFlight = 0;
const waiting = [];

function admit(req, res, handler) {
  if (inFlight < MAX_IN_FLIGHT) return run(req, res, handler);
  if (waiting.length >= MAX_WAITING) {
    res.writeHead(503, { "Retry-After": "1" });
    return res.end("overloaded");
  }
  waiting.push(() => run(req, res, handler));
}

async function run(req, res, handler) {
  inFlight++;
  try { await handler(req, res); }
  finally {
    inFlight--;
    const next = waiting.shift();
    if (next) next();
  }
}

Fire a few hundred simultaneous requests at a slow handler behind this and the excess get an instant 503 while the rest complete at normal speed. Without it, all of them would complete slowly or not at all.

What about requests that are already too old?

The third row in the table uses a different idea: check the deadline when work is taken off the queue, and skip anything whose caller has already given up. This removes wasted work, and goodput is about the same as the bounded queue.

It doesn't fix latency. Every useful response still waited close to the full second, because the queue stays near the timeout. And the queue is still unbounded in principle, so memory is at risk if the overload lasts. The two techniques combine well: bound the queue to cap the wait, and drop expired items so a sudden burst doesn't leave stale work behind.

To check deadlines, the server needs to know them. Clients can pass a deadline or remaining time budget in a header, and services can forward a reduced budget to their own downstream calls. A request with 20 ms left shouldn't start a 200 ms database query.

Some systems also switch from FIFO to LIFO (last in, first out) when the queue is long, serving the newest requests first because they are the ones whose callers are most likely still waiting. In the same simulation, an unbounded LIFO queue delivers about 6,000 useful responses, but the oldest requests starve and memory still grows, so it works best alongside a bound.

When should you reject, and how?

Shed load as early and as cheaply as possible. A request rejected at the edge costs almost nothing; one rejected after authentication, two database queries and a template render has already consumed the capacity you were trying to protect.

A few practical choices:

• Use the right status code. 503 Service Unavailable with a Retry-After header says the server is temporarily overloaded. 429 Too Many Requests is for a client exceeding its own quota, which is a rate limiting decision rather than a capacity one.
• Shed by priority. Not all traffic is equal. Health checks, checkout and logged-in users can be admitted while background sync, prefetch and analytics beacons are rejected first.
• Signal on something you can measure. Queue length, queue wait time, in-flight count and CPU are all workable triggers. Queue wait time is often the most direct, since it measures exactly what the client experiences.
• Make clients cooperate. Rejections only help if clients don't immediately retry them. Retries should use exponential backoff with jitter, and callers can stop sending to a struggling dependency altogether with a circuit breaker.

Shedding is the server protecting itself; backoff and circuit breakers are the clients protecting it. You want both, because a server that rejects 20% of traffic while every client retries three times has quadrupled its incoming load.

Key takeaways

• Under overload, an unbounded queue turns all work into late work, and goodput collapses even at 100% CPU.
• A bounded queue caps wait time; size it from your latency budget, not from memory.
• Limit concurrency so admitted requests finish at normal speed.
• Drop requests whose deadline has passed before doing any work on them.
• Reject early, by priority, with a 503 and Retry-After, and make sure clients back off.

FAQ

Isn't rejecting requests worse than serving them slowly?

Only if the slow response arrives before the client gives up. Under sustained overload most don't, so rejecting some requests is what lets the others succeed.

How is load shedding different from rate limiting?

Rate limiting caps how much each client may send, regardless of server health. Load shedding reacts to the server's current capacity and rejects work when the whole system is full, even if every client is within its quota.

Should autoscaling replace load shedding?

No. New capacity takes time to start, and shedding keeps the service responsive during that gap. Autoscaling raises the ceiling; shedding decides what happens when you hit it.