use serde::{Deserialize, Serialize};
#[cfg(feature = "wincode")]
use wincode_derive::{SchemaRead, SchemaWrite};
use super::EvictionPolicy;
use crate::types::{BasisPoints, EpochNumber, RoundNumber};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Fold {
Ignored,
Advanced,
Rebuild,
}
#[derive(Clone, Copy, Debug, Default, Deserialize, Eq, PartialEq, Serialize)]
#[cfg_attr(feature = "wincode", derive(SchemaRead, SchemaWrite))]
pub struct PeerRecord {
pub opportunities: u64,
pub successes: u64,
pub consecutive_misses: u64,
pub last_epoch: EpochNumber,
pub last_round: RoundNumber,
pub started: bool,
pub recent: u64,
pub recent_len: u64,
}
pub const RECENT_ROUNDS: u32 = u64::BITS;
impl PeerRecord {
pub fn record(
&mut self,
epoch: EpochNumber,
round: RoundNumber,
proved: bool,
prior: Option<bool>,
) -> Fold {
match prior {
Some(true) => return Fold::Ignored,
Some(false) if !proved => return Fold::Ignored,
Some(false) => {
self.successes += 1;
return Fold::Rebuild;
}
None => {}
}
self.opportunities += 1;
if proved {
self.successes += 1;
}
if self.started && (epoch, round) <= (self.last_epoch, self.last_round) {
return Fold::Rebuild;
}
if proved {
self.consecutive_misses = 0;
} else {
self.consecutive_misses += 1;
}
self.recent = (self.recent << 1) | u64::from(proved);
self.recent_len = (self.recent_len + 1).min(RECENT_ROUNDS as u64);
self.last_epoch = epoch;
self.last_round = round;
self.started = true;
Fold::Advanced
}
pub fn rebuild_recency(
&mut self,
rounds: &[(EpochNumber, RoundNumber, bool)],
preceding_misses: u64,
) {
let trailing_misses = rounds
.iter()
.rev()
.take_while(|(_, _, proved)| !proved)
.count() as u64;
self.consecutive_misses = trailing_misses
+ if trailing_misses == rounds.len() as u64 {
preceding_misses
} else {
0
};
self.recent = 0;
let tail = rounds.len().saturating_sub(RECENT_ROUNDS as usize);
for (_, _, proved) in &rounds[tail..] {
self.recent = (self.recent << 1) | u64::from(*proved);
}
self.recent_len = (rounds.len() - tail) as u64;
if let Some((epoch, round, _)) = rounds.last() {
self.last_epoch = *epoch;
self.last_round = *round;
self.started = true;
}
}
pub fn success_rate(&self) -> BasisPoints {
if self.opportunities == 0 {
return BasisPoints(BasisPoints::MAX);
}
BasisPoints(self.successes * BasisPoints::MAX / self.opportunities)
}
pub fn run_fires(&self, policy: &EvictionPolicy) -> bool {
self.consecutive_misses >= policy.max_consecutive_misses
}
pub fn rate_fires(&self, policy: &EvictionPolicy) -> bool {
self.opportunities >= policy.min_opportunities
&& self.success_rate() < policy.minimum_success_rate_bps
}
pub fn eviction_fires(&self, policy: &EvictionPolicy) -> bool {
self.run_fires(policy) || self.rate_fires(policy)
}
pub fn recent_rounds(&self) -> Vec<bool> {
let judged = self.recent_len.min(RECENT_ROUNDS as u64) as u32;
(0..judged)
.rev()
.map(|bit| self.recent & (1 << bit) != 0)
.collect()
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum NodeVerdict {
Unproven,
RateFailed,
RunFailed,
Healthy,
}
pub fn node_verdict<'a>(
records: impl IntoIterator<Item = &'a PeerRecord>,
policy: &EvictionPolicy,
) -> NodeVerdict {
let mut judged = 0;
let mut rate = false;
let mut run = false;
for record in records {
judged = judged.max(record.opportunities);
rate |= record.rate_fires(policy);
run |= record.run_fires(policy);
}
if rate {
NodeVerdict::RateFailed
} else if run {
NodeVerdict::RunFailed
} else if judged < policy.min_opportunities {
NodeVerdict::Unproven
} else {
NodeVerdict::Healthy
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct NodeTally {
pub spools: u64,
pub opportunities: u64,
pub successes: u64,
pub worst_run: u64,
}
impl NodeTally {
pub fn rate(&self) -> BasisPoints {
if self.opportunities == 0 {
return BasisPoints(BasisPoints::MAX);
}
BasisPoints(self.successes * BasisPoints::MAX / self.opportunities)
}
}
pub fn node_tally<'a>(records: impl IntoIterator<Item = &'a PeerRecord>) -> NodeTally {
let mut tally = NodeTally::default();
for record in records {
tally.spools += 1;
tally.opportunities += record.opportunities;
tally.successes += record.successes;
tally.worst_run = tally.worst_run.max(record.consecutive_misses);
}
tally
}
#[cfg(test)]
mod tests {
use super::*;
const POLICY: EvictionPolicy = EvictionPolicy {
max_consecutive_misses: 20,
min_opportunities: 4,
minimum_success_rate_bps: BasisPoints(5_000),
};
#[test]
fn policies_are_independent_and_do_not_need_initialization() {
let record = spool(10, 7, 3);
let sensitive = EvictionPolicy {
max_consecutive_misses: 3,
..POLICY
};
for _ in 0..3 {
assert_eq!(node_verdict(&[record], &POLICY), NodeVerdict::Healthy);
assert_eq!(node_verdict(&[record], &sensitive), NodeVerdict::RunFailed);
}
}
#[test]
fn minimum_rate_sample_does_not_override_the_consecutive_miss_rule() {
let policy = EvictionPolicy {
max_consecutive_misses: 30,
min_opportunities: 60,
..POLICY
};
let record = spool(30, 0, 30);
assert!(record.eviction_fires(&policy));
assert!(!record.rate_fires(&policy));
assert_eq!(node_verdict(&[record], &policy), NodeVerdict::RunFailed);
}
#[test]
fn rate_rule_waits_for_its_configured_evidence() {
let policy = EvictionPolicy {
min_opportunities: 60,
..POLICY
};
assert!(!spool(59, 10, 1).rate_fires(&policy));
assert!(spool(60, 10, 1).rate_fires(&policy));
assert!(!spool(60, 30, 1).rate_fires(&policy));
}
fn spool(opportunities: u64, successes: u64, run: u64) -> PeerRecord {
PeerRecord {
opportunities,
successes,
consecutive_misses: run,
..PeerRecord::default()
}
}
#[test]
fn one_dead_spool_fails_the_node() {
let healthy = spool(20, 20, 0);
let dead = spool(20, 0, POLICY.max_consecutive_misses);
let records = [healthy, healthy, healthy, healthy, dead];
assert_eq!(node_verdict(&records, &POLICY), NodeVerdict::RateFailed);
let tally = node_tally(&records);
assert_eq!(tally.spools, 5);
assert!(tally.rate() > POLICY.minimum_success_rate_bps);
assert_eq!(tally.worst_run, POLICY.max_consecutive_misses);
}
#[test]
fn rate_outranks_run() {
let both = spool(POLICY.min_opportunities, 0, POLICY.max_consecutive_misses);
assert!(both.rate_fires(&POLICY) && both.run_fires(&POLICY));
assert_eq!(node_verdict(&[both], &POLICY), NodeVerdict::RateFailed);
}
#[test]
fn too_few_rounds_is_unproven() {
let short = spool(
POLICY.min_opportunities - 1,
0,
POLICY.min_opportunities - 1,
);
assert!(
!short.rate_fires(&POLICY),
"too few rounds for the rate arm"
);
assert!(!short.run_fires(&POLICY), "too few rounds to be a run");
assert_eq!(node_verdict(&[short], &POLICY), NodeVerdict::Unproven);
}
#[test]
fn a_long_run_fails_the_node() {
let stalled = spool(
POLICY.min_opportunities + 4,
POLICY.min_opportunities + 1,
POLICY.max_consecutive_misses,
);
assert!(!stalled.rate_fires(&POLICY));
assert_eq!(node_verdict(&[stalled], &POLICY), NodeVerdict::RunFailed);
}
#[test]
fn no_records_is_unproven() {
assert_eq!(node_verdict(&[], &POLICY), NodeVerdict::Unproven);
assert_eq!(node_tally(&[]).rate(), BasisPoints(BasisPoints::MAX));
}
#[test]
fn every_spool_answering_is_healthy() {
let good = spool(
POLICY.min_opportunities + 2,
POLICY.min_opportunities + 2,
0,
);
assert_eq!(
node_verdict(&[good, good, good], &POLICY),
NodeVerdict::Healthy
);
}
fn at(round: u64) -> (EpochNumber, RoundNumber) {
(EpochNumber(1), RoundNumber(round))
}
#[test]
fn fresh_record() {
let record = PeerRecord::default();
assert!(!record.eviction_fires(&POLICY));
assert_eq!(record.success_rate(), BasisPoints(BasisPoints::MAX));
}
#[test]
fn always_answers() {
let mut record = PeerRecord::default();
for round in 0..500 {
let (epoch, round) = at(round);
assert_eq!(record.record(epoch, round, true, None), Fold::Advanced);
}
assert_eq!(record.success_rate(), BasisPoints(BasisPoints::MAX));
assert!(!record.eviction_fires(&POLICY));
}
#[test]
fn run_of_misses() {
let mut record = PeerRecord::default();
for round in 0..100 {
record.record(EpochNumber(1), RoundNumber(round), true, None);
}
for round in 100..100 + POLICY.max_consecutive_misses {
record.record(EpochNumber(1), RoundNumber(round), false, None);
}
assert!(record.success_rate() > POLICY.minimum_success_rate_bps);
assert!(record.eviction_fires(&POLICY));
}
#[test]
fn single_miss() {
let mut record = PeerRecord::default();
for round in 0..10 {
record.record(EpochNumber(1), RoundNumber(round), round != 5, None);
}
assert!(!record.eviction_fires(&POLICY));
}
#[test]
fn erratic_peer() {
let mut record = PeerRecord::default();
for round in 0..40 {
record.record(EpochNumber(1), RoundNumber(round), round % 2 == 0, None);
}
assert_eq!(record.consecutive_misses, 1);
assert_eq!(record.success_rate(), BasisPoints(5_000));
assert!(!record.eviction_fires(&POLICY));
record.record(EpochNumber(1), RoundNumber(40), false, None);
assert!(record.success_rate() < POLICY.minimum_success_rate_bps);
assert!(record.eviction_fires(&POLICY));
}
#[test]
fn recent_strip() {
let mut record = PeerRecord::default();
assert!(record.recent_rounds().is_empty());
for (round, proved) in [true, true, false, true].into_iter().enumerate() {
record.record(EpochNumber(1), RoundNumber(round as u64), proved, None);
}
assert_eq!(record.recent_rounds(), vec![true, true, false, true]);
}
#[test]
fn strip_ages_out() {
let mut record = PeerRecord::default();
for round in 0..(RECENT_ROUNDS as u64 + 10) {
record.record(EpochNumber(1), RoundNumber(round), round != 0, None);
}
let strip = record.recent_rounds();
assert_eq!(strip.len(), RECENT_ROUNDS as usize);
assert!(
strip.iter().all(|proved| *proved),
"an aged-out miss lingered"
);
assert_eq!(record.opportunities, RECENT_ROUNDS as u64 + 10);
}
#[test]
fn strip_survives_pruned_rounds() {
let mut record = PeerRecord::default();
for round in 0..5 {
record.record(EpochNumber(1), RoundNumber(round), true, None);
}
let fold = record.record(EpochNumber(1), RoundNumber(4), true, None);
assert_eq!(fold, Fold::Rebuild);
record.rebuild_recency(&[at_round(2, 0, true), at_round(2, 1, true)], 0);
assert_eq!(record.opportunities, 6);
assert_eq!(record.recent_rounds(), vec![true, true]);
}
fn at_round(epoch: u64, round: u64, proved: bool) -> (EpochNumber, RoundNumber, bool) {
(EpochNumber(epoch), RoundNumber(round), proved)
}
fn run(pattern: &[bool], rounds: u64) -> PeerRecord {
let mut record = PeerRecord::default();
for round in 0..rounds {
let answered = pattern[(round as usize) % pattern.len()];
record.record(EpochNumber(1), RoundNumber(round), answered, None);
}
record
}
#[test]
fn stops_partway() {
let mut record = run(&[true], 40);
assert!(!record.eviction_fires(&POLICY));
let last = 40 + POLICY.max_consecutive_misses - 1;
for round in 40..last {
record.record(EpochNumber(1), RoundNumber(round), false, None);
assert!(
!record.eviction_fires(&POLICY),
"fired after {} misses",
round - 39
);
}
record.record(EpochNumber(1), RoundNumber(last), false, None);
assert!(
record.eviction_fires(&POLICY),
"a full run of misses should fire"
);
}
#[test]
fn flapping_survives() {
let record = run(&[true, false], 400);
assert_eq!(record.consecutive_misses, 1);
assert_eq!(record.success_rate(), POLICY.minimum_success_rate_bps);
assert!(!record.eviction_fires(&POLICY));
}
#[test]
fn arms_apart() {
let mut stopped = run(&[true], 40);
for round in 40..40 + POLICY.max_consecutive_misses {
stopped.record(EpochNumber(1), RoundNumber(round), false, None);
}
assert!(stopped.run_fires(&POLICY));
assert!(
!stopped.rate_fires(&POLICY),
"a stopped peer's lifetime rate is still good"
);
let erratic = run(&[true, false, false], 60);
assert!(
!erratic.run_fires(&POLICY),
"one answer in three never reaches a full run"
);
assert!(erratic.rate_fires(&POLICY));
}
#[test]
fn under_half() {
let record = run(&[true, false, false], 60);
assert!(record.consecutive_misses < POLICY.max_consecutive_misses);
assert!(record.success_rate() < POLICY.minimum_success_rate_bps);
assert!(record.eviction_fires(&POLICY));
}
#[test]
fn recovers() {
let mut record = run(&[true], 20);
record.record(EpochNumber(1), RoundNumber(20), false, None);
record.record(EpochNumber(1), RoundNumber(21), false, None);
record.record(EpochNumber(1), RoundNumber(22), true, None);
assert_eq!(record.consecutive_misses, 0);
assert!(!record.eviction_fires(&POLICY));
}
#[test]
fn resets_the_run() {
let record = run(&[true, false, false], 300);
assert!(record.eviction_fires(&POLICY));
}
#[test]
fn replayed_round() {
let mut record = PeerRecord::default();
assert_eq!(
record.record(EpochNumber(1), RoundNumber(7), false, None),
Fold::Advanced
);
assert_eq!(
record.record(EpochNumber(1), RoundNumber(7), false, Some(false)),
Fold::Ignored
);
assert_eq!(record.opportunities, 1);
assert_eq!(record.consecutive_misses, 1);
}
#[test]
fn success_stands() {
let mut record = PeerRecord::default();
record.record(EpochNumber(1), RoundNumber(7), true, None);
assert_eq!(
record.record(EpochNumber(1), RoundNumber(7), false, Some(true)),
Fold::Ignored
);
assert_eq!(record.opportunities, 1);
assert_eq!(record.successes, 1);
assert_eq!(record.consecutive_misses, 0);
}
#[test]
fn late_certificate() {
let mut record = PeerRecord::default();
record.record(EpochNumber(1), RoundNumber(7), false, None);
record.record(EpochNumber(1), RoundNumber(8), false, None);
assert_eq!(record.consecutive_misses, 2);
assert_eq!(
record.record(EpochNumber(1), RoundNumber(7), true, Some(false)),
Fold::Rebuild
);
record.rebuild_recency(
&[
(EpochNumber(1), RoundNumber(7), true),
(EpochNumber(1), RoundNumber(8), false),
],
0,
);
assert_eq!(record.opportunities, 2);
assert_eq!(record.successes, 1);
assert_eq!(record.consecutive_misses, 1);
assert_eq!(record.recent_rounds(), vec![true, false]);
}
#[test]
fn late_miss() {
let mut record = PeerRecord::default();
record.record(EpochNumber(1), RoundNumber(8), true, None);
assert_eq!(
record.record(EpochNumber(1), RoundNumber(7), false, None),
Fold::Rebuild
);
record.rebuild_recency(
&[
(EpochNumber(1), RoundNumber(7), false),
(EpochNumber(1), RoundNumber(8), true),
],
0,
);
assert_eq!(record.opportunities, 2);
assert_eq!(record.successes, 1);
assert_eq!(
record.consecutive_misses, 0,
"a later success already broke the run"
);
assert_eq!(record.recent_rounds(), vec![false, true]);
}
#[test]
fn rebuild_matches() {
let rounds: Vec<(EpochNumber, RoundNumber, bool)> = (0..100)
.map(|round| (EpochNumber(1), RoundNumber(round), round % 3 != 0))
.collect();
let mut folded = PeerRecord::default();
for (epoch, round, proved) in &rounds {
folded.record(*epoch, *round, *proved, None);
}
let mut rebuilt = folded;
rebuilt.rebuild_recency(&rounds, 0);
assert_eq!(rebuilt, folded);
}
#[test]
fn across_epochs() {
let mut record = PeerRecord::default();
record.record(EpochNumber(1), RoundNumber(9), false, None);
for round in 0..POLICY.max_consecutive_misses - 1 {
record.record(EpochNumber(2), RoundNumber(round), false, None);
}
assert_eq!(record.consecutive_misses, POLICY.max_consecutive_misses);
assert!(record.eviction_fires(&POLICY));
}
}