minerva 0.2.0

Causal ordering for distributed systems
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

use super::jitter::jitter_spins;
use super::{Backoff, spin};

/// An exponential backoff: the spin count doubles each attempt, capped at a
/// maximum, plus optional jitter.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ExponentialBackoff {
    base_spins: u32,
    max_spins: u32,
    #[cfg(feature = "rand")]
    jitter: Option<u32>, // max extra spins
    #[cfg(not(feature = "rand"))]
    jitter: Option<(u64, u32)>, // (LCG seed, max extra spins)
}

impl ExponentialBackoff {
    #[cfg(feature = "rand")]
    /// A backoff whose spin count starts at `base_spins`, doubles each attempt, and
    /// caps at `max_spins`, plus a random extra count in `[0, jitter)` (thread
    /// RNG entropy). With the `rand` feature off, this signature takes
    /// `Option<(seed, max)>` instead; see
    /// [`BackoffStrategy`](super::BackoffStrategy) for the
    /// feature-unification hazard.
    ///
    /// Spin counts are relative contention knobs, not wall-clock durations.
    #[must_use]
    pub const fn new(base_spins: u32, max_spins: u32, jitter: Option<u32>) -> Self {
        Self {
            base_spins,
            max_spins,
            jitter,
        }
    }

    #[cfg(not(feature = "rand"))]
    /// A backoff whose spin count starts at `base_spins`, doubles each attempt, and
    /// caps at `max_spins`. `jitter` is an optional `(seed, max)` for the
    /// in-crate LCG, adding a derived extra count in `[0, max)`. With the
    /// `rand` feature on, this signature takes `Option<u32>` instead; see
    /// [`BackoffStrategy`](super::BackoffStrategy) for the
    /// feature-unification hazard.
    ///
    /// Spin counts are relative contention knobs, not wall-clock durations.
    #[must_use]
    pub const fn new(base_spins: u32, max_spins: u32, jitter: Option<(u64, u32)>) -> Self {
        Self {
            base_spins,
            max_spins,
            jitter,
        }
    }

    /// Spin count for `attempt`: `base_spins << (attempt - 1)`, saturating, capped
    /// at `max_spins`. The shift is bounded at 31 because attempts are unbounded
    /// under infallible generation and `1u32 << 32` would overflow; past the cap the
    /// count pins at `max_spins`.
    pub(in crate::kairos) const fn spins(&self, attempt: u32) -> u32 {
        let shift = attempt.saturating_sub(1);
        let shift = if shift > 31 { 31 } else { shift };
        let scaled = self.base_spins.saturating_mul(1u32 << shift);
        if scaled < self.max_spins {
            scaled
        } else {
            self.max_spins
        }
    }
}

impl Backoff for ExponentialBackoff {
    fn backoff(&self, attempt: u32) {
        spin(
            self.spins(attempt)
                .saturating_add(jitter_spins(self.jitter, attempt)),
        );
    }
}