tor_basic_utils/
retry.rs

1//! An implementation of the "decorrelated jitter" algorithm for scheduling retries.
2//!
3//! See [`RetryDelay`] for more information.
4
5use std::time::Duration;
6
7use crate::RngExt as _;
8use rand::Rng;
9
10/// An implementation for retrying a remote operation based on a [decorrelated
11/// jitter] schedule.
12///
13/// The algorithm used here has several desirable properties:
14///    * It is randomized, so that multiple timeouts don't have a danger of
15///      getting synchronized with each other and hammering the same servers all
16///      at once.
17///    * It tends on average to wait longer and longer over time, so that if the
18///      server is down, it won't get pummeled by a zillion failing clients
19///      when it comes back up.
20///    * It has a chance of retrying promptly, which results in better client
21///      performance on average.
22///
23/// For a more full specification, see [`dir-spec.txt`].
24///
25/// [decorrelated jitter]:
26///     https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/
27/// [`dir-spec.txt`]: https://spec.torproject.org/dir-spec
28#[derive(Clone, Debug)]
29pub struct RetryDelay {
30    /// The last delay that this retry delay returned (in msec), or 0
31    /// if this never returned a delay.
32    last_delay_ms: u32,
33    /// The lowest allowable delay (in msec).
34    low_bound_ms: u32,
35}
36
37/// Lowest possible lower bound, in milliseconds.
38// We're doing this in MS, and Tor does it in seconds, so I'm
39// multiplying the minimum by 1000 here.
40const MIN_LOW_BOUND: u32 = 1000;
41
42/// Largest possible lower bound, in milliseconds.
43const MAX_LOW_BOUND: u32 = u32::MAX - 1;
44
45/// Maximum amount to multiply the previous delay by.
46const MAX_DELAY_MULT: u32 = 3;
47
48impl RetryDelay {
49    /// Construct a new RetryDelay from a given base delay in
50    /// milliseconds.
51    ///
52    /// The base delay defines the lowest possible interval that can
53    /// be returned.
54    ///
55    /// # Limitations
56    ///
57    /// If the base delay is less than 1000, a base delay of 1000 is
58    /// used instead, since that's what the C tor implementation does.
59    pub fn from_msec(base_delay_msec: u32) -> Self {
60        let low_bound_ms = base_delay_msec.clamp(MIN_LOW_BOUND, MAX_LOW_BOUND);
61        RetryDelay {
62            last_delay_ms: 0,
63            low_bound_ms,
64        }
65    }
66
67    /// Construct a new RetryDelay from a given base delay.
68    ///
69    /// See from_msec for more information.
70    pub fn from_duration(d: Duration) -> Self {
71        let msec = d.as_millis();
72        let msec = std::cmp::min(msec, u128::from(MAX_LOW_BOUND)) as u32;
73        RetryDelay::from_msec(msec)
74    }
75
76    /// Helper: Return a lower and upper bound for the next delay to
77    /// be yielded.
78    ///
79    /// Values are in milliseconds.
80    ///
81    /// The return value `(low, high)` is guaranteed to have `low < high`.
82    fn delay_bounds(&self) -> (u32, u32) {
83        let low = self.low_bound_ms;
84        let high = std::cmp::max(
85            // We don't need a saturating_add here, since low is always
86            // <= MAX_LOW_BOUND, so low cannot be equal to u32::MAX.
87            low + 1,
88            self.last_delay_ms.saturating_mul(MAX_DELAY_MULT),
89        );
90        (low, high)
91    }
92
93    /// Return the next delay to be used (in milliseconds), according
94    /// to a given random number generator.
95    fn next_delay_msec<R: Rng>(&mut self, rng: &mut R) -> u32 {
96        let (low, high) = self.delay_bounds();
97        let val = rng.gen_range_checked(low..high).expect("low as not < high");
98        self.last_delay_ms = val;
99        val
100    }
101
102    /// Return the next delay to be used (as a [`Duration`]),
103    /// according to a given random number generator.
104    pub fn next_delay<R: Rng>(&mut self, rng: &mut R) -> Duration {
105        Duration::from_millis(u64::from(self.next_delay_msec(rng)))
106    }
107
108    /// Return this [`RetryDelay`] to its original state.
109    pub fn reset(&mut self) {
110        self.last_delay_ms = 0;
111    }
112}
113
114impl Default for RetryDelay {
115    fn default() -> Self {
116        RetryDelay::from_msec(0)
117    }
118}
119
120#[cfg(test)]
121mod test {
122    // @@ begin test lint list maintained by maint/add_warning @@
123    #![allow(clippy::bool_assert_comparison)]
124    #![allow(clippy::clone_on_copy)]
125    #![allow(clippy::dbg_macro)]
126    #![allow(clippy::mixed_attributes_style)]
127    #![allow(clippy::print_stderr)]
128    #![allow(clippy::print_stdout)]
129    #![allow(clippy::single_char_pattern)]
130    #![allow(clippy::unwrap_used)]
131    #![allow(clippy::unchecked_duration_subtraction)]
132    #![allow(clippy::useless_vec)]
133    #![allow(clippy::needless_pass_by_value)]
134    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
135    use super::*;
136    use crate::test_rng::testing_rng;
137
138    #[test]
139    fn init() {
140        let rd = RetryDelay::from_msec(2000);
141        assert_eq!(rd.last_delay_ms, 0);
142        assert_eq!(rd.low_bound_ms, 2000);
143
144        let rd = RetryDelay::from_msec(0);
145        assert_eq!(rd.last_delay_ms, 0);
146        assert_eq!(rd.low_bound_ms, 1000);
147
148        let rd = RetryDelay::from_duration(Duration::new(1, 500_000_000));
149        assert_eq!(rd.last_delay_ms, 0);
150        assert_eq!(rd.low_bound_ms, 1500);
151    }
152
153    #[test]
154    fn bounds() {
155        let mut rd = RetryDelay::from_msec(1000);
156        assert_eq!(rd.delay_bounds(), (1000, 1001));
157        rd.last_delay_ms = 1500;
158        assert_eq!(rd.delay_bounds(), (1000, 4500));
159        rd.last_delay_ms = 3_000_000_000;
160        assert_eq!(rd.delay_bounds(), (1000, u32::MAX));
161        rd.reset();
162        assert_eq!(rd.delay_bounds(), (1000, 1001));
163    }
164
165    #[test]
166    fn rng() {
167        let mut rd = RetryDelay::from_msec(50);
168        let real_low_bound = std::cmp::max(50, MIN_LOW_BOUND);
169
170        let mut rng = testing_rng();
171        for _ in 1..100 {
172            let (b_lo, b_hi) = rd.delay_bounds();
173            assert!(b_lo == real_low_bound);
174            assert!(b_hi > b_lo);
175            let delay = rd.next_delay(&mut rng).as_millis() as u32;
176            assert_eq!(delay, rd.last_delay_ms);
177            assert!(delay >= b_lo);
178            assert!(delay < b_hi);
179        }
180    }
181}