diff options
Diffstat (limited to 'src')
| -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 |
3 files changed, 260 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)), 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 |
