aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-18 20:08:28 +0000
committertv <tv@krebsco.de>2026-11-18 21:17:40 +0100
commit79614926332977718956f35e1adf80ae67e219f1 (patch)
tree011d1b66381233f61f04c77360e1f9f8f704c5c6 /src/federation
parent8369d2ef1ce1f5856cbff2bd33b1c39dfe80e445 (diff)
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.
Diffstat (limited to 'src/federation')
-rw-r--r--src/federation/held.rs102
-rw-r--r--src/federation/store/memory.rs48
2 files changed, 143 insertions, 7 deletions
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<Vec<u8>>,
- /// 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<Id, Vec<u8>>,
/// The members there, by node ID.
pub(crate) members: BTreeSet<String>,
@@ -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<u8>)> {
let mut held: HashSet<Id> = 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<AtBase> {
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<Id> = 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<F: Fold> Store<F> {
.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<Id, &Event> = self
+ .held_back
+ .iter()
+ .map(|(id, event)| (*id, event))
+ .chain(self.waiting.iter().map(|(id, event)| (*id, event)))
+ .collect();
+ let mut placed: HashSet<Id> = 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<Id> {
@@ -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<Id> = 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)),