tokio_retry/strategy/
fibonacci_backoff.rs

1use std::iter::Iterator;
2use std::time::Duration;
3use std::u64::MAX as U64_MAX;
4
5/// A retry strategy driven by the fibonacci series.
6///
7/// Each retry uses a delay which is the sum of the two previous delays.
8///
9/// Depending on the problem at hand, a fibonacci retry strategy might
10/// perform better and lead to better throughput than the `ExponentialBackoff`
11/// strategy.
12///
13/// See ["A Performance Comparison of Different Backoff Algorithms under Different Rebroadcast Probabilities for MANETs."](http://www.comp.leeds.ac.uk/ukpew09/papers/12.pdf)
14/// for more details.
15#[derive(Debug, Clone)]
16pub struct FibonacciBackoff {
17    curr: u64,
18    next: u64,
19    factor: u64,
20    max_delay: Option<Duration>,
21}
22
23impl FibonacciBackoff {
24    /// Constructs a new fibonacci back-off strategy,
25    /// given a base duration in milliseconds.
26    pub fn from_millis(millis: u64) -> FibonacciBackoff {
27        FibonacciBackoff {
28            curr: millis,
29            next: millis,
30            factor: 1u64,
31            max_delay: None,
32        }
33    }
34
35    /// A multiplicative factor that will be applied to the retry delay.
36    ///
37    /// For example, using a factor of `1000` will make each delay in units of seconds.
38    ///
39    /// Default factor is `1`.
40    pub fn factor(mut self, factor: u64) -> FibonacciBackoff {
41        self.factor = factor;
42        self
43    }
44
45    /// Apply a maximum delay. No retry delay will be longer than this `Duration`.
46    pub fn max_delay(mut self, duration: Duration) -> FibonacciBackoff {
47        self.max_delay = Some(duration);
48        self
49    }
50}
51
52impl Iterator for FibonacciBackoff {
53    type Item = Duration;
54
55    fn next(&mut self) -> Option<Duration> {
56        // set delay duration by applying factor
57        let duration = if let Some(duration) = self.curr.checked_mul(self.factor) {
58            Duration::from_millis(duration)
59        } else {
60            Duration::from_millis(U64_MAX)
61        };
62
63        // check if we reached max delay
64        if let Some(ref max_delay) = self.max_delay {
65            if duration > *max_delay {
66                return Some(*max_delay);
67            }
68        }
69
70        if let Some(next_next) = self.curr.checked_add(self.next) {
71            self.curr = self.next;
72            self.next = next_next;
73        } else {
74            self.curr = self.next;
75            self.next = U64_MAX;
76        }
77
78        Some(duration)
79    }
80}
81
82#[test]
83fn returns_the_fibonacci_series_starting_at_10() {
84    let mut iter = FibonacciBackoff::from_millis(10);
85    assert_eq!(iter.next(), Some(Duration::from_millis(10)));
86    assert_eq!(iter.next(), Some(Duration::from_millis(10)));
87    assert_eq!(iter.next(), Some(Duration::from_millis(20)));
88    assert_eq!(iter.next(), Some(Duration::from_millis(30)));
89    assert_eq!(iter.next(), Some(Duration::from_millis(50)));
90    assert_eq!(iter.next(), Some(Duration::from_millis(80)));
91}
92
93#[test]
94fn saturates_at_maximum_value() {
95    let mut iter = FibonacciBackoff::from_millis(U64_MAX);
96    assert_eq!(iter.next(), Some(Duration::from_millis(U64_MAX)));
97    assert_eq!(iter.next(), Some(Duration::from_millis(U64_MAX)));
98}
99
100#[test]
101fn stops_increasing_at_max_delay() {
102    let mut iter = FibonacciBackoff::from_millis(10).max_delay(Duration::from_millis(50));
103    assert_eq!(iter.next(), Some(Duration::from_millis(10)));
104    assert_eq!(iter.next(), Some(Duration::from_millis(10)));
105    assert_eq!(iter.next(), Some(Duration::from_millis(20)));
106    assert_eq!(iter.next(), Some(Duration::from_millis(30)));
107    assert_eq!(iter.next(), Some(Duration::from_millis(50)));
108    assert_eq!(iter.next(), Some(Duration::from_millis(50)));
109}
110
111#[test]
112fn returns_max_when_max_less_than_base() {
113    let mut iter = FibonacciBackoff::from_millis(20).max_delay(Duration::from_millis(10));
114
115    assert_eq!(iter.next(), Some(Duration::from_millis(10)));
116    assert_eq!(iter.next(), Some(Duration::from_millis(10)));
117}
118
119#[test]
120fn can_use_factor_to_get_seconds() {
121    let factor = 1000;
122    let mut s = FibonacciBackoff::from_millis(1).factor(factor);
123
124    assert_eq!(s.next(), Some(Duration::from_secs(1)));
125    assert_eq!(s.next(), Some(Duration::from_secs(1)));
126    assert_eq!(s.next(), Some(Duration::from_secs(2)));
127}
tokio_retry/strategy/fibonacci_backoff.rs

tokio_retry/strategy/
fibonacci_backoff.rs
