backon/backoff/
exponential.rs

1use core::time::Duration;
2
3use crate::backoff::BackoffBuilder;
4
5/// ExponentialBuilder is used to construct an [`ExponentialBackoff`] that offers delays with exponential retries.
6///
7/// # Default
8///
9/// - jitter: false
10/// - factor: 2
11/// - min_delay: 1s
12/// - max_delay: 60s
13/// - max_times: 3
14///
15/// # Examples
16///
17/// ```no_run
18/// use anyhow::Result;
19/// use backon::ExponentialBuilder;
20/// use backon::Retryable;
21///
22/// async fn fetch() -> Result<String> {
23///     Ok(reqwest::get("https://www.rust-lang.org")
24///         .await?
25///         .text()
26///         .await?)
27/// }
28///
29/// #[tokio::main(flavor = "current_thread")]
30/// async fn main() -> Result<()> {
31///     let content = fetch.retry(ExponentialBuilder::default()).await?;
32///     println!("fetch succeeded: {}", content);
33///
34///     Ok(())
35/// }
36/// ```
37#[derive(Debug, Clone, Copy)]
38pub struct ExponentialBuilder {
39    jitter: bool,
40    factor: f32,
41    min_delay: Duration,
42    max_delay: Option<Duration>,
43    max_times: Option<usize>,
44    total_delay: Option<Duration>,
45    seed: Option<u64>,
46}
47
48impl Default for ExponentialBuilder {
49    fn default() -> Self {
50        Self::new()
51    }
52}
53
54impl ExponentialBuilder {
55    /// Create a new `ExponentialBuilder` with default values.
56    pub const fn new() -> Self {
57        Self {
58            jitter: false,
59            factor: 2.0,
60            min_delay: Duration::from_secs(1),
61            max_delay: Some(Duration::from_secs(60)),
62            max_times: Some(3),
63            total_delay: None,
64            seed: None,
65        }
66    }
67
68    /// Enable jitter for the backoff.
69    ///
70    /// When jitter is enabled, [`ExponentialBackoff`] will add a random jitter within `(0, current_delay)`
71    /// to the current delay.
72    pub const fn with_jitter(mut self) -> Self {
73        self.jitter = true;
74        self
75    }
76
77    /// Set the seed value for the jitter random number generator. If no seed is given, a random seed is used in std and default seed is used in no_std.
78    pub fn with_jitter_seed(mut self, seed: u64) -> Self {
79        self.seed = Some(seed);
80        self
81    }
82
83    /// Set the factor for the backoff.
84    ///
85    /// Note: Having a factor less than `1.0` does not make any sense as it would create a
86    /// smaller negative backoff.
87    pub const fn with_factor(mut self, factor: f32) -> Self {
88        self.factor = factor;
89        self
90    }
91
92    /// Set the minimum delay for the backoff.
93    pub const fn with_min_delay(mut self, min_delay: Duration) -> Self {
94        self.min_delay = min_delay;
95        self
96    }
97
98    /// Set the maximum delay for the backoff.
99    ///
100    /// The delay will not increase if the current delay exceeds the maximum delay.
101    pub const fn with_max_delay(mut self, max_delay: Duration) -> Self {
102        self.max_delay = Some(max_delay);
103        self
104    }
105
106    /// Set no maximum delay for the backoff.
107    ///
108    /// The delay will keep increasing.
109    ///
110    /// _The delay will saturate at `Duration::MAX` which is an **unrealistic** delay._
111    pub const fn without_max_delay(mut self) -> Self {
112        self.max_delay = None;
113        self
114    }
115
116    /// Set the maximum number of attempts for the current backoff.
117    ///
118    /// The backoff will stop if the maximum number of attempts is reached.
119    pub const fn with_max_times(mut self, max_times: usize) -> Self {
120        self.max_times = Some(max_times);
121        self
122    }
123
124    /// Set no maximum number of attempts for the current backoff.
125    ///
126    /// The backoff will not stop by itself.
127    ///
128    /// _The backoff could stop reaching `usize::MAX` attempts but this is **unrealistic**._
129    pub const fn without_max_times(mut self) -> Self {
130        self.max_times = None;
131        self
132    }
133
134    /// Set the total delay for the backoff.
135    ///
136    /// The backoff will stop yielding sleep durations once the cumulative sleep time
137    /// plus the next sleep duration would exceed `total_delay`.
138    pub const fn with_total_delay(mut self, total_delay: Option<Duration>) -> Self {
139        self.total_delay = total_delay;
140        self
141    }
142}
143
144impl BackoffBuilder for ExponentialBuilder {
145    type Backoff = ExponentialBackoff;
146
147    fn build(self) -> Self::Backoff {
148        ExponentialBackoff {
149            jitter: self.jitter,
150            rng: if let Some(seed) = self.seed {
151                fastrand::Rng::with_seed(seed)
152            } else {
153                #[cfg(feature = "std")]
154                let rng = fastrand::Rng::new();
155
156                #[cfg(not(feature = "std"))]
157                let rng = fastrand::Rng::with_seed(super::RANDOM_SEED);
158
159                rng
160            },
161            factor: self.factor,
162            min_delay: self.min_delay,
163            max_delay: self.max_delay,
164            max_times: self.max_times,
165
166            current_delay: None,
167            attempts: 0,
168            cumulative_delay: Duration::ZERO,
169            total_delay: self.total_delay,
170        }
171    }
172}
173
174impl BackoffBuilder for &ExponentialBuilder {
175    type Backoff = ExponentialBackoff;
176
177    fn build(self) -> Self::Backoff {
178        (*self).build()
179    }
180}
181
182/// ExponentialBackoff provides a delay with exponential retries.
183///
184/// This backoff strategy is constructed by [`ExponentialBuilder`].
185#[doc(hidden)]
186#[derive(Debug)]
187pub struct ExponentialBackoff {
188    jitter: bool,
189    rng: fastrand::Rng,
190    factor: f32,
191    min_delay: Duration,
192    max_delay: Option<Duration>,
193    max_times: Option<usize>,
194    total_delay: Option<Duration>,
195
196    current_delay: Option<Duration>,
197    cumulative_delay: Duration,
198    attempts: usize,
199}
200
201impl Iterator for ExponentialBackoff {
202    type Item = Duration;
203
204    fn next(&mut self) -> Option<Self::Item> {
205        if self.attempts >= self.max_times.unwrap_or(usize::MAX) {
206            return None;
207        }
208        self.attempts += 1;
209
210        let mut tmp_cur = match self.current_delay {
211            None => {
212                // If current_delay is None, it's must be the first time to retry.
213                self.min_delay
214            }
215            Some(mut cur) => {
216                // If current delay larger than max delay, we should stop increment anymore.
217                if let Some(max_delay) = self.max_delay {
218                    if cur < max_delay {
219                        cur = saturating_mul(cur, self.factor);
220                    }
221                    if cur > max_delay {
222                        cur = max_delay;
223                    }
224                } else {
225                    cur = saturating_mul(cur, self.factor);
226                }
227                cur
228            }
229        };
230
231        let current_delay = tmp_cur;
232        // If jitter is enabled, add random jitter based on min delay.
233        if self.jitter {
234            tmp_cur = tmp_cur.saturating_add(tmp_cur.mul_f32(self.rng.f32()));
235        }
236
237        // Check if adding the current delay would exceed the total delay limit.
238        let total_delay_check = self
239            .total_delay
240            .map_or(true, |total| self.cumulative_delay + tmp_cur <= total);
241
242        if !total_delay_check {
243            return None;
244        }
245
246        if self.total_delay.is_some() {
247            self.cumulative_delay = self.cumulative_delay.saturating_add(tmp_cur);
248        }
249
250        self.current_delay = Some(current_delay);
251
252        Some(tmp_cur)
253    }
254}
255
256#[inline]
257pub(crate) fn saturating_mul(d: Duration, rhs: f32) -> Duration {
258    Duration::try_from_secs_f32(rhs * d.as_secs_f32()).unwrap_or(Duration::MAX)
259}
260
261#[cfg(test)]
262mod tests {
263    use core::time::Duration;
264
265    #[cfg(target_arch = "wasm32")]
266    use wasm_bindgen_test::wasm_bindgen_test as test;
267
268    use crate::BackoffBuilder;
269    use crate::ExponentialBuilder;
270
271    const TEST_BUILDER: ExponentialBuilder = ExponentialBuilder::new()
272        .with_jitter()
273        .with_factor(1.5)
274        .with_min_delay(Duration::from_secs(2))
275        .with_max_delay(Duration::from_secs(30))
276        .with_max_times(5);
277
278    #[test]
279    fn test_exponential_default() {
280        let mut exp = ExponentialBuilder::default().build();
281
282        assert_eq!(Some(Duration::from_secs(1)), exp.next());
283        assert_eq!(Some(Duration::from_secs(2)), exp.next());
284        assert_eq!(Some(Duration::from_secs(4)), exp.next());
285        assert_eq!(None, exp.next());
286    }
287
288    #[test]
289    fn test_exponential_factor() {
290        let mut exp = ExponentialBuilder::default().with_factor(1.5).build();
291
292        assert_eq!(Some(Duration::from_secs_f32(1.0)), exp.next());
293        assert_eq!(Some(Duration::from_secs_f32(1.5)), exp.next());
294        assert_eq!(Some(Duration::from_secs_f32(2.25)), exp.next());
295        assert_eq!(None, exp.next());
296    }
297
298    #[test]
299    fn test_exponential_jitter() {
300        let mut exp = ExponentialBuilder::default().with_jitter().build();
301
302        let v = exp.next().expect("value must valid");
303        assert!(v >= Duration::from_secs(1), "current: {v:?}");
304        assert!(v < Duration::from_secs(2), "current: {v:?}");
305
306        let v = exp.next().expect("value must valid");
307        assert!(v >= Duration::from_secs(2), "current: {v:?}");
308        assert!(v < Duration::from_secs(4), "current: {v:?}");
309
310        let v = exp.next().expect("value must valid");
311        assert!(v >= Duration::from_secs(4), "current: {v:?}");
312        assert!(v < Duration::from_secs(8), "current: {v:?}");
313
314        assert_eq!(None, exp.next());
315    }
316
317    #[test]
318    fn test_exponential_min_delay() {
319        let mut exp = ExponentialBuilder::default()
320            .with_min_delay(Duration::from_millis(500))
321            .build();
322
323        assert_eq!(Some(Duration::from_millis(500)), exp.next());
324        assert_eq!(Some(Duration::from_secs(1)), exp.next());
325        assert_eq!(Some(Duration::from_secs(2)), exp.next());
326        assert_eq!(None, exp.next());
327    }
328
329    #[test]
330    fn test_exponential_total_delay() {
331        let mut exp = ExponentialBuilder::default()
332            .with_min_delay(Duration::from_secs(1))
333            .with_factor(1.0)
334            .with_total_delay(Some(Duration::from_secs(3)))
335            .with_max_times(5)
336            .build();
337
338        assert_eq!(Some(Duration::from_secs(1)), exp.next());
339        assert_eq!(Some(Duration::from_secs(1)), exp.next());
340        assert_eq!(Some(Duration::from_secs(1)), exp.next());
341        assert_eq!(None, exp.next());
342    }
343
344    #[test]
345    fn test_exponential_no_max_times_with_default() {
346        let mut exp = ExponentialBuilder::default()
347            .with_min_delay(Duration::from_secs(1))
348            .with_factor(1_f32)
349            .without_max_times()
350            .build();
351
352        // to fully test we would need to call this `usize::MAX`
353        // which seems unreasonable for a test as it would take too long...
354        for _ in 0..10_000 {
355            assert_eq!(Some(Duration::from_secs(1)), exp.next());
356        }
357    }
358
359    #[test]
360    fn test_exponential_max_delay_with_default() {
361        let mut exp = ExponentialBuilder::default()
362            .with_max_delay(Duration::from_secs(2))
363            .build();
364
365        assert_eq!(Some(Duration::from_secs(1)), exp.next());
366        assert_eq!(Some(Duration::from_secs(2)), exp.next());
367        assert_eq!(Some(Duration::from_secs(2)), exp.next());
368        assert_eq!(None, exp.next());
369    }
370
371    #[test]
372    fn test_exponential_no_max_delay_with_default() {
373        let mut exp = ExponentialBuilder::default()
374            .with_min_delay(Duration::from_secs(1))
375            .with_factor(10_000_000_000_f32)
376            .without_max_delay()
377            .with_max_times(4)
378            .build();
379
380        assert_eq!(Some(Duration::from_secs(1)), exp.next());
381        assert_eq!(Some(Duration::from_secs(10_000_000_000)), exp.next());
382        assert_eq!(Some(Duration::MAX), exp.next());
383        assert_eq!(Some(Duration::MAX), exp.next());
384        assert_eq!(None, exp.next());
385    }
386
387    #[test]
388    fn test_exponential_max_delay_without_default_1() {
389        let mut exp = ExponentialBuilder {
390            jitter: false,
391            seed: Some(0x2fdb0020ffc7722b),
392            factor: 10_000_000_000_f32,
393            min_delay: Duration::from_secs(1),
394            max_delay: None,
395            max_times: None,
396            total_delay: None,
397        }
398        .build();
399
400        assert_eq!(Some(Duration::from_secs(1)), exp.next());
401        assert_eq!(Some(Duration::from_secs(10_000_000_000)), exp.next());
402        assert_eq!(Some(Duration::MAX), exp.next());
403        assert_eq!(Some(Duration::MAX), exp.next());
404    }
405
406    #[test]
407    fn test_exponential_max_delay_without_default_2() {
408        let mut exp = ExponentialBuilder {
409            jitter: true,
410            seed: Some(0x2fdb0020ffc7722b),
411            factor: 10_000_000_000_f32,
412            min_delay: Duration::from_secs(10_000_000_000),
413            max_delay: None,
414            max_times: Some(2),
415            total_delay: None,
416        }
417        .build();
418        let v = exp.next().expect("value must valid");
419        assert!(v >= Duration::from_secs(10_000_000_000), "current: {v:?}");
420        assert!(v < Duration::from_secs(20_000_000_000), "current: {v:?}");
421        assert_eq!(Some(Duration::MAX), exp.next());
422        assert_eq!(None, exp.next());
423    }
424
425    #[test]
426    fn test_exponential_max_delay_without_default_3() {
427        let mut exp = ExponentialBuilder {
428            jitter: false,
429            seed: Some(0x2fdb0020ffc7722b),
430            factor: 10_000_000_000_f32,
431            min_delay: Duration::from_secs(10_000_000_000),
432            max_delay: Some(Duration::from_secs(60_000_000_000)),
433            max_times: Some(3),
434            total_delay: None,
435        }
436        .build();
437        assert_eq!(Some(Duration::from_secs(10_000_000_000)), exp.next());
438        assert_eq!(Some(Duration::from_secs(60_000_000_000)), exp.next());
439        assert_eq!(Some(Duration::from_secs(60_000_000_000)), exp.next());
440        assert_eq!(None, exp.next());
441    }
442
443    #[test]
444    fn test_exponential_max_times() {
445        let mut exp = ExponentialBuilder::default().with_max_times(1).build();
446
447        assert_eq!(Some(Duration::from_secs(1)), exp.next());
448        assert_eq!(None, exp.next());
449    }
450
451    // allow assertions on constants because they are not optimized out by unit tests
452    #[allow(clippy::assertions_on_constants)]
453    #[test]
454    fn test_exponential_const_builder() {
455        assert!(TEST_BUILDER.jitter);
456        assert_eq!(TEST_BUILDER.factor, 1.5);
457        assert_eq!(TEST_BUILDER.min_delay, Duration::from_secs(2));
458        assert_eq!(TEST_BUILDER.max_delay, Some(Duration::from_secs(30)));
459        assert_eq!(TEST_BUILDER.max_times, Some(5));
460    }
461}