iota_common/
backoff.rs

1// Copyright (c) Mysten Labs, Inc.
2// Modifications Copyright (c) 2025 IOTA Stiftung
3// SPDX-License-Identifier: Apache-2.0
4
5use std::{iter::Iterator, time::Duration};
6
7use rand::RngExt;
8
9/// Creates a generator which yields an approximately exponential series of
10/// durations, as back-off delays. Jitters are added to each delay by default to
11/// prevent thundering herd on retries.
12///
13/// The API is inspired by tokio-retry::strategy::ExponentialBackoff for ease of
14/// use. But bugs in the original implementation have been fixed.
15///
16/// ```rust,no_run
17/// use std::time::Duration;
18///
19/// use iota_common::backoff::ExponentialBackoff;
20///
21/// // Basic example:
22/// let mut backoff = ExponentialBackoff::new(Duration::from_millis(100), Duration::from_secs(10));
23/// for (attempt, delay) in backoff.enumerate() {
24///     println!("Attempt {attempt}: Delay: {:?}", delay);
25/// }
26///
27/// // Specifying backoff factor and maximum jitter:
28/// let mut backoff = ExponentialBackoff::new(Duration::from_secs(5), Duration::from_secs(60))
29///     .factor(2.0)
30///     .max_jitter(Duration::from_secs(1));
31/// loop {
32///     // next() should always return a Some(Duration).
33///     let delay = backoff.next().unwrap();
34///     println!("Delay: {:?}", delay);
35/// }
36/// ```
37#[derive(Debug, Clone)]
38pub struct ExponentialBackoff {
39    next: Duration,
40    factor: f64,
41    max_delay: Duration,
42    max_jitter: Duration,
43}
44
45impl ExponentialBackoff {
46    /// Constructs a new exponential backoff generator, specifying the maximum
47    /// delay.
48    pub fn new(initial_delay: Duration, max_delay: Duration) -> ExponentialBackoff {
49        ExponentialBackoff {
50            next: initial_delay,
51            factor: 1.2,
52            max_delay,
53            max_jitter: initial_delay,
54        }
55    }
56
57    /// Sets the approximate ratio of consecutive backoff delays, before jitters
58    /// are applied. Setting this to Duration::ZERO disables jittering.
59    ///
60    /// Default is 1.2.
61    pub fn factor(mut self, factor: f64) -> ExponentialBackoff {
62        self.factor = factor;
63        self
64    }
65
66    /// Sets the maximum jitter per delay.
67    ///
68    /// Default is the initial delay.
69    pub fn max_jitter(mut self, max_jitter: Duration) -> ExponentialBackoff {
70        self.max_jitter = max_jitter;
71        self
72    }
73}
74
75impl Iterator for ExponentialBackoff {
76    type Item = Duration;
77
78    /// Yields backoff delays. Never terminates.
79    fn next(&mut self) -> Option<Duration> {
80        let current = self.next;
81
82        let jitter = if self.max_jitter.is_zero() {
83            Duration::ZERO
84        } else {
85            Duration::from_secs_f64(rand::rng().random_range(0.0..self.max_jitter.as_secs_f64()))
86        };
87        self.next = current
88            .mul_f64(self.factor)
89            .min(self.max_delay)
90            .saturating_add(jitter);
91
92        Some(current)
93    }
94}
95
96#[test]
97fn test_exponential_backoff_default() {
98    let mut backoff = ExponentialBackoff::new(Duration::from_millis(50), Duration::from_secs(10));
99
100    let bounds = vec![
101        (Duration::from_millis(50), Duration::from_millis(100)),
102        (Duration::from_millis(60), Duration::from_millis(170)),
103    ];
104    for ((lower, upper), delay) in bounds.into_iter().zip(backoff.next()) {
105        assert!(delay >= lower && delay <= upper);
106    }
107}
108
109#[test]
110fn test_exponential_backoff_base_100_factor_2_no_jitter() {
111    let mut backoff = ExponentialBackoff::new(Duration::from_millis(100), Duration::from_secs(10))
112        .factor(2.0)
113        .max_jitter(Duration::ZERO);
114
115    assert_eq!(backoff.next(), Some(Duration::from_millis(100)));
116    assert_eq!(backoff.next(), Some(Duration::from_millis(200)));
117    assert_eq!(backoff.next(), Some(Duration::from_millis(400)));
118    assert_eq!(backoff.next(), Some(Duration::from_millis(800)));
119}
120
121#[test]
122fn test_exponential_backoff_max_delay() {
123    let mut backoff = ExponentialBackoff::new(Duration::from_millis(200), Duration::from_secs(1))
124        .factor(3.0)
125        .max_jitter(Duration::ZERO);
126
127    assert_eq!(backoff.next(), Some(Duration::from_millis(200)));
128    assert_eq!(backoff.next(), Some(Duration::from_millis(600)));
129
130    for _ in 0..10 {
131        assert_eq!(backoff.next(), Some(Duration::from_secs(1)));
132    }
133}
iota_common/backoff.rs

iota_common/
backoff.rs
