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}