retry_policies/policies/
exponential_backoff.rs

Help
1use crate::{RetryDecision, RetryPolicy};
2use chrono::Utc;
3use rand::distributions::uniform::{UniformFloat, UniformSampler};
4use std::{cmp, time::Duration};
5
6const MIN_JITTER: f64 = 0.0;
7const MAX_JITTER: f64 = 3.0;
8
9/// We are using the "decorrelated jitter" approach detailed here:
10/// `<https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/>`
11#[derive(Debug, Clone, Copy, PartialEq, Eq)]
12pub struct ExponentialBackoff {
13    /// Maximum number of allowed retries attempts.
14    pub max_n_retries: u32,
15    /// Minimum waiting time between two retry attempts (it can end up being lower due to jittering).
16    pub min_retry_interval: Duration,
17    /// Maximum waiting time between two retry attempts.
18    pub max_retry_interval: Duration,
19    /// Growing factor governing how fast the retry interval increases with respect to the number
20    /// of failed attempts. If set to 3:
21    /// - first retry: 3^0 = 1
22    /// - second retry: 3^1 = 3
23    /// - third retry: 3^2 = 9
24    /// ...
25    pub backoff_exponent: u32,
26}
27
28impl ExponentialBackoff {
29    /// Returns a builder.
30    ///
31    /// # Example
32    /// ```
33    /// use retry_policies::policies::ExponentialBackoff;
34    /// use std::time::Duration;
35    ///
36    /// let backoff = ExponentialBackoff::builder()
37    ///     .build_with_total_retry_duration(Duration::from_secs(24 * 60 * 60));
38    ///
39    /// assert_eq!(backoff.backoff_exponent, 3);
40    /// assert_eq!(backoff.min_retry_interval, Duration::from_secs(1));
41    /// assert_eq!(backoff.max_retry_interval, Duration::from_secs(30 * 60));
42    /// assert_eq!(backoff.max_n_retries, 55); // calculated
43    /// ```
44    pub fn builder() -> ExponentialBackoffBuilder {
45        <_>::default()
46    }
47}
48
49impl RetryPolicy for ExponentialBackoff {
50    fn should_retry(&self, n_past_retries: u32) -> RetryDecision {
51        if n_past_retries >= self.max_n_retries {
52            RetryDecision::DoNotRetry
53        } else {
54            let unjittered_wait_for = self.min_retry_interval
55                * self
56                    .backoff_exponent
57                    .checked_pow(n_past_retries)
58                    .unwrap_or(u32::MAX);
59            let jitter_factor =
60                UniformFloat::<f64>::sample_single(MIN_JITTER, MAX_JITTER, &mut rand::thread_rng());
61            let jittered_wait_for = unjittered_wait_for.mul_f64(jitter_factor);
62
63            let execute_after =
64                Utc::now() + clip_and_convert(jittered_wait_for, self.max_retry_interval);
65            RetryDecision::Retry { execute_after }
66        }
67    }
68}
69
70/// Clip to the maximum allowed retry interval and convert to chrono::Duration
71fn clip_and_convert(duration: Duration, max_duration: Duration) -> chrono::Duration {
72    // Unwrapping is fine given that we are guaranteed to never exceed the maximum retry interval
73    // in magnitude and that is well withing range for chrono::Duration
74    chrono::Duration::from_std(cmp::min(duration, max_duration)).unwrap()
75}
76
77pub struct ExponentialBackoffBuilder {
78    min_retry_interval: Duration,
79    max_retry_interval: Duration,
80    backoff_exponent: u32,
81}
82
83impl Default for ExponentialBackoffBuilder {
84    fn default() -> Self {
85        Self {
86            min_retry_interval: Duration::from_secs(1),
87            max_retry_interval: Duration::from_secs(30 * 60),
88            backoff_exponent: 3,
89        }
90    }
91}
92
93impl ExponentialBackoffBuilder {
94    /// Add min & max retry interval bounds. _Default [1s, 30m]_.
95    ///
96    /// See [`ExponentialBackoff::min_retry_interval`], [`ExponentialBackoff::max_retry_interval`].
97    ///
98    /// Panics if `min_retry_interval` > `max_retry_interval`.
99    pub fn retry_bounds(
100        mut self,
101        min_retry_interval: Duration,
102        max_retry_interval: Duration,
103    ) -> Self {
104        assert!(
105            min_retry_interval <= max_retry_interval,
106            "The maximum interval between retries should be greater or equal than the minimum retry interval."
107        );
108        self.min_retry_interval = min_retry_interval;
109        self.max_retry_interval = max_retry_interval;
110        self
111    }
112
113    /// Set backoff exponent. _Default 3_.
114    ///
115    /// See [`ExponentialBackoff::backoff_exponent`].
116    pub fn backoff_exponent(mut self, exponent: u32) -> Self {
117        self.backoff_exponent = exponent;
118        self
119    }
120
121    /// Builds a [`ExponentialBackoff`] with the given maximum retries.
122    ///
123    /// See [`ExponentialBackoff::max_n_retries`].
124    pub fn build_with_max_retries(self, n: u32) -> ExponentialBackoff {
125        ExponentialBackoff {
126            min_retry_interval: self.min_retry_interval,
127            max_retry_interval: self.max_retry_interval,
128            backoff_exponent: self.backoff_exponent,
129            max_n_retries: n,
130        }
131    }
132
133    /// Builds a [`ExponentialBackoff`] with [`ExponentialBackoff::max_n_retries`] calculated
134    /// from an approximate total duration. So that after the resultant `max_n_retries` we'll
135    /// have (generally) retried past the given `total_duration`.
136    ///
137    /// The _actual_ duration will be approximate due to retry jitter, though this calculation
138    /// is itself deterministic (based off mean jitter).
139    ///
140    /// # Example
141    /// ```
142    /// use retry_policies::policies::ExponentialBackoff;
143    /// use std::time::Duration;
144    ///
145    /// let backoff = ExponentialBackoff::builder()
146    ///     .backoff_exponent(2)
147    ///     .retry_bounds(Duration::from_secs(1), Duration::from_secs(60 * 60))
148    ///     // set a retry count so we retry for ~3 hours
149    ///     .build_with_total_retry_duration(Duration::from_secs(3 * 60 * 60));
150    ///
151    /// // mean delay steps: 1.5s, 3s, 6s, 12s, 24s, 48s, 96s, 192s,
152    /// //                   384s, 768s, 1536s, 3072s, 3600s, 3600s
153    /// // expected total delay: 13342.5s = 3.7h (least number of retries >= 3h)
154    /// assert_eq!(backoff.max_n_retries, 14);
155    /// ```
156    pub fn build_with_total_retry_duration(self, total_duration: Duration) -> ExponentialBackoff {
157        let mut out = self.build_with_max_retries(0);
158
159        const MEAN_JITTER: f64 = (MIN_JITTER + MAX_JITTER) / 2.0;
160
161        let delays = (0u32..).into_iter().map(|n| {
162            let min_interval = out.min_retry_interval;
163            let backoff_factor = out.backoff_exponent.checked_pow(n).unwrap_or(u32::MAX);
164            let n_delay = (min_interval * backoff_factor).mul_f64(MEAN_JITTER);
165            cmp::min(n_delay, out.max_retry_interval)
166        });
167
168        let mut approx_total = Duration::from_secs(0);
169        for (n, delay) in delays.enumerate() {
170            approx_total += delay;
171            if approx_total >= total_duration {
172                out.max_n_retries = (n + 1) as _;
173                break;
174            } else if delay == out.max_retry_interval {
175                // Optimisation: The delay aint changing now
176                let remaining_s = (total_duration - approx_total).as_secs_f64();
177                let additional_tries = (remaining_s / delay.as_secs_f64()).ceil() as usize;
178                out.max_n_retries = (n + 1 + additional_tries) as _;
179                break;
180            }
181        }
182
183        out
184    }
185}
186
187#[cfg(test)]
188mod tests {
189    use super::*;
190    use fake::Fake;
191
192    fn get_retry_policy() -> ExponentialBackoff {
193        ExponentialBackoff {
194            max_n_retries: 6,
195            min_retry_interval: Duration::from_secs(1),
196            max_retry_interval: Duration::from_secs(5 * 60),
197            backoff_exponent: 3,
198        }
199    }
200
201    #[test]
202    fn if_n_past_retries_is_below_maximum_it_decides_to_retry() {
203        // Arrange
204        let policy = get_retry_policy();
205        let n_past_retries = (0..policy.max_n_retries).fake();
206        assert!(n_past_retries < policy.max_n_retries);
207
208        // Act
209        let decision = policy.should_retry(n_past_retries);
210
211        // Assert
212        matches!(decision, RetryDecision::Retry { .. });
213    }
214
215    #[test]
216    fn if_n_past_retries_is_above_maximum_it_decides_to_mark_as_failed() {
217        // Arrange
218        let policy = get_retry_policy();
219        let n_past_retries = (policy.max_n_retries..).fake();
220        assert!(n_past_retries >= policy.max_n_retries);
221
222        // Act
223        let decision = policy.should_retry(n_past_retries);
224
225        // Assert
226        matches!(decision, RetryDecision::DoNotRetry);
227    }
228
229    #[test]
230    fn maximum_retry_interval_is_never_exceeded() {
231        // Arrange
232        let policy = get_retry_policy();
233        let max_interval = chrono::Duration::from_std(policy.max_retry_interval).unwrap();
234
235        // Act
236        let decision = policy.should_retry(policy.max_n_retries - 1);
237
238        // Assert
239        match decision {
240            RetryDecision::Retry { execute_after } => {
241                assert!((execute_after - Utc::now()) <= max_interval)
242            }
243            RetryDecision::DoNotRetry => panic!("Expected Retry decision."),
244        }
245    }
246
247    #[test]
248    fn overflow_backoff_exponent_does_not_cause_a_panic() {
249        let policy = ExponentialBackoff {
250            max_n_retries: u32::MAX,
251            backoff_exponent: 2,
252            ..get_retry_policy()
253        };
254        let max_interval = chrono::Duration::from_std(policy.max_retry_interval).unwrap();
255        let n_failed_attempts = u32::MAX - 1;
256
257        // Act
258        let decision = policy.should_retry(n_failed_attempts);
259
260        // Assert
261        match decision {
262            RetryDecision::Retry { execute_after } => {
263                assert!((execute_after - Utc::now()) <= max_interval)
264            }
265            RetryDecision::DoNotRetry => panic!("Expected Retry decision."),
266        }
267    }
268
269    #[test]
270    #[should_panic]
271    fn builder_invalid_retry_bounds() {
272        // bounds are the wrong way round or invalid
273        ExponentialBackoff::builder().retry_bounds(Duration::from_secs(3), Duration::from_secs(2));
274    }
275}
retry_policies/policies/exponential_backoff.rs

retry_policies/policies/
exponential_backoff.rs
