0026 - Shared per-request retry budget with full-jitter backoff and per-try timeout re-arming

• Status: Accepted
• Date: 2026-08-06
• Deciders: nexus core team
• Tags: gateway, retries, fallback, streaming, timeouts

Context and Problem Statement

0017 - Retry policy for gateway upstream attempts described the gateway’s retry budget as scoped to “a single provider attempt” and claimed exponential backoff used jitter. Neither matched the implementation: the retry budget was actually re-granted per fallback candidate (so a request with several candidates could multiply its total upstream call count by the candidate count), and backoff between retries was bare deterministic exponential with no jitter at all — meaning concurrent clients retrying the same failing upstream would retry in lockstep, turning a transient blip into a synchronized retry storm.

Separately, the per-operation-class total-time timeouts (fast/standard/images) that bound one non-streaming attempt gave no guidance on how they should behave across a retry: re-armed in full on every retry (generous, but lets a candidate that reliably stalls just under budget consume much more wall-clock time than one timeout value suggests), or shared cumulatively across the whole candidate (strict, but turns a retry into a shrinking second chance rather than a fresh one).

This decision corrects both mismatches between documented and actual behavior, and settles the re-arming question explicitly.

Decision Drivers

• The retry budget’s total upstream call count per request must stay bounded by the client-supplied nexus-retries value regardless of how many fallback candidates the route has — a candidate count should never act as a hidden retry-budget multiplier.
• Concurrent retries against the same failing upstream must not visibly cluster into synchronized timing bands.
• A retry exists to give a transient stall another full, independent chance to succeed — its own timeout budget must not already be eaten by a previous try’s timeout.
• The ADR must describe what the code actually does, not aspirational behavior that was never implemented.

Considered Options

• Shared per-request retry budget, re-granted per try (this decision) — one extra-tries pool spent across every candidate in the request; each candidate still always gets its mandatory initial try regardless of budget.
• Keep the retry budget per-candidate — simpler bookkeeping, but a route with N fallback candidates and a nexus-retries budget of R could cost up to N * (1 + R) upstream calls instead of N + R, an unbounded multiplier as routes grow more candidates.
• Cumulative per-try timeout across retries of one candidate — a strict total-time ceiling per candidate, but a candidate that times out once and then would have answered normally on a fresh try never gets the chance, since its retry inherits whatever budget the first try didn’t use.

Decision Outcome

Chosen option: Shared per-request retry budget, re-granted per try, with full-jitter backoff and per-try timeout re-arming.

• nexus-retries (capped at 16) is parsed into a single RetryBudget (services/gateway/src/retry.rs in the source repository) shared across every fallback candidate in the request via RetryBudget::try_consume, not re-granted to each candidate in turn. Each candidate still always gets its mandatory initial try regardless of remaining budget; only retries of a failed attempt draw from the shared pool. Worst case for one non-streaming request is bounded by call count: num_candidates + shared_retry_budget, never num_candidates * (1 + shared_retry_budget).
• Backoff between consumed retries uses full jitter — a random duration in [0, min(50ms * 2^attempt, 2000ms)], not the deterministic ceiling itself — so concurrent clients retrying the same failing upstream desynchronize instead of retrying in lockstep.
• A per-try total-time timeout (where one applies — non-streaming operation classes only; streaming relies on the shared client’s idle-read timeout instead, since a legitimate stream can run far longer than any fixed total-time budget) is re-armed in full on every retry, not shared cumulatively across them: a candidate that times out once and answers normally on retry is not penalized by the first try’s elapsed time.
• Retries apply only to retryable failures: transport failures (including a gateway-side timeout elapsing — now GatewayError::Timeout, a dedicated variant rather than free-form text folded into GatewayError::Upstream) and a fixed set of retryable upstream statuses (429, 500, 502, 503, 504, 529 — the last being Anthropic’s “temporarily overloaded” status, which the Anthropic edge renders as overloaded_error). Deterministic, non-transient rejections are classified non-retryable, since replaying the identical request only spends budget before failing identically again: an oversized response (GatewayError::ResponseTooLarge), and any rejection an adapter maps to GatewayError::UpstreamNotRetryable. Today the only adapter that makes that distinction is Bedrock, which maps a refused or expired credential, a ValidationException, and ServiceQuotaExceededException to it. A provider that reports an exhausted quota as a bare 429 — OpenAI’s insufficient_quota shape — is indistinguishable from a rate limit at the status level and is retried like one; classifying them would mean parsing a provider-specific error body to decide retryability, which the gateway deliberately does not do.
• Once a streaming response has begun delivering bytes to the client, the gateway does not cross to another fallback attempt (unchanged from 0017 - Retry policy for gateway upstream attempts).

This supersedes 0017 - Retry policy for gateway upstream attempts, whose Decision Outcome described the pre-existing (and, per the mismatches above, partially aspirational) per-candidate/no-jitter behavior. Its context is retained as the historical record of the original decision, not as a statement of current behavior.

The upstream connect timeout consolidates here

0024 - Operator-owned upstream environment identifiers introduced NEXUS_GATEWAY_UPSTREAM_CONNECT_TIMEOUT_SECS alongside the CA-bundle and insecure-TLS controls. That variable is removed and the connect bound moves to NEXUS_GATEWAY_TIMEOUT_CONNECT_SECS, so one config surface owns every timeout the gateway enforces and the read-dominance invariant can be checked across all of them. upstream_tls::build_client_from still owns trust configuration and now takes both budgets from TimeoutConfig.

Two behavioural differences follow, and only one of them reverses that ADR:

• Unset now means ten seconds, not unbounded. The prior decision left the bound to the operating system when the variable was absent, which is the hang it names as the reason the variable exists.
• A malformed value warns and takes the default, as the prior decision requires. Its line — a malformed tuning value is not a reason to refuse to serve, while a trust store that cannot be read is — is kept, via parse_env_warning. A zero is the exception and remains fatal: it parses cleanly so no warning would fire, and it is a functional break rather than a tuning preference (tokio::time::timeout fires immediately; a zero connect timeout fails every dial).

0024 - Operator-owned upstream environment identifiers’s trust decisions are untouched and its status is unchanged: this supersedes one paragraph of it, not the decision.

Residual gaps (disclosed, not closed by this decision)

• None of these budgets bound the whole request: each is re-armed per candidate and per retry, so a request with several fallback candidates and a large nexus-retries value can still take a long time in aggregate. nexus-retries is capped at 16 and the client-supplied route is capped at pipeline::MAX_ROUTE_CANDIDATES segments, but the candidate count is not itself a constant — one unpinned segment fans out to an attempt per registry endpoint, and each endpoint can add a PTB attempt alongside its BYOK one — so a deployment wanting a tighter hard total-duration ceiling must size it against its own catalog width and lower the retry budget it accepts rather than rely on these timeouts alone. This is a deliberate non-goal, not an oversight; see Threat Model row D2 for the worked-out worst-case formulas for both non-streaming and streaming requests.
• A slow-but-technically-alive trickle (bytes arriving just often enough to keep resetting the idle-read timer) is not time-bounded by any mechanism here.

Consequences

• Operational tuning stays header-driven per tenant or SDK without redeploying, unchanged from the prior policy.
• nexus_gateway_attempt_retries_total metrics are unaffected in shape; the shared budget changes when retries are available, not how they’re counted.
• A route with many fallback candidates no longer has a hidden retry-budget multiplier — capacity planning based on nexus-retries alone is now accurate regardless of route width.
• retry::retryable() and GatewayError::Timeout are the single source of truth for “was this failure worth retrying”; Threat Model D2 is written to match.

More Information

• Implementation: services/gateway/src/retry.rs (RetryBudget, run_attempt_with_retries, backoff_after_failure), services/gateway/src/timeouts.rs (per-operation-class budgets and the idle-read timeout streaming relies on) in the source repository.
• Threat model: Threat Model row D2 (hung/slow upstream) and D3 (oversized/unbounded response).