How do you reduce tail latency with spiky traffic?

In this article

1. Before you start
2. Why interviewers ask this
3. Tail latency under spiky traffic from first principles
4. The Staff-level answer
5. The rubric
6. Three variants of this question
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This question is one part of the machine learning (ML) system design interview guide, where latency budgets come up in almost every serving design.

Why interviewers ask this

A service that looks healthy at average load can fail in the first minute of a spike, so this question tests whether you design for the worst minute and not the average one. It also separates people who know a list of tricks from people who know why the tail forms.

A weak answer says "add more servers and a cache." A strong answer explains that spikes build queues, queues create the slowest requests, and then names the controls: shedding, deadlines, retry limits, capacity ahead of time and the right metrics. A Staff-level answer adds the failure of the fixes themselves: retries that multiply load, shedding that hides a problem in the median, and shedding that switches off autoscaling.

Tail latency under spiky traffic from first principles

Tail latency

Tail latency is the response time of the slowest few percent of requests, such as the p99, which is the time that 99 percent of requests beat, so it describes what unlucky users see and not what the average user sees.

In plain words

Picture a supermarket with one open checkout. When shoppers arrive slowly, nobody waits. When a coach party walks in, the line grows, and the last person in the line waits far longer than the cashier's speed would suggest. The analogy breaks in two places. A real server wastes effort on requests whose clients have already given up, and unhappy clients retry, which adds shoppers to the line.

In one precise sentence, spiky traffic raises utilization for a short time, a queue builds, every request behind the queue inherits its wait, and the controls below keep that queue short or stop the system from adding to it.

Step 1: A spike builds a queue, and the queue is the tail

Latency is not constant. The Amazon Builders' Library reports that a server's latency at low utilization is lower than at high utilization, because contention, context switching, garbage collection and input/output contention grow under heavy load. Queueing theory shows the shape. In the simplest queueing model, called M/M/1 (random arrivals, exponentially distributed service times, one server), the mean time in the system is $\frac{1}{1-\rho }$ times the service time, where $\rho$ is the utilization. The response time is exponentially distributed, so the p99 is $\ln (100)$, about 4.6, times the mean.¹

The p99 time is 9.21, 46.05 and 92.1 times the service time at 50, 90 and 95 percent utilization.¹ Other queue types give other multiples, but the shape is the same: delay rises steeply near full utilization. A spike pushes utilization toward the bottom of this table for a few seconds, and the requests that arrive then form the tail. You now know why the tail grows: waiting, not work. The next step limits the wait.

Text description of the diagram

• The p99 time is 9.21, 46.05 and 92.1 times the service time at 50, 90 and 95 percent utilization.
• A spike pushes utilization toward the bottom of this table for a few seconds.

Step 2: Shed excess load early and pass deadlines

Shedding rejects excess requests early so accepted requests stay fast. The Builders' Library describes the goal as keeping latency low for accepted requests so the service replies before the client times out. It also notes that when latency exceeds the client timeout, a latency problem becomes an availability problem.

Take illustrative numbers: capacity of 1,000 requests per second, a burst of 1,500 requests per second for 10 seconds, and a client timeout of 1 second. Without shedding, a backlog of 5,000 requests builds and the last request waits 5 seconds; after 2 seconds of burst every new request already waits longer than the timeout. With shedding, the server rejects 500 requests per second, a third of the burst, and the rest finish on time.¹

Rank what you reject: as examples of priorities, the Amazon Builders' Library lists load balancer health checks, human traffic ahead of crawler traffic, and over-quota traffic ranked lower than traffic within quota. Clients should also send timeout hints, so servers drop requests nobody is waiting for; check the remaining time after a request leaves the queue, and drop any request already older than its deadline at that point.

Bound the queue as well: an unbounded queue only turns overload into long waits. By Little's law, the number of requests in flight equals throughput times time in the system, so a cap on in-flight requests of capacity times target latency keeps waits near the target, and an adaptive concurrency limit adjusts that cap as measured latency changes. Under overload, serving the newest requests first (last in, first out) lets fresh requests still finish in time, while the oldest ones have probably timed out already.

Step 3: Retries with a budget stop a spike from feeding itself

Retries are the part of the answer that makes or breaks it. The Builders' Library warns that clients often retry, which multiplies the offered load on the system, and a timeout also wastes the partial work the server already did. Retries at several layers of a call chain multiply: with three layers that each try a request three times (illustrative), one user request can become 27 calls at the bottom layer.¹

A retry budget is a cap on retries as a share of recent requests, so retries cannot multiply the load; the Google site reliability engineering (SRE) book, 2016 describes a per-client retry budget of 10 percent, which limits the worst case to 1.1 times the normal load.¹ Retry at one layer only, retry only requests that are safe to repeat, and wait a random, growing delay (backoff with jitter) between attempts so that clients do not return together.

A circuit breaker adds a second guard between services: after a dependency fails repeatedly, the caller stops calling it for a short time and fails fast or degrades, so the failing dependency does not soak up threads and retries. This is backpressure applied at the caller.

The common-error pattern is a service that survives the spike and then collapses under its own retries. You now have the three controls that act inside the spike: shedding, deadlines and a retry budget.

Step 4: Add capacity ahead of time and measure the right percentiles

Autoscaling alone does not handle a sudden spike. The Amazon Builders' Library describes a layered defence that includes proactive autoscaling, graceful shedding, monitoring of those mechanisms and continuous load testing. New servers take time to start, so shedding covers the gap until they arrive; for a spike you can predict, scale before it starts.

The two layers can clash. The Builders' Library warns that a misconfigured shedder can disable reactive automatic scaling, for example when both trigger at a similar processor target, so set shedding above the scaling point.

Measure carefully. If a service sheds, say, 60 percent of its traffic (illustrative), the median latency can look excellent while the latency of successful requests is terrible, because fast-failed rejections under-report it, the effect the Builders' Library warns about. Track percentiles for successful requests, count rejections separately, and watch goodput.

Step 5: Hedge slow calls and watch fan-out

Fan-out makes the tail matter, as Dean and Barroso (2013) show. If a request calls 100 services in parallel and each call independently lands in its own slowest 1 percent with probability 0.01, the chance that at least one call is slow is 1 − 0.99^100, about 63.4 percent; for 10 calls it is 9.56 percent.¹ The independence assumption is what makes the arithmetic simple; correlated slowness changes the exact figure.

A hedged request is a duplicate sent to a second replica only after the first has been slow for a set time, a deferred hedged request in the terms of Dean and Barroso (2013). If the delay is the p95 of normal response time, only about 5 percent of requests are duplicated, so the extra load is small.¹ Hedging fixes random slow replicas. It does not fix overload, where a duplicate only adds load, so turn it off when the system sheds. The multi-stage retrieval funnel is a typical fan-out design where this matters.

1 · Spike builds a queue2 · Shed and set deadlines3 · Budget the retries4 · Scale ahead, measure5 · Hedge slow callsReplay

Step-by-step description

1. Spikes build queues, and queues create the tail.
2. Reject excess requests early so accepted ones stay fast.
3. Retries multiply the load, so cap them.
4. Add capacity before the spike and track percentiles.
5. Duplicate a slow call only after a delay.

• Spikes build queues, and queues create the slowest requests.
• Shedding rejects excess requests early so accepted requests stay fast.
• Retries multiply the offered load on the system.
• A hedged request is a duplicate sent to a second replica only after the first has been slow.

Text description of the diagram

• For 100 parallel calls the chance that at least one call is slow is about 63.4 percent.
• For 10 calls the chance is 9.56 percent.

The Staff-level answer

What makes this Staff-level is that it orders the controls by what acts inside the spike, ends on hedging with a limit, and states the availability trade-off out loud.

The rubric

Three variants of this question

What if the spike is predictable, like a daily peak?

Scale proactively before the peak and load-test it, and keep shedding as the safety net for the surprise on top. A predictable spike makes reactive scaling the wrong tool, because the capacity arrives after the damage.

What if the service is a model server on GPUs?

The same ideas apply, with one addition: a server that batches requests waits a short window to fill each batch, and that window adds directly to tail latency. Keep it small relative to the deadline, and shed or degrade before the queue in front of the batch grows.

What if you cannot reject any request?

Bound the queue and degrade the response instead: serve a cached, cheaper or smaller-model result, and put important requests ahead in a priority queue. A typeahead design with a tight latency budget often makes exactly this choice.

Common mistakes

• "I will add retries so slow requests succeed." (wrong) Retries multiply the offered load during overload. (right) "Retries are budgeted, backed off with jitter and done at one layer."
• "Average latency looks fine, so we are safe." (wrong) Rejections can make the median look excellent. (right) "I track percentiles of successful requests and count rejections separately."
• "Autoscaling handles spikes." (wrong) It is only the first layer, and it is slow for a sudden spike. (right) "I scale ahead of known spikes and keep shedding as the backstop."
• "A bigger queue or connection limit protects the service." (wrong) In the Amazon Builders' Library account, a fixed connection limit is imprecise: set low it can cut off traffic despite spare capacity, set high it lets servers slow down. (right) "I bound the queue, adapt the concurrency limit and shed by deadline and priority, not by one fixed limit."

Follow-up questions

Is load shedding the same as autoscaling?

No. Autoscaling adds capacity over minutes; shedding protects accepted requests within seconds. They can conflict if both trigger at a similar processor target, so set shedding above the scaling point.

Why not simply add more retries?

Each retry adds load to a system that is already slow, and retries at several layers multiply. Use a budget, backoff with jitter and a single retrying layer. A real-time fraud design shows why repeat-safety matters: a retried call that updates velocity counters can double-count.

How do you measure tail latency when you shed load?

Report percentiles for successful requests separately from rejected ones, and watch goodput and the rejection rate. Shedding can also hide that the fleet is closer to its capacity limit than processor metrics suggest.

When should you hedge a request?

Hedge when the slowness comes from random replicas and the extra load is small, and stop when the system is overloaded. A pricing service for a marketplace with sharp peaks, as in dynamic surge pricing, is a case where you would test hedging under peak load before relying on it.

Where does this show up in other designs?

Any design with a latency budget and fan-out meets it, for example an estimated time of arrival (ETA) prediction service that calls several models per request.

Sources

1. Using load shedding to avoid overload — Amazon Builders' Library (David Yanacek), 5 Dec 2019
2. The Tail at Scale — Communications of the ACM 56(2) (Dean and Barroso), 1 Feb 2013
3. Handling Overload (Site Reliability Engineering book) — Google (SRE book), 23 Mar 2016