From 79614926332977718956f35e1adf80ae67e219f1 Mon Sep 17 00:00:00 2001 From: tv Date: Wed, 18 Nov 2026 20:08:28 +0000 Subject: store: a stopped node leaves out none of what it holds back A store that stopped can't tell which of what it holds back will be taken, nor which of what waits: `Store::held_back` gives both, each after what it builds on. A node leaves out none of it: it puts it again where its document lacks it (`Holding::lacking`), a remake's snapshot holds it (`Holding::at_base`), and after a switch or a rejoin it puts again what of it the document it left held (`Holding::left`). A remake while nodes are stopped no longer drops what was put since the stop, nor the event they stopped at. Tested: a node keeps what it holds back, what waited among it, through a snapshot, and a store read anew from that stops there again; and a simulation: a swarm stopped at a version compacts, a node away meanwhile rejoins and one started again with nothing reads the new epoch, each stopping there, holding back what came after, until their operators have them drop that event. --- src/federation/held.rs | 102 ++++++++++++++++++++++++++++++++++++++--- src/federation/store/memory.rs | 48 +++++++++++++++++++ 2 files changed, 143 insertions(+), 7 deletions(-) (limited to 'src/federation') diff --git a/src/federation/held.rs b/src/federation/held.rs index 5155573..66f20e9 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -156,7 +156,8 @@ struct Inner { pub(crate) struct AtBase { /// The checkpoint the store reaches there, where it isn't the root. pub(crate) checkpoint: Option>, - /// The root, the events that checkpoint keeps, and those after it, by ID. + /// The root, the events that checkpoint keeps, and those after it, by ID: those it + /// holds back too, where it stops there. pub(crate) events: BTreeMap>, /// The members there, by node ID. pub(crate) members: BTreeSet, @@ -473,7 +474,8 @@ impl Holding { /// The events the node has that `doc` lacks, each after its dependencies: of the /// document it left, what a store starting at `doc`'s checkpoint takes (`left`); then - /// what its store's checkpoint keeps, then what it took after it. + /// what its store's checkpoint keeps, then what it took after it, then what it holds + /// back, stopped (`Store::held_back`). pub(crate) fn lacking(&self, doc: &impl ReadDoc) -> Vec<(Id, Vec)> { let mut held: HashSet = events::ids(doc).into_iter().collect(); let mut inner = self.inner.lock_or_recover(); @@ -490,6 +492,12 @@ impl Holding { .taken() .iter() .filter_map(|id| Some((*id, store.get(id)?.to_vec()))), + ) + .chain( + store + .held_back() + .into_iter() + .map(|(id, bytes)| (id, bytes.to_vec())), ), ); } @@ -570,9 +578,10 @@ impl Holding { /// What `left`, the document the node left at a switch or a rejoin, holds that a store /// starting at `doc`'s checkpoint takes, by the node's own refusals and its operator's - /// drops, and `doc` lacks (`docs/store.md`, Remakes): kept, to put again (`lacking`). - /// So what the node held beyond the base goes again, and, where it moved to a later - /// checkpoint since, what a store starting at the snapshot's takes to reach it. + /// drops, or holds back, stopped, and `doc` lacks (`docs/store.md`, Remakes): kept, to + /// put again (`lacking`). So what the node held beyond the base goes again, and, where + /// it moved to a later checkpoint since, what a store starting at the snapshot's takes + /// to reach it. pub(crate) fn left(&self, doc: &impl ReadDoc, left: &impl ReadDoc) { let reading = Holding { pin: self.pin, @@ -602,6 +611,13 @@ impl Holding { ); } } + put.extend( + store + .held_back() + .into_iter() + .filter(|(id, _)| events.contains_key(id)) + .map(|(id, bytes)| (id, bytes.to_vec())), + ); } if !put.is_empty() { info!( @@ -854,8 +870,9 @@ impl Holding { /// What a remake's snapshot holds of the store: as this node reads it anew from /// `base`, the document at the remake's base, by its own refusals and its operator's - /// drops, as it reads its document whenever it starts. None where `base` holds no - /// store, or none this node reads there. + /// drops, as it reads its document whenever it starts; and what it holds back there, + /// where it stops (`Store::held_back`). None where `base` holds no store, or none this + /// node reads there. pub(crate) fn at_base(&self, base: &impl ReadDoc) -> Option { let reading = Holding { pin: self.pin, @@ -880,6 +897,10 @@ impl Holding { events.insert(*id, bytes.to_vec()); } } + // Stopped, what it can't judge it doesn't leave out. + for (id, bytes) in store.held_back() { + events.insert(id, bytes.to_vec()); + } events.insert(swarm, root); AtBase { checkpoint: (Id::of(checkpoint) != swarm).then(|| checkpoint.to_vec()), @@ -1804,6 +1825,73 @@ mod tests { assert!(holding.with(|_| ()).is_none()); } + /// A node whose store stopped leaves out none of what it holds back, as it can't tell + /// which will be taken: what waited when it stopped among it, it puts again where its + /// document lacks it, each after what it builds on, and a remake's snapshot holds it, so + /// that a store read anew from that stops there again. + #[test] + fn a_node_that_stopped_keeps_what_it_holds_back_through_a_remake() { + let (tv, lass, makefu) = ( + Party::new("tv", 1), + Party::new("lass", 2), + Party::new("makefu", 3), + ); + let first = Spec::first(&[&tv, &lass, &makefu], &[]); + let root = first.root(); + let on = first.hash(); + let mut none = first.after(on); + none.rules + .push(("_continuum/x".to_owned(), harness::str("tv"))); + let proposal = tv.propose(&[Id::of(&root)], &none.json()); + let votes = + [&tv, &lass].map(|party| party.vote(&[Id::of(&proposal)], on, none.hash(), true)); + let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], none.hash()); + let after = tv.write(&[Id::of(&written)], "home/tv/a", harness::str("1")); + let beside = lass.write(&[Id::of(&votes[1])], "home/lass/b", harness::str("2")); + let on_beside = makefu.write(&[Id::of(&beside)], "home/makefu/c", harness::str("3")); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); + for event in [&proposal].into_iter().chain(&votes) { + put(&mut doc, event); + } + let holding = Holding::default(); + read(&holding, &doc, 0); + // Waiting for what it builds on when the store stops; that one comes after. + assert_eq!(holding.offer(on_beside.clone()), Some(Offered::Waiting)); + put(&mut doc, &written); + put(&mut doc, &after); + read(&holding, &doc, 0); + assert_eq!(holding.offer(beside.clone()), Some(Offered::Stopped)); + let lacking: Vec = holding + .lacking(&doc) + .into_iter() + .map(|(id, _)| id) + .collect(); + assert_eq!(lacking, vec![Id::of(&beside), Id::of(&on_beside)]); + + put(&mut doc, &on_beside); + put(&mut doc, &beside); + let snapshot = snapshot(&doc, &holding); + let held = events::ids(&snapshot); + for kept in [&written, &after, &beside, &on_beside] { + assert!(held.contains(&Id::of(kept))); + } + let anew = Holding::default(); + read(&anew, &snapshot, 1); + assert_eq!( + anew.with(|store| store.stopped().map(|(id, ..)| *id)), + Some(Some(Id::of(&written))) + ); + anew.drop_taken(&[Id::of(&written)]).unwrap().unwrap(); + assert_eq!( + anew.with(|store| { + store.holds(&Id::of(&beside)) + && store.holds(&Id::of(&on_beside)) + && !store.holds(&Id::of(&after)) + }), + Some(true) + ); + } + /// A node voting by itself whose store stopped casts nothing, by itself or by hand: /// what it reads is behind what passed. #[test] diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index f721b47..8493735 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -222,6 +222,47 @@ impl Store { .map(|(id, why)| (id, why.as_str(), self.held_back.len())) } + /// What the store holds back, stopped (`Fold::stops`): the events offered since, and + /// those waiting for events it doesn't hold, as it can't tell which will be taken; each + /// after those of its dependencies among them, by ID otherwise. Nothing while it isn't + /// stopped. + pub(crate) fn held_back(&self) -> Vec<(Id, &[u8])> { + if self.stopped.is_none() { + return Vec::new(); + } + let all: BTreeMap = self + .held_back + .iter() + .map(|(id, event)| (*id, event)) + .chain(self.waiting.iter().map(|(id, event)| (*id, event))) + .collect(); + let mut placed: HashSet = HashSet::new(); + let mut ordered = Vec::new(); + for first in all.keys() { + let mut todo = vec![(*first, false)]; + while let Some((id, ready)) = todo.pop() { + if placed.contains(&id) { + continue; + } + let event = all[&id]; + if ready { + placed.insert(id); + ordered.push((id, event.bytes.as_slice())); + continue; + } + todo.push((id, true)); + todo.extend( + event + .dependencies + .iter() + .filter(|dependency| all.contains_key(dependency)) + .map(|dependency| (*dependency, false)), + ); + } + } + ordered + } + /// What a new event builds on: the events nothing else held builds on, or the /// checkpoint's heads where nothing came after it. pub(crate) fn heads(&self) -> Vec { @@ -971,10 +1012,17 @@ mod tests { assert_eq!(store.taken(), &[mark]); assert_eq!(store.refused().count(), 0); assert_eq!(store.stopped().map(|(_, _, held)| held), Some(3)); + // What it holds back, what waits among it, each after what it builds on. + let held: Vec = store.held_back().iter().map(|(id, _)| *id).collect(); + let place = |id: Id| held.iter().position(|held| *held == id); + assert_eq!(held.len(), 4); + assert!(place(at) < place(Id::of(&on))); + assert!(place(Id::of(&later)).is_some() && place(Id::of(&junk)).is_some()); assert!(store.drop_taken(&[Id::of(&later)]).is_err()); // Dropped: what it held back is taken, or refused, and what waited for it refused. assert_eq!(store.drop_taken(&[at]), Ok(vec![at])); assert!(store.stopped().is_none()); + assert!(store.held_back().is_empty()); assert_eq!(store.taken(), &[mark, Id::of(&later)]); assert!(matches!( store.refusal(&Id::of(&junk)), -- cgit v1.3.1