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::Rng as _;
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(
86                rand::thread_rng().gen_range(0.0..self.max_jitter.as_secs_f64()),
87            )
88        };
89        self.next = current
90            .mul_f64(self.factor)
91            .min(self.max_delay)
92            .saturating_add(jitter);
93
94        Some(current)
95    }
96}
97
98#[test]
99fn test_exponential_backoff_default() {
100    let mut backoff = ExponentialBackoff::new(Duration::from_millis(50), Duration::from_secs(10));
101
102    let bounds = vec![
103        (Duration::from_millis(50), Duration::from_millis(100)),
104        (Duration::from_millis(60), Duration::from_millis(170)),
105    ];
106    for ((lower, upper), delay) in bounds.into_iter().zip(backoff.next()) {
107        assert!(delay >= lower && delay <= upper);
108    }
109}
110
111#[test]
112fn test_exponential_backoff_base_100_factor_2_no_jitter() {
113    let mut backoff = ExponentialBackoff::new(Duration::from_millis(100), Duration::from_secs(10))
114        .factor(2.0)
115        .max_jitter(Duration::ZERO);
116
117    assert_eq!(backoff.next(), Some(Duration::from_millis(100)));
118    assert_eq!(backoff.next(), Some(Duration::from_millis(200)));
119    assert_eq!(backoff.next(), Some(Duration::from_millis(400)));
120    assert_eq!(backoff.next(), Some(Duration::from_millis(800)));
121}
122
123#[test]
124fn test_exponential_backoff_max_delay() {
125    let mut backoff = ExponentialBackoff::new(Duration::from_millis(200), Duration::from_secs(1))
126        .factor(3.0)
127        .max_jitter(Duration::ZERO);
128
129    assert_eq!(backoff.next(), Some(Duration::from_millis(200)));
130    assert_eq!(backoff.next(), Some(Duration::from_millis(600)));
131
132    for _ in 0..10 {
133        assert_eq!(backoff.next(), Some(Duration::from_secs(1)));
134    }
135}
iota_common/backoff.rs

iota_common/
backoff.rs
