use std::time::Duration;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Jitter {
None,
Seeded(u64),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Backoff {
pub base: Duration,
pub cap: Duration,
pub jitter: Jitter,
pub honor_retry_after: bool,
}
impl Default for Backoff {
fn default() -> Backoff {
Backoff {
base: Duration::from_millis(500),
cap: Duration::from_secs(30),
jitter: Jitter::None,
honor_retry_after: true,
}
}
}
impl Backoff {
pub fn seeded(seed: u64) -> Backoff {
Backoff {
jitter: Jitter::Seeded(seed),
..Backoff::default()
}
}
pub fn delay(&self, retries: u32, retry_after: Option<Duration>) -> Duration {
if self.honor_retry_after {
if let Some(asked) = retry_after {
return asked.saturating_add(match self.jitter {
Jitter::None => Duration::ZERO,
Jitter::Seeded(seed) => Duration::from_millis(1)
.saturating_add(self.base.min(self.cap).mul_f64(unit_draw(seed, retries))),
});
}
}
let doubled = self.base.saturating_mul(1u32 << retries.min(16));
let capped = doubled.min(self.cap);
match self.jitter {
Jitter::None => capped,
Jitter::Seeded(seed) => capped.mul_f64(0.5 + 0.5 * unit_draw(seed, retries)),
}
}
}
fn unit_draw(seed: u64, counter: u32) -> f64 {
let mut z = seed
.wrapping_add(u64::from(counter).wrapping_mul(0x9E37_79B9_7F4A_7C15))
.wrapping_add(0x9E37_79B9_7F4A_7C15);
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^= z >> 31;
((z >> 11) as f64) / ((1u64 << 53) as f64)
}
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::expect_used,
clippy::panic,
clippy::unreachable,
clippy::indexing_slicing,
clippy::string_slice
)]
use super::*;
#[test]
fn the_curve_doubles_until_it_hits_the_ceiling() {
let backoff = Backoff {
base: Duration::from_millis(500),
cap: Duration::from_secs(4),
jitter: Jitter::None,
honor_retry_after: true,
};
assert_eq!(backoff.delay(0, None), Duration::from_millis(500));
assert_eq!(backoff.delay(1, None), Duration::from_secs(1));
assert_eq!(backoff.delay(2, None), Duration::from_secs(2));
assert_eq!(backoff.delay(3, None), Duration::from_secs(4));
assert_eq!(backoff.delay(9, None), Duration::from_secs(4));
}
#[test]
fn the_service_figure_is_never_shortened() {
let backoff = Backoff {
cap: Duration::from_secs(10),
..Backoff::default()
};
assert_eq!(
backoff.delay(0, Some(Duration::from_secs(7))),
Duration::from_secs(7)
);
assert_eq!(
backoff.delay(0, Some(Duration::from_secs(600))),
Duration::from_secs(600)
);
}
#[test]
fn the_service_figure_is_ignored_when_it_was_turned_off() {
let backoff = Backoff {
honor_retry_after: false,
..Backoff::default()
};
assert_eq!(
backoff.delay(0, Some(Duration::from_secs(7))),
Duration::from_millis(500)
);
}
#[test]
fn a_seeded_draw_repeats_and_stays_within_half_the_curve() {
let backoff = Backoff::seeded(42);
let first = backoff.delay(3, None);
assert_eq!(first, Backoff::seeded(42).delay(3, None));
let plain = Duration::from_millis(500) * 8;
assert!(first >= plain / 2, "{first:?} below half of {plain:?}");
assert!(first <= plain, "{first:?} above {plain:?}");
}
#[test]
fn two_seeds_disagree() {
assert_ne!(
Backoff::seeded(1).delay(2, None),
Backoff::seeded(2).delay(2, None)
);
}
#[test]
fn f2_server_waits_get_positive_bounded_seeded_jitter() {
let asked = Duration::from_secs(600);
let first = Backoff::seeded(1).delay(0, Some(asked));
assert_eq!(first, Backoff::seeded(1).delay(0, Some(asked)));
assert_ne!(first, Backoff::seeded(2).delay(0, Some(asked)));
assert!(first > asked);
assert!(first <= asked + Duration::from_millis(501));
}
#[test]
fn the_draw_covers_its_range() {
let mut low = false;
let mut high = false;
for seed in 0..500u64 {
let d = unit_draw(seed, 0);
assert!((0.0..1.0).contains(&d), "seed {seed} drew {d}");
low |= d < 0.25;
high |= d > 0.75;
}
assert!(low && high, "the draw is stuck in the middle of its range");
}
}