use crate::error::{Failure, Result};
use std::future::Future;
use std::time::{Duration, Instant};
use tokio_util::sync::CancellationToken;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Backoff {
pub extra_attempts: u32,
pub base: Duration,
pub ceiling: Duration,
pub deadline: Duration,
}
impl Backoff {
#[must_use]
pub const fn new(
extra_attempts: u32,
base: Duration,
ceiling: Duration,
deadline: Duration,
) -> Self {
Self {
extra_attempts,
base,
ceiling,
deadline,
}
}
#[must_use]
pub const fn none() -> Self {
Self::new(
0,
Duration::from_millis(0),
Duration::from_millis(0),
Duration::from_millis(0),
)
}
#[must_use]
pub fn wait_before(&self, repeat: u32) -> Duration {
if repeat == 0 {
return Duration::from_millis(0);
}
let factor = 1_u32.checked_shl(repeat - 1).unwrap_or(u32::MAX);
self.base
.checked_mul(factor)
.unwrap_or(self.ceiling)
.min(self.ceiling)
}
#[must_use]
pub fn spread(&self, nominal: Duration) -> Duration {
let kept = nominal / 2;
if kept.is_zero() {
return nominal;
}
let width = u64::try_from(nominal.saturating_sub(kept).as_nanos()).unwrap_or(u64::MAX);
kept + Duration::from_nanos(draw() % width.saturating_add(1))
}
#[must_use]
pub fn exceeds_deadline(&self, spent: Duration, pause: Duration) -> bool {
!self.deadline.is_zero() && spent.saturating_add(pause) > self.deadline
}
}
fn draw() -> u64 {
use std::hash::{BuildHasher, Hasher};
std::collections::hash_map::RandomState::new()
.build_hasher()
.finish()
}
pub async fn retry<T, F, Fut>(
policy: &Backoff,
token: &CancellationToken,
mut operation: F,
) -> Result<T>
where
F: FnMut(u32) -> Fut,
Fut: Future<Output = Result<T>>,
{
let started = Instant::now();
let mut repeat = 0;
loop {
match operation(repeat + 1).await {
Ok(value) => return Ok(value),
Err(failure) => {
if !failure.is_retryable() {
crate::i18n::report::attempt_permanent();
return Err(failure);
}
if repeat >= policy.extra_attempts {
return Err(failure);
}
let attempt = repeat + 1;
repeat += 1;
let pause = policy.spread(policy.wait_before(repeat));
let spent = started.elapsed();
if policy.exceeds_deadline(spent, pause) {
crate::i18n::report::attempt_budget_spent(
spent.as_millis(),
policy.deadline.as_millis(),
);
return Err(failure);
}
crate::i18n::report::attempt_retrying(
attempt,
policy.extra_attempts + 1,
pause.as_millis(),
);
wait(pause, token).await?;
}
}
}
}
async fn wait(duration: Duration, token: &CancellationToken) -> Result<()> {
tokio::select! {
() = token.cancelled() => Err(Failure::interrupted(
"interrupted.waiting_to_retry",
"the invocation was stopped while waiting to try again",
)),
() = tokio::time::sleep(duration) => Ok(()),
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::cell::Cell;
fn policy() -> Backoff {
Backoff::new(
3,
Duration::from_millis(1),
Duration::from_millis(8),
Duration::from_secs(30),
)
}
#[test]
fn the_wait_doubles_and_then_stops_at_the_ceiling() {
let policy = policy();
assert_eq!(policy.wait_before(0), Duration::from_millis(0));
assert_eq!(policy.wait_before(1), Duration::from_millis(1));
assert_eq!(policy.wait_before(2), Duration::from_millis(2));
assert_eq!(policy.wait_before(3), Duration::from_millis(4));
assert_eq!(policy.wait_before(4), Duration::from_millis(8));
assert_eq!(policy.wait_before(50), Duration::from_millis(8));
}
#[test]
fn two_waits_of_the_same_length_do_not_land_on_the_same_instant() {
let policy = Backoff::new(
5,
Duration::from_millis(200),
Duration::from_millis(6_400),
Duration::from_secs(30),
);
let nominal = policy.wait_before(3);
let drawn: std::collections::BTreeSet<Duration> =
(0..100).map(|_| policy.spread(nominal)).collect();
assert!(
drawn.len() > 50,
"a hundred waits produced {} distinct lengths, which is a herd",
drawn.len()
);
}
#[test]
fn a_spread_wait_never_leaves_the_upper_half_of_the_nominal_one() {
let policy = Backoff::new(
8,
Duration::from_millis(200),
Duration::from_millis(6_400),
Duration::from_secs(30),
);
for repeat in 1..=8 {
let nominal = policy.wait_before(repeat);
for _ in 0..50 {
let spread = policy.spread(nominal);
assert!(spread >= nominal / 2, "repeat {repeat}: {spread:?}");
assert!(spread <= nominal, "repeat {repeat}: {spread:?}");
}
}
}
#[test]
fn a_wait_with_nothing_to_spread_is_kept_whole() {
let policy = policy();
assert_eq!(policy.spread(Duration::ZERO), Duration::ZERO);
assert_eq!(
policy.spread(Duration::from_nanos(1)),
Duration::from_nanos(1)
);
}
#[test]
fn the_deadline_bounds_the_series_and_not_each_wait() {
let policy = Backoff::new(
9,
Duration::from_secs(1),
Duration::from_secs(1),
Duration::from_secs(4),
);
assert!(
!policy.exceeds_deadline(Duration::from_secs(2), Duration::from_secs(1)),
"three seconds of a four second budget still fits"
);
assert!(
policy.exceeds_deadline(Duration::from_secs(4), Duration::from_secs(1)),
"the budget is spent and six attempts are still left"
);
}
#[test]
fn a_policy_with_no_deadline_never_stops_for_one() {
let unbounded = Backoff::new(
3,
Duration::from_millis(1),
Duration::from_millis(8),
Duration::ZERO,
);
assert!(!unbounded.exceeds_deadline(Duration::from_secs(3_600), Duration::from_secs(1)));
}
#[tokio::test]
async fn a_spent_budget_ends_the_series_before_the_attempts_do() {
let attempts = Cell::new(0);
let tight = Backoff::new(
20,
Duration::from_millis(40),
Duration::from_millis(80),
Duration::from_millis(1),
);
let failure = retry(&tight, &CancellationToken::new(), |_| {
attempts.set(attempts.get() + 1);
async { Err::<u8, Failure>(Failure::network("network.unreachable", "lost")) }
})
.await
.expect_err("must fail");
assert_eq!(
attempts.get(),
1,
"the budget was spent before the second attempt, and twenty were left"
);
assert_eq!(
failure.code(),
"network.unreachable",
"the caller gets what the work produced, not a report about the policy"
);
}
#[tokio::test]
async fn a_clean_call_is_never_repeated() {
let attempts = Cell::new(0);
let value = retry(&policy(), &CancellationToken::new(), |_| {
attempts.set(attempts.get() + 1);
async { Ok::<u8, Failure>(7) }
})
.await
.expect("clean");
assert_eq!(value, 7);
assert_eq!(attempts.get(), 1);
}
#[tokio::test]
async fn a_refused_credential_is_never_repeated() {
let attempts = Cell::new(0);
let failure = retry(&policy(), &CancellationToken::new(), |_| {
attempts.set(attempts.get() + 1);
async {
Err::<u8, Failure>(Failure::authentication(
"auth.refused",
"the credential was refused",
))
}
})
.await
.expect_err("must fail");
assert_eq!(attempts.get(), 1, "a final answer is never asked twice");
assert_eq!(failure.exit_number().code(), 6);
}
#[tokio::test]
async fn a_repeatable_failure_is_tried_again_until_it_clears() {
let attempts = Cell::new(0);
let value = retry(&policy(), &CancellationToken::new(), |attempt| {
attempts.set(attempts.get() + 1);
async move {
if attempt < 3 {
return Err(Failure::conflict("conflict.deadlock", "deadlock found"));
}
Ok(attempt)
}
})
.await
.expect("cleared on the third attempt");
assert_eq!(value, 3);
assert_eq!(attempts.get(), 3);
}
#[tokio::test]
async fn the_last_failure_survives_when_the_attempts_run_out() {
let attempts = Cell::new(0);
let failure = retry(&policy(), &CancellationToken::new(), |_| {
attempts.set(attempts.get() + 1);
async {
Err::<u8, Failure>(Failure::network(
"network.unreachable",
"the server could not be reached",
))
}
})
.await
.expect_err("must fail");
assert_eq!(attempts.get(), 4, "the first attempt plus three repeats");
assert_eq!(failure.code(), "network.unreachable");
}
#[tokio::test]
async fn a_policy_that_never_repeats_asks_exactly_once() {
let attempts = Cell::new(0);
let _ = retry(&Backoff::none(), &CancellationToken::new(), |_| {
attempts.set(attempts.get() + 1);
async { Err::<u8, Failure>(Failure::network("network.unreachable", "lost")) }
})
.await;
assert_eq!(attempts.get(), 1);
}
#[tokio::test]
async fn a_stopped_invocation_never_finishes_its_wait() {
let token = CancellationToken::new();
let slow = Backoff::new(
5,
Duration::from_secs(60),
Duration::from_secs(60),
Duration::from_secs(600),
);
token.cancel();
let failure = retry(&slow, &token, |_| async {
Err::<u8, Failure>(Failure::network("network.unreachable", "lost"))
})
.await
.expect_err("must stop");
assert_eq!(failure.category(), crate::error::Category::Interrupted);
}
}