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
248    #[test]
249    fn exponential_build_errors() {
250        let b = ExponentialBackoffBuilder::new()
251            .with_initial_delay(Duration::ZERO)
252            .with_maximum_delay(Duration::from_secs(5))
253            .build();
254        assert!(matches!(b, Err(Error::InvalidInitialDelay(_))), "{b:?}");
255        let b = ExponentialBackoffBuilder::new()
256            .with_initial_delay(Duration::from_secs(10))
257            .with_maximum_delay(Duration::from_secs(5))
258            .build();
259        assert!(matches!(b, Err(Error::EmptyRange { .. })), "{b:?}");
260
261        let b = ExponentialBackoffBuilder::new()
262            .with_initial_delay(Duration::from_secs(1))
263            .with_maximum_delay(Duration::from_secs(60))
264            .with_scaling(-1.0)
265            .build();
266        assert!(
267            matches!(b, Err(Error::InvalidScalingFactor { .. })),
268            "{b:?}"
269        );
270
271        let b = ExponentialBackoffBuilder::new()
272            .with_initial_delay(Duration::from_secs(1))
273            .with_maximum_delay(Duration::from_secs(60))
274            .with_scaling(0.0)
275            .build();
276        assert!(
277            matches!(b, Err(Error::InvalidScalingFactor { .. })),
278            "{b:?}"
279        );
280
281        let b = ExponentialBackoffBuilder::new()
282            .with_initial_delay(Duration::ZERO)
283            .build();
284        assert!(matches!(b, Err(Error::InvalidInitialDelay { .. })), "{b:?}");
285    }
286
287    #[test]
288    fn exponential_build_limits() {
289        let r = ExponentialBackoffBuilder::new()
290            .with_initial_delay(Duration::from_secs(1))
291            .with_maximum_delay(Duration::MAX)
292            .build();
293        assert!(r.is_ok(), "{r:?}");
294
295        let r = ExponentialBackoffBuilder::new()
296            .with_initial_delay(Duration::from_nanos(1))
297            .with_maximum_delay(Duration::MAX)
298            .build();
299        assert!(r.is_ok(), "{r:?}");
300
301        let r = ExponentialBackoffBuilder::new()
302            .with_initial_delay(Duration::from_nanos(1))
303            .with_maximum_delay(Duration::MAX)
304            .with_scaling(1.0)
305            .build();
306        assert!(r.is_ok(), "{r:?}");
307    }
308
309    #[test]
310    fn exponential_builder_defaults() {
311        let r = ExponentialBackoffBuilder::new().build();
312        assert!(r.is_ok(), "{r:?}");
313        let r = ExponentialBackoffBuilder::default().build();
314        assert!(r.is_ok(), "{r:?}");
315    }
316
317    #[test_case::test_case(Duration::from_secs(1), Duration::MAX, 0.5; "scaling below range")]
318    #[test_case::test_case(Duration::from_secs(1), Duration::MAX, 1_000_000.0; "scaling over range"
319	)]
320    #[test_case::test_case(Duration::from_secs(1), Duration::MAX, 8.0; "max over range")]
321    #[test_case::test_case(Duration::from_secs(1), Duration::ZERO, 8.0; "max below range")]
322    #[test_case::test_case(Duration::from_secs(10), Duration::ZERO, 8.0; "init over range")]
323    #[test_case::test_case(Duration::ZERO, Duration::ZERO, 8.0; "init below range")]
324    fn exponential_clamp(init: Duration, max: Duration, scaling: f64) {
325        let b = ExponentialBackoffBuilder::new()
326            .with_initial_delay(init)
327            .with_maximum_delay(max)
328            .with_scaling(scaling)
329            .clamp();
330        assert_eq!(b.scaling.clamp(1.0, 32.0), b.scaling);
331        assert_eq!(
332            b.initial_delay
333                .clamp(Duration::from_millis(1), b.maximum_delay),
334            b.initial_delay
335        );
336        assert_eq!(
337            b.maximum_delay
338                .clamp(b.initial_delay, Duration::from_secs(24 * 60 * 60)),
339            b.maximum_delay
340        );
341    }
342
343    #[test]
344    fn exponential_full_jitter() {
345        let b = ExponentialBackoffBuilder::new()
346            .with_initial_delay(Duration::from_secs(10))
347            .with_maximum_delay(Duration::from_secs(10))
348            .build()
349            .expect("should succeed with the hard-coded test values");
350
351        let now = std::time::Instant::now();
352        let mut rng = rand::rngs::mock::StepRng::new(1, 0);
353        assert_eq!(b.delay_with_jitter(now, 1, &mut rng), Duration::ZERO);
354
355        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX / 2, 0);
356        assert_eq!(
357            b.delay_with_jitter(now, 2, &mut rng),
358            Duration::from_secs(5)
359        );
360
361        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX, 0);
362        assert_eq!(
363            b.delay_with_jitter(now, 3, &mut rng),
364            Duration::from_secs(10)
365        );
366    }
367
368    #[test]
369    fn exponential_scaling() {
370        let b = ExponentialBackoffBuilder::new()
371            .with_initial_delay(Duration::from_secs(1))
372            .with_maximum_delay(Duration::from_secs(4))
373            .with_scaling(2.0)
374            .build()
375            .expect("should succeed with the hard-coded test values");
376
377        let now = std::time::Instant::now();
378        assert_eq!(b.delay(now, 1), Duration::from_secs(1));
379        assert_eq!(b.delay(now, 2), Duration::from_secs(2));
380        assert_eq!(b.delay(now, 3), Duration::from_secs(4));
381        assert_eq!(b.delay(now, 4), Duration::from_secs(4));
382    }
383
384    #[test]
385    fn wait_period() {
386        use crate::polling_backoff_policy::PollingBackoffPolicy;
387        let b = ExponentialBackoffBuilder::new()
388            .with_initial_delay(Duration::from_secs(1))
389            .with_maximum_delay(Duration::from_secs(4))
390            .with_scaling(2.0)
391            .build()
392            .expect("should succeed with the hard-coded test values");
393
394        let now = std::time::Instant::now();
395        assert_eq!(b.wait_period(now, 1), Duration::from_secs(1));
396        assert_eq!(b.wait_period(now, 2), Duration::from_secs(2));
397        assert_eq!(b.wait_period(now, 3), Duration::from_secs(4));
398        assert_eq!(b.wait_period(now, 4), Duration::from_secs(4));
399    }
400
401    #[test]
402    fn exponential_scaling_jitter() {
403        let b = ExponentialBackoffBuilder::new()
404            .with_initial_delay(Duration::from_secs(1))
405            .with_maximum_delay(Duration::from_secs(4))
406            .with_scaling(2.0)
407            .build()
408            .expect("should succeed with the hard-coded test values");
409
410        let now = std::time::Instant::now();
411        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX, 0);
412        assert_eq!(
413            b.delay_with_jitter(now, 1, &mut rng),
414            Duration::from_secs(1)
415        );
416
417        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX, 0);
418        assert_eq!(
419            b.delay_with_jitter(now, 2, &mut rng),
420            Duration::from_secs(2)
421        );
422
423        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX, 0);
424        assert_eq!(
425            b.delay_with_jitter(now, 3, &mut rng),
426            Duration::from_secs(4)
427        );
428
429        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX, 0);
430        assert_eq!(
431            b.delay_with_jitter(now, 4, &mut rng),
432            Duration::from_secs(4)
433        );
434    }
435
436    #[test]
437    fn on_failure() {
438        use crate::backoff_policy::BackoffPolicy;
439        let b = ExponentialBackoffBuilder::new()
440            .with_initial_delay(Duration::from_secs(1))
441            .with_maximum_delay(Duration::from_secs(4))
442            .with_scaling(2.0)
443            .build()
444            .expect("should succeed with the hard-coded test values");
445
446        let now = std::time::Instant::now();
447        let d = b.on_failure(now, 1);
448        assert!(Duration::ZERO <= d && d <= Duration::from_secs(1), "{d:?}");
449        let d = b.on_failure(now, 2);
450        assert!(Duration::ZERO <= d && d <= Duration::from_secs(2), "{d:?}");
451        let d = b.on_failure(now, 3);
452        assert!(Duration::ZERO <= d && d <= Duration::from_secs(4), "{d:?}");
453        let d = b.on_failure(now, 4);
454        assert!(Duration::ZERO <= d && d <= Duration::from_secs(4), "{d:?}");
455        let d = b.on_failure(now, 5);
456        assert!(Duration::ZERO <= d && d <= Duration::from_secs(4), "{d:?}");
457    }
458
459    #[test]
460    fn default() {
461        let b = ExponentialBackoff::default();
462
463        let now = std::time::Instant::now();
464        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX, 0);
465        let next = 2 * b.delay_with_jitter(now, 1, &mut rng);
466
467        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX, 0);
468        assert_eq!(b.delay_with_jitter(now, 2, &mut rng), next);
469        let next = 2 * next;
470
471        let mut rng = rand::rngs::mock::StepRng::new(u64::MAX, 0);
472        assert_eq!(b.delay_with_jitter(now, 3, &mut rng), next);
473    }
474}
google_cloud_gax/exponential_backoff.rs

google_cloud_gax/
exponential_backoff.rs
