use std::collections::hash_map::RandomState;
use std::hash::BuildHasher;
use std::time::{Duration, SystemTime};
#[derive(Debug, Clone)]
pub(crate) struct Backoff {
min_ms: u64,
max_ms: u64,
jitter: f64,
attempts: u32,
}
pub(crate) const DEFAULT_JITTER: f64 = 0.5;
impl Backoff {
pub(crate) fn new(min_ms: u64, max_ms: u64, jitter: f64) -> Self {
Backoff {
min_ms,
max_ms,
jitter: if jitter > 0.0 && jitter <= 1.0 {
jitter
} else {
0.0
},
attempts: 0,
}
}
pub(crate) fn attempts(&self) -> u32 {
self.attempts
}
pub(crate) fn duration(&mut self) -> Duration {
self.duration_with(random_unit())
}
pub(crate) fn duration_with(&mut self, rand: f64) -> Duration {
let mut ms = self.min_ms as f64 * 2f64.powi(self.attempts.min(62) as i32);
self.attempts = self.attempts.saturating_add(1);
if self.jitter > 0.0 {
let deviation = (rand * self.jitter * ms).floor();
ms = if ((rand * 10.0).floor() as u64) & 1 == 0 {
ms - deviation
} else {
ms + deviation
};
}
Duration::from_millis(ms.min(self.max_ms as f64).max(0.0) as u64)
}
#[cfg(test)]
pub(crate) fn reset(&mut self) {
self.attempts = 0;
}
}
fn random_unit() -> f64 {
let bits = RandomState::new().hash_one(SystemTime::now());
(bits >> 11) as f64 / (1u64 << 53) as f64
}
#[cfg(test)]
mod tests {
use super::*;
fn ms(d: Duration) -> u64 {
d.as_millis() as u64
}
#[test]
fn without_jitter_doubles_up_to_max() {
let mut b = Backoff::new(1000, 5000, 0.0);
let got: Vec<u64> = (0..5).map(|_| ms(b.duration())).collect();
assert_eq!(got, [1000, 2000, 4000, 5000, 5000]);
assert_eq!(b.attempts(), 5);
b.reset();
assert_eq!(ms(b.duration()), 1000);
}
#[test]
fn jitter_matches_backo2() {
assert_eq!(ms(Backoff::new(1000, 5000, 0.5).duration_with(0.25)), 875);
assert_eq!(ms(Backoff::new(1000, 5000, 0.5).duration_with(0.35)), 1175);
let mut b = Backoff::new(1000, 5000, 0.5);
b.attempts = 3;
assert_eq!(ms(b.duration_with(0.99)), 5000);
}
#[test]
fn invalid_jitter_is_ignored() {
assert_eq!(ms(Backoff::new(100, 1000, 1.5).duration_with(0.35)), 100);
}
#[test]
fn random_stays_in_range() {
for _ in 0..1000 {
let r = random_unit();
assert!((0.0..1.0).contains(&r));
}
let mut b = Backoff::new(1000, 5000, 0.5);
for _ in 0..1000 {
let d = ms(b.duration());
assert!((500..=5000).contains(&d), "{d}");
b.reset();
}
}
}