use alloc::collections::BTreeMap;
use alloc::vec::Vec;
use super::Replica;
use crate::batch::{Entry, Item, Kind};
use crate::codec::Body;
use crate::types::{NodeId, ProposalId, Slot, Timestamp};
pub(super) const PROBE_INTERVAL: u64 = 1_000_000_000;
pub(super) const FRESH_FOR: u64 = 4 * PROBE_INTERVAL;
const LATENCY_SAMPLES: usize = 1024;
pub(super) const ACTIVE_FOR: u64 = 4 * PROBE_INTERVAL;
#[derive(Clone, Debug, Default)]
#[cfg_attr(feature = "model", derive(Hash))]
pub(super) struct Placement {
pub(super) rtt: BTreeMap<NodeId, (u64, Timestamp)>,
pub(super) awaiting: BTreeMap<NodeId, Vec<u64>>,
pub(super) tables: BTreeMap<NodeId, (Vec<(NodeId, u64)>, Timestamp)>,
pub(super) latencies: Vec<u64>,
pub(super) latency_seen: u64,
pub(super) latency_stride: u64,
pub(super) observed: BTreeMap<NodeId, (u64, Timestamp)>,
pub(super) led: BTreeMap<NodeId, Led>,
pub(super) tail: Option<u64>,
pub(super) writes: BTreeMap<NodeId, u64>,
pub(super) rates: BTreeMap<NodeId, u64>,
pub(super) last_write: Option<Timestamp>,
pub(super) next_probe: Option<Timestamp>,
pub(super) last_round: Option<Timestamp>,
pub(super) target: Option<Target>,
pub(super) changed_at: Option<Timestamp>,
pub(super) led_since: Timestamp,
pub(super) excluded: BTreeMap<NodeId, Exclusion>,
pub(super) moving: Option<ProposalId>,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
pub(super) struct Led {
pub(super) count: u64,
pub(super) sum: u128,
pub(super) sum_sq: u128,
pub(super) since: Timestamp,
pub(super) at: Timestamp,
}
impl Led {
pub(super) fn add(&mut self, us: u64, at: Timestamp) {
if self.count == 0 {
self.since = at;
}
self.count += 1;
self.sum = self.sum.saturating_add(u128::from(us));
self.sum_sq = self.sum_sq.saturating_add(u128::from(us) * u128::from(us));
self.at = at;
}
pub(super) fn mean(&self) -> u128 {
self.sum / u128::from(self.count.max(1))
}
fn var_of_mean(&self) -> u128 {
let n = u128::from(self.count.max(1));
self.sum_sq.saturating_sub(self.sum * self.sum / n) / n / n
}
pub(super) fn worse_than(&self, other: &Led) -> bool {
let (a, b) = (self.mean(), other.mean());
a > b && (a - b) * (a - b) > 9 * (self.var_of_mean() + other.var_of_mean())
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
pub(super) struct Target {
pub(super) member: NodeId,
pub(super) leader: NodeId,
pub(super) since: Timestamp,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
pub(super) struct Exclusion {
pub(super) until: Timestamp,
pub(super) factor: u64,
}
pub(super) fn fresh(at: Timestamp, now: Timestamp) -> bool {
now.0.saturating_sub(at.0) <= FRESH_FOR
}
impl Replica {
pub(super) fn count_writes(&mut self, items: &[Item]) {
if !self.cfg.placement {
return;
}
let p = &mut self.placement;
let mut any = false;
for Item { entry: Entry { origin, .. }, kind } in items {
if *kind == Kind::App {
*p.writes.entry(*origin).or_default() += 1;
any = true;
}
}
if any {
p.last_write = Some(self.now);
p.next_probe.get_or_insert(self.now);
}
}
pub(super) fn note_commit_latency(&mut self, ns: u64) {
if !self.cfg.placement {
return;
}
let p = &mut self.placement;
let stride = p.latency_stride.max(1);
p.latency_seen += 1;
if !(p.latency_seen - 1).is_multiple_of(stride) {
return;
}
p.latencies.push(ns);
if p.latencies.len() >= LATENCY_SAMPLES {
let mut i = 0;
p.latencies.retain(|_| {
i += 1;
i % 2 == 1
});
p.latency_stride = stride * 2;
}
}
pub(super) fn fresh_rtt(&self, member: NodeId) -> Option<u64> {
self.placement.rtt.get(&member).filter(|(_, at)| fresh(*at, self.now)).map(|(rtt, _)| *rtt)
}
pub(super) fn fire_probe(&mut self) {
let now = self.now;
if !self.placement.next_probe.is_some_and(|t| t <= now) {
return;
}
let active = self.placement.last_write.is_some_and(|t| now.0.saturating_sub(t.0) <= ACTIVE_FOR);
if !active {
self.placement.next_probe = None;
return;
}
self.placement.next_probe = Some(now.after(PROBE_INTERVAL));
let mut l = core::mem::take(&mut self.placement.latencies);
(self.placement.latency_seen, self.placement.latency_stride) = (0, 1);
self.placement.tail = (!l.is_empty()).then(|| {
l.sort_unstable();
l[(l.len() - 1) * 9 / 10]
});
self.close_round();
let members = self.schedule.members(Slot(self.committed)).to_vec();
self.placement.rtt.retain(|n, _| members.contains(n));
self.placement.tables.retain(|n, _| members.contains(n));
self.placement.observed.retain(|n, _| members.contains(n));
self.placement.awaiting.retain(|n, _| members.contains(n));
if !members.contains(&self.me) {
return;
}
let table: Vec<(NodeId, u64)> =
members.iter().filter_map(|&m| Some((m, self.fresh_rtt(m)?))).collect();
let me = self.me;
for &to in members.iter().filter(|&&m| m != me) {
let sent = self.placement.awaiting.entry(to).or_default();
if sent.len() as u64 >= FRESH_FOR / PROBE_INTERVAL {
sent.remove(0);
}
sent.push(now.0);
let (incarnation, commit) = (self.incarnation, self.placement.tail.unwrap_or(0));
self.send(to, Body::RttProbe { incarnation, sent: now.0, commit, table: table.clone() });
}
self.evaluate_placement();
}
pub(super) fn on_rtt_probe(
&mut self,
from: NodeId,
incarnation: u64,
sent: u64,
commit: u64,
mut table: Vec<(NodeId, u64)>,
) {
if !self.cfg.placement {
return;
}
let members = self.schedule.members(Slot(self.committed));
if !members.contains(&from) {
return;
}
table.retain(|(n, _)| members.contains(n));
self.placement.tables.insert(from, (table, self.now));
if commit > 0 {
self.placement.observed.insert(from, (commit, self.now));
} else {
self.placement.observed.remove(&from);
}
self.send(from, Body::RttReply { incarnation, sent });
}
pub(super) fn on_rtt_reply(&mut self, from: NodeId, incarnation: u64, sent: u64) {
if !self.cfg.placement || incarnation != self.incarnation || sent > self.now.0 {
return;
}
let Some(probes) = self.placement.awaiting.get_mut(&from) else { return };
let Some(i) = probes.iter().position(|&s| s == sent) else { return };
probes.drain(..=i);
let sample = self.now.0 - sent;
let now = self.now;
match self.placement.rtt.get_mut(&from) {
Some((avg, at)) if fresh(*at, now) => {
*avg = *avg - *avg / 8 + sample / 8;
*at = now;
}
_ => {
self.placement.rtt.insert(from, (sample, now));
}
}
}
}