Backoff.pudu

Pudu85 lines3.1 KB

Copy pathGitHub ↗

1/** @Domain.Backoff.Module — delays between retries, with and without jitter */2module PuduLangResilience.Domain.Backoff34import Std.Math.Float as Float5import Std.Math as Math6import Std.Option as Option7import PuduLangResilience.Utils.Numeric as Numeric89/** @Domain.Backoff.Shape — how the delay grows with each retry */10export type Shape = Constant | Linear | Exponential1112/** @Domain.Backoff.Plan — the inputs every delay is computed from */13export type Plan = { shape: Shape, delay: Int, maxDelay: Option[Int], useJitter: Bool }1415/// The share of a constant or linear delay that jitter spreads over, centred on the delay.16const JITTER_SPREAD: Float = 0.51718/// Smooths the first delays of the exponential jitter curve.19const CURVE_SMOOTHING: Float = 4.02021/// Scales the exponential jitter curve so its medians fall near whole multiples of the delay.22const CURVE_SCALE: Float = 0.71428571428571432324/// The delay before retry `attempt`, counting from 0, and the jitter state for the next one.25/// `state` starts at 0.0 for a run of retries; `draw` is a uniform number from 0 up to 1.26export fn next(plan: &Plan, attempt: Int, state: Float, draw: Float) -> (Int, Float) {27  if plan.delay <= 0 { return (0, state) }28  let raw = if plan.useJitter { jittered(plan, attempt, state, draw) } else { (steady(plan, attempt), state) }29  (capped(plan, raw[0]), raw[1])30}3132/// The delay before retry `attempt` without jitter.33export fn steady(plan: &Plan, attempt: Int) -> Int {34  match plan.shape {35    case Constant => plan.delay36    case Linear => Numeric.multiply(Numeric.add(attempt, 1), plan.delay)37    case Exponential => doubled(plan.delay, attempt)38  }39}4041/// `value` doubled `times` times, saturating at `Numeric.LARGEST`.42fn doubled(value: Int, times: Int) -> Int {43  var held = value44  var step = 045  while step < times {46    if held == Numeric.LARGEST { return held }47    held = Numeric.multiply(held, 2)48    step = step + 149  }50  held51}5253/// A delay no longer than the plan's ceiling, when it has one.54fn capped(plan: &Plan, delay: Int) -> Int {55  match plan.maxDelay {56    case Some(ceiling) => Math.min(delay, ceiling)57    case None => delay58  }59}6061/// The jittered delay and the next jitter state.62fn jittered(plan: &Plan, attempt: Int, state: Float, draw: Float) -> (Int, Float) {63  match plan.shape {64    case Exponential => decorrelated(plan.delay, attempt, state, draw)65    case _ => (spread(steady(plan, attempt), draw), state)66  }67}6869/// A delay moved by up to a quarter of itself either way.70fn spread(delay: Int, draw: Float) -> Int {71  let base = Numeric.toFloat(delay)72  Numeric.toInt(base + base * JITTER_SPREAD * draw - base * JITTER_SPREAD / 2.0)73}7475/// The decorrelated exponential curve: `2^t * tanh(sqrt(4t))` at `t = attempt + draw`, less the76/// curve's previous value, scaled by the base delay.77fn decorrelated(delay: Int, attempt: Int, state: Float, draw: Float) -> (Int, Float) {78  let t = Numeric.toFloat(attempt) + draw79  let growth = Option.unwrapOr(Float.powf(2.0, t), 0.0 / 0.0)80  let root = Option.unwrapOr(Float.sqrt(CURVE_SMOOTHING * t), 0.0)81  let curve = growth * Float.tanh(root)82  if !Float.isFinite(curve) { return (Numeric.LARGEST, curve) }83  (Numeric.toInt((curve - state) * CURVE_SCALE * Numeric.toFloat(delay)), curve)84}85