retry.rs
1 //! An implementation of the "decorrelated jitter" algorithm for scheduling retries. 2 //! 3 //! See [`RetryDelay`] for more information. 4 5 use std::time::Duration; 6 7 use crate::RngExt as _; 8 use 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)] 29 pub 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. 40 const MIN_LOW_BOUND: u32 = 1000; 41 42 /// Largest possible lower bound, in milliseconds. 43 const MAX_LOW_BOUND: u32 = u32::MAX - 1; 44 45 /// Maximum amount to multiply the previous delay by. 46 const MAX_DELAY_MULT: u32 = 3; 47 48 impl 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 114 impl Default for RetryDelay { 115 fn default() -> Self { 116 RetryDelay::from_msec(0) 117 } 118 } 119 120 #[cfg(test)] 121 mod 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 }