Skip to main content

net_io/
retry.rs

1//! Delays between reconnect attempts: doubling, capped, and spread so a fleet of
2//! clients that lost the same server does not return in step.
3
4use std::collections::hash_map::RandomState;
5use std::hash::{BuildHasher, Hasher};
6use std::time::{Duration, Instant};
7
8/// Delays between attempts: `first`, doubling each attempt up to `max`, each one
9/// drawn from the upper half of its step when jitter is on, so retries spread out
10/// but never come faster than half the step (D-142).
11///
12/// ```
13/// use net_io::Backoff;
14/// use std::time::Duration;
15///
16/// let mut b = Backoff::new()
17///     .first(Duration::from_millis(100))
18///     .max(Duration::from_secs(2))
19///     .jitter(false)
20///     .attempts(3);
21/// assert_eq!(b.next_delay(), Some(Duration::from_millis(100)));
22/// assert_eq!(b.next_delay(), Some(Duration::from_millis(200)));
23/// assert_eq!(b.next_delay(), Some(Duration::from_millis(400)));
24/// assert_eq!(b.next_delay(), None);
25/// b.reset();
26/// assert_eq!(b.attempt(), 0);
27/// ```
28#[must_use]
29#[derive(Clone, Debug)]
30pub struct Backoff {
31    first: Duration,
32    max: Duration,
33    jitter: bool,
34    attempts: Option<u32>,
35    give_up_after: Option<Duration>,
36    attempt: u32,
37    started: Option<Instant>,
38    state: u64,
39}
40
41impl Default for Backoff {
42    fn default() -> Backoff {
43        Backoff::new()
44    }
45}
46
47impl Backoff {
48    /// 100 ms doubling to 30 s, jitter on, no limit on attempts or time.
49    pub fn new() -> Backoff {
50        let mut h = RandomState::new().build_hasher();
51        h.write_u64(0x6e65_742d_696f);
52        Backoff {
53            first: Duration::from_millis(100),
54            max: Duration::from_secs(30),
55            jitter: true,
56            attempts: None,
57            give_up_after: None,
58            attempt: 0,
59            started: None,
60            // xorshift never leaves zero.
61            state: h.finish() | 1,
62        }
63    }
64
65    /// The first delay (at least 1 ms).
66    pub fn first(mut self, d: Duration) -> Backoff {
67        self.first = d.max(Duration::from_millis(1));
68        self.max = self.max.max(self.first);
69        self
70    }
71
72    /// The longest delay (at least `first`).
73    pub fn max(mut self, d: Duration) -> Backoff {
74        self.max = d.max(self.first);
75        self
76    }
77
78    /// Whether each delay is drawn from the upper half of its step (on by default).
79    pub fn jitter(mut self, on: bool) -> Backoff {
80        self.jitter = on;
81        self
82    }
83
84    /// At most `n` delays; then [`Backoff::next_delay`] returns `None`.
85    pub fn attempts(mut self, n: u32) -> Backoff {
86        self.attempts = Some(n);
87        self
88    }
89
90    /// `next_delay` returns `None` once waiting the next delay would end later
91    /// than `total` after the first call.
92    pub fn give_up_after(mut self, total: Duration) -> Backoff {
93        self.give_up_after = Some(total);
94        self
95    }
96
97    /// The delay before the next attempt, or `None` when the attempts or the time
98    /// are spent.
99    pub fn next_delay(&mut self) -> Option<Duration> {
100        if self.attempts.is_some_and(|n| self.attempt >= n) {
101            return None;
102        }
103        let now = Instant::now();
104        let started = *self.started.get_or_insert(now);
105        let step = self
106            .first
107            .checked_mul(1u32.checked_shl(self.attempt).unwrap_or(u32::MAX))
108            .unwrap_or(self.max)
109            .min(self.max);
110        let delay = if self.jitter {
111            let half = step / 2;
112            let span = u64::try_from((step - half).as_nanos()).unwrap_or(u64::MAX);
113            half + Duration::from_nanos(self.random() % span.saturating_add(1))
114        } else {
115            step
116        };
117        if let Some(total) = self.give_up_after {
118            let ends = now.saturating_duration_since(started).checked_add(delay);
119            if ends.is_none_or(|e| e > total) {
120                return None;
121            }
122        }
123        self.attempt = self.attempt.saturating_add(1);
124        Some(delay)
125    }
126
127    /// Delays handed out since the last reset.
128    #[must_use]
129    pub fn attempt(&self) -> u32 {
130        self.attempt
131    }
132
133    /// Back to the first delay, with the time limit counted again from the next call.
134    pub fn reset(&mut self) {
135        self.attempt = 0;
136        self.started = None;
137    }
138
139    fn random(&mut self) -> u64 {
140        let mut x = self.state;
141        x ^= x << 13;
142        x ^= x >> 7;
143        x ^= x << 17;
144        self.state = x;
145        x
146    }
147}
148
149#[cfg(test)]
150mod tests {
151    use super::*;
152
153    #[test]
154    fn test_backoff_doubles_to_the_cap() {
155        let mut b = Backoff::new()
156            .first(Duration::from_millis(10))
157            .max(Duration::from_millis(50))
158            .jitter(false);
159        let got: Vec<u128> = (0..5)
160            .map(|_| b.next_delay().map_or(0, |d| d.as_millis()))
161            .collect();
162        assert_eq!(got, [10, 20, 40, 50, 50]);
163    }
164
165    #[test]
166    fn test_backoff_jitter_stays_in_the_upper_half() {
167        let mut b = Backoff::new()
168            .first(Duration::from_millis(100))
169            .max(Duration::from_millis(100));
170        let mut seen = std::collections::HashSet::new();
171        for _ in 0..1_000 {
172            let d = b.next_delay().unwrap_or_default();
173            assert!(d >= Duration::from_millis(50) && d <= Duration::from_millis(100));
174            seen.insert(d.as_micros() / 1_000);
175        }
176        // Spread, not one value.
177        assert!(seen.len() > 20, "{}", seen.len());
178    }
179
180    #[test]
181    fn test_backoff_never_overflows() {
182        let mut b = Backoff::new()
183            .first(Duration::from_secs(1))
184            .max(Duration::MAX);
185        for _ in 0..200 {
186            assert!(b.next_delay().is_some());
187        }
188        assert_eq!(b.attempt(), 200);
189        let mut b = Backoff::new()
190            .first(Duration::MAX)
191            .jitter(true)
192            .attempts(u32::MAX);
193        assert!(b.next_delay().is_some_and(|d| d >= Duration::MAX / 2));
194    }
195
196    #[test]
197    fn test_backoff_gives_up_on_time_and_count() {
198        let mut b = Backoff::new()
199            .first(Duration::from_secs(1))
200            .jitter(false)
201            .give_up_after(Duration::from_millis(2_500));
202        assert_eq!(b.next_delay(), Some(Duration::from_secs(1)));
203        assert_eq!(b.next_delay(), Some(Duration::from_secs(2)));
204        // Almost no time has passed, but the next delay, 4 s, ends past 2.5 s.
205        assert_eq!(b.next_delay(), None);
206        b.reset();
207        assert_eq!(b.next_delay(), Some(Duration::from_secs(1)));
208        let mut b = Backoff::new().attempts(0);
209        assert_eq!(b.next_delay(), None);
210    }
211
212    #[test]
213    fn test_backoff_instances_spread_differently() {
214        let draw = || {
215            let mut b = Backoff::new().first(Duration::from_secs(10));
216            b.next_delay()
217        };
218        let all: std::collections::HashSet<_> = (0..16).map(|_| draw()).collect();
219        assert!(all.len() > 8, "{}", all.len());
220    }
221}