Timeout Budgets, Deadline Propagation, and the Arithmetic of Retry Amplification

A timeout is usually described as a client’s decision about how long to wait. It is more usefully described as a statement about the latency distribution the client expects, and as such it is a load parameter: any attempt that exceeds the timeout is discarded by the client and often reissued, so the timeout’s position in the distribution determines how much of the server’s work is wasted and how much extra load the failure generates.

The same reasoning applies one level down. A request that has already spent 300 milliseconds of its budget cannot be served by a call that is allowed to take a second. Timeouts set independently at each tier compose into a system whose worst-case latency is the sum of the tier timeouts, and whose failure behaviour under overload is determined by the ratio between the timeouts and the actual service times.

Where a timeout sits in the distribution

A timeout at the median of the service’s latency distribution fails about half of all requests when the service is healthy. That is obviously wrong, and the usual correction is to set the timeout above a high percentile, on the argument that only the tail should fail. The argument is sound but incomplete, because the fraction of requests that exceed the timeout is the fraction that both fails the client and consumes server resources.

Setting a timeout at the p99.9 of a healthy service means one request in a thousand times out. Under moderate overload the distribution shifts and that fraction rises; if the p99.9 doubles under load while the timeout is fixed, the timeout fraction rises from 0.1 percent to a value determined by where the old p99.9 now sits in the shifted distribution, which can be several percent. The timeout fraction is therefore not a constant property of the configuration; it is a function of the load.

The choice is between a timeout that is generous enough to survive load shifts, at the cost of a long wait for requests that will fail anyway, and a tight timeout that caps the wait, at the cost of failing requests that would have succeeded. The relevant comparison is the service time of a succeeding request against the cost of a failing one. A request that is abandoned after 500 milliseconds has consumed 500 milliseconds of a worker; a request that would have succeeded in 600 milliseconds and instead failed at 500 has consumed the same 500 milliseconds and returned nothing. The tighter timeout saves nothing except the client’s waiting time, which is why it helps only when the client can use those 100 milliseconds for something else.

Retry amplification is multiplicative across tiers

A single retry policy is easy to reason about. A client making up to three attempts contributes at most three times the work per logical request. Observed from the server, an arrival rate of $r$ logical requests becomes up to $3r$ attempts, and the server’s capacity is consumed by attempts.

Composition across tiers multiplies. If the frontend retries twice and each of its attempts goes to a service that retries twice, a single user request can generate up to $3 \times 3 = 9$ calls at the bottom tier. With one more level the exponent rises again. The amplification factor is the product of the per-tier attempt counts, and it applies exactly when the system is least able to absorb it, because retries are triggered by failures, and failures cluster.

The arithmetic of a retry storm follows from the same structure. Suppose a service at its capacity limit experiences a transient that makes 5 percent of requests fail by timing out. The failure triggers retries, which adds 5 percent to the offered load. If the service is at capacity, that extra load increases latency, which increases the timeout fraction, which increases retries. Above a threshold the fixed point of this feedback is total collapse, where the offered load is dominated by retries of requests that will never succeed. An unbounded queue makes the first of those possible, because the load that arrives during the overload period is retained rather than refused; the bound described in Bounded Queues, Backpressure, and What to Drop Under Overload is what keeps the retry rate bounded as well, since it fails requests quickly enough for the client’s own timeout to be the binding constraint rather than the server’s.

The standard mechanism is a retry budget: a limit on the fraction of additional attempts relative to the successful request rate. Expressed as a token bucket that is refilled by completed requests and consumed by retries, it allows a healthy system to retry freely (successes refill the budget) and throttles retries as soon as the success rate falls, which is exactly when retries stop helping. The budget is a control on the amplification factor itself, whereas a per-request attempt cap only bounds each request’s contribution.

Jitter addresses a different failure. A retry after a fixed delay produces a synchronized second wave of arrivals, and if the retry delay is exponential backoff without jitter, all the clients that failed at the same instant retry at the same instants. Adding a random component to the delay spreads the retries over an interval, converting a spike into a plateau. The amount of jitter matters: a delay drawn uniformly between zero and the backoff interval spreads arrivals maximally over that interval, while a small additive jitter around a fixed delay leaves them clustered. A retry is also not the same mechanism as a hedge: a retry is issued after a failure and therefore adds load after the system has already shown it cannot keep up, whereas the speculative duplicate described in Hedged Requests, Tied Requests, and the Cost of Buying Back the Tail is issued on a timer against a system that is still succeeding, and it is the timer rather than a failure that bounds its cost.

Deadline propagation

A budget that is set at each tier independently produces a latency bound that is the sum of the tier timeouts. A request with three tiers each allowing one second can legitimately take three seconds, even though the client’s own timeout may be 500 milliseconds, in which case the frontend’s work is wasted from the moment it starts the first call.

Propagating a deadline fixes this by making the remaining time part of the request. The frontend computes a deadline from its own budget, sends it with the request, and each tier subtracts the time it has already consumed before deciding whether to start a downstream call. A tier that receives a deadline already in the past refuses immediately, which is the correct behaviour: the work would be discarded by the caller.

import time

def with_budget(deadline_ns, stages, reserve_ns=5_000_000):
    """Run stages in order, stopping when the remaining budget is insufficient.
    deadline_ns is an absolute monotonic deadline shared by all participants."""
    results = []
    for name, cost_ns, work in stages:
        remaining = deadline_ns - time.monotonic_ns()
        if remaining <= reserve_ns:
            return results, name        # refuse: not enough time to be useful
        if cost_ns > remaining:
            return results, name
        results.append(work())
    return results, None

Two details make the mechanism work in practice. The deadline must be an absolute instant rather than a duration, so that tiers do not each start a fresh timer; and it must be compared against a monotonic clock, since wall-clock time can step. The reserve term accounts for the time to transmit the response and for the caller’s own processing, both of which are outside the callee’s view.

A propagated deadline degrades the system in a specific and useful way. Under load, as latency rises, the fraction of requests whose deadline has already expired at each tier rises, and those requests are refused without work. The effect is a feedback loop that removes work from the system as the system slows, which is the opposite of the retry loop. The two loops coexist and their relative strength determines whether an overload episode recovers.

Cascading timeouts and the tightest-bound rule

Independent per-tier timeouts create a case where a downstream call is allowed to outlive the caller’s tolerance. The frontend gives up at 500 milliseconds, the mid-tier allowed itself one second for the same work, and the bottom tier two seconds. Between the frontend’s abandonment and the bottom tier’s completion, work continues for 1.5 seconds on behalf of nobody.

The rule that avoids this is that each tier’s timeout must be strictly smaller than the remaining budget it was given, by at least the cost of the round trip. Applying the rule from the outside in makes the innermost timeout the smallest, which is the reverse of the common configuration where timeouts are set to generous round numbers at every level.

The rule also exposes the ragged bottom of the distribution. A frontend timeout of 500 milliseconds with three tiers implies that the innermost call has perhaps 400 milliseconds after transmission and processing overheads, and a call that needs 600 milliseconds at the p99.9 has an irreducible failure rate under that budget. Fixing it requires either a larger frontend budget or a faster innermost operation; loosening the inner timeout without loosening the outer one changes nothing.

Protocol-level examples

TCP’s retransmission timer is the canonical implementation of the feedback problem in miniature. The specification requires the initial retransmission timeout to be one second and requires the timer to be derived from measured round-trip times and their variance on subsequent retransmissions, with exponential backoff on continued failure. The one-second initial value is deliberately conservative, because a retransmission sent too early on a path whose round trip is genuinely long adds duplicate load without helping. The measurement and variance terms are what let the timer adapt to the actual path rather than to an assumption about it.

At the application layer, HTTP defines a status code for temporary unavailability and a header that states how long the client should wait before trying again. The header is the mechanism that lets a server throttle retries without relying on the client’s own backoff discipline, and it is the only point in the exchange at which the server can express a rate as well as a refusal. A server that sheds load but omits the signal leaves retry timing to the client, and clients that default to immediate retries reproduce the load at the refusal rate.

Observing whether the budget is being spent usefully

The measurement that governs all of this is the distribution of remaining budget at each tier, not just the count of timeouts. A tier whose requests typically arrive with 20 percent of their budget remaining is serving requests that are near the edge, and its own p99 will produce failures even if its own latency distribution is unchanged. The same tier receiving requests with 80 percent of budget remaining is operating comfortably.

The two counters worth keeping alongside it are the count of requests refused because the deadline had passed and the count of attempts per successful logical request. The first measures how much work the propagation mechanism is correctly avoiding; the second measures the amplification factor directly, and it is the number that reveals a retry storm before it becomes one. Both are cheap, additive across the fleet, and independent of the latency distribution’s shape, unlike the percentile of the end-to-end latency that first draws attention to the problem.