use alloc::vec::Vec;
use super::Replica;
use super::placement::{Exclusion, Led, PROBE_INTERVAL, Target, fresh};
use crate::batch::{self, Kind};
use crate::types::{NodeId, Slot};
const MIN_ROUNDS: u64 = 10;
const STALE_HOLDS: u64 = 8;
const TIE: u128 = 11;
const TIE_SLACK: u128 = 5_000_000;
pub(super) const WRITE_FLOOR: u64 = 8;
impl Replica {
pub(super) fn close_round(&mut self) {
let members = self.applied_schedule.members(Slot(self.emitted)).to_vec();
let p = &mut self.placement;
let writes = core::mem::take(&mut p.writes);
for origin in writes.keys() {
p.rates.entry(*origin).or_default();
}
p.rates.retain(|origin, rate| {
*rate = match writes.get(origin).copied().unwrap_or(0) {
0 => *rate - rate.div_ceil(8),
n => *rate - *rate / 8 + n,
};
*rate > 0 && members.contains(origin)
});
if self.now.0.saturating_sub(p.led_since.0) >= self.cfg.placement_hold {
p.excluded.remove(&members[0]);
}
p.excluded.retain(|n, _| members.contains(n));
p.led.retain(|n, _| members.contains(n));
self.sample_leader(&members);
}
fn sample_leader(&mut self, members: &[NodeId]) {
let (now, leader) = (self.now, members[0]);
if now.0.saturating_sub(self.placement.led_since.0) < 2 * PROBE_INTERVAL {
return;
}
let (mut seen, mut weight, mut total) = (0u128, 0u128, 0u128);
for (&origin, &rate) in self.placement.rates.iter().filter(|(o, _)| members.contains(o)) {
let rate = u128::from(rate);
total += rate;
let tail = if origin == self.me {
self.placement.tail
} else {
self.placement.observed.get(&origin).filter(|(_, at)| fresh(*at, now)).map(|(t, _)| *t)
};
if let Some(tail) = tail {
seen += rate * u128::from(tail);
weight += rate;
}
}
if weight == 0 || 2 * weight < total {
return;
}
let us = u64::try_from(seen / weight / 1_000).unwrap_or(u64::MAX);
self.placement.led.entry(leader).or_default().add(us, now);
}
fn explore(&mut self, order: &[NodeId], costs: &[Option<u128>]) {
let now = self.now;
let p = &self.placement;
let hold = self.cfg.placement_hold;
let sustain = self.cfg.placement_sustain;
let whole = |l: &Led| {
l.count >= MIN_ROUNDS && l.at.0.saturating_sub(l.since.0) + 2 * PROBE_INTERVAL >= sustain
};
let Some(mine) = p.led.get(&self.me).copied().filter(whole) else { return };
let Some(current) = costs[0] else { return };
if now.0.saturating_sub(p.led_since.0) < sustain {
return;
}
let writes: u128 = p.rates.values().map(|&r| u128::from(r)).sum();
let alike = |c: u128| c.saturating_mul(10) <= current.saturating_mul(TIE) + writes * TIE_SLACK * 10;
let demoted =
|n: NodeId| p.excluded.get(&n).is_some_and(|e| e.until.after(hold.saturating_mul(4)) > now);
let measured = |n: NodeId| {
p.led
.get(&n)
.copied()
.filter(|l| whole(l) && now.0.saturating_sub(l.at.0) < hold.saturating_mul(STALE_HOLDS))
};
let tied: Vec<usize> =
(1..order.len()).filter(|&i| costs[i].is_some_and(alike) && !demoted(order[i])).collect();
if let Some(&i) =
tied.iter().filter(|&&i| measured(order[i]).is_none()).min_by_key(|&&i| (costs[i], i))
{
self.move_lead(order[i], order, costs);
return;
}
let held = p.changed_at.is_some_and(|t| now.0.saturating_sub(t.0) < hold);
let best = tied
.iter()
.filter_map(|&i| measured(order[i]).map(|l| (i, l)))
.min_by_key(|(i, l)| (l.mean(), *i));
if let Some((i, l)) = best
&& !held
&& mine.worse_than(&l)
&& l.mean().saturating_mul(TIE) < mine.mean().saturating_mul(10)
{
self.move_lead(order[i], order, costs);
}
}
fn quorum_rtt(&self, c: NodeId, members: &[NodeId]) -> Option<u64> {
let mut rtts: Vec<u64> = members.iter().filter_map(|&m| self.rtt_between(c, m)).collect();
let majority = members.len() / 2 + 1;
if rtts.len() < majority {
return None;
}
rtts.sort_unstable();
Some(rtts[majority - 1])
}
pub(super) fn note_applied(&mut self, applied: Slot) {
let next = Slot(applied.0 + 1);
let (old, new) = (self.applied_schedule.leader(applied), self.applied_schedule.leader(next));
if self.applied_schedule.members(applied) == self.applied_schedule.members(next) {
return;
}
let now = self.now;
let p = &mut self.placement;
p.changed_at = Some(now);
if new == old {
return;
}
p.led_since = now;
p.led.remove(&new);
if self.applied_schedule.epoch().1 != next.0 {
let factor = p.excluded.get(&old).map_or(1, |e| e.factor.saturating_mul(2));
let until = now.after(self.cfg.placement_hold.saturating_mul(factor));
p.excluded.insert(old, Exclusion { until, factor });
}
}
pub(super) fn restart_hold(&mut self) {
self.placement.led_since = self.now;
if self.applied_schedule.generation() > 0 {
self.placement.changed_at = Some(self.now);
self.placement.target = None;
}
}
fn may_move(&self) -> bool {
self.leads_now() && self.may_change()
}
fn may_change(&self) -> bool {
let pending_change = |kind: Kind| kind == Kind::Reconfigure;
self.cfg.placement
&& !self.watch.aside
&& self.schedule.settled(Slot(self.committed))
&& self.placement.moving.is_none()
&& !self.outstanding.values().any(|(_, kind, _)| pending_change(*kind))
&& !self.pending.iter().chain(&self.relayed).any(|i| pending_change(i.kind))
&& !self.batches.values().any(|b| !batch::changes(&b.value).is_empty())
}
fn rtt_between(&self, a: NodeId, b: NodeId) -> Option<u64> {
let row = |from: NodeId, to: NodeId| {
if from == self.me {
return self.fresh_rtt(to);
}
let (table, at) = self.placement.tables.get(&from)?;
fresh(*at, self.now).then(|| table.iter().find(|(n, _)| *n == to).map(|(_, r)| *r))?
};
if a == b { Some(0) } else { row(a, b).or_else(|| row(b, a)) }
}
pub(super) fn placed_order(&self, in_force: &[NodeId], members: &[NodeId]) -> Vec<NodeId> {
let now = self.now;
let mut staying: Vec<(usize, NodeId)> =
in_force.iter().copied().enumerate().filter(|(_, n)| members.contains(n)).collect();
staying.sort_by_key(|&(i, n)| {
let excluded = self.placement.excluded.get(&n).is_some_and(|e| e.until > now);
let cost = self.cost(n, in_force);
(excluded, cost.is_none(), cost, i)
});
let mut order: Vec<NodeId> = staying.into_iter().map(|(_, n)| n).collect();
order.extend(members.iter().copied().filter(|n| !in_force.contains(n)));
order
}
fn cost(&self, c: NodeId, members: &[NodeId]) -> Option<u128> {
let own_table = self.placement.tables.get(&c).is_some_and(|(_, at)| fresh(*at, self.now));
if c != self.me && !own_table {
return None;
}
let (mut sum, mut total) = (0u128, 0u128);
for (&origin, &rate) in self.placement.rates.iter().filter(|(o, _)| members.contains(o)) {
let rtt = self.rtt_between(origin, c)?;
sum = sum.checked_add(u128::from(rate).checked_mul(u128::from(rtt))?)?;
total += u128::from(rate);
}
sum.checked_add(total.checked_mul(u128::from(self.quorum_rtt(c, members)?))?)
}
pub(super) fn evaluate_placement(&mut self) {
let now = self.now;
let last = self.placement.last_round.replace(now);
if last.is_none_or(|t| now.0.saturating_sub(t.0) > 2 * PROBE_INTERVAL) {
self.placement.target = None;
}
let total: u64 = self.placement.rates.values().sum();
if !self.may_move() || total < WRITE_FLOOR {
self.placement.target = None;
return;
}
let order = self.schedule.members(Slot(self.committed)).to_vec();
let leader = order[0];
let costs: Vec<Option<u128>> = order.iter().map(|&c| self.cost(c, &order)).collect();
let Some(current) = costs[0] else {
self.placement.target = None;
return;
};
let slack = u128::from(total) * TIE_SLACK;
let may_lead = |i: usize| {
costs[i].is_some_and(|c| c.saturating_mul(5) <= current.saturating_mul(4) && current - c > slack)
&& !self.placement.excluded.get(&order[i]).is_some_and(|e| e.until > now)
};
let best = (1..order.len()).filter(|&i| may_lead(i)).min_by_key(|&i| (costs[i], i));
let tracked = self.placement.target.filter(|t| {
t.leader == leader && order.iter().position(|&n| n == t.member).is_some_and(may_lead)
});
let target = tracked.or_else(|| Some(Target { member: order[best?], leader, since: now }));
self.placement.target = target;
let Some(target) = target else {
self.explore(&order, &costs);
return;
};
let held =
self.placement.changed_at.is_some_and(|t| now.0.saturating_sub(t.0) < self.cfg.placement_hold);
if now.0.saturating_sub(target.since.0) < self.cfg.placement_sustain || held {
return;
}
let first = best.map_or(target.member, |i| order[i]);
self.move_lead(first, &order, &costs);
}
fn move_lead(&mut self, first: NodeId, order: &[NodeId], costs: &[Option<u128>]) {
let mut rest: Vec<usize> = (0..order.len()).filter(|&i| order[i] != first).collect();
rest.sort_by_key(|&i| (costs[i].is_none(), costs[i], i));
let new_order: Vec<NodeId> =
core::iter::once(first).chain(rest.into_iter().map(|i| order[i])).collect();
let change = crate::schedule::encode_change(self.schedule.generation(), &new_order);
if let Ok(id) = self.submit(change, Kind::Reconfigure) {
self.metrics.placement_moves += 1;
self.placement.moving = Some(id);
self.placement.target = None;
}
}
}