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

mod constant;
mod exponential;
mod jitter;
mod model;

pub use constant::ConstantBackoff;
pub use exponential::ExponentialBackoff;
pub use model::ModelBasedBackoff;

/// Strategy for spacing out contended compare-and-swap retries.
pub trait Backoff: Send + Sync + core::fmt::Debug {
    /// Spins briefly before the next retry. `attempt` is 1-based.
    ///
    /// Generation is infallible and retries until the CAS commits, so this never
    /// signals "give up"; it only spaces out the loser of a CAS race. The currency
    /// is spin-loop iterations, not wall-clock time: the `no_std` core has no clock
    /// to measure a delay against, and reusing the stamp
    /// [`TimeSource`](crate::kairos::TimeSource) would
    /// conflate advancing logical time with measuring a wait. A strategy wanting
    /// real wall-time backoff (meaningful only with an OS clock) must read that
    /// clock itself; this seam stays time-free.
    ///
    /// The trait is implementable, but
    /// [`ClockConfig`](crate::kairos::ClockConfig) accepts only the closed
    /// [`BackoffStrategy`] set, so an external implementation cannot be
    /// installed in a clock today.
    fn backoff(&self, attempt: u32);
}

/// Spins `count` times as a pure contention-reduction hint.
///
/// The lock-free loop is correct with no backoff at all; spinning only lowers the
/// odds that the losers of a CAS race re-collide. Iterations, not nanoseconds, are
/// the honest unit on a clockless core.
fn spin(count: u32) {
    for _ in 0..count {
        core::hint::spin_loop();
    }
}

/// Closed set of built-in backoff strategies.
///
/// The jitter parameter of [`ConstantBackoff::new`] and
/// [`ExponentialBackoff::new`] is feature-dependent: `Option<u32>` with
/// `rand`, `Option<(seed, max)>` without. Feature unification can therefore
/// change those signatures under a `default-features = false` consumer. Pin
/// the feature set, or use
/// [`ClockConfig::default`](crate::kairos::ClockConfig).
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum BackoffStrategy {
    /// A backoff strategy using a constant delay with optional jitter.
    Constant(ConstantBackoff),
    /// A backoff strategy using an exponential delay with optional jitter.
    Exponential(ExponentialBackoff),
    /// A backoff strategy using a precomputed array of delays.
    ModelBased(ModelBasedBackoff),
}

impl Backoff for BackoffStrategy {
    fn backoff(&self, attempt: u32) {
        match self {
            Self::Constant(b) => b.backoff(attempt),
            Self::Exponential(b) => b.backoff(attempt),
            Self::ModelBased(b) => b.backoff(attempt),
        }
    }
}