diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/simtest/bench.rs | 40 | ||||
| -rw-r--r-- | src/swarm/tree.rs | 131 | ||||
| -rw-r--r-- | src/transport/sim.rs | 10 |
3 files changed, 178 insertions, 3 deletions
diff --git a/src/simtest/bench.rs b/src/simtest/bench.rs index 19603d2..40b413d 100644 --- a/src/simtest/bench.rs +++ b/src/simtest/bench.rs @@ -550,14 +550,16 @@ async fn run(seed: u64, scenario: &'static Scenario) -> String { (start, Totals::of(&nodes).await), converged, ); - trees(&mut out, &nodes).await; + trees(&mut out, &nodes, &sim.net).await; } out } /// Every node's own writer's tree (`swarm::tree::own_shape`, `/admin/stats`), as it -/// computes it at the end: the hops its writes take, and the members it leaves out. -async fn trees(out: &mut String, nodes: &[AppState]) { +/// computes it at the end: the hops its writes take, and the members it leaves out; +/// and how long they take by the links' latencies alone, against parents chosen by +/// latency and the fastest paths (`swarm::tree::own_latencies`). +async fn trees(out: &mut String, nodes: &[AppState], net: &crate::transport::sim::SimNet) { let mut shapes = Vec::new(); for node in nodes { shapes.extend(crate::swarm::tree::own_shape(node).await); @@ -586,6 +588,38 @@ async fn trees(out: &mut String, nodes: &[AppState]) { }, off as f64 / count, ); + + // Node IDs to the net's names (each node's alias). + let names: std::collections::HashMap<String, String> = nodes + .iter() + .filter_map(|node| Some((node.local_id().to_owned(), node.alias.clone()?))) + .collect(); + let latency = |from: &str, to: &str| match (names.get(from), names.get(to)) { + (Some(from), Some(to)) => net.mean_delay(from, to).as_secs_f64() * 1000.0, + _ => f64::NAN, + }; + let mut latencies = Vec::new(); + for node in nodes { + latencies.extend(crate::swarm::tree::own_latencies(node, &latency).await); + } + let members: usize = latencies.iter().map(|l| l.members).sum(); + if members == 0 { + return; + } + let mean = |of: fn(&crate::swarm::tree::Latencies) -> f64| { + latencies + .iter() + .map(|l| of(l) * l.members as f64) + .sum::<f64>() + / members as f64 + }; + let _ = writeln!( + out, + " by link latency, to a member: {:.0} ms along own trees; {:.0} ms with parents chosen by latency; {:.0} ms by the fastest paths", + mean(|l| l.tree), + mean(|l| l.by_latency), + mean(|l| l.fastest), + ); } /// The workload's counts (`during`), and the quiet phase's for as long. diff --git a/src/swarm/tree.rs b/src/swarm/tree.rs index d6d4a35..c84056c 100644 --- a/src/swarm/tree.rs +++ b/src/swarm/tree.rs @@ -273,6 +273,137 @@ fn shape( shape } +/// How long our writes take to reach the members along our own tree, by link latency +/// alone (the bench's, which knows each link's): the mean over the members it reaches +/// (and the others do), against two other trees of ours. In one, each member's parent is chosen as now, but +/// among those as close to us and as well placed (`rank`) by latency before pair +/// score; in the other, every member takes the fastest path over the links members +/// reach (no tree computed alike everywhere gets below it). In milliseconds, one way. +#[cfg(test)] +#[derive(Debug, Clone, Copy)] +pub(crate) struct Latencies { + pub(crate) members: usize, + pub(crate) tree: f64, + pub(crate) by_latency: f64, + pub(crate) fastest: f64, +} + +/// `Latencies` of our own tree, by `latency(from, to)` in milliseconds; None while the +/// member list isn't known, or we aren't in it, or the tree reaches nobody. +#[cfg(test)] +pub(crate) async fn own_latencies( + state: &AppState, + latency: &(dyn Fn(&str, &str) -> f64 + Sync), +) -> Option<Latencies> { + let me = state.local_id(); + let (graph, distance) = distances(state, topology::pair_key(me))?; + let reaches = known_reaches(state, &graph).await; + let reached = |by: &str, member: &str| { + reaches + .get(by) + .is_none_or(|keys| keys.contains(&topology::pair_key(member))) + }; + let members: Vec<&str> = graph + .keys() + .map(String::as_str) + .filter(|member| distance.get(*member).is_some_and(|d| *d > 0)) + .collect(); + let now: HashMap<&str, Option<&str>> = members + .iter() + .map(|member| (*member, parent(&graph, &distance, &reached, member))) + .collect(); + let faster: HashMap<&str, Option<&str>> = members + .iter() + .map(|member| { + let its_rank = rank(&graph, &distance, &reached, member); + let candidate = graph + .get(*member) + .into_iter() + .flatten() + .map(String::as_str) + .filter(|candidate| { + its_rank.is_some_and(|its| { + rank(&graph, &distance, &reached, candidate).is_some_and(|r| r < its) + }) && reached(member, candidate) + }) + .min_by(|a, b| { + let (da, fa, _) = rank(&graph, &distance, &reached, a).expect("ranked"); + let (db, fb, _) = rank(&graph, &distance, &reached, b).expect("ranked"); + (da, fa) + .cmp(&(db, fb)) + .then(latency(a, member).total_cmp(&latency(b, member))) + .then(topology::pair_score(a, member).cmp(&topology::pair_score(b, member))) + }); + (*member, candidate) + }) + .collect(); + // Arrival along parents; None where the chain ends without us. Parents come + // before their children, so chains end. + fn arrival<'g>( + member: &'g str, + parents: &HashMap<&'g str, Option<&'g str>>, + latency: &dyn Fn(&str, &str) -> f64, + known: &mut HashMap<&'g str, Option<f64>>, + ) -> Option<f64> { + if let Some(at) = known.get(member) { + return *at; + } + let at = parents.get(member).copied().flatten().and_then(|parent| { + arrival(parent, parents, latency, known).map(|at| at + latency(parent, member)) + }); + known.insert(member, at); + at + } + let arrivals = |parents: &HashMap<&str, Option<&str>>| -> HashMap<&str, f64> { + let mut known = HashMap::from([(me, Some(0.0))]); + members + .iter() + .filter_map(|member| { + arrival(member, parents, latency, &mut known).map(|at| (*member, at)) + }) + .collect() + }; + let (now, faster) = (arrivals(&now), arrivals(&faster)); + // The fastest paths: Dijkstra over the links members reach (a parent `p` of + // `c` where `c` reaches `p`), from us. + let mut fastest: HashMap<&str, f64> = HashMap::from([(me, 0.0)]); + let mut done = std::collections::HashSet::new(); + while let Some((&next, &at)) = fastest + .iter() + .filter(|(member, _)| !done.contains(*member)) + .min_by(|a, b| a.1.total_cmp(b.1)) + { + done.insert(next); + for other in graph.get(next).into_iter().flatten().map(String::as_str) { + if !reached(other, next) { + continue; + } + let through = at + latency(next, other); + if fastest.get(other).is_none_or(|known| through < *known) { + fastest.insert(other, through); + } + } + } + // Over the members all three reach (the other tree may leave out others than ours). + let common: Vec<&str> = now + .keys() + .copied() + .filter(|member| faster.contains_key(member) && fastest.contains_key(member)) + .collect(); + if common.is_empty() { + return None; + } + let mean = |times: &HashMap<&str, f64>| { + common.iter().map(|member| times[member]).sum::<f64>() / common.len() as f64 + }; + Some(Latencies { + members: common.len(), + tree: mean(&now), + by_latency: mean(&faster), + fastest: mean(&fastest), + }) +} + /// What `writer`'s tree means for us: our children in it, and our neighbours it leaves /// out (`uncovered`). pub(crate) struct Plan { diff --git a/src/transport/sim.rs b/src/transport/sim.rs index d218d5c..12f3885 100644 --- a/src/transport/sim.rs +++ b/src/transport/sim.rs @@ -170,6 +170,16 @@ impl SimNet { .insert((from.to_owned(), to.to_owned()), params); } + /// The mean delay from `from` to `to` (one way): its link's, or the default's. + pub(crate) fn mean_delay(&self, from: &str, to: &str) -> Duration { + let inner = self.lock(); + let link = inner + .links + .get(&(from.to_owned(), to.to_owned())) + .unwrap_or(&inner.default_link); + (link.delay.0 + link.delay.1) / 2 + } + /// Everything to and from `id` is lost until [`bring_up`](Self::bring_up), including /// messages already on their way. The node itself keeps running. pub(crate) fn take_down(&self, id: &str) { |