aboutsummaryrefslogtreecommitdiffstats
path: root/src/swarm/tree.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/swarm/tree.rs')
-rw-r--r--src/swarm/tree.rs183
1 files changed, 134 insertions, 49 deletions
diff --git a/src/swarm/tree.rs b/src/swarm/tree.rs
index c84056c..f04e442 100644
--- a/src/swarm/tree.rs
+++ b/src/swarm/tree.rs
@@ -7,7 +7,8 @@
//! (`swarm::reach`). Every member's distance from the writer over that graph orders the
//! members: by distance, then whether it reaches a member a hop closer, then pair key;
//! a member's parent is the neighbour it reaches that comes before it, the closest to
-//! the writer first, then one that reaches closer, then by pair score
+//! the writer first, then one that reaches closer, then the one it has the shortest
+//! round trip to (as it said, a bucket: `rtt::bucket`), then by pair score
//! (`topology::pair_score`). Coming before rules out cycles, and taking only a neighbour
//! it reaches routes around links that don't work: where a writer behind NAT reaches a
//! single member, that one comes first and the others take it.
@@ -32,7 +33,7 @@ use tracing::trace;
use crate::locks::MutexExt;
use crate::state::AppState;
-use crate::swarm::{reach, topology};
+use crate::swarm::{reach, rtt, topology};
/// The writers whose distances are kept at most.
const MAX_WRITERS: usize = 256;
@@ -94,7 +95,7 @@ fn distances(state: &AppState, writer: u64) -> Option<(Arc<Graph>, Arc<HashMap<S
/// Members are ordered by distance from the writer, then whether they reach a member a
/// hop closer (as they say: else, while it hasn't the change from its own side, it is
/// as good as farther), then pair key; a member's parent is the neighbour it reaches
-/// that comes before it, by the same, then pair score. So where the writer reaches few
+/// that comes before it, by the same, then round trip, then pair score. So where the writer reaches few
/// (behind NAT), those it reaches come first among the members as far from it, and the
/// others take them as parents. What a member reaches we know of ourselves and our
/// neighbours, as they said; of others, the graph is taken as right (if we're wrong,
@@ -127,12 +128,15 @@ fn rank(
}
/// `member`'s parent in the writer's tree (`rank`): the neighbour it reaches that comes
-/// before it, the closest to the writer first, then one that reaches closer, then by
-/// pair score; None if none does (or it is the writer).
+/// before it, the closest to the writer first, then one that reaches closer, then the
+/// one it has the shortest round trip to, as it said (`round_trip(member, candidate)`,
+/// a bucket: `rtt::bucket`), then by pair score; None if none does (or it is the
+/// writer).
fn parent<'g>(
graph: &'g Graph,
distance: &HashMap<String, u32>,
reached: &dyn Fn(&str, &str) -> bool,
+ round_trip: &dyn Fn(&str, &str) -> u8,
member: &str,
) -> Option<&'g str> {
let its_rank = rank(graph, distance, reached, member)?;
@@ -147,19 +151,25 @@ fn parent<'g>(
})
.min_by_key(|candidate| {
let (d, far, _) = rank(graph, distance, reached, candidate).expect("ranked");
- (d, far, topology::pair_score(candidate, member))
+ (
+ d,
+ far,
+ round_trip(member, candidate),
+ topology::pair_score(candidate, member),
+ )
})
}
-/// `writer`'s whole tree, as far as `reached` knows whom each member reaches (the
-/// dashboard's map, from the links members report): every member's parent, None for
-/// those without one (they get the writer's changes by announcement). None while the
-/// member list isn't known, or the writer isn't in it.
+/// `writer`'s whole tree, as far as `reached` knows whom each member reaches and
+/// `round_trip` how far (the dashboard's map, from the links members report): every
+/// member's parent, None for those without one (they get the writer's changes by
+/// announcement). None while the member list isn't known, or the writer isn't in it.
#[cfg_attr(not(feature = "dashboard"), allow(dead_code))]
pub(crate) fn whole(
state: &AppState,
writer: &str,
reached: &dyn Fn(&str, &str) -> bool,
+ round_trip: &dyn Fn(&str, &str) -> u8,
) -> Option<BTreeMap<String, Option<String>>> {
let (graph, distance) = distances(state, topology::pair_key(writer))?;
Some(
@@ -167,29 +177,70 @@ pub(crate) fn whole(
.keys()
.filter(|member| distance.get(member.as_str()).is_some_and(|d| *d > 0))
.map(|member| {
- let parent = parent(&graph, &distance, reached, member).map(str::to_owned);
+ let parent =
+ parent(&graph, &distance, reached, round_trip, member).map(str::to_owned);
(member.clone(), parent)
})
.collect(),
)
}
-/// Whom we and our neighbours in `graph` reach, by pair key, as far as we know (our
-/// own, and what our neighbours said).
-async fn known_reaches<'g>(state: &AppState, graph: &'g Graph) -> HashMap<&'g str, Vec<u64>> {
+/// Whom a member reaches, by pair key, and its round trip to each (`rtt::bucket`), as
+/// it said.
+struct Said {
+ keys: Vec<u64>,
+ round_trips: Option<Vec<u8>>,
+}
+
+/// Whom we and our neighbours in `graph` reach, and how far, as far as we know (our
+/// own, and what our neighbours said). Of other members, nothing: the graph is taken as
+/// right, and their round trips as alike.
+struct Known<'g>(HashMap<&'g str, Said>);
+
+impl Known<'_> {
+ /// Whether `by` reaches `member`: as it said, or by the graph.
+ fn reached(&self, by: &str, member: &str) -> bool {
+ self.0
+ .get(by)
+ .is_none_or(|said| said.keys.contains(&topology::pair_key(member)))
+ }
+
+ /// `by`'s round trip to `member`, as a bucket; `rtt::UNKNOWN_BUCKET` if not said.
+ fn round_trip(&self, by: &str, member: &str) -> u8 {
+ let key = topology::pair_key(member);
+ self.0
+ .get(by)
+ .and_then(|said| {
+ let index = said.keys.iter().position(|said| *said == key)?;
+ said.round_trips.as_ref()?.get(index).copied()
+ })
+ .unwrap_or(rtt::UNKNOWN_BUCKET)
+ }
+}
+
+async fn known_reaches<'g>(state: &AppState, graph: &'g Graph) -> Known<'g> {
let me = state.local_id();
- let mut reaches: HashMap<&str, Vec<u64>> = HashMap::new();
+ let mut reaches: HashMap<&str, Said> = HashMap::new();
if let Some((me, _)) = graph.get_key_value(me) {
- reaches.insert(me.as_str(), reach::published(state));
+ let (keys, round_trips) = reach::published_with_round_trips(state);
+ reaches.insert(
+ me.as_str(),
+ Said {
+ keys,
+ round_trips: Some(round_trips),
+ },
+ );
}
for member in graph.get(me).into_iter().flatten() {
- if let Some(peer_state) = state.get_peer_state(member).await
- && let Some(keys) = reach::of(peer_state.lock().await.reaches.as_ref())
- {
- reaches.insert(member.as_str(), keys);
+ if let Some(peer_state) = state.get_peer_state(member).await {
+ let peer_state = peer_state.lock().await;
+ if let Some(keys) = reach::of(peer_state.reaches.as_ref()) {
+ let round_trips = peer_state.round_trips.clone();
+ reaches.insert(member.as_str(), Said { keys, round_trips });
+ }
}
}
- reaches
+ Known(reaches)
}
/// Our own tree, as our writes go along it (`Plan`, as every member computes its part).
@@ -213,13 +264,10 @@ pub(crate) struct Shape {
pub(crate) async fn own_shape(state: &AppState) -> Option<Shape> {
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)))
- };
- Some(shape(&graph, &distance, &reached, me))
+ let known = known_reaches(state, &graph).await;
+ let reached = |by: &str, member: &str| known.reached(by, member);
+ let round_trip = |by: &str, member: &str| known.round_trip(by, member);
+ Some(shape(&graph, &distance, &reached, &round_trip, me))
}
/// `own_shape` over `graph`, from `me` at distance 0.
@@ -227,12 +275,16 @@ fn shape(
graph: &Graph,
distance: &HashMap<String, u32>,
reached: &dyn Fn(&str, &str) -> bool,
+ round_trip: &dyn Fn(&str, &str) -> u8,
me: &str,
) -> Shape {
let parents: HashMap<&str, Option<&str>> = graph
.keys()
.filter(|member| distance.get(member.as_str()).is_some_and(|d| *d > 0))
- .map(|member| (member.as_str(), parent(graph, distance, reached, member)))
+ .map(|member| {
+ let parent = parent(graph, distance, reached, round_trip, member);
+ (member.as_str(), parent)
+ })
.collect();
// Hops from us along parents; None where the chain ends without us. Parents come
// before their children, so chains end.
@@ -275,9 +327,9 @@ fn 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
+/// (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 the
+/// exact latency, not the round-trip bucket it said; 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)]
@@ -297,12 +349,9 @@ pub(crate) async fn own_latencies(
) -> 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 known = known_reaches(state, &graph).await;
+ let reached = |by: &str, member: &str| known.reached(by, member);
+ let round_trip = |by: &str, member: &str| known.round_trip(by, member);
let members: Vec<&str> = graph
.keys()
.map(String::as_str)
@@ -310,7 +359,12 @@ pub(crate) async fn own_latencies(
.collect();
let now: HashMap<&str, Option<&str>> = members
.iter()
- .map(|member| (*member, parent(&graph, &distance, &reached, member)))
+ .map(|member| {
+ (
+ *member,
+ parent(&graph, &distance, &reached, &round_trip, member),
+ )
+ })
.collect();
let faster: HashMap<&str, Option<&str>> = members
.iter()
@@ -428,12 +482,9 @@ pub(crate) async fn plan(state: &AppState, writer: u64) -> Option<Plan> {
if !distance.contains_key(me) {
return None;
}
- 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 known = known_reaches(state, &graph).await;
+ let reached = |by: &str, member: &str| known.reached(by, member);
+ let round_trip = |by: &str, member: &str| known.round_trip(by, member);
let my_rank = rank(&graph, &distance, &reached, me)?;
let my_key = topology::pair_key(me);
let mut children = Vec::new();
@@ -448,14 +499,15 @@ pub(crate) async fn plan(state: &AppState, writer: u64) -> Option<Plan> {
covered.push(member.clone());
continue;
}
- match parent(&graph, &distance, &reached, member) {
+ match parent(&graph, &distance, &reached, &round_trip, member) {
None => uncovered.push(member.clone()),
Some(parent)
if parent == me && its_rank > my_rank && topology::reaches(state, member).await =>
{
- if reaches
+ if known
+ .0
.get(member.as_str())
- .is_some_and(|keys| keys.iter().all(|key| *key == my_key))
+ .is_some_and(|said| said.keys.iter().all(|key| *key == my_key))
{
alone.push(member.clone());
}
@@ -549,6 +601,33 @@ pub(crate) async fn forward(
mod tests {
use super::*;
+ /// Of the members as close to the writer and as well placed, the one a member has
+ /// the shorter round trip to is its parent, whatever the pair scores.
+ #[test]
+ fn the_nearer_parent_wins() {
+ let mut graph = Graph::new();
+ for (a, b) in [("w", "a"), ("w", "b"), ("a", "c"), ("b", "c")] {
+ graph.entry(a.into()).or_default().insert(b.into());
+ graph.entry(b.into()).or_default().insert(a.into());
+ }
+ let distance: HashMap<String, u32> = [("w", 0), ("a", 1), ("b", 1), ("c", 2)]
+ .into_iter()
+ .map(|(member, d)| (member.to_owned(), d))
+ .collect();
+ let reached = |_: &str, _: &str| true;
+ for (near, far) in [("a", "b"), ("b", "a")] {
+ let round_trip = |by: &str, member: &str| match (by, member) {
+ ("c", m) if m == near => 1,
+ ("c", m) if m == far => 5,
+ _ => rtt::UNKNOWN_BUCKET,
+ };
+ assert_eq!(
+ parent(&graph, &distance, &reached, &round_trip, "c"),
+ Some(near)
+ );
+ }
+ }
+
/// Hops along parents from us; members without a parent, below one without, or
/// not connected count as off the tree.
#[test]
@@ -570,7 +649,13 @@ mod tests {
// c doesn't reach us: no parent, nor e below it.
let reached = |by: &str, member: &str| !(by == "c" && member == "me");
assert_eq!(
- shape(&graph, &distance, &reached, "me"),
+ shape(
+ &graph,
+ &distance,
+ &reached,
+ &|_, _| rtt::UNKNOWN_BUCKET,
+ "me"
+ ),
Shape {
members: 2,
depth: 2,