sisyphus/
jitter.rs

1//! Jitter / randomness abstraction.
2//!
3//! Adding randomness to backoff delays is the standard defence against the
4//! *thundering herd*: if a thousand peers all fail at the same instant and all
5//! back off by exactly the same amount, they will all retry at the same instant
6//! too. Jitter spreads them out.
7//!
8//! Crucially, the randomness is **injected**, not pulled from a global RNG.
9//! Inject [`NoJitter`] for fully deterministic behaviour, a seeded
10//! [`SplitMix64`] for reproducible-yet-spread-out behaviour (ideal for P2P
11//! simulation and consensus tests), or your own host RNG in production.
12
13use core::time::Duration;
14
15use crate::util::saturating_mul_f64;
16
17/// A source of uniform randomness used to perturb backoff delays.
18///
19/// The only required method is [`next_unit_f64`], which yields a value in
20/// `[0.0, 1.0)`. The provided [`apply`] method turns that into a symmetric
21/// jitter around a base delay.
22///
23/// [`next_unit_f64`]: Jitter::next_unit_f64
24/// [`apply`]: Jitter::apply
25pub trait Jitter {
26    /// Return the next pseudo-random value in the half-open range `[0.0, 1.0)`.
27    fn next_unit_f64(&mut self) -> f64;
28
29    /// Apply symmetric jitter of `factor` around `base`.
30    ///
31    /// With `factor == 0.0` the `base` is returned unchanged. With
32    /// `factor == r` the result is uniformly distributed in
33    /// `[base * (1 - r), base * (1 + r))`. `factor` is clamped to `[0.0, 1.0]`.
34    ///
35    /// The conversion is saturating and therefore panic-free.
36    #[inline]
37    fn apply(&mut self, base: Duration, factor: f64) -> Duration {
38        if factor <= 0.0 || base.is_zero() {
39            return base;
40        }
41        let factor = factor.min(1.0);
42        let r = self.next_unit_f64();
43        // scale ranges over [1 - factor, 1 + factor).
44        let scale = (1.0 - factor) + r * (2.0 * factor);
45        saturating_mul_f64(base, scale)
46    }
47}
48
49impl<J: Jitter + ?Sized> Jitter for &mut J {
50    #[inline]
51    fn next_unit_f64(&mut self) -> f64 {
52        (**self).next_unit_f64()
53    }
54}
55
56/// A [`Jitter`] that adds no randomness at all.
57///
58/// [`apply`](Jitter::apply) always returns the base delay unchanged, so a
59/// policy using `NoJitter` is fully deterministic. This is the default jitter
60/// for [`ExponentialBackoff`].
61///
62/// [`ExponentialBackoff`]: crate::ExponentialBackoff
63#[derive(Debug, Clone, Copy, Default)]
64pub struct NoJitter;
65
66impl Jitter for NoJitter {
67    /// Returns the midpoint `0.5`, so any symmetric jitter collapses to the
68    /// base delay (`(1 - f) + 0.5 * 2f == 1`).
69    #[inline]
70    fn next_unit_f64(&mut self) -> f64 {
71        0.5
72    }
73}
74
75/// A tiny, fast, deterministic PRNG (Steele et al.'s SplitMix64).
76///
77/// This is **not** cryptographically secure, but it is excellent for jitter:
78/// it is allocation-free, `const`-constructible, has good statistical spread,
79/// and is perfectly reproducible from a seed. That reproducibility is the whole
80/// point in P2P/consensus testing.
81///
82/// # Example
83///
84/// ```
85/// use sisyphus::{Jitter, SplitMix64};
86///
87/// let mut a = SplitMix64::new(42);
88/// let mut b = SplitMix64::new(42);
89/// // Same seed => identical stream => reproducible tests.
90/// assert_eq!(a.next_unit_f64(), b.next_unit_f64());
91/// ```
92#[derive(Debug, Clone, Copy)]
93pub struct SplitMix64 {
94    state: u64,
95}
96
97impl SplitMix64 {
98    /// Create a new generator from a 64-bit seed.
99    #[inline]
100    #[must_use]
101    pub const fn new(seed: u64) -> Self {
102        Self { state: seed }
103    }
104
105    /// Advance the generator and return the next raw 64-bit value.
106    #[inline]
107    pub fn next_u64(&mut self) -> u64 {
108        self.state = self.state.wrapping_add(0x9E37_79B9_7F4A_7C15);
109        let mut z = self.state;
110        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
111        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
112        z ^ (z >> 31)
113    }
114}
115
116impl Default for SplitMix64 {
117    #[inline]
118    fn default() -> Self {
119        // An arbitrary non-zero default seed.
120        Self::new(0x2545_F491_4F6C_DD1D)
121    }
122}
123
124impl Jitter for SplitMix64 {
125    #[inline]
126    fn next_unit_f64(&mut self) -> f64 {
127        // Use the top 53 bits to fill an f64 mantissa, giving a uniform
128        // value in [0, 1). 2^-53 is exactly representable.
129        const SCALE: f64 = 1.0 / (1u64 << 53) as f64;
130        (self.next_u64() >> 11) as f64 * SCALE
131    }
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137
138    #[test]
139    fn no_jitter_is_identity() {
140        let mut j = NoJitter;
141        let base = Duration::from_millis(100);
142        assert_eq!(j.apply(base, 0.5), base);
143        assert_eq!(j.apply(base, 1.0), base);
144    }
145
146    #[test]
147    fn unit_values_are_in_range() {
148        let mut rng = SplitMix64::new(7);
149        for _ in 0..10_000 {
150            let v = rng.next_unit_f64();
151            assert!((0.0..1.0).contains(&v), "value out of range: {v}");
152        }
153    }
154
155    #[test]
156    fn jitter_stays_within_symmetric_bounds() {
157        let mut rng = SplitMix64::new(99);
158        let base = Duration::from_millis(1000);
159        for _ in 0..10_000 {
160            let d = rng.apply(base, 0.5);
161            assert!(d >= Duration::from_millis(500));
162            assert!(d < Duration::from_millis(1500));
163        }
164    }
165
166    #[test]
167    fn seeded_streams_are_reproducible() {
168        let mut a = SplitMix64::new(123);
169        let mut b = SplitMix64::new(123);
170        for _ in 0..100 {
171            assert_eq!(a.next_u64(), b.next_u64());
172        }
173    }
174}
sisyphus/jitter.rs

sisyphus/
jitter.rs
