Retry and hedge budgets

Why is a budget the only stable retry policy, and when must hedging switch off?

A per-request retry count has a multiplier that depends on the failure rate, so it is largest at the worst moment (retry amplification). A budget expressed as a fraction of the success rate has a multiplier that is bounded by construction, and it is tied to evidence that the callee is alive. The difference is not one of degree: one is bounded, the other is not.

Retry budgets

A token bucket implements this. The bucket gains a small number of tokens for each success (for example 0.1) and each retry spends one token. If the bucket is empty, no retry is sent. With a 10% ratio, retries add at most about 10% extra load, instead of the 4 × 4 × 4 × 4 = 256-fold growth of four tiers that each retry three times.

The budget is a control system whose feedback signal is the success rate. Its key property is that it throttles itself precisely in the correlated case. A per-request cap is a policy that only makes sense if failures are independent, and a fraction-of-success budget stays sane when they are not. The budget also belongs at the client and not on the server, because by the time the server is rejecting requests it is already spending resources on the rejection.

A tiny sketch of the idea:

# Retry budget: allow a retry only if recent retries are below 10% of recent successes.
class RetryBudget:
    def __init__(self, ratio=0.1):
        self.ratio = ratio
        self.successes = 0.0   # decayed count of recent successes
        self.retries = 0.0     # decayed count of recent retries

    def record_success(self):
        self.successes += 1

    def can_retry(self):
        if self.retries < self.ratio * self.successes:
            self.retries += 1
            return True
        return False           # budget empty: fail fast, do not retry

(A real version also lets the counts decay over a time window. This sketch shows only the rule.)

The cost: a shared counter (coordination) and some legitimate retries denied during a genuine transient failure. Two supporting rules have real force:

• Retry at one layer only. Retries multiply through a chain and no layer can see the product. In practice, retry at the outermost layer that can do it meaningfully, and explicitly do not retry everywhere else.
• A retry is a client-side admission decision. If the callee says it is overloaded, the right behaviour is not to retry at all. That requires telling "overloaded" apart from "failed" in the error taxonomy, and most taxonomies do not. This is why HTTP 503 with a Retry-After header exists, and why it is widely ignored.

Hedge budgets

A hedged request sends a second copy of a request after waiting for the p95 latency of the first, and takes whichever answers first. Hedging at p95 adds about 5% load and removes most of the tail. Under overload it has two boundary conditions:

• It works only against random stragglers, because it needs the two attempts to be independent. A deterministic straggler (a throttled network card, a dying disk, a hot shard) is hit by both copies, or cannot be avoided in a full fan-out query.
• It must be disabled under overload. When capacity is short, hedging adds load exactly then. This is the regime-flip principle: a defence that turns into a pathology.

So hedging belongs to the tail, not to overload. The correct design is a hedge budget (a fixed fraction of total requests, the same shape as the retry budget) plus suppression when a shed or breaker signal is active.