use std::collections::hash_map::RandomState;
use std::hash::{BuildHasher, Hasher};
use std::time::{Duration, Instant};
#[must_use]
#[derive(Clone, Debug)]
pub struct Backoff {
first: Duration,
max: Duration,
jitter: bool,
attempts: Option<u32>,
give_up_after: Option<Duration>,
attempt: u32,
started: Option<Instant>,
state: u64,
}
impl Default for Backoff {
fn default() -> Backoff {
Backoff::new()
}
}
impl Backoff {
pub fn new() -> Backoff {
let mut h = RandomState::new().build_hasher();
h.write_u64(0x6e65_742d_696f);
Backoff {
first: Duration::from_millis(100),
max: Duration::from_secs(30),
jitter: true,
attempts: None,
give_up_after: None,
attempt: 0,
started: None,
state: h.finish() | 1,
}
}
pub fn first(mut self, d: Duration) -> Backoff {
self.first = d.max(Duration::from_millis(1));
self.max = self.max.max(self.first);
self
}
pub fn max(mut self, d: Duration) -> Backoff {
self.max = d.max(self.first);
self
}
pub fn jitter(mut self, on: bool) -> Backoff {
self.jitter = on;
self
}
pub fn attempts(mut self, n: u32) -> Backoff {
self.attempts = Some(n);
self
}
pub fn give_up_after(mut self, total: Duration) -> Backoff {
self.give_up_after = Some(total);
self
}
pub fn next_delay(&mut self) -> Option<Duration> {
if self.attempts.is_some_and(|n| self.attempt >= n) {
return None;
}
let now = Instant::now();
let started = *self.started.get_or_insert(now);
let step = self
.first
.checked_mul(1u32.checked_shl(self.attempt).unwrap_or(u32::MAX))
.unwrap_or(self.max)
.min(self.max);
let delay = if self.jitter {
let half = step / 2;
let span = u64::try_from((step - half).as_nanos()).unwrap_or(u64::MAX);
half + Duration::from_nanos(self.random() % span.saturating_add(1))
} else {
step
};
if let Some(total) = self.give_up_after {
let ends = now.saturating_duration_since(started).checked_add(delay);
if ends.is_none_or(|e| e > total) {
return None;
}
}
self.attempt = self.attempt.saturating_add(1);
Some(delay)
}
#[must_use]
pub fn attempt(&self) -> u32 {
self.attempt
}
pub fn reset(&mut self) {
self.attempt = 0;
self.started = None;
}
fn random(&mut self) -> u64 {
let mut x = self.state;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.state = x;
x
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_backoff_doubles_to_the_cap() {
let mut b = Backoff::new()
.first(Duration::from_millis(10))
.max(Duration::from_millis(50))
.jitter(false);
let got: Vec<u128> = (0..5)
.map(|_| b.next_delay().map_or(0, |d| d.as_millis()))
.collect();
assert_eq!(got, [10, 20, 40, 50, 50]);
}
#[test]
fn test_backoff_jitter_stays_in_the_upper_half() {
let mut b = Backoff::new()
.first(Duration::from_millis(100))
.max(Duration::from_millis(100));
let mut seen = std::collections::HashSet::new();
for _ in 0..1_000 {
let d = b.next_delay().unwrap_or_default();
assert!(d >= Duration::from_millis(50) && d <= Duration::from_millis(100));
seen.insert(d.as_micros() / 1_000);
}
assert!(seen.len() > 20, "{}", seen.len());
}
#[test]
fn test_backoff_never_overflows() {
let mut b = Backoff::new()
.first(Duration::from_secs(1))
.max(Duration::MAX);
for _ in 0..200 {
assert!(b.next_delay().is_some());
}
assert_eq!(b.attempt(), 200);
let mut b = Backoff::new()
.first(Duration::MAX)
.jitter(true)
.attempts(u32::MAX);
assert!(b.next_delay().is_some_and(|d| d >= Duration::MAX / 2));
}
#[test]
fn test_backoff_gives_up_on_time_and_count() {
let mut b = Backoff::new()
.first(Duration::from_secs(1))
.jitter(false)
.give_up_after(Duration::from_millis(2_500));
assert_eq!(b.next_delay(), Some(Duration::from_secs(1)));
assert_eq!(b.next_delay(), Some(Duration::from_secs(2)));
assert_eq!(b.next_delay(), None);
b.reset();
assert_eq!(b.next_delay(), Some(Duration::from_secs(1)));
let mut b = Backoff::new().attempts(0);
assert_eq!(b.next_delay(), None);
}
#[test]
fn test_backoff_instances_spread_differently() {
let draw = || {
let mut b = Backoff::new().first(Duration::from_secs(10));
b.next_delay()
};
let all: std::collections::HashSet<_> = (0..16).map(|_| draw()).collect();
assert!(all.len() > 8, "{}", all.len());
}
}