Deadlines, Timeouts, Retries, Hedging, and Idempotency

The trace begins with one logical operation and ends with four different stories about it:

00 ms  client starts capture op-834; absolute deadline is +240 ms
18 ms  gateway calls payment service; its client timeout is 200 ms
31 ms  service calls fraud check; library timeout is 200 ms
79 ms  service calls ledger; library timeout is 300 ms
240 ms caller stops waiting and reports "outcome unknown"
261 ms gateway cancels its local wait
388 ms ledger commits the capture
401 ms service tries to publish a response to an abandoned caller
427 ms client retries op-834 through another gateway

The caller observed failure. The ledger recorded success. The first service attempt became orphan work. The second attempt may duplicate the effect unless both requests carry the same durable operation identity. Every component’s timeout can be locally reasonable and the system can still be globally incoherent.

The modeled stack makes the defect visible. The caller allows 240 ms, while independent hop settings permit 200 + 300 + 100 = 600 ms along one sequential path. Those numbers are not a latency budget; they are unrelated patience limits. Repair starts by propagating the caller’s absolute deadline, subtracting elapsed time and a return-path reserve, and refusing a child budget that cannot fit. Retry and hedging policy comes later, after time ownership and effect semantics are explicit.

Follow one logical operation across its attempts. The governing rule is stricter than “use exponential backoff”: create another attempt only when safety, remaining time, transient-failure evidence, and a system-wide retry budget all agree.

One deadline owns the whole completion path

A deadline is the latest instant at which the caller still values a terminal outcome. A timeout bounds one wait, phase, connection, or operation. An idle timeout limits a period without progress. These controls may coexist, but they answer different questions.

Prefer an absolute deadline in a clock domain whose propagation rules are defined. Each hop computes remaining time at receipt. If a protocol carries a relative duration, account for transit and queue time and avoid treating a freshly decoded duration as a renewed budget. Clock uncertainty matters when independent wall clocks interpret an absolute timestamp; some RPC systems encode timeout durations specifically to avoid that dependence. State the convention.

The fixture repairs the trace as follows:

The arithmetic is modeled, not a production SLO. It illustrates the invariant:

[ T_{elapsed} + T_{critical\ path} + T_{return} + U \le D_{caller} ]

where every term is in time units and (U) covers declared uncertainty. A parallel branch consumes wall-clock budget according to the slowest required branch, not the sum of all branches, but it still consumes resource demand on every branch. A quorum can finish before every replica, yet the unfinished calls continue unless cancellation or bounded background ownership stops them.

The child does not automatically receive every remaining millisecond. Reserve enough time to marshal a response, persist an operation record, or return useful failure advice. Subtract known upstream queueing. Reject or degrade before beginning a stage whose upper-bound completion no longer fits, as Chapter 24’s admission rule requires.

Timeout selection is a loss decision

“Set the timeout to the downstream p99” is incomplete. Ask which latency distribution, which outcome population, which load state, and which loss the threshold trades.

A timeout that is too short creates false failures, duplicates, and retry load. One that is too long traps capacity in work that can no longer deliver value. The selection needs:

• the caller’s remaining deadline and return reserve;
• connection establishment, name resolution, handshake, request, response, and streaming-idle phases;
• warm, cold, deployment, overload, failed, and recovering distributions;
• false-timeout tolerance by operation class;
• the downstream’s rejection and effect semantics;
• cancellation and cleanup latency; and
• enough margin for network and scheduler variance without hiding a saturated queue.

Measure at the boundary being controlled. A socket read timeout may exclude DNS, connect, TLS, pool acquisition, request serialization, or time waiting for an execution slot. A library’s “request timeout” may restart between redirects or attempts. An idle stream timeout can fire even though the end-to-end deadline is far away, while a stream producing tiny heartbeats may evade the idle rule forever. Test the actual lifecycle.

Cold paths deserve explicit budgets, not permanently inflated steady-state timeouts. Pre-establish connections where justified, separate readiness from user traffic, and classify handshake failures. If deployment causes a known 80 ms cold connection path but the warm p99 is 20 ms, a 25 ms universal timeout will manufacture a retry wave on every rollout. A 200 ms universal timeout may instead hide queue collapse. Model both states and control the transition.

Cancellation transfers ownership; it does not undo effects

When a deadline expires, the caller relinquishes interest. It does not follow that the callee stopped, a queued task disappeared, memory was freed, a database statement aborted, or a write rolled back. Cancellation is a protocol with observation delay and boundaries at which work can safely stop.

For every asynchronous or remote stage, record:

1. who owns the work before and after dispatch;
2. how cancellation reaches that owner;
3. which waits and child calls are interrupted;
4. which cleanup must complete even after caller abandonment;
5. which effects may already be durable; and
6. which terminal operation record a later query can read.

A cancelled read can often stop scanning and release buffers. A cancelled write may need to finish a commit, roll back a transaction, or leave a recovery record. Killing a task between “effect committed” and “result recorded” creates the most important ambiguous interval. Design that interval rather than relying on task cancellation to erase it.

Orphan work needs its own telemetry: started after the caller deadline, completed after abandonment, resource demand after cancellation, cancellation delivery delay, and cleanup failures. High CPU with ordinary accepted traffic can be orphan work from the previous window. Admission accounting should charge it, because the resource cannot distinguish useful from abandoned instructions.

Cancellation also interacts with fan-out. Cancel optional branches once a sufficient result exists. For a required quorum, cancel only branches whose result is no longer needed and whose protocol permits safe interruption. Cap cleanup concurrency; a broad deadline expiry can otherwise create a second storm of rollback, connection teardown, log emission, and cache invalidation.

Attempts are a tax on logical work

Suppose a caller permits three attempts and an intermediate service independently permits three attempts to its dependency. One logical operation can cause nine downstream attempts. Add another three-attempt layer and the theoretical path reaches 27. Parallel fan-out multiplies it again.

The upper bound across sequential retrying layers is:

[ A_{downstream} \le \prod_{i=1}^{n} A_i ]

This bound is not a prediction; deadlines and early successes may reduce it. It is a design alarm. Retrying at one deliberate layer is usually easier to budget and observe than retries hidden in SDKs, proxies, service code, database drivers, and queues.

Define a retry budget in attempts or normalized demand, not only “two retries per request.” In the fixture, 10,000 logical operations permit at most 800 additional attempts in the evaluation window: an 8% tax. If 220 first attempts receive a plausibly transient failure and each gets one retry, the observed tax is 2.2%, inside the budget. If failures rise, the retry controller spends the remaining tokens and then stops. Protect a small, explicit class if critical recovery operations require different treatment; do not let it borrow without bound.

Count retries against admission, tenant quota where appropriate, concurrency, and downstream capacity. A retry is not free because the first attempt failed. Charge expected demand when different errors fail at different stages. Retrying a request rejected before parsing may be cheap; retrying a timed-out query after 95% of its scan is expensive and may overlap the original.

Backoff spreads attempts; it does not create capacity

Exponential backoff increases delay between attempts, commonly from a base (b) toward a cap:

[ d_k = \min(d_{max}, b \cdot 2^k) ]

Without jitter, clients that failed together retry together. Full jitter samples a delay between zero and the current cap; equal-jitter and decorrelated variants trade mean delay, clustering, and implementation behavior differently. Name the algorithm rather than writing “add jitter.” Include server-provided not-before advice only when the client trusts its scope and can still fit the logical deadline.

A retry storm is this correlation at system scale: many individually bounded clients align their additional attempts with a shared failure or recovery boundary, so the aggregate exceeds the destination’s recovering capacity.

Backoff must stop on the earliest of:

• absolute logical deadline;
• maximum safe attempts;
• exhausted retry budget;
• permanent or unsafe outcome;
• caller cancellation;
• circuit/admission decision that says the downstream is not a candidate; or
• a terminal operation status obtained through reconciliation.

Test correlation. Restart ten thousand clients, inject a regional dependency failure, and graph attempts per logical operation over time. A pretty per-client delay distribution can still align at a common cap, deployment boundary, token refresh, or Retry-After timestamp.

Retry control must compose with admission and recovery

A retry budget answers how much duplicate work may be attempted; it does not decide whether the destination is currently eligible. Admission may reject the retry because its remaining deadline, predicted cost, tenant allocation, or downstream headroom no longer fits. A circuit-style availability state may temporarily remove a destination from consideration, but an open circuit is not evidence that another region or replica is safe. Placement, admission, and retry policy need one consistent view of failure scope.

Preserve a small number of bounded probes when the recovery contract requires them. If every client independently probes, the probes become the outage load. Let a controlled owner sample recovery, publish scoped eligibility, and ramp traffic with hysteresis. Separate health/control traffic from user retries and reserve enough capacity that overload cannot prevent recovery observation.

Retries during recovery are especially dangerous. Cold caches, replay, replica catch-up, connection establishment, and deferred cleanup already consume capacity. A destination that returns one success is not ready for the backlog. Ramp logical operations first; allow the retry tax to grow only after useful completion and queue evidence remain stable. Carry retry-budget balance and attempt origin into the recovery dashboard.

Do not use a breaker to conceal ambiguous effects. If a write attempt lost its response, opening the destination may stop new calls but does not resolve the operation. The client still needs the idempotency record or reconciliation path. Likewise, a half-open probe must be an intentionally safe operation; repeating a real customer effect merely to learn whether the dependency recovered is not a health check.

Classify the outcome before choosing retry

Transport errors do not reveal whether an effect occurred. Application errors do not all mean the same future attempt is useful. Classify along two axes: could the effect have happened? and is another attempt plausibly useful now?

HTTP methods have standardized semantics, but method names alone do not prove application safety. RFC 9110 defines idempotent methods as having the same intended effect for multiple identical requests, while acknowledging that logging and other non-requested side effects may still differ. A PUT can be application-idempotent and still be unsafe to repeat under an expired authorization version. A POST can be safely retried when the application supplies a durable idempotency protocol. Make the effect boundary concrete.

Pointless retries deserve equal attention. Retrying overload immediately, repeating an invalid payload, asking the same empty replica before convergence can occur, or retrying after the logical deadline consumes work without increasing completion probability. “Transient” must be supported by a time horizon and a different opportunity: recovered capacity, another eligible replica, refreshed route, or corrected state.

Idempotency is durable operation identity, not a cache trick

For the payment-like capture, the client sends an idempotency key with a canonical request. The server scopes the key to merchant-42:capture, stores a request hash, and establishes one authoritative operation record before causing the external effect.

ABSENT ──create atomically──> PENDING ──effect commits──> COMMITTED
                               │                         │
                               ├──definitive failure──> FAILED
                               └──lease/recovery───────> RECONCILING

The state names are illustrative. The invariants matter:

• the same scope and key identify one logical operation;
• a different payload hash under that identity is a conflict, never a replay;
• concurrent duplicates observe or join the one operation rather than start effects independently;
• the record distinguishes pending, terminal success, terminal failure, and reconciliation;
• a committed response can be replayed with stable effect identity;
• the retention window covers documented client retry and delayed-delivery behavior; and
• expiry does not silently authorize a duplicate effect if an older authoritative record may still exist elsewhere.

The fixture’s key op-834 uses a canonical hash of amount, currency, and source. A duplicate while PENDING receives an in-progress outcome, not a second capture. A duplicate after COMMITTED receives the stored 201 response. Reusing the key with a different amount receives conflict. The modeled deduplication window is 48 hours; it is a policy example, not a recommendation. Real retention follows maximum retry, offline queue, reconciliation, legal, privacy, and storage requirements.

Persisting the record before the effect creates a recoverable pending state. Persisting only after the effect leaves a crash interval in which the server cannot distinguish “not started” from “committed but not recorded.” Some external systems accept the same idempotency key, allowing end-to-end identity. Otherwise, recovery may query by a stable business reference, consume an authoritative event, or enter manual reconciliation. No arrangement should be called exactly once without naming the observation boundary and failure assumptions.

Applied design: the ambiguous capture

Use this response contract:

Compensation is not erasure. A refund after duplicate capture creates two ledger events, may incur fees, and may be visible to the user. It is a business recovery operation with its own identity, authorization, deadline, and failure modes. Prefer prevention and reconciliation; use compensation when the domain permits it and retain the causal link.

Hedging spends controlled duplicates to buy a tail opportunity

A hedge starts a duplicate attempt before the original definitively fails, often after a latency threshold. It can reduce tail latency when delays are partly independent and spare capacity exists. It can also double expensive work, concentrate on already slow requests, destroy cache locality, violate side-effect safety, and worsen the very queue causing the tail.

The fixture supplies a qualitative modeled frontier:

These values do not come from a queue simulator or production trace. They demonstrate why “hedge at p95” is not a policy. Measure conditional completion probability after age (t), correlation between candidates, cancellation delay of losers, capacity headroom, extra bytes/CPU/I/O, and effect safety. Evaluate overloaded and recovering states; a hedge enabled only during healthy headroom may need to disable before admission starts shedding.

Hedge read-only or duplicate-safe work first. Use the same logical operation identity for any write-like speculation. Prefer a different failure domain only when the consistency and locality contract permits it. Starting the duplicate on the same saturated worker is unlikely to help. Ensure the first acceptable result wins while later failures cannot overwrite it, and cancel losers without corrupting shared state.

Quorum requests and speculative execution are related but not interchangeable. A quorum deliberately requires enough responses to satisfy a consistency or durability rule; it may issue to more replicas than the minimum so the fastest sufficient set can finish. Speculative execution re-runs a task believed to be a straggler. A hedge duplicates an individual request for latency. All create duplicate demand, but their correctness condition, selection rule, and stopping point differ. Chapter 27 develops replication and quorum assumptions; here the completion contract must reserve time, cap branches, and stop surplus work.

Partial completion needs a user-visible truth

A multi-step operation can reserve inventory, commit a ledger entry, publish an event, and fail to send a receipt. “The request failed” loses essential state. Define which step is the user-visible commit point, which outputs are derived, which can be retried independently, and who reconciles each gap.

Return an operation identifier before asynchronous completion only when the client contract supports polling or notification. A 202-style accepted response is not success; it transfers completion ownership to a durable worker and status resource. Bound how long PENDING may remain, how a stuck lease is recovered, and which terminal states exist.

If a response is lost after commit, the client should query or replay the same operation identity. If the service cannot determine the outcome, say UNKNOWN rather than converting uncertainty to failure or success. Give the user a stable next action and prevent the UI from inviting a new logical operation that duplicates the effect.

Client-server retry advice should include stable category, scope, execution/effect possibility, retry eligibility, bounded delay or not-before time, operation identity, and status lookup where relevant. Do not expose sensitive capacity details. Do not promise retry safety when an intermediary may have stripped the idempotency key or changed the payload.

Telemetry must join logical operations to attempts

An attempt-level success rate can improve while logical completion worsens. If each logical operation makes three attempts and one succeeds, the attempt success rate is 33% but logical completion may be 100% at triple cost. Conversely, cancelling two surplus quorum branches is not two user failures.

Record at least:

• logical operations started, completed, failed, unknown, and expired;
• attempts per logical operation and layer that created each attempt;
• remaining deadline at every dispatch and terminal outcome;
• timeout phase, configured bound, elapsed time, and observed effect possibility;
• retry reason, delay algorithm, budget balance, and server advice;
• duplicate attempts, hedges, quorum branches, and loser cancellation delay;
• orphan work and resource demand after caller abandonment;
• idempotency lookup, new/pending/replay/conflict/expired outcomes;
• time in pending or reconciling states; and
• useful completion latency measured from the first logical start, not the winning attempt.

Use a logical operation ID across traces, metrics exemplars, logs, and durable state without turning it into an unbounded-cardinality metric label. Sample detailed traces by outcome and tail class. Preserve counters for the full population. Separate original attempts from retries and hedges so admission dashboards can identify amplification.

Test with lost responses, delayed cancellation, slow success, explicit overload, connection failure before and after send, partial writes, duplicate delivery, process crash before and after commit, stale route, regional loss, and recovery. A fault injector that only returns an immediate error misses the ambiguous intervals that justify the protocol.

Completion policy record

Use this copyable artifact in an API or architecture review:

LOGICAL OPERATION
Name, user-visible outcome, and effect boundary:
Operation identity, key scope, canonical request hash:
Absolute deadline convention and maximum supported lifetime:

TIME BUDGET
Ingress / queue / critical-path / return / uncertainty allocations:
Phase timeouts and what each includes:
Cold, overload, failed, and recovery distributions:
Cancellation owner, propagation path, cleanup bound, orphan-work policy:

ATTEMPT POLICY
Single retry-owning layer:
Retryable categories and evidence that a new attempt can help:
Unsafe and pointless categories:
Maximum attempts, normalized retry budget, backoff, jitter, and stop rules:
Hedge/quorum/speculation threshold, candidates, duplicate-cost ceiling:

EFFECT AND REPLAY
Authoritative states and transition owner:
Concurrent duplicate behavior:
Committed response replay; mismatched-payload behavior:
Deduplication/tombstone retention and expiry proof:
Unknown outcome, reconciliation, compensation, and operator path:

CLIENT-SERVER CONTRACT
Rejection category/scope, effect possibility, retry advice:
Operation status lookup and user-visible ambiguity:
Intermediary propagation requirements:

EVIDENCE
Logical outcomes, attempts, late/orphan work, wasted demand:
Normal, tail, overload, partition, crash, duplicate, and recovery tests:
Rollout guardrail, abort threshold, and policy owner:

Field questions

• Is there one logical deadline, or can child patience outlive caller value?
• Which timeout phase includes pool wait, handshake, serialization, and response read?
• What continues after cancellation, and who owns cleanup?
• Which single layer creates retries, and what is the fleet-wide tax ceiling?
• Can the failure be permanent, unsafe, or pointless to retry?
• Does a duplicate carry the same scoped operation identity and request hash?
• What state is returned while the first attempt is pending?
• Can record expiry be mistaken for proof that no effect occurred?
• Are hedge delays sufficiently independent, and is loser cancellation fast?
• Do metrics count useful logical outcomes rather than winning attempts?

Decision drill: repair the stack and the effect

Start with the modeled 240 ms capture. Eighteen milliseconds have elapsed at the service boundary. Reserve 22 ms for the response. Allocate no more than 200 ms to the downstream critical path. The modeled fraud, ledger, receipt, and handoff allowances total 190 ms, leaving 10 ms. Replace the three independent 200/300/100 ms settings with child bounds capped by the absolute remaining deadline. A branch that cannot fit is rejected or moved outside the synchronous success contract. Propagate cancellation, but retain durable completion ownership after a possible commit.

Then assume the client times out after the ledger committed but before it received a response. A strong design does not issue a fresh capture. It reuses merchant-42:capture:op-834 with the identical canonical request or queries the operation URI. The server finds COMMITTED and replays the stored outcome. A changed amount conflicts. A still-pending record returns in-progress status. A recovery worker resolves an expired lease through the ledger’s stable reference before any effect can be attempted again.

Finally, inject 220 transient first failures among 10,000 logical operations. One deliberate retry layer creates 220 extra attempts, a 2.2% tax within the modeled 8% budget. If the failure expands, retries stop as the budget empties; backoff alone is not allowed to convert an outage into deferred overload.

Durable decision rules

1. Propagate one end-to-end deadline and cap every child wait by remaining time after return and uncertainty reserves.
2. Treat cancellation as ownership transfer and cleanup signaling, never as proof that an effect rolled back.
3. Put retries at one deliberate layer, charge their full resource demand, jitter them, and stop on budget, deadline, or unsafe outcome.
4. Retry only when the operation is duplicate-safe, remaining time is sufficient, the failure is plausibly transient, and another candidate can change the outcome.
5. Make idempotency a durable scoped identity with canonical-request conflict detection, explicit pending/terminal states, replay, retention, and reconciliation.
6. Hedge only where candidate delays are sufficiently independent, duplicate effects are safe, loser work is cancellable, and measured tail benefit exceeds extra demand.
7. Measure logical completion, ambiguous outcomes, attempts, late/orphan work, and duplicate cost on the same timeline.

Evidence and transfer limits

• RFC 9110 defines HTTP method semantics, idempotent methods, 503, and Retry-After. It does not make an application’s effect duplicate-safe or choose a retry policy.
• gRPC deadlines guide documents deadline propagation and cancellation behavior in gRPC. Its APIs and clock handling are implementation-specific, and cancellation does not undo committed effects.
• Google SRE: Addressing Cascading Failures discusses deadlines, retry amplification, overload, and load testing in Google’s production context. Its values are not defaults for other systems.
• AWS Builders’ Library: Timeouts, retries, and backoff with jitter presents an engineering approach to false timeouts, token-limited retries, backoff, and jitter. The examples reflect AWS systems and require workload-specific validation.
• The Tail at Scale is a primary research account of tail-tolerance techniques including hedged requests. Its workload assumptions and results do not justify hedging arbitrary writes or saturated systems.
• Google AIP-155 specifies one request-ID convention for duplicate detection in long-running API operations. It is an API design pattern, not a proof of exactly-once effects.
• All deadline, retry, hedge, and replay values are deterministic modeled evidence in examples/performance-engineering-system-design-handbook/part-03/request-completion/. The fixture has no clocks, network, queue, persistent store, failure injector, payment processor, or production measurements.

Once logical completion is bounded, the system still needs to decide which owner holds each unit of state and work. The next chapter moves from duplicate attempts to divided ownership: choosing partition keys, detecting demand skew, and transferring authority without turning rebalancing into an unbounded second workload.