use alloc::collections::{BTreeMap, VecDeque};
use alloc::vec::Vec;
use super::Replica;
use crate::codec::Body;
use crate::types::{NodeId, Slot, Timestamp};
#[derive(Clone, Debug, Default)]
#[cfg_attr(feature = "model", derive(Hash))]
pub(super) struct Watch {
pub(super) suspects: BTreeMap<NodeId, Timestamp>,
pub(super) heard: BTreeMap<NodeId, Timestamp>,
pub(super) committed: BTreeMap<NodeId, u64>,
pub(super) asked: Option<(NodeId, Timestamp)>,
pub(super) forwarded_to: Option<(NodeId, Timestamp)>,
pub(super) reply: BTreeMap<NodeId, u64>,
pub(super) unpersisted: VecDeque<(u64, Timestamp)>,
pub(super) persist: Option<u64>,
pub(super) wrote: Timestamp,
pub(super) decided_elsewhere: Timestamp,
pub(super) resumed: Timestamp,
pub(super) aside: bool,
pub(super) progressed: Timestamp,
pub(super) acked: BTreeMap<NodeId, Timestamp>,
pub(super) ack_due: BTreeMap<NodeId, Timestamp>,
}
impl Replica {
pub(super) fn target(&self) -> NodeId {
let first = self.first_unsuspected();
if first == self.me && self.stepped_aside() { self.next_after_me() } else { first }
}
fn first_unsuspected(&self) -> NodeId {
let order = self.schedule.members(Slot(self.committed));
order
.iter()
.copied()
.find(|n| *n == self.me || !self.watch.suspects.contains_key(n))
.unwrap_or(self.me)
}
fn next_after_me(&self) -> NodeId {
let order = self.schedule.members(Slot(self.committed));
order
.iter()
.copied()
.skip_while(|n| *n != self.me)
.skip(1)
.find(|n| !self.watch.suspects.contains_key(n))
.unwrap_or(self.me)
}
pub(super) fn aside_at(&self) -> Option<Timestamp> {
if !self.cfg.silent_leader_takeover
|| self.first_unsuspected() != self.me
|| self.next_after_me() == self.me
{
return None;
}
let (d, usual) = (self.hedge_delay(), self.watch.persist?);
let (_, oldest) = self.watch.unpersisted.front()?;
if self.watch.decided_elsewhere <= *oldest {
return None;
}
Some(oldest.after(d.saturating_mul(4).min(self.cfg.hedge_max).max(d).max(usual.saturating_mul(4))))
}
pub(super) fn all_stuck_at(&self) -> Option<Timestamp> {
let (d, usual) = (self.hedge_delay(), self.watch.persist?);
let (_, oldest) = self.watch.unpersisted.front()?;
let due = oldest.after(usual.saturating_mul(4));
let idle = (*oldest).max(self.watch.wrote).after(d.max(usual.saturating_mul(4)));
(self.watch.decided_elsewhere <= due).then_some(idle)
}
pub(super) fn stepped_aside(&self) -> bool {
self.aside_at().is_some_and(|t| t <= self.now)
}
pub(super) fn check_aside(&mut self) {
let aside = self.stepped_aside();
if aside == self.watch.aside {
return;
}
self.watch.aside = aside;
if !aside {
return;
}
self.metrics.stepped_aside += 1;
let mut handed = Vec::new();
self.batches.retain(|_, b| {
handed.extend(crate::batch::decode(&b.value).unwrap_or_default());
b.slot.is_some()
});
for e in handed {
let (o, inc, id) = e.key();
if self.dedup.contains(o, inc, id) {
continue;
}
if o == self.me
&& let Some(out) = self.outstanding.get_mut(&id)
{
out.2 = true;
}
self.pending.push_back(e);
}
let relayed = core::mem::take(&mut self.relayed);
self.pending.extend(relayed);
}
pub(super) fn proposes_directly(&self) -> bool {
self.target() == self.me
}
pub(super) fn suspect_target(&mut self) {
let target = self.target();
if target != self.me {
self.watch.suspects.insert(target, self.now);
self.metrics.suspicions += 1;
}
self.watch.asked = None;
for (id, (e, _)) in core::mem::take(&mut self.forwarded).into_iter().rev() {
if let Some(o) = self.outstanding.get_mut(&id) {
o.2 = true;
}
self.metrics.hedged += 1;
self.pending.push_front(e);
}
}
pub(super) fn heard_from(&mut self, from: NodeId) {
self.watch.suspects.remove(&from);
self.watch.heard.insert(from, self.now);
if let Some((to, at)) = self.watch.asked
&& to == from
{
self.watch.asked = None;
let sample = self.now.0.saturating_sub(at.0);
let avg = self.watch.reply.entry(from).or_insert(sample);
*avg = if sample < *avg { *avg - *avg / 8 + sample / 8 } else { sample };
}
}
fn ack_every(&self) -> u64 {
self.cfg.retransmit_interval / 8
}
pub(super) fn ack_forward(&mut self, from: NodeId) {
if self.stepped_aside() {
self.watch.ack_due.remove(&from);
return;
}
let every = self.ack_every();
if let Some(due) = self.watch.acked.get(&from).map(|t| t.after(every))
&& self.now < due
{
self.watch.ack_due.insert(from, due);
return;
}
self.watch.ack_due.remove(&from);
self.watch.acked.insert(from, self.now);
self.send(from, Body::ForwardAck);
}
pub(super) fn forwarded_now(&mut self) {
let target = self.target();
if self.watch.forwarded_to.is_none_or(|(to, _)| to != target) {
self.watch.forwarded_to = Some((target, self.now));
}
if self.watch.asked.is_none_or(|(to, _)| to != target) {
self.watch.asked = Some((target, self.now));
}
}
pub(super) fn silence_wait(&self, node: NodeId) -> Option<u64> {
if !self.cfg.silent_leader_takeover {
return None;
}
let (latency, reply) = (self.commit_latency?, *self.watch.reply.get(&node)?);
let answer = reply.saturating_mul(2).max(reply.saturating_add(self.ack_every()));
let sigma = latency.max(answer).max(self.cfg.hedge_min);
(sigma < self.hedge_delay()).then_some(sigma)
}
fn silent_since(&self, node: NodeId, t: Timestamp) -> bool {
self.watch.heard.get(&node).is_none_or(|h| *h <= t)
}
pub(super) fn silent_at(&self, at: Timestamp) -> Option<Timestamp> {
let target = self.target();
let (to, since) = self.watch.forwarded_to?;
if to != target {
return None;
}
let at = at.max(since);
let sigma = self.silence_wait(target)?;
self.silent_since(target, at).then(|| at.after(sigma))
}
pub(super) fn late_at(&self, at: Timestamp) -> Option<Timestamp> {
let d = self.hedge_delay();
let busy = d.saturating_mul(4).min(self.cfg.hedge_max).max(d);
let late = at.max(self.watch.resumed).after(if self.watch.progressed > at { busy } else { d });
let held = !self.watch.aside && self.all_stuck_at().is_some_and(|s| s <= late.min(self.now));
(!held).then_some(late)
}
pub(super) fn hedge_at(&self, at: Timestamp) -> Option<Timestamp> {
let (late, silent) = (self.late_at(at), self.silent_at(at));
late.into_iter().chain(silent).min()
}
pub(super) fn takeover_at(&self, slot: Slot, seen: Timestamp) -> Timestamp {
let position = self.schedule.position(self.me, slot);
let leader = self.schedule.leader(slot);
let usual = seen.after((position + 1).saturating_mul(self.hedge_delay()));
match self.silence_wait(leader) {
Some(sigma) if leader != self.me => {
let silent = self.watch.heard.get(&leader).map_or(seen, |h| (*h).max(seen)).after(sigma);
seen.after(position.max(1).saturating_mul(sigma)).max(silent).min(usual)
}
_ => usual,
}
}
}