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

#[cfg(feature = "rand")]
use rand::Rng;

/// A minimal MINSTD LCG: the `no_std` jitter source, used when `rand` is off.
///
/// Private and feature-gated: callers pass a raw `u64` seed to a backoff
/// constructor and never hold a generator, and under the `rand` feature the thread
/// RNG supplies jitter so this type is absent entirely.
#[cfg(not(feature = "rand"))]
struct LcgJitter {
    state: u64,
}

#[cfg(not(feature = "rand"))]
impl LcgJitter {
    /// A generator seeded with `seed`, forced non-zero.
    const fn new(seed: u64) -> Self {
        Self { state: seed | 1 }
    }

    // MINSTD parameters: a = 48271, c = 0, m = 2^31 - 1 (a Mersenne prime).
    const fn next(&mut self) -> u64 {
        const M: u64 = (1u64 << 31) - 1;
        self.state = self.state.wrapping_mul(48271) % M;
        self.state
    }

    /// A deterministic jitter in `[0, max_spins)` for this attempt. Folding
    /// `attempt` into the seed varies the value across a thread's retries without
    /// interior mutability, so the shared strategy needs none.
    fn spins(seed: u64, attempt: u32, max_spins: u32) -> u32 {
        if max_spins == 0 {
            return 0;
        }
        let mut lcg = Self::new(seed.wrapping_add(u64::from(attempt)));
        // The modulo lands in [0, max_spins), so the narrowing cast cannot truncate.
        u32::try_from(lcg.next() % u64::from(max_spins)).unwrap_or(0)
    }
}

/// Extra spin iterations of jitter for `attempt`, or `0` when jitter is disabled.
///
/// With `rand` the thread RNG supplies entropy (so `attempt` is unused); without
/// it, a seeded LCG does, folding `attempt` in for per-retry variation.
#[cfg(feature = "rand")]
pub(in crate::kairos::backoff) fn jitter_spins(jitter: Option<u32>, _attempt: u32) -> u32 {
    jitter
        .filter(|&max| max > 0)
        .map_or(0, |max| rand::rng().random_range(0..max))
}

#[cfg(not(feature = "rand"))]
pub(in crate::kairos::backoff) fn jitter_spins(jitter: Option<(u64, u32)>, attempt: u32) -> u32 {
    jitter.map_or(0, |(seed, max)| LcgJitter::spins(seed, attempt, max))
}