From 36a4a54b1c9204d72e405f5bbfa2a1b595ccba04 Mon Sep 17 00:00:00 2001 From: tv Date: Fri, 6 Nov 2026 20:22:03 +0100 Subject: flood dissemination --- docs/development.md | 9 ++++--- docs/example.toml | 5 ++-- src/config/mod.rs | 8 ++++-- src/simtest/mod.rs | 1 + src/swarm/dissemination.rs | 3 +++ src/swarm/flood.rs | 65 ++++++++++++++++++++++++++++++++++++++++++++++ src/swarm/mod.rs | 1 + 7 files changed, 84 insertions(+), 8 deletions(-) create mode 100644 src/swarm/flood.rs diff --git a/docs/development.md b/docs/development.md index 9296e8b..ed95bf0 100644 --- a/docs/development.md +++ b/docs/development.md @@ -30,10 +30,11 @@ unless `BENCH_WRITES` says otherwise (more, to see what grows with them); each scenario run several times, one run after another, with `BENCH_REPEAT=3`, and a summary of each workload's mean delay and messages per write, run by run (runs differ: one can't tell a small change from chance); with -`SIM_DISSEMINATION=plumtree`, every simulated node passes changes on by PlumTree -(`--dissemination`), the benchmark's views of the trees still being the writers' -trees'; with `SIM_TOPOLOGY=hyparview`, every simulated node chooses its neighbours by -HyParView (`--topology`; with PlumTree, as writers' trees need the shared graph); all at once with +`SIM_DISSEMINATION=plumtree` (or `flood`), every simulated node passes changes on by +PlumTree (or by flooding: `--dissemination`), the benchmark's views of the trees still +being the writers' trees'; with `SIM_TOPOLOGY=hyparview`, every simulated node chooses +its neighbours by HyParView (`--topology`; with PlumTree unless `SIM_DISSEMINATION` +says otherwise, as `--dissemination` defaults to then); all at once with `BENCH_PARALLEL=1`, faster on many cores, though sharing them makes delays come out somewhat higher; and in `bench_bridge`, large values from a writer on a fast transport through a bridge to a node on a slow one: what that node gets as sync messages and as diff --git a/docs/example.toml b/docs/example.toml index de32ada..a44f1eb 100644 --- a/docs/example.toml +++ b/docs/example.toml @@ -189,8 +189,9 @@ htpasswd = "/etc/continuum/htpasswd" # superseded-writes = "drop" # How a change reaches every member: writers-trees (computed alike on every node from -# the member list) or plumtree (eager links pruned where they deliver twice, grafted -# where announcements had to bring a change). A genesis node records its own in the +# the member list), plumtree (eager links pruned where they deliver twice, grafted +# where announcements had to bring a change) or flood (every change pushed to every +# neighbour: the baseline). A genesis node records its own in the # document; every node follows what the swarm records, which a protocol writer may # change (_continuum/dissemination), and uses its own only where the swarm records none # it knows. diff --git a/src/config/mod.rs b/src/config/mod.rs index b7c7ff2..25b1c73 100644 --- a/src/config/mod.rs +++ b/src/config/mod.rs @@ -294,9 +294,9 @@ pub(crate) const OPTIONS: &[OptionSpec] = &[ option( "dissemination", Kind::Text, - "writers-trees|plumtree", + "writers-trees|plumtree|flood", Some("writers-trees"), - "How a change reaches every member: along writers' trees computed alike on every node from the member list, or by PlumTree (eager links pruned where they deliver twice, grafted where announcements had to bring a change). A genesis node records its own in the document; every node follows what the swarm records, which a protocol writer may change (_continuum/dissemination), and uses its own only where the swarm records none it knows. Default: plumtree with topology hyparview, else writers-trees (docs/topology.md).", + "How a change reaches every member: along writers' trees computed alike on every node from the member list, by PlumTree (eager links pruned where they deliver twice, grafted where announcements had to bring a change), or by flooding (every change pushed to every neighbour: the baseline). A genesis node records its own in the document; every node follows what the swarm records, which a protocol writer may change (_continuum/dissemination), and uses its own only where the swarm records none it knows. Default: plumtree with topology hyparview, else writers-trees (docs/topology.md).", ), option( "superseded-writes", @@ -1581,6 +1581,10 @@ fn warn_combinations(settings: &Settings, set: &dyn Fn(&str) -> bool) { (Topology::Hyparview, Dissemination::WritersTrees) => warn!( "topology hyparview with dissemination writers-trees: writers' trees need the graph every node shares, which HyParView has none of, so changes pass on by announcements alone, a round and a pull per hop; dissemination plumtree is what goes with it" ), + (_, Dissemination::Flood) if settings.neighbours > HYPARVIEW_NEIGHBOURS => warn!( + neighbours = settings.neighbours, + "dissemination flood: every member pushes every change to each of its neighbours, so each link carries it about twice; a baseline to measure against, costly with this many" + ), (Topology::RingAndPairs, Dissemination::Plumtree) => warn!( "dissemination plumtree with topology ring-and-pairs: an experiment; writers' trees, on the graph every node shares, were faster in every scenario benchmarked (docs/topology.md)" ), diff --git a/src/simtest/mod.rs b/src/simtest/mod.rs index dadc3e8..011483e 100644 --- a/src/simtest/mod.rs +++ b/src/simtest/mod.rs @@ -203,6 +203,7 @@ impl Sim { // Unset with `SIM_TOPOLOGY=hyparview`: PlumTree, as `--dissemination` is then. dissemination: match std::env::var("SIM_DISSEMINATION").as_deref() { Ok("plumtree") => crate::swarm::dissemination::Kind::Plumtree, + Ok("flood") => crate::swarm::dissemination::Kind::Flood, Err(_) if std::env::var("SIM_TOPOLOGY").as_deref() == Ok("hyparview") => { crate::swarm::dissemination::Kind::Plumtree } diff --git a/src/swarm/dissemination.rs b/src/swarm/dissemination.rs index 93ad4e9..9763449 100644 --- a/src/swarm/dissemination.rs +++ b/src/swarm/dissemination.rs @@ -139,6 +139,8 @@ pub(crate) enum Kind { WritersTrees, /// PlumTree (`swarm::plumtree`). Plumtree, + /// Flooding (`swarm::flood`). + Flood, } impl Kind { @@ -146,6 +148,7 @@ impl Kind { match self { Kind::WritersTrees => std::sync::Arc::new(crate::swarm::tree::WritersTrees), Kind::Plumtree => std::sync::Arc::new(crate::swarm::plumtree::PlumTree::default()), + Kind::Flood => std::sync::Arc::new(crate::swarm::flood::Flood), } } } diff --git a/src/swarm/flood.rs b/src/swarm/flood.rs new file mode 100644 index 0000000..39cb096 --- /dev/null +++ b/src/swarm/flood.rs @@ -0,0 +1,65 @@ +//! Flooding (`--dissemination flood`, `swarm::dissemination`): a node pushes every +//! change it gets, at once, to every neighbour but the one it came from. The broadcast +//! HyParView's paper pairs its views with, and what PlumTree prunes down to a tree: the +//! baseline the others are measured against. Every link carries every change about +//! twice (once each way, where both ends got it before the other's push came), so the +//! messages grow with the neighbours each member keeps; the latency is that of the +//! fastest path, with no tree to compute or to repair. + +use async_trait::async_trait; + +use crate::document::ChangeHash; +use crate::state::AppState; +use crate::swarm::dissemination::{Dissemination, pass_on}; +use crate::swarm::topology; +use crate::swarm::tree::Plan; + +pub(crate) struct Flood; + +#[async_trait] +impl Dissemination for Flood { + fn name(&self) -> &'static str { + "flood" + } + + /// Every neighbour gets the writer's changes at once, and is told of them in the slow + /// round too (`Plan::alone`): with every neighbour a child, no round would tell + /// anyone, and a push lost on a lossy link waited for the next write, or a keepalive. + async fn plan(&self, state: &AppState, writer: u64) -> Option { + let _ = writer; + let neighbours = topology::our_neighbours(state); + Some(Plan { + children: neighbours.clone(), + alone: neighbours, + uncovered: Vec::new(), + covered: Vec::new(), + }) + } + + async fn forward( + &self, + state: &AppState, + writer: u64, + from: &str, + changes: &[ChangeHash], + ) -> Option { + let plan = self.plan(state, writer).await?; + Some(pass_on(state, writer, from, changes, plan).await) + } + + /// Counted as the trees' counters count (`/admin/stats`): a push with nothing new as + /// a message from another than the parent. + async fn note_arrival( + &self, + state: &AppState, + peer: &str, + writer: Option, + carried: bool, + authors: &[(String, Vec)], + ) { + let _ = peer; + if writer.is_some() && carried && authors.is_empty() { + state.stats.tree_from_other(); + } + } +} diff --git a/src/swarm/mod.rs b/src/swarm/mod.rs index 63ddcfa..ccffaa0 100644 --- a/src/swarm/mod.rs +++ b/src/swarm/mod.rs @@ -7,6 +7,7 @@ pub(crate) mod bootstrap; pub(crate) mod changes; pub(crate) mod dissemination; pub(crate) mod document_file; +pub(crate) mod flood; pub(crate) mod hop; pub(crate) mod hyparview; pub(crate) mod links; -- cgit v1.3.1