use alloc::vec::Vec;
use bytes::BufMut;
use crate::codec::{DecodeError, Reader};
use crate::types::{NodeId, Slot};
pub(crate) const LAG: u64 = 64;
const ROTATE_AFTER: u32 = 8;
pub(crate) const MAX_MEMBERS: usize = 1024;
pub(crate) fn encode_change(base: u64, order: &[NodeId]) -> bytes::Bytes {
let mut out = Vec::with_capacity(12 + 4 * order.len());
out.put_u64_le(base);
out.put_u32_le(order.len() as u32);
for n in order {
out.put_u32_le(n.0);
}
bytes::Bytes::from(out)
}
pub(crate) fn decode_change(b: &bytes::Bytes) -> Option<(u64, Vec<NodeId>)> {
let mut r = Reader::new(b);
let base = r.u64().ok()?;
let len = r.u32().ok()? as usize;
if len == 0 || len > MAX_MEMBERS {
return None;
}
let mut order = Vec::with_capacity(len);
for _ in 0..len {
let n = NodeId(r.u32().ok()?);
if order.contains(&n) {
return None;
}
order.push(n);
}
r.finish().ok()?;
Some((base, order))
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
pub(crate) struct Schedule {
history: Vec<(u64, Vec<NodeId>)>,
streak: u32,
quiet_until: u64,
epoch: u64,
epoch_from: u64,
generation: u64,
}
impl Schedule {
#[cfg(test)]
pub fn new(members: &[NodeId]) -> Self {
let mut order = members.to_vec();
order.sort_unstable();
Self::with_order(order)
}
pub fn with_order(order: Vec<NodeId>) -> Self {
Self {
history: alloc::vec![(0, order)],
streak: 0,
quiet_until: 0,
epoch: 0,
epoch_from: 0,
generation: 0,
}
}
fn order(&self, slot: Slot) -> &[NodeId] {
let i = self.history.partition_point(|(from, _)| *from <= slot.0);
&self.history[i.saturating_sub(1)].1
}
pub fn leader(&self, slot: Slot) -> NodeId {
self.order(slot)[0]
}
pub fn members(&self, slot: Slot) -> &[NodeId] {
self.order(slot)
}
pub fn knows(&self, node: NodeId) -> bool {
self.history.iter().any(|(_, order)| order.contains(&node))
}
pub fn member_sets_from(&self, slot: Slot) -> impl Iterator<Item = &[NodeId]> {
let first = self.history.partition_point(|(from, _)| *from <= slot.0).saturating_sub(1);
self.history[first..].iter().map(|(_, order)| order.as_slice())
}
pub fn everyone(&self) -> Vec<NodeId> {
let mut all: Vec<NodeId> = self.history.iter().flat_map(|(_, o)| o.iter().copied()).collect();
all.sort_unstable();
all.dedup();
all
}
pub fn settled(&self, slot: Slot) -> bool {
self.history.last().is_some_and(|(from, _)| *from <= slot.0)
}
pub fn epoch(&self) -> (u64, u64) {
(self.epoch, self.epoch_from)
}
pub fn generation(&self) -> u64 {
self.generation
}
pub fn reconfigure(&mut self, slot: Slot, base: u64, order: Vec<NodeId>) -> Option<(u64, u64)> {
let from = slot.0 + LAG;
let rotated_here = self.history.last().is_some_and(|(f, _)| *f >= from);
if base != self.generation || slot.0 < self.epoch_from || rotated_here {
return None;
}
self.history.push((from, order));
self.epoch += 1;
self.generation += 1;
self.epoch_from = from;
self.streak = 0;
self.quiet_until = from;
self.prune(slot);
Some((self.epoch, from))
}
fn prune(&mut self, slot: Slot) {
let keep_from = self.history.partition_point(|(f, _)| *f <= slot.0).saturating_sub(1);
self.history.drain(..keep_from);
}
pub fn position(&self, node: NodeId, slot: Slot) -> u64 {
let order = self.order(slot);
order.iter().position(|&n| n == node).unwrap_or(order.len()) as u64
}
pub fn encode(&self, out: &mut Vec<u8>) {
out.put_u64_le(self.epoch);
out.put_u64_le(self.epoch_from);
out.put_u64_le(self.generation);
out.put_u32_le(self.streak);
out.put_u64_le(self.quiet_until);
out.put_u32_le(self.history.len() as u32);
for (from, order) in &self.history {
out.put_u64_le(*from);
out.put_u32_le(order.len() as u32);
for n in order {
out.put_u32_le(n.0);
}
}
}
pub fn decode(r: &mut Reader<'_>, members: &[NodeId]) -> Result<Self, DecodeError> {
let epoch = r.u64()?;
let epoch_from = r.u64()?;
let generation = r.u64()?;
if generation < epoch {
return Err(DecodeError::BadTag);
}
let streak = r.u32()?;
if streak >= ROTATE_AFTER {
return Err(DecodeError::BadTag);
}
let quiet_until = r.u64()?;
let n = r.u32()? as usize;
let mut history = Vec::new();
for _ in 0..n {
let from = r.u64()?;
let configured = epoch == 0;
let len = r.u32()? as usize;
if len == 0 || len > MAX_MEMBERS || (configured && len != members.len()) {
return Err(DecodeError::BadTag);
}
let mut order = Vec::with_capacity(len);
for _ in 0..len {
let node = NodeId(r.u32()?);
if (configured && !members.contains(&node)) || order.contains(&node) {
return Err(DecodeError::BadTag);
}
order.push(node);
}
history.push((from, order));
}
if history.is_empty() || !history.is_sorted_by_key(|(f, _)| *f) {
return Err(DecodeError::BadTag);
}
Ok(Self { history, streak, quiet_until, epoch, epoch_from, generation })
}
pub fn fits(&self, next: u64) -> bool {
let increasing = self.history.windows(2).all(|w| w[0].0 < w[1].0);
let bumps = u128::from(self.generation) * u128::from(LAG);
let bounded = bumps <= u128::from(self.quiet_until) + u128::from(self.epoch_from);
match next.checked_sub(1) {
Some(fed) => {
let reach = fed.saturating_add(LAG);
increasing
&& bounded
&& self.history[0].0 <= fed
&& self.history.iter().all(|(from, _)| *from <= reach)
&& self.quiet_until <= reach
&& self.epoch_from <= reach
}
None => {
self.history.len() == 1
&& self.history[0].0 == 0
&& self.quiet_until == 0
&& self.epoch_from == 0
}
}
}
pub fn observe(&mut self, slot: Slot, origin: NodeId) {
if slot.0 < self.quiet_until {
return;
}
if origin == self.leader(slot) {
self.streak = 0;
return;
}
self.streak += 1;
if self.streak >= ROTATE_AFTER {
let mut order = self.order(slot).to_vec();
order.rotate_left(1);
let from = slot.0 + LAG;
self.history.push((from, order));
self.generation += 1;
self.streak = 0;
self.quiet_until = from;
self.prune(slot);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn ids(v: &[u32]) -> Vec<NodeId> {
v.iter().copied().map(NodeId).collect()
}
#[test]
fn initial_leader_is_the_smallest_member() {
let s = Schedule::new(&ids(&[3, 1, 2]));
assert_eq!((s.leader(Slot(0)), s.position(NodeId(3), Slot(0))), (NodeId(1), 2));
}
#[test]
fn eight_missed_slots_rotate_the_leader_after_the_lag() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
for slot in 0..8 {
s.observe(Slot(slot), NodeId(1));
}
assert_eq!(s.leader(Slot(7 + LAG - 1)), NodeId(0));
assert_eq!(s.leader(Slot(7 + LAG)), NodeId(1));
assert_eq!(s.position(NodeId(0), Slot(7 + LAG)), 2);
}
#[test]
fn a_slot_led_by_its_leader_resets_the_streak() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
for slot in 0..7 {
s.observe(Slot(slot), NodeId(2));
}
s.observe(Slot(7), NodeId(0));
for slot in 8..15 {
s.observe(Slot(slot), NodeId(2));
}
assert_eq!(s.leader(Slot(200)), NodeId(0));
}
#[test]
fn misses_before_a_rotation_takes_effect_do_not_rotate_again() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
for slot in 0..(8 + LAG) {
s.observe(Slot(slot), NodeId(2));
}
assert_eq!(s.leader(Slot(8 + LAG)), NodeId(1));
}
#[test]
fn decode_rejects_an_empty_or_unsorted_history() {
let members = ids(&[0, 1, 2]);
let encoded = |froms: &[u64]| {
let mut out = Vec::new();
out.put_u64_le(0);
out.put_u64_le(0);
out.put_u64_le(0);
out.put_u32_le(0);
out.put_u64_le(0);
out.put_u32_le(froms.len() as u32);
for from in froms {
out.put_u64_le(*from);
out.put_u32_le(3);
[0, 1, 2].into_iter().for_each(|n| out.put_u32_le(n));
}
bytes::Bytes::from(out)
};
let decode =
|b: &bytes::Bytes| Schedule::decode(&mut Reader::new(b), &members).map(|s| s.history.len());
assert_eq!(decode(&encoded(&[0, 9])), Ok(2));
assert!(decode(&encoded(&[])).is_err());
assert!(decode(&encoded(&[9, 0])).is_err());
}
#[test]
fn a_membership_change_takes_effect_a_window_later() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
assert_eq!(s.reconfigure(Slot(10), 0, ids(&[3, 1, 2])), Some((1, 10 + LAG)));
assert_eq!(s.members(Slot(10 + LAG - 1)), ids(&[0, 1, 2]));
assert_eq!((s.members(Slot(10 + LAG)), s.leader(Slot(10 + LAG))), (&ids(&[3, 1, 2])[..], NodeId(3)));
assert!(s.knows(NodeId(3)) && s.knows(NodeId(0)));
assert_eq!(s.everyone(), ids(&[0, 1, 2, 3]));
}
#[test]
fn one_change_at_a_time_and_never_twice() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
s.reconfigure(Slot(10), 0, ids(&[1, 2, 3])).unwrap();
assert_eq!(s.reconfigure(Slot(11), 1, ids(&[0, 1])), None, "the first is still pending");
assert_eq!(s.reconfigure(Slot(10 + LAG), 0, ids(&[1, 2, 3])), None, "a late duplicate");
assert_eq!(s.reconfigure(Slot(10 + LAG), 1, ids(&[0, 1])), Some((2, 10 + 2 * LAG)));
assert_eq!(s.epoch(), (2, 10 + 2 * LAG));
}
#[test]
fn a_change_computed_before_a_newer_one_never_undoes_it() {
let mut s = Schedule::new(&ids(&[0, 1, 2, 4]));
s.reconfigure(Slot(10), 0, ids(&[0, 1, 2])).unwrap();
assert_eq!(s.reconfigure(Slot(10 + LAG + 5), 0, ids(&[0, 1, 2, 4])), None, "a stale change");
assert_eq!(s.members(Slot(10 + 3 * LAG)), ids(&[0, 1, 2]));
assert_eq!(s.epoch(), (1, 10 + LAG));
}
#[test]
fn a_change_computed_before_a_rotation_is_ignored() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
let base = s.generation();
for slot in 0..8 {
s.observe(Slot(slot), NodeId(1));
}
assert_eq!(s.generation(), base + 1, "the rotation counts");
assert_eq!(s.reconfigure(Slot(8 + LAG), base, ids(&[0, 1, 2])), None);
assert_eq!(s.leader(Slot(8 + LAG)), NodeId(1));
assert!(s.reconfigure(Slot(8 + LAG), base + 1, ids(&[0, 1, 2])).is_some());
}
#[test]
fn a_change_decided_in_the_slot_that_counts_a_rotation_is_ignored() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
for slot in 0..8 {
s.observe(Slot(slot), NodeId(1));
}
assert_eq!(s.reconfigure(Slot(7), 0, ids(&[2, 0])), None);
assert_eq!(s.reconfigure(Slot(7), 1, ids(&[2, 0])), None);
assert_eq!(s.members(Slot(7 + LAG)), ids(&[1, 2, 0]));
s.reconfigure(Slot(8 + LAG), 1, ids(&[2, 0])).unwrap();
for slot in (8 + 2 * LAG)..(8 + 2 * LAG + 8) {
s.observe(Slot(slot), NodeId(0));
}
assert_eq!(s.leader(Slot(8 + 3 * LAG + 7)), NodeId(0));
}
#[test]
fn epochs_round_trip() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
s.reconfigure(Slot(3), 0, ids(&[4, 5, 6, 7])).unwrap();
let mut out = Vec::new();
s.encode(&mut out);
let b = bytes::Bytes::from(out);
let mut restored = Schedule::decode(&mut Reader::new(&b), &ids(&[0, 1, 2]));
assert_eq!(restored, Ok(s));
let restored = restored.as_mut().unwrap();
assert_eq!(restored.reconfigure(Slot(3 + LAG), 0, ids(&[4, 5, 6, 7])), None);
assert_eq!(restored.epoch(), (1, 3 + LAG));
}
#[test]
fn changes_decode_only_when_well_formed() {
assert_eq!(decode_change(&encode_change(3, &ids(&[2, 0]))), Some((3, ids(&[2, 0]))));
assert_eq!(decode_change(&encode_change(0, &[])), None);
assert_eq!(decode_change(&encode_change(0, &ids(&[1, 1]))), None);
assert_eq!(decode_change(&bytes::Bytes::from_static(&[0; 8])), None);
assert_eq!(decode_change(&bytes::Bytes::from_static(&[1, 0, 0, 0, 5, 0, 0, 0])), None);
}
#[test]
fn changes_are_bounded_in_size() {
let at_most = (0..MAX_MEMBERS as u32).map(NodeId).collect::<Vec<_>>();
assert!(decode_change(&encode_change(0, &at_most)).is_some());
let too_many = (0..=MAX_MEMBERS as u32).map(NodeId).collect::<Vec<_>>();
assert_eq!(decode_change(&encode_change(0, &too_many)), None);
}
#[test]
fn old_schedules_are_pruned() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
for slot in 0..10_000 {
s.observe(Slot(slot), NodeId(9));
}
assert!(s.history.len() <= 2, "{} orders kept", s.history.len());
}
fn encoded(epoch: u64, order: &[u32]) -> bytes::Bytes {
let mut out = Vec::new();
out.put_u64_le(epoch);
out.put_u64_le(0);
out.put_u64_le(epoch);
out.put_u32_le(0);
out.put_u64_le(0);
out.put_u32_le(1);
out.put_u64_le(0);
out.put_u32_le(order.len() as u32);
order.iter().for_each(|n| out.put_u32_le(*n));
bytes::Bytes::from(out)
}
#[test]
fn decoding_checks_every_order() {
let members = ids(&[0, 1, 2]);
let decode = |epoch: u64, order: &[u32]| {
Schedule::decode(&mut Reader::new(&encoded(epoch, order)), &members).is_ok()
};
assert!(decode(0, &[2, 0, 1]));
assert!(!decode(0, &[0, 1]) && !decode(0, &[0, 1, 7]) && !decode(0, &[0, 1, 1]));
assert!(decode(1, &[7, 8]) && decode(1, &[5]));
assert!(!decode(1, &[]) && !decode(1, &[7, 7]));
let max: Vec<u32> = (0..MAX_MEMBERS as u32).collect();
let over: Vec<u32> = (0..=MAX_MEMBERS as u32).collect();
assert!(decode(1, &max) && !decode(1, &over));
let mut short = encoded(2, &[5]).to_vec();
short[16..24].copy_from_slice(&1u64.to_le_bytes());
let short = bytes::Bytes::from(short);
assert!(Schedule::decode(&mut Reader::new(&short), &members).is_err());
}
proptest::proptest! {
#[test]
fn same_log_same_leaders(origins in proptest::collection::vec(0u32..3, 0..400)) {
let (mut a, mut b) = (Schedule::new(&ids(&[0, 1, 2])), Schedule::new(&ids(&[2, 1, 0])));
for (slot, o) in origins.iter().enumerate() {
a.observe(Slot(slot as u64), NodeId(*o));
b.observe(Slot(slot as u64), NodeId(*o));
}
for k in 0..(origins.len() as u64 + LAG) {
proptest::prop_assert_eq!(a.leader(Slot(k)), b.leader(Slot(k)));
}
}
}
#[test]
fn fits_only_what_feeding_the_slots_below_next_can_build() {
let s = Schedule::new(&ids(&[0, 1, 2]));
assert!(s.fits(0) && s.fits(10));
let ahead = Schedule { history: alloc::vec![(74, ids(&[0, 1, 2]))], ..s.clone() };
assert!(!ahead.fits(10) && ahead.fits(75));
let tied = Schedule {
history: alloc::vec![(0, ids(&[0, 1, 2])), (5, ids(&[1, 2, 0])), (5, ids(&[2, 0, 1]))],
..s.clone()
};
assert!(!tied.fits(10));
let far =
Schedule { history: alloc::vec![(0, ids(&[0, 1, 2])), (10 + LAG, ids(&[1, 2, 0]))], ..s.clone() };
assert!(!far.fits(10) && far.fits(11));
}
#[test]
fn fits_bounds_the_generation_by_the_slots_fed() {
let mut s = Schedule::new(&ids(&[0, 1, 2]));
s.reconfigure(Slot(3), 0, ids(&[0, 1])).unwrap();
assert!(s.fits(4));
let forged = Schedule { generation: u64::MAX, ..s.clone() };
assert!(!forged.fits(4) && !forged.fits(u64::MAX));
let quiet_ahead = Schedule { quiet_until: 4 + LAG, ..s };
assert!(!quiet_ahead.fits(4) && quiet_ahead.fits(5));
let fresh = Schedule::new(&ids(&[0, 1, 2]));
assert!(!Schedule { generation: 1, ..fresh }.fits(10));
}
#[test]
fn before_any_slot_only_the_initial_schedule_fits() {
let s = Schedule::new(&ids(&[0, 1, 2]));
assert!(s.fits(0));
let two = Schedule { history: alloc::vec![(0, ids(&[0, 1, 2])), (0, ids(&[1, 2, 0]))], ..s.clone() };
let later = Schedule { history: alloc::vec![(1, ids(&[0, 1, 2]))], ..s.clone() };
let quiet = Schedule { quiet_until: 1, ..s.clone() };
let epoch = Schedule { epoch_from: 1, ..s };
assert!(!two.fits(0) && !later.fits(0) && !quiet.fits(0) && !epoch.fits(0));
}
}