google_cloud_gax/
exponential_backoff.rs

1// Copyright 2025 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Common implements for exponential backoff.
16//!
17//! This module provides an implementation of truncated [exponential backoff].
18//! It implements the [BackoffPolicy] and [PollingBackoffPolicy] traits.
19//!
20//! [BackoffPolicy]: crate::backoff_policy::BackoffPolicy
21//! [PollingBackoffPolicy]: crate::polling_backoff_policy::PollingBackoffPolicy
22
23use std::time::Duration;
24
25/// The error type for exponential backoff creation.
26#[derive(thiserror::Error, Debug)]
27#[non_exhaustive]
28pub enum Error {
29    #[error("the scaling value ({0}) should be >= 1.0")]
30    InvalidScalingFactor(f64),
31    #[error("the initial delay ({0:?}) should be greater than zero")]
32    InvalidInitialDelay(Duration),
33    #[error(
34        "the maximum delay ({maximum:?}) should be greater than or equal to the initial delay ({initial:?})"
35    )]
36    EmptyRange {
37        maximum: Duration,
38        initial: Duration,
39    },
40}
41
42/// Implements truncated exponential backoff with jitter.
43#[derive(Clone, Debug)]
44pub struct ExponentialBackoffBuilder {
45    initial_delay: Duration,
46    maximum_delay: Duration,
47    scaling: f64,
48}
49
50impl ExponentialBackoffBuilder {
51    /// Creates a builder with the default parameters.
52    ///
53    /// # Example
54    /// ```
55    /// # use google_cloud_gax::exponential_backoff::Error;
56    /// # use google_cloud_gax::exponential_backoff::ExponentialBackoffBuilder;
57    /// use std::time::Duration;
58    ///
59    /// let policy = ExponentialBackoffBuilder::new()
60    ///         .with_initial_delay(Duration::from_millis(100))
61    ///         .with_maximum_delay(Duration::from_secs(5))
62    ///         .with_scaling(4.0)
63    ///         .build()?;
64    /// # Ok::<(), Error>(())
65    /// ```
66    pub fn new() -> Self {
67        Self {
68            initial_delay: Duration::from_secs(1),
69            maximum_delay: Duration::from_secs(60),
70            scaling: 2.0,
71        }
72    }
73
74    /// Change the initial delay.
75    pub fn with_initial_delay<V: Into<Duration>>(mut self, v: V) -> Self {
76        self.initial_delay = v.into();
77        self
78    }
79
80    /// Change the initial delay.
81    pub fn with_maximum_delay<V: Into<Duration>>(mut self, v: V) -> Self {
82        self.maximum_delay = v.into();
83        self
84    }
85
86    /// Change the scaling factor in this backoff policy.
87    pub fn with_scaling<V: Into<f64>>(mut self, v: V) -> Self {
88        self.scaling = v.into();
89        self
90    }
91
92    /// Creates a new exponential backoff policy.
93    ///
94    /// # Example
95    /// ```
96    /// # use google_cloud_gax::exponential_backoff::Error;
97    /// # use google_cloud_gax::exponential_backoff::ExponentialBackoffBuilder;
98    /// # use google_cloud_gax::backoff_policy::BackoffPolicy;
99    /// use std::time::Duration;
100    /// use std::time::Instant;
101    /// let backoff = ExponentialBackoffBuilder::new()
102    ///     .with_initial_delay(Duration::from_secs(5))
103    ///     .with_maximum_delay(Duration::from_secs(50))
104    ///     .with_scaling(2.0)
105    ///     .build()?;
106    /// let p = backoff.on_failure(Instant::now(), 1);
107    /// assert!(p <= Duration::from_secs(5));
108    /// let p = backoff.on_failure(Instant::now(), 2);
109    /// assert!(p <= Duration::from_secs(10));
110    /// # Ok::<(), Error>(())
111    /// ```
112    pub fn build(self) -> Result<ExponentialBackoff, Error> {
113        if self.scaling < 1.0 {
114            return Err(Error::InvalidScalingFactor(self.scaling));
115        }
116        if self.initial_delay.is_zero() {
117            return Err(Error::InvalidInitialDelay(self.initial_delay));
118        }
119        if self.maximum_delay < self.initial_delay {
120            return Err(Error::EmptyRange {
121                maximum: self.maximum_delay,
122                initial: self.initial_delay,
123            });
124        }
125        Ok(ExponentialBackoff {
126            maximum_delay: self.maximum_delay,
127            scaling: self.scaling,
128            initial_delay: self.initial_delay,
129        })
130    }
131
132    /// Creates a new exponential backoff policy clamping the ranges towards
133    /// recommended values.
134    ///
135    /// The maximum delay is clamped first, to be between one second and one day
136    /// (both inclusive). The upper value is hardly useful, typically the retry
137    /// policy would expire earlier than such a long backoff. The exceptions may
138    /// tests and very long running operations.
139    ///
140    /// Then the initial delay is clamped to be between one millisecond and the
141    /// maximum delay. One millisecond is rarely useful outside of tests, but it
142    /// is unlikely to cause problems.
143    ///
144    /// Finally, the scaling factor is clamped to the `[1.0, 32.0]` range.
145    /// Neither extreme is very useful, but neither are necessarily going to
146    /// cause trouble.
147    ///
148    /// # Example
149    /// ```
150    /// # use google_cloud_gax::*;
151    /// # use google_cloud_gax::exponential_backoff::ExponentialBackoffBuilder;
152    /// # use google_cloud_gax::backoff_policy::BackoffPolicy;
153    /// use std::time::Duration;
154    /// use std::time::Instant;
155    /// let mut backoff = ExponentialBackoffBuilder::new().clamp();
156    /// assert!(backoff.on_failure(Instant::now(), 1) > Duration::ZERO);
157    /// ```
158    pub fn clamp(self) -> ExponentialBackoff {
159        let scaling = self.scaling.clamp(1.0, 32.0);
160        let maximum_delay = self
161            .maximum_delay
162            .clamp(Duration::from_secs(1), Duration::from_secs(24 * 60 * 60));
163        let current_delay = self
164            .initial_delay
165            .clamp(Duration::from_millis(1), maximum_delay);
166        ExponentialBackoff {
167            initial_delay: current_delay,
168            maximum_delay,
169            scaling,
170        }
171    }
172}
173
174impl Default for ExponentialBackoffBuilder {
175    fn default() -> Self {
176        Self::new()
177    }
178}
179
180/// Implements truncated exponential backoff.
181#[derive(Debug)]
182pub struct ExponentialBackoff {
183    initial_delay: Duration,
184    maximum_delay: Duration,
185    scaling: f64,
186}
187
188impl ExponentialBackoff {
189    fn delay(&self, _loop_start: std::time::Instant, attempt_count: u32) -> Duration {
190        let exp = std::cmp::min(i32::MAX as u32, attempt_count) as i32;
191        let exp = exp.saturating_sub(1);
192        let scaling = self.scaling.powi(exp);
193        if scaling >= self.maximum_delay.div_duration_f64(self.initial_delay) {
194            self.maximum_delay
195        } else {
196            // .mul_f64() cannot assert because (1) we guarantee scaling >= 1.0,
197            // and (2) we just checked that
198            //     self.initial_delay * scaling < maximum_delay.
199            self.initial_delay.mul_f64(scaling)
200        }
201    }
202
203    fn delay_with_jitter(
204        &self,
205        loop_start: std::time::Instant,
206        attempt_count: u32,
207        rng: &mut impl rand::Rng,
208    ) -> std::time::Duration {
209        let delay = self.delay(loop_start, attempt_count);
210        rng.random_range(Duration::ZERO..=delay)
211    }
212}
213
214impl Default for ExponentialBackoff {
215    fn default() -> Self {
216        Self {
217            initial_delay: Duration::from_secs(1),
218            maximum_delay: Duration::from_secs(60),
219            scaling: 2.0,
220        }
221    }
222}
223
224impl crate::polling_backoff_policy::PollingBackoffPolicy for ExponentialBackoff {
225    fn wait_period(
226        &self,
227        loop_start: std::time::Instant,
228        attempt_count: u32,
229    ) -> std::time::Duration {
230        self.delay(loop_start, attempt_count)
231    }
232}
233
234impl crate::backoff_policy::BackoffPolicy for ExponentialBackoff {
235    fn on_failure(
236        &self,
237        loop_start: std::time::Instant,
238        attempt_count: u32,
239    ) -> std::time::Duration {
240        self.delay_with_jitter(loop_start, attempt_count, &mut rand::rng())
241    }
242}
243
244#[cfg(test)]
245mod tests {
246    use super::*;
247    use crate::mock_rng::MockRng;
248
249    #[test]
250    fn exponential_build_errors() {
251        let b = ExponentialBackoffBuilder::new()
252            .with_initial_delay(Duration::ZERO)
253            .with_maximum_delay(Duration::from_secs(5))
254            .build();
255        assert!(matches!(b, Err(Error::InvalidInitialDelay(_))), "{b:?}");
256        let b = ExponentialBackoffBuilder::new()
257            .with_initial_delay(Duration::from_secs(10))
258            .with_maximum_delay(Duration::from_secs(5))
259            .build();
260        assert!(matches!(b, Err(Error::EmptyRange { .. })), "{b:?}");
261
262        let b = ExponentialBackoffBuilder::new()
263            .with_initial_delay(Duration::from_secs(1))
264            .with_maximum_delay(Duration::from_secs(60))
265            .with_scaling(-1.0)
266            .build();
267        assert!(
268            matches!(b, Err(Error::InvalidScalingFactor { .. })),
269            "{b:?}"
270        );
271
272        let b = ExponentialBackoffBuilder::new()
273            .with_initial_delay(Duration::from_secs(1))
274            .with_maximum_delay(Duration::from_secs(60))
275            .with_scaling(0.0)
276            .build();
277        assert!(
278            matches!(b, Err(Error::InvalidScalingFactor { .. })),
279            "{b:?}"
280        );
281
282        let b = ExponentialBackoffBuilder::new()
283            .with_initial_delay(Duration::ZERO)
284            .build();
285        assert!(matches!(b, Err(Error::InvalidInitialDelay { .. })), "{b:?}");
286    }
287
288    #[test]
289    fn exponential_build_limits() {
290        let r = ExponentialBackoffBuilder::new()
291            .with_initial_delay(Duration::from_secs(1))
292            .with_maximum_delay(Duration::MAX)
293            .build();
294        assert!(r.is_ok(), "{r:?}");
295
296        let r = ExponentialBackoffBuilder::new()
297            .with_initial_delay(Duration::from_nanos(1))
298            .with_maximum_delay(Duration::MAX)
299            .build();
300        assert!(r.is_ok(), "{r:?}");
301
302        let r = ExponentialBackoffBuilder::new()
303            .with_initial_delay(Duration::from_nanos(1))
304            .with_maximum_delay(Duration::MAX)
305            .with_scaling(1.0)
306            .build();
307        assert!(r.is_ok(), "{r:?}");
308    }
309
310    #[test]
311    fn exponential_builder_defaults() {
312        let r = ExponentialBackoffBuilder::new().build();
313        assert!(r.is_ok(), "{r:?}");
314        let r = ExponentialBackoffBuilder::default().build();
315        assert!(r.is_ok(), "{r:?}");
316    }
317
318    #[test_case::test_case(Duration::from_secs(1), Duration::MAX, 0.5; "scaling below range")]
319    #[test_case::test_case(Duration::from_secs(1), Duration::MAX, 1_000_000.0; "scaling over range"
320	)]
321    #[test_case::test_case(Duration::from_secs(1), Duration::MAX, 8.0; "max over range")]
322    #[test_case::test_case(Duration::from_secs(1), Duration::ZERO, 8.0; "max below range")]
323    #[test_case::test_case(Duration::from_secs(10), Duration::ZERO, 8.0; "init over range")]
324    #[test_case::test_case(Duration::ZERO, Duration::ZERO, 8.0; "init below range")]
325    fn exponential_clamp(init: Duration, max: Duration, scaling: f64) {
326        let b = ExponentialBackoffBuilder::new()
327            .with_initial_delay(init)
328            .with_maximum_delay(max)
329            .with_scaling(scaling)
330            .clamp();
331        assert_eq!(b.scaling.clamp(1.0, 32.0), b.scaling);
332        assert_eq!(
333            b.initial_delay
334                .clamp(Duration::from_millis(1), b.maximum_delay),
335            b.initial_delay
336        );
337        assert_eq!(
338            b.maximum_delay
339                .clamp(b.initial_delay, Duration::from_secs(24 * 60 * 60)),
340            b.maximum_delay
341        );
342    }
343
344    #[test]
345    fn exponential_full_jitter() {
346        let b = ExponentialBackoffBuilder::new()
347            .with_initial_delay(Duration::from_secs(10))
348            .with_maximum_delay(Duration::from_secs(10))
349            .build()
350            .expect("should succeed with the hard-coded test values");
351
352        let now = std::time::Instant::now();
353        let mut rng = MockRng::new(1);
354        assert_eq!(b.delay_with_jitter(now, 1, &mut rng), Duration::ZERO);
355
356        let mut rng = MockRng::new(u64::MAX / 2);
357        assert_eq!(
358            b.delay_with_jitter(now, 2, &mut rng),
359            Duration::from_secs(5)
360        );
361
362        let mut rng = MockRng::new(u64::MAX);
363        assert_eq!(
364            b.delay_with_jitter(now, 3, &mut rng),
365            Duration::from_secs(10)
366        );
367    }
368
369    #[test]
370    fn exponential_scaling() {
371        let b = ExponentialBackoffBuilder::new()
372            .with_initial_delay(Duration::from_secs(1))
373            .with_maximum_delay(Duration::from_secs(4))
374            .with_scaling(2.0)
375            .build()
376            .expect("should succeed with the hard-coded test values");
377
378        let now = std::time::Instant::now();
379        assert_eq!(b.delay(now, 1), Duration::from_secs(1));
380        assert_eq!(b.delay(now, 2), Duration::from_secs(2));
381        assert_eq!(b.delay(now, 3), Duration::from_secs(4));
382        assert_eq!(b.delay(now, 4), Duration::from_secs(4));
383    }
384
385    #[test]
386    fn wait_period() {
387        use crate::polling_backoff_policy::PollingBackoffPolicy;
388        let b = ExponentialBackoffBuilder::new()
389            .with_initial_delay(Duration::from_secs(1))
390            .with_maximum_delay(Duration::from_secs(4))
391            .with_scaling(2.0)
392            .build()
393            .expect("should succeed with the hard-coded test values");
394
395        let now = std::time::Instant::now();
396        assert_eq!(b.wait_period(now, 1), Duration::from_secs(1));
397        assert_eq!(b.wait_period(now, 2), Duration::from_secs(2));
398        assert_eq!(b.wait_period(now, 3), Duration::from_secs(4));
399        assert_eq!(b.wait_period(now, 4), Duration::from_secs(4));
400    }
401
402    #[test]
403    fn exponential_scaling_jitter() {
404        let b = ExponentialBackoffBuilder::new()
405            .with_initial_delay(Duration::from_secs(1))
406            .with_maximum_delay(Duration::from_secs(4))
407            .with_scaling(2.0)
408            .build()
409            .expect("should succeed with the hard-coded test values");
410
411        let now = std::time::Instant::now();
412        let mut rng = MockRng::new(u64::MAX);
413        assert_eq!(
414            b.delay_with_jitter(now, 1, &mut rng),
415            Duration::from_secs(1)
416        );
417
418        let mut rng = MockRng::new(u64::MAX);
419        assert_eq!(
420            b.delay_with_jitter(now, 2, &mut rng),
421            Duration::from_secs(2)
422        );
423
424        let mut rng = MockRng::new(u64::MAX);
425        assert_eq!(
426            b.delay_with_jitter(now, 3, &mut rng),
427            Duration::from_secs(4)
428        );
429
430        let mut rng = MockRng::new(u64::MAX);
431        assert_eq!(
432            b.delay_with_jitter(now, 4, &mut rng),
433            Duration::from_secs(4)
434        );
435    }
436
437    #[test]
438    fn on_failure() {
439        use crate::backoff_policy::BackoffPolicy;
440        let b = ExponentialBackoffBuilder::new()
441            .with_initial_delay(Duration::from_secs(1))
442            .with_maximum_delay(Duration::from_secs(4))
443            .with_scaling(2.0)
444            .build()
445            .expect("should succeed with the hard-coded test values");
446
447        let now = std::time::Instant::now();
448        let d = b.on_failure(now, 1);
449        assert!(Duration::ZERO <= d && d <= Duration::from_secs(1), "{d:?}");
450        let d = b.on_failure(now, 2);
451        assert!(Duration::ZERO <= d && d <= Duration::from_secs(2), "{d:?}");
452        let d = b.on_failure(now, 3);
453        assert!(Duration::ZERO <= d && d <= Duration::from_secs(4), "{d:?}");
454        let d = b.on_failure(now, 4);
455        assert!(Duration::ZERO <= d && d <= Duration::from_secs(4), "{d:?}");
456        let d = b.on_failure(now, 5);
457        assert!(Duration::ZERO <= d && d <= Duration::from_secs(4), "{d:?}");
458    }
459
460    #[test]
461    fn default() {
462        let b = ExponentialBackoff::default();
463
464        let now = std::time::Instant::now();
465        let mut rng = MockRng::new(u64::MAX);
466        let next = 2 * b.delay_with_jitter(now, 1, &mut rng);
467
468        let mut rng = MockRng::new(u64::MAX);
469        assert_eq!(b.delay_with_jitter(now, 2, &mut rng), next);
470        let next = 2 * next;
471
472        let mut rng = MockRng::new(u64::MAX);
473        assert_eq!(b.delay_with_jitter(now, 3, &mut rng), next);
474    }
475}
google_cloud_gax/exponential_backoff.rs

google_cloud_gax/
exponential_backoff.rs
