object_store/client/
backoff.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18use rand::{Rng, RngExt, rng};
19use std::time::Duration;
20
21/// Exponential backoff with decorrelated jitter algorithm
22///
23/// The first backoff will always be `init_backoff`.
24///
25/// Subsequent backoffs will pick a random value between `init_backoff` and
26/// `base * previous` where `previous` is the duration of the previous backoff
27///
28/// See <https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/>
29#[allow(missing_copy_implementations)]
30#[derive(Debug, Clone)]
31pub struct BackoffConfig {
32    /// The initial backoff duration
33    pub init_backoff: Duration,
34    /// The maximum backoff duration
35    pub max_backoff: Duration,
36    /// The multiplier to use for the next backoff duration
37    pub base: f64,
38}
39
40impl Default for BackoffConfig {
41    fn default() -> Self {
42        Self {
43            init_backoff: Duration::from_millis(100),
44            max_backoff: Duration::from_secs(15),
45            base: 2.,
46        }
47    }
48}
49
50/// [`Backoff`] can be created from a [`BackoffConfig`]
51///
52/// Consecutive calls to [`Backoff::next`] will return the next backoff interval
53///
54pub(crate) struct Backoff {
55    init_backoff: f64,
56    next_backoff_secs: f64,
57    max_backoff_secs: f64,
58    base: f64,
59    rng: Option<Box<dyn Rng + Sync + Send>>,
60}
61
62impl std::fmt::Debug for Backoff {
63    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
64        f.debug_struct("Backoff")
65            .field("init_backoff", &self.init_backoff)
66            .field("next_backoff_secs", &self.next_backoff_secs)
67            .field("max_backoff_secs", &self.max_backoff_secs)
68            .field("base", &self.base)
69            .finish()
70    }
71}
72
73impl Backoff {
74    /// Create a new [`Backoff`] from the provided [`BackoffConfig`]
75    pub(crate) fn new(config: &BackoffConfig) -> Self {
76        Self::new_with_rng(config, None)
77    }
78
79    /// Creates a new `Backoff` with the optional `rng`
80    ///
81    /// Used [`rand::rng()`] if no rng provided
82    pub(crate) fn new_with_rng(
83        config: &BackoffConfig,
84        rng: Option<Box<dyn Rng + Sync + Send>>,
85    ) -> Self {
86        let init_backoff = config.init_backoff.as_secs_f64();
87        Self {
88            init_backoff,
89            next_backoff_secs: init_backoff,
90            max_backoff_secs: config.max_backoff.as_secs_f64(),
91            base: config.base,
92            rng,
93        }
94    }
95
96    /// Returns the next backoff duration to wait for
97    pub(crate) fn next(&mut self) -> Duration {
98        let range = self.init_backoff..(self.next_backoff_secs * self.base);
99
100        let rand_backoff = match self.rng.as_mut() {
101            Some(rng) => rng.random_range(range),
102            None => rng().random_range(range),
103        };
104
105        let next_backoff = self.max_backoff_secs.min(rand_backoff);
106        Duration::from_secs_f64(std::mem::replace(&mut self.next_backoff_secs, next_backoff))
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use std::convert::Infallible;
113
114    use rand::{TryRng, rand_core::utils::fill_bytes_via_next_word};
115
116    use super::*;
117
118    struct FixedRng(u64);
119
120    impl TryRng for FixedRng {
121        type Error = Infallible;
122
123        fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
124            Ok(self.0 as _)
125        }
126
127        fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
128            Ok(self.0)
129        }
130
131        fn try_fill_bytes(&mut self, dst: &mut [u8]) -> Result<(), Self::Error> {
132            fill_bytes_via_next_word(dst, || self.try_next_u64())
133        }
134    }
135
136    #[test]
137    fn test_backoff() {
138        let init_backoff_secs = 1.;
139        let max_backoff_secs = 500.;
140        let base = 3.;
141
142        let config = BackoffConfig {
143            init_backoff: Duration::from_secs_f64(init_backoff_secs),
144            max_backoff: Duration::from_secs_f64(max_backoff_secs),
145            base,
146        };
147
148        let assert_fuzzy_eq = |a: f64, b: f64| assert!((b - a).abs() < 0.0001, "{a} != {b}");
149
150        // Create a static rng that takes the minimum of the range
151        let rng = Box::new(FixedRng(0));
152        let mut backoff = Backoff::new_with_rng(&config, Some(rng));
153
154        for _ in 0..20 {
155            assert_eq!(backoff.next().as_secs_f64(), init_backoff_secs);
156        }
157
158        // Create a static rng that takes the maximum of the range
159        let rng = Box::new(FixedRng(u64::MAX));
160        let mut backoff = Backoff::new_with_rng(&config, Some(rng));
161
162        for i in 0..20 {
163            let value = (base.powi(i) * init_backoff_secs).min(max_backoff_secs);
164            assert_fuzzy_eq(backoff.next().as_secs_f64(), value);
165        }
166
167        // Create a static rng that takes the mid point of the range
168        let rng = Box::new(FixedRng(u64::MAX / 2));
169        let mut backoff = Backoff::new_with_rng(&config, Some(rng));
170
171        let mut value = init_backoff_secs;
172        for _ in 0..20 {
173            assert_fuzzy_eq(backoff.next().as_secs_f64(), value);
174            value =
175                (init_backoff_secs + (value * base - init_backoff_secs) / 2.).min(max_backoff_secs);
176        }
177    }
178}
object_store/client/backoff.rs

object_store/client/
backoff.rs
