use serde::{Deserialize, Serialize};
#[cfg(feature = "wincode")]
use wincode_derive::{SchemaRead, SchemaWrite};
use crate::types::{BasisPoints, EpochNumber, RoundNumber};
pub const MIN_OPPORTUNITIES: u64 = 4;
pub const RATE_FLOOR: BasisPoints = BasisPoints(5_000);
pub const MAX_CONSECUTIVE_MISSES: u64 = 20;
const TEST_RUN_MISSES: u64 = 3;
const TEST_EPOCH_SECS: u64 = 30;
static RUN_MISSES: std::sync::OnceLock<u64> = std::sync::OnceLock::new();
pub fn set_run_threshold(epoch_secs: u64) {
if epoch_secs > 0 {
let _ = RUN_MISSES.set(if epoch_secs <= TEST_EPOCH_SECS {
TEST_RUN_MISSES
} else {
MAX_CONSECUTIVE_MISSES
});
}
}
fn run_threshold() -> u64 {
*RUN_MISSES.get().unwrap_or(&MAX_CONSECUTIVE_MISSES)
}
#[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)]) {
self.consecutive_misses = rounds
.iter()
.rev()
.take_while(|(_, _, proved)| !proved)
.count() as u64;
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) -> bool {
self.consecutive_misses >= run_threshold()
}
pub fn rate_fires(&self) -> bool {
self.opportunities >= MIN_OPPORTUNITIES && self.success_rate() < RATE_FLOOR
}
pub fn eviction_fires(&self) -> bool {
self.run_fires() || self.rate_fires()
}
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>) -> 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();
run |= record.run_fires();
}
if rate {
NodeVerdict::RateFailed
} else if judged < MIN_OPPORTUNITIES {
NodeVerdict::Unproven
} else if run {
NodeVerdict::RunFailed
} 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::*;
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, MAX_CONSECUTIVE_MISSES);
let records = [healthy, healthy, healthy, healthy, dead];
assert_eq!(node_verdict(&records), NodeVerdict::RateFailed);
let tally = node_tally(&records);
assert_eq!(tally.spools, 5);
assert!(tally.rate() > RATE_FLOOR);
assert_eq!(tally.worst_run, MAX_CONSECUTIVE_MISSES);
}
#[test]
fn rate_outranks_run() {
let both = spool(MIN_OPPORTUNITIES, 0, MAX_CONSECUTIVE_MISSES);
assert!(both.rate_fires() && both.run_fires());
assert_eq!(node_verdict(&[both]), NodeVerdict::RateFailed);
}
#[test]
fn too_few_rounds_is_unproven() {
let short = spool(MIN_OPPORTUNITIES - 1, 0, MIN_OPPORTUNITIES - 1);
assert!(!short.rate_fires(), "too few rounds for the rate arm");
assert!(!short.run_fires(), "too few rounds to be a run");
assert_eq!(node_verdict(&[short]), NodeVerdict::Unproven);
}
#[test]
fn a_long_run_fails_the_node() {
let stalled = spool(MIN_OPPORTUNITIES + 4, MIN_OPPORTUNITIES + 1, MAX_CONSECUTIVE_MISSES);
assert!(!stalled.rate_fires());
assert_eq!(node_verdict(&[stalled]), NodeVerdict::RunFailed);
}
#[test]
fn no_records_is_unproven() {
assert_eq!(node_verdict(&[]), NodeVerdict::Unproven);
assert_eq!(node_tally(&[]).rate(), BasisPoints(BasisPoints::MAX));
}
#[test]
fn every_spool_answering_is_healthy() {
let good = spool(MIN_OPPORTUNITIES + 2, MIN_OPPORTUNITIES + 2, 0);
assert_eq!(node_verdict(&[good, good, good]), NodeVerdict::Healthy);
}
fn at(round: u64) -> (EpochNumber, RoundNumber) {
(EpochNumber(1), RoundNumber(round))
}
#[test]
fn fresh_record() {
let record = PeerRecord::default();
assert!(!record.eviction_fires());
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());
}
#[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 + MAX_CONSECUTIVE_MISSES {
record.record(EpochNumber(1), RoundNumber(round), false, None);
}
assert!(record.success_rate() > RATE_FLOOR);
assert!(record.eviction_fires());
}
#[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());
}
#[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());
record.record(EpochNumber(1), RoundNumber(40), false, None);
assert!(record.success_rate() < RATE_FLOOR);
assert!(record.eviction_fires());
}
#[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)]);
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());
let last = 40 + MAX_CONSECUTIVE_MISSES - 1;
for round in 40..last {
record.record(EpochNumber(1), RoundNumber(round), false, None);
assert!(!record.eviction_fires(), "fired after {} misses", round - 39);
}
record.record(EpochNumber(1), RoundNumber(last), false, None);
assert!(record.eviction_fires(), "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(), RATE_FLOOR);
assert!(!record.eviction_fires());
}
#[test]
fn arms_apart() {
let mut stopped = run(&[true], 40);
for round in 40..40 + MAX_CONSECUTIVE_MISSES {
stopped.record(EpochNumber(1), RoundNumber(round), false, None);
}
assert!(stopped.run_fires());
assert!(!stopped.rate_fires(), "a stopped peer's lifetime rate is still good");
let erratic = run(&[true, false, false], 60);
assert!(!erratic.run_fires(), "one answer in three never reaches a full run");
assert!(erratic.rate_fires());
}
#[test]
fn under_half() {
let record = run(&[true, false, false], 60);
assert!(record.consecutive_misses < MAX_CONSECUTIVE_MISSES);
assert!(record.success_rate() < RATE_FLOOR);
assert!(record.eviction_fires());
}
#[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());
}
#[test]
fn resets_the_run() {
let record = run(&[true, false, false], 300);
assert!(record.eviction_fires());
}
#[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),
]);
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),
]);
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);
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..MAX_CONSECUTIVE_MISSES - 1 {
record.record(EpochNumber(2), RoundNumber(round), false, None);
}
assert_eq!(record.consecutive_misses, MAX_CONSECUTIVE_MISSES);
assert!(record.eviction_fires());
}
}