1use std::collections::hash_map::RandomState;
5use std::hash::{BuildHasher, Hasher};
6use std::time::{Duration, Instant};
7
8#[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 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 state: h.finish() | 1,
62 }
63 }
64
65 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 pub fn max(mut self, d: Duration) -> Backoff {
74 self.max = d.max(self.first);
75 self
76 }
77
78 pub fn jitter(mut self, on: bool) -> Backoff {
80 self.jitter = on;
81 self
82 }
83
84 pub fn attempts(mut self, n: u32) -> Backoff {
86 self.attempts = Some(n);
87 self
88 }
89
90 pub fn give_up_after(mut self, total: Duration) -> Backoff {
93 self.give_up_after = Some(total);
94 self
95 }
96
97 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 #[must_use]
129 pub fn attempt(&self) -> u32 {
130 self.attempt
131 }
132
133 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 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 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}