diff options
| author | tv <tv@krebsco.de> | 2026-11-18 20:08:28 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-18 21:17:40 +0100 |
| commit | 79614926332977718956f35e1adf80ae67e219f1 (patch) | |
| tree | 011d1b66381233f61f04c77360e1f9f8f704c5c6 | |
| parent | 8369d2ef1ce1f5856cbff2bd33b1c39dfe80e445 (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.
| -rw-r--r-- | docs/federation.md | 7 | ||||
| -rw-r--r-- | docs/guides/federation/when-things-go-wrong.md | 5 | ||||
| -rw-r--r-- | docs/store.md | 32 | ||||
| -rw-r--r-- | src/federation/held.rs | 102 | ||||
| -rw-r--r-- | src/federation/store/memory.rs | 48 | ||||
| -rw-r--r-- | src/simtest/holding.rs | 117 |
6 files changed, 287 insertions, 24 deletions
diff --git a/docs/federation.md b/docs/federation.md index a179846..ae010fb 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -813,9 +813,10 @@ moves to it by a version of its policy that names it (`"federation": 2`), which parties pass once their nodes run a continuum that knows it. A node that doesn't know the federation its swarm's root names holds no store, and says so. One that doesn't read a version that passed on the version it reads stops at the version event writing it, and -says so: it takes nothing and refuses nothing from then on, and keeps none of it across a -restart, until it runs a continuum that reads it, or its operator has it drop that event -([`store.md`](store.md), [A node's own](store.md#a-nodes-own)). Dropped, the node refuses +says so: it takes nothing and refuses nothing from then on, leaving out none of it, a +remake's snapshot neither, and keeps none of it across a restart, until it runs a +continuum that reads it, or its operator has it drop that event ([`store.md`](store.md), +[A node's own](store.md#a-nodes-own)). Dropped, the node refuses that event and any writing that version, as any version its operator had it drop, and goes on under the version before. One beside the version it reads, it refuses of its own, as any other ([Changing the policy](#changing-the-policy)). diff --git a/docs/guides/federation/when-things-go-wrong.md b/docs/guides/federation/when-things-go-wrong.md index 8c46e1d..b59b69b 100644 --- a/docs/guides/federation/when-things-go-wrong.md +++ b/docs/guides/federation/when-things-go-wrong.md @@ -91,7 +91,10 @@ curl -u tv:secret -X POST -H 'Content-Type: application/json' \ ``` Allowed again (`/admin/events/allow`), it stops there once more. A node that stopped -keeps none of it in its store file: restarted, it stops there again. +keeps none of it in its store file: restarted, it stops there again. What it holds back +it leaves out of nothing, as it can't tell which will be taken: it puts it again where its +document lacks it, and a remake keeps it, so a remake while nodes are stopped loses none +of what was put since. ## A node doing less than it should diff --git a/docs/store.md b/docs/store.md index b598539..ad98f9f 100644 --- a/docs/store.md +++ b/docs/store.md @@ -216,10 +216,13 @@ a fold knowing more reads (the federation's node: a version event writing a vers that passed, which its continuum doesn't read, [Changing the federation](federation.md#changing-the-federation)). The node takes nothing and refuses nothing from then on: it holds back whatever comes, that event first, -keeps none of it across a restart, where it stops there again, and reports it, until it +keeps none of it in its file, as a restart stops there again, and reports it, until it runs a continuum that reads the event, or its operator has it drop the event, or one it -builds on. Then it refuses it, as dropped or as built on what was, with everything built -on it, and judges what it held back. What it took before it stopped, it holds as it did. +builds on. Then it refuses that event, as dropped or as built on what was, with +everything built on it, and judges what it held back. What it took before it stopped, it +holds as it did. Of what it holds back, and what waits, it leaves out none, as it can't +tell which will be taken: it puts it again where its document lacks it, and a remake's +snapshot holds it ([Remakes](#remakes)). ## Forks @@ -308,11 +311,12 @@ a restart. **A node puts again**, in changes of its own, every event its document lacks that a store starting at the document's checkpoint would take, but for the node's own refusals and drops, and that the node has: one it holds, one in a change it refused, or one the -document it left held, at a switch or a rejoin ([Remakes](#remakes)). It puts each after -its dependencies, once a short wait of its own has passed, random, so that not every node -puts the same, and none another node put meanwhile. Each event is taken again as it was: -its history is there too. Continuum still refuses some changes on its own, by what they -are or who wrote them: of a writer's two changes of one number, the second +document it left held, at a switch or a rejoin ([Remakes](#remakes)); and, where its store +stopped, what it holds back and what waits ([A node's own](#a-nodes-own)). It puts each +after its dependencies, once a short wait of its own has passed, random, so that not +every node puts the same, and none another node put meanwhile. Each event is taken again +as it was: its history is there too. Continuum still refuses some changes on its own, by +what they are or who wrote them: of a writer's two changes of one number, the second ([Where Automerge sets limits](#where-automerge-sets-limits)); what such a change carried still reaches the store, and the documents those two changes part hold the same events. And no remake leaves out an event a store starting at the new document's checkpoint takes. @@ -348,14 +352,16 @@ coordinator): two remakes at one base are two epochs. * **The snapshot** holds the store a node reads from the document up to the base, starting at the document's checkpoint, by its own refusals and drops: the checkpoint it reaches there, where it isn't the root, the events that one keeps and those after - it, each at its ID; the policy; and of continuum's protocol data what a compaction - carries, but the entries of nodes that aren't members at the base. What that + it, and, where the store stops there, what it holds back and what waits, as it can't + tell which will be taken ([A node's own](#a-nodes-own)), each at its ID; the policy; + and of continuum's protocol data what a compaction carries, but the entries of nodes + that aren't members at the base. What that checkpoint forgot, and events nobody takes, leave the document here. A node that moved to a later checkpoint since the base builds the snapshot as one that didn't, as both read the document; nodes that read the store differently at the base (the sides of - keys that voted twice, in the federation, or a node that stopped, holding back what - the others took: [A node's own](#a-nodes-own)) build different snapshots, and part - here. + keys that voted twice, in the federation, or a node that stopped, where the others + refuse, or still wait for, some of what it holds back) build different snapshots, and + part here. * **A node follows a decision** whichever node coordinated it: a decision reaches it only through a member, which could decide one itself, and a remake changes no event. It builds the snapshot itself, from a base it holds, and checks it against the 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)), diff --git a/src/simtest/holding.rs b/src/simtest/holding.rs index f7ac715..74086e2 100644 --- a/src/simtest/holding.rs +++ b/src/simtest/holding.rs @@ -1139,6 +1139,123 @@ async fn store_attack_16() { assert!(read.iter().all(|counts| counts == &read[0]), "{read:?}"); } +/// Whether `node`'s store stopped (`Fold::stops`), and at which event. +fn stopped(node: &AppState) -> Option<Id> { + read(node, |store| store.stopped().map(|(id, ..)| *id)).flatten() +} + +/// Whether `node`'s store holds back every event of `ids`. +fn holds_back(node: &AppState, ids: &[Id]) -> bool { + read(node, |store| { + let held: BTreeSet<Id> = store.held_back().into_iter().map(|(id, _)| id).collect(); + ids.iter().all(|id| held.contains(id)) + }) == Some(true) +} + +/// A version of a federation this continuum doesn't know passes, and a version event +/// writes it: every node stops there, and holds back what is put meanwhile. A compaction +/// leaves none of it out: the new document holds that event and what came after. c, away +/// meanwhile, rejoins the new epoch and stops there too, and so does b, started again with +/// nothing. Their operators have them drop that event: they take again, all alike. +#[tokio::test(flavor = "multi_thread", worker_threads = 4)] +async fn a_stopped_store_keeps_what_it_holds_back_through_a_remake_and_a_rejoin() { + let sim = Sim::with_identity(98); + let (tv, lass, makefu) = three(); + let (first, root, id) = federation(&[(&tv, &["a"]), (&lass, &["b"]), (&makefu, &["c"])]); + let nodes = started( + &sim, + &root, + vec![ + ("a", holding("tv")), + ("b", holding("lass")), + ("c", holding("makefu")), + ], + ) + .await; + let on = first.hash(); + let text = String::from_utf8(first.after(on).json().bytes()) + .expect("UTF-8") + .replace(r#""federation":1"#, r#""federation":2"#); + let unknown = crate::federation::jcs::read(text.as_bytes()).expect("JCS"); + let hash = Id::of(&unknown.bytes()); + let proposal = tv.propose(&[id], &unknown); + let votes = [&tv, &lass].map(|party| party.vote(&[Id::of(&proposal)], on, hash, true)); + let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], hash); + let at = Id::of(&written); + put(&nodes[0], &[&proposal, &votes[0], &votes[1], &written]).await; + let all = &nodes; + sim.wait_until("every node stopped there", LONG, move || async move { + all.iter().all(|node| stopped(node) == Some(at)) + }) + .await; + + sim.net.take_down("c"); + let meanwhile = tv.write(&[id], "home/tv/a", s("1")); + put(&nodes[0], &[&meanwhile]).await; + let meanwhile = Id::of(&meanwhile); + sim.wait_until("a and b hold it back", LONG, move || async move { + all[..2] + .iter() + .all(|node| holds_back(node, &[at, meanwhile])) + }) + .await; + compact(&nodes[0]).await; + on_generation(&sim, &nodes[..2], 1, Duration::from_secs(60)).await; + { + let replica = nodes[0].doc.read().await; + let held = events::ids(&replica.doc); + assert!(held.contains(&at) && held.contains(&meanwhile)); + } + for node in &nodes[..2] { + assert_eq!(stopped(node), Some(at)); + assert!(holds_back(node, &[meanwhile])); + } + + sim.net.bring_up("c"); + let c = &nodes[2]; + sim.wait_until( + "c rejoins the new epoch, and stops there too", + Duration::from_secs(60), + move || async move { + c.local_epoch().generation == 1 + && c.is_ready().await + && stopped(c) == Some(at) + && holds_back(c, &[meanwhile]) + }, + ) + .await; + let b = sim.restart_with("b", &["a"], Start::Join, move |config| { + of_the_store(config, id, None, holding("lass")) + }); + let b = &b; + sim.wait_until( + "b, started again with nothing, reads the new epoch and stops there", + Duration::from_secs(60), + move || async move { + b.local_epoch().generation == 1 + && b.is_ready().await + && stopped(b) == Some(at) + && holds_back(b, &[meanwhile]) + }, + ) + .await; + + let every = [nodes[0].clone(), b.clone(), nodes[2].clone()]; + for node in &every { + let dropped = node.holding.drop_taken(&[at]).expect("a store"); + assert_eq!(dropped, Ok(vec![at])); + } + let every = &every; + sim.wait_until("every node takes again", LONG, move || async move { + every + .iter() + .all(|node| stopped(node).is_none() && holds(node, &[meanwhile])) + }) + .await; + let read: Vec<Option<Counts>> = every.iter().map(counts).collect(); + assert!(read.iter().all(|counts| counts == &read[0]), "{read:?}"); +} + /// A compaction whose base comes before a checkpoint, switched after nodes moved to it: /// they switch, keep their checkpoint, read none of what it forgot, and put again from /// the old document what a store starting at the snapshot's checkpoint takes to reach |
