Exponential backoff with jitter

Deep dive

How it works

In: attempt number, base, cap, optional server hint (Retry-After), retry budget · Out: the delay to sleep, or give up · State: none for full jitter; previous delay for decorrelated jitter; a token count for a retry budget · Cost: O(1) per retry (one RNG draw).

1. Classify the error: retryable (timeouts, 429, 503, connection reset, UNAVAILABLE) vs not.
2. Check budgets: attempts left, deadline left, client-wide retry budget.
3. Compute delay:
   • Full jitter: rand(0, min(cap, base·2^n)).
   • Equal jitter: v/2 + rand(0, v/2) with v = min(cap, base·2^n); keeps a minimum wait.
   • Decorrelated jitter: sleep = min(cap, rand(base, prev·3)); grows from the previous sleep, not the attempt count.
4. Honor server hints (Retry-After, gRPC pushback) when present: use max(hint, computed).
5. Sleep, retry, repeat; give up with the last error.

no jitter:   ||||      ||||            ||||                    (synchronized waves)
full jitter: | |  | || |  |   |  |  |    |   |    |      |     (spread load)

Code

use std::time::{Duration, Instant};

/// xorshift64*: tiny, good enough for jitter (not for crypto).
pub struct Rng(u64);
impl Rng {
    pub fn new(seed: u64) -> Self { Rng(seed | 1) }
    pub fn next_f64(&mut self) -> f64 {
        self.0 ^= self.0 >> 12; self.0 ^= self.0 << 25; self.0 ^= self.0 >> 27;
        (self.0.wrapping_mul(0x2545F4914F6CDD1D) >> 11) as f64 / (1u64 << 53) as f64
    }
}

pub struct Backoff { pub base: Duration, pub cap: Duration, prev: Duration }

impl Backoff {
    pub fn new(base: Duration, cap: Duration) -> Self { Backoff { base, cap, prev: base } }

    /// Full jitter: uniform in [0, min(cap, base * 2^attempt)].
    pub fn full_jitter(&self, attempt: u32, rng: &mut Rng) -> Duration {
        let exp = self.base.saturating_mul(1u32.checked_shl(attempt.min(31)).unwrap_or(u32::MAX));
        exp.min(self.cap).mul_f64(rng.next_f64())
    }

    /// Decorrelated jitter: uniform in [base, prev * 3], capped.
    pub fn decorrelated(&mut self, rng: &mut Rng) -> Duration {
        let hi = self.prev.saturating_mul(3).max(self.base);
        let d = self.base + (hi - self.base).mul_f64(rng.next_f64());
        self.prev = d.min(self.cap);
        self.prev
    }
}

/// Client-wide retry budget: retries may not exceed `ratio` of recent requests (+ a floor).
pub struct RetryBudget { tokens: f64, ratio: f64, max: f64 }
impl RetryBudget {
    pub fn new(ratio: f64, max: f64) -> Self { RetryBudget { tokens: max, ratio, max } }
    pub fn on_request(&mut self) { self.tokens = (self.tokens + self.ratio).min(self.max); }
    pub fn try_retry(&mut self) -> bool {
        if self.tokens >= 1.0 { self.tokens -= 1.0; true } else { false }
    }
}

pub enum Failure<E> { Retryable(E, Option<Duration>), Permanent(E) } // Option = server's Retry-After

pub fn retry<T, E>(
    mut op: impl FnMut() -> Result<T, Failure<E>>,
    max_attempts: u32, deadline: Instant, backoff: &Backoff,
    budget: &mut RetryBudget, rng: &mut Rng,
) -> Result<T, E> {
    budget.on_request();
    let mut attempt = 0;
    loop {
        let (err, hint) = match op() {
            Ok(v) => return Ok(v),
            Err(Failure::Permanent(e)) => return Err(e),
            Err(Failure::Retryable(e, hint)) => (e, hint),
        };
        attempt += 1;
        if attempt >= max_attempts || !budget.try_retry() { return Err(err); }
        let delay = backoff.full_jitter(attempt - 1, rng).max(hint.unwrap_or_default());
        if Instant::now() + delay >= deadline { return Err(err); } // no point sleeping past it
        std::thread::sleep(delay);
    }
}

In async code replace thread::sleep with the runtime's timer; the logic is unchanged.

Complexity and constants

• Typical parameters: base 50-100 ms for RPCs (1 s for reconnects), cap 10-30 s for RPCs (minutes for reconnect loops), 3-5 attempts.
• Expected full-jitter delay at attempt n is half of min(cap, base·2^n); total expected wait over n attempts ≈ base·2^n (geometric sum) until the cap.
• Load during an outage: with N clients and full jitter, the retry rate settles near N / (average delay) instead of N per wave.
• AWS SDK "standard" retry mode: 3 attempts, jittered exponential backoff capped at 20 s, plus a client-side retry quota (500 tokens, 5 spent per retry).

Efficiency

• Cost: One RNG draw, a shift and a multiply per retry: order of 10 ns, negligible next to the sleep. The real cost is load: a attempts at each of k layers make a^k requests (4 attempts, 3 layers → 64). The bound is the failing service's capacity and the caller's deadline, not CPU.
• Levers:
  • Full or decorrelated jitter — spreads retries instead of synchronized waves (Brooker 2015) — many clients failing together.
  • Retry budget of about 10 % of requests — caps amplification (SRE book) — any client.
  • Retry at one layer only — a^k → a — layered stacks.
  • Honor Retry-After / gRPC pushback — no wasted attempts — servers that send hints.
  • Deadline check before sleeping — no work nobody waits for — RPC chains.
• Naive → standard → state of the art:
  • Fixed-delay retry loop · every client retries in lockstep, a^k amplification across layers.
  • Exponential backoff without jitter · fewer waves, still synchronized.
  • Full or decorrelated jitter, retry budget, one retry layer, Retry-After honored (Brooker, AWS SDK adaptive mode) · retry rate settles near N / average delay, retries a small fraction of traffic.

Implementation notes

• Retry at one layer only (usually the outermost client or the innermost RPC stub), and propagate deadlines down the stack so inner layers don't retry work nobody waits for.
• Distinguish overload signals: on 429/503 back off harder or stop; on a connection reset to one replica, retry immediately on another replica.
• Make writes idempotent with idempotency keys stored server-side (e.g. Stripe's Idempotency-Key header) so retries are safe.
• Seed the RNG per client/thread; identical seeds recreate synchronized retries.
• Combine with a circuit breaker: when the breaker is open, don't even schedule retries.
• Hedged requests (send a second copy after the p95 latency) cut tail latency, but count them against the same budget.

Pitfalls

• Exponential backoff without jitter: synchronized retry storms (the reason jitter exists).
• Unbounded retries or no cap: a minutes-long outage turns into hours of retry load or hour-long sleeps.
• Retrying non-idempotent operations: double charges, duplicate messages.
• Nested retries (client, SDK, proxy, service mesh, server-side job runner): multiplicative amplification.
• Retrying on timeout with a timeout shorter than the server's processing time: every retry adds work that will also time out.

Variants and alternatives

In production

AWS SDKs (standard and adaptive retry modes), gRPC retry policies and connection backoff, Google Cloud client libraries, Finagle RetryBudget, Envoy retry policy (retry_back_off with jitter, retry budgets), Kubernetes client-go (wait.Backoff), Ethernet CSMA/CD (binary exponential backoff, Metcalfe and Boggs 1976).

Implementations

Sources

• Marc Brooker, Exponential Backoff And Jitter, AWS Architecture Blog, 2015. post
• Betsy Beyer et al. (eds.), Site Reliability Engineering, O'Reilly 2016, ch. 22 Addressing Cascading Failures. book
• gRPC, Connection Backoff Protocol (doc/connection-backoff.md in the grpc repository). spec
• Jeffrey Dean, Luiz André Barroso, The Tail at Scale, CACM 2013. paper
• Robert M. Metcalfe, David R. Boggs, Ethernet: Distributed Packet Switching for Local Computer Networks, CACM 1976. paper