[Serve] [RFC] Computed Retry-After for backpressure rejections

[vinay7373]

Motivation

PR #65193 added BackpressureConfig. Deployments can now reject backpressured requests with a 429 and a static Retry-After header. Each caller (proxy or DeploymentHandle) has its own request queue, and at the time of a backpressure rejection a static Retry-After value can be incorrect in both directions: too short or too long. If the queue is deep and the static value is too short, then clients retry into another rejection, adding load exactly when the system is trying to shed it. If the queue drains fast and the value is too long, then capacity sits idle while clients wait.

This proposal computes the Retry-After value from observed load. This makes the Retry-After header a reliable estimate of when capacity will be available, instead of a number the operator guessed. This was the original shape of the production request behind #65193 and it fits the discussion there about making 429 the default at some point.

No OSS inference server does this today. TGI, Triton, NVIDIA Dynamo and TorchServe all reject without a retry hint. The closest prior art is on the cloud side: Azure OpenAI's retry-after-ms and AWS's x-amz-retry-after. The AWS SDK contract notes that the service jitters the value so it can "communicate exactly when it expects to have capacity available".

Goals

• An opt-in BackpressureConfig policy that computes Retry-After from load signals the router already has.
• Keep the rejection path as cheap as it is today. No RPCs, locks or extra work on reject-and-respond. Fast rejection is the whole point of load shedding.
• Degrade gracefully. If signals are not available (for example right after a router starts), fall back to the static value, then to no header. Never fail or delay a rejection.

Non-goals

• Changing when requests are rejected. Admission control is a separate discussion.
• Guaranteeing admission at the suggested time. The header is a hint, not a reservation.
• Changing the default rejection status code. Tracked separately.
• Implementing any further policy, such as the cluster-informed one (see "Future policies" below). The design leaves room for them, but only router_queue_drain_rate is built here.

Proposed API

from ray.serve.config import BackpressureConfig

@serve.deployment(
    max_queued_requests=64,
    backpressure_config=BackpressureConfig(
        status_code=429,
        retry_after_policy="router_queue_drain_rate",   # NEW: "static" (default) | "router_queue_drain_rate"
        retry_after_s=5,                    # static value; also the fallback for computed policies
    ),
)

retry_after_policy is a named policy instead of a bare "auto" so future strategies can be added without changing what existing configs mean.

Proposed design

This design adds a new field to BackpressureConfig called retry_after_policy, and one new policy named router_queue_drain_rate that computes Retry-After from the rejecting router's observed queue depth and drain rate. The router is a strong vantage point for this: its power of two choices routing continuously samples replica queue lengths across the whole fleet, so the drain rate it measures reflects where work actually flows, with faster replicas naturally absorbing more of it.

This proposal ships exactly one computed policy. The retry_after_policy field is also the extension point: future strategies arrive as new named policies alongside it, and existing configs keep their meaning. One such future policy is cluster_informed, outlined briefly in "Future policies" below but not built here.

The overall mechanism has 3 basic aspects: (i) how to compute the Retry-After value (this is what the router_queue_drain_rate policy implements), (ii) where to compute it, and (iii) who stamps the header and emits it to the client.

These 3 aspects boil down to emission and estimation. Emission answers (iii) and is fixed: the router stamps the header, because the router is the code that rejects the request. Estimation covers (i) and (ii): it is a function of load inputs feeding a fallback ladder, and this proposal computes it at the router, from inputs the router already has. A cluster-level input can be layered on later (see "Designed-for extension") without reworking anything below it.

The router_queue_drain_rate policy (this proposal)

This section answers (i): it specifies what the router_queue_drain_rate policy computes. The policy runs in the router at the moment it rejects a request, and produces the estimate with this formula:

retry_after ≈ ceil(own_queue_depth / drain_rate × saturation_factor)

Reading it left to right:

• own_queue_depth is what we start with: the number of requests already queued at this router, ahead of the one being rejected.
• drain_rate is how fast that queue empties. It is an exponentially weighted moving average (EWMA) of the router's own assignment throughput, meaning a smoothed, recency-biased rate of requests handed to replicas per second, tracked at existing counter sites. Dividing depth by rate gives the base estimate: roughly how many seconds until this router's queue clears. The rate is also fleet-blended by construction, so mixed hardware is priced in automatically: faster replicas free slots sooner, get picked more often by power of two choices, and contribute more to the measured rate. Locality-preferring routing can skew the blend toward same-node replicas, but under saturation (when backpressure fires) routing spills fleet-wide and the measurement re-blends.
• saturation_factor is a multiplier (>= 1) that stretches the base estimate when the whole fleet is jammed, so the suggestion errs longer under heavy contention. It is derived from two signals the router already has: occupancy, which is the sum of cached per-replica queue lengths divided by total fleet capacity (num_replicas × max_ongoing_requests), and the router's current placement backoff streak. Note the occupancy signal saturates exactly when backpressure fires (every cache entry reads "full"), so it only nudges the multiplier. The drain-rate EWMA carries the estimate.

Concretely, the two derived terms are:

drain_rate        = alpha * (assignments_in_last_interval / interval_s)
                    + (1 - alpha) * previous_drain_rate

capacity          = num_replicas * max_ongoing_requests
occupancy         = min(1, sum(cached_replica_queue_lens) / capacity)
backoff_signal    = min(current_backoff_streak / B, 1)
saturation_factor = 1 + w1 * occupancy + w2 * backoff_signal

alpha, the interval, B, w1 and w2 are implementation constants (for example alpha = 0.3 over 1s intervals, B = 5, w1 = w2 = 0.25, which bounds the factor to [1, 1.5]). The formula shapes are the proposal; the constants are tunables, and the acceptance criterion in the open question below is the instrument for tuning them. Setting w1 = 0 drops the occupancy term if the first cut should stay minimal. The EWMA counts as warm after a minimum number of intervals with traffic; until then the fallback ladder applies.

Where these signals come from: the router already makes an informed decision for every request it places. The default power of two choices router probes candidate replicas for (queue_len, accepted), retries with exponential backoff (25ms up to a 500ms cap) when both reject, and keeps a ReplicaQueueLengthCache (per-replica queue lengths with a 10s staleness TTL) across the full replica set. Replica queue lengths count admissions from all callers, so each router already has a fleet-wide view of the capacity side. Everything the formula needs is already at the rejection site. No new plumbing.

• Clamp to [1, 60] seconds. The common client SDKs ignore Retry-After above 60s and fall back to their own exponential backoff, so values outside this range communicate nothing.
• Server-side jitter (for example ±20%). If computed values agree across routers, clients retry in sync and create a thundering herd one Retry-After later. AWS documents jitter as the service's job, so client SDKs don't re-jitter. Estimates already diverge a bit across routers, which helps.
• Fallback ladder: computed value (if the EWMA is warm), else the static retry_after_s (if set), else no header. A policy failure downgrades silently. It never fails a request.
• Format: RFC 9110 delta-seconds (integer, rounded up), same as the static path today.
• Observability: record the suggested delay as a metric and/or access log field, so operators (and this feature's own evaluation) can compare suggested delays against observed queue-drain times.

Future policies (not in scope)

The policy field makes new strategies additive. One example is a cluster_informed policy: the controller already aggregates cluster-wide load for autoscaling and broadcasts per-deployment state to routers over long-poll, so it could supply the two signals no router sees locally (queued demand at other callers, and time-to-new-capacity when a scale-up is in flight). It would slot in as one more input at the top of the same fallback ladder, with routers reading only a locally cached broadcast so rejections never wait on the controller. It is not proposed here: the value would be stale by the metrics cadence, it needs its own anti-herding jitter, and the observability in this proposal is the evidence to decide whether it earns that complexity.

Alternatives considered

• Client-side adaptive backoff only (status quo for most users): SDK backoff can't see queue state. The server is the only party that knows.
• Expose raw signals in headers (queue depth, capacity, in the spirit of the IETF RateLimit headers draft): pushes the estimation problem onto every client. Could complement a computed Retry-After later, not replace it.
• Static only (shipped in [Serve] Configurable status code and Retry-After header for backpressure rejections #65193): works, but the operator has to guess a number that is wrong under exactly the conditions where it matters.

Open question

What makes the computed value "good"? We propose: a retry issued at the suggested delay should be admitted at least X% of the time, measured with the observability above. We are looking for input on the target X. It could also become a per-deployment knob later, since latency-critical apps prefer optimistic values (fail over fast) and transactional apps prefer conservative ones (retry once, succeed).

cc @edoakes @zcin @abrarsheikh @YashwanthRanjanSingaravel @brent-anyscale @RehanSD

[abrarsheikh]

@suppagoddo can you review this please

[suppagoddo]

@abrarsheikh - Sure, Will review