diff options
| -rw-r--r-- | src/swarm/topology.rs | 87 |
1 files changed, 65 insertions, 22 deletions
diff --git a/src/swarm/topology.rs b/src/swarm/topology.rs index 84ae1cd..4d37f6f 100644 --- a/src/swarm/topology.rs +++ b/src/swarm/topology.rs @@ -214,7 +214,7 @@ pub(crate) async fn refresh(state: &AppState) -> Option<NeighbourChange> { } const RING_LABEL: &[u8] = b"continuum/topology-ring/1"; -const PAIR_LABEL: &[u8] = b"continuum/topology-pair/1"; +const PAIR_LABEL: &[u8] = b"continuum/topology-pair/2"; /// How many members may prefer the same stable member, as a multiple of `k`. Without a /// bound, 20 stable members among 2000 get about 500 neighbours each: every @@ -239,9 +239,11 @@ pub(crate) fn neighbours( .unwrap_or_default() } -/// Every reachable member's neighbours. Costs about N² hashes (a few milliseconds for -/// hundreds of members). `stable` members (`swarm::stability`) are preferred for half of -/// each member's scored slots, each by at most `STABLE_FANIN_FACTOR * k` members. +/// Every reachable member's neighbours. Hashes each member once and scores pairs by +/// mixing the two hashes (`pair_score`), so the N² scores are a few nanoseconds each: +/// tens of milliseconds for thousands of members. `stable` members (`swarm::stability`) +/// are preferred for half of each member's scored slots, each by at most +/// `STABLE_FANIN_FACTOR * k` members. /// /// Each reachable member walks the ring (by key hash) both ways to the first reachable /// member, which gives a ring over the reachable members, and adds the `k - 2` @@ -296,42 +298,54 @@ pub(crate) fn graph( .expect("more than k + 1 live members") }; - // How many members have preferred each stable member so far (`live` iterates in key + // Live members in key order, with their pair keys; and those of them that are stable. + let keyed: Vec<(&str, u64)> = live.iter().map(|m| (*m, pair_key(m))).collect(); + let stable_keyed: Vec<(&str, u64)> = keyed.iter().copied().filter(|(m, _)| stable(m)).collect(); + + // How many members have preferred each stable member so far (`keyed` is in key // order, the same on every node). let budget = STABLE_FANIN_FACTOR * k; let mut preferred_by: BTreeMap<&str, usize> = BTreeMap::new(); + // Half the slots (rounded up) prefer stable members, so long-running nodes form a + // backbone; the rest go by pair score alone, keeping paths short. A stable member + // enough others prefer already is skipped, so no hub grows with the swarm. + let stable_slots = (k - 2).div_ceil(2); - for member in &live { + for &(member, key) in &keyed { let at = position[member]; let next = first_live(at, 1); let prev = first_live(at, n - 1); link(member, next); link(member, prev); - let mut candidates: Vec<([u8; 32], &str)> = live - .iter() - .copied() - .filter(|other| other != member && *other != next && *other != prev) - .map(|other| (pair_score(member, other), other)) - .collect(); - candidates.sort_unstable(); - // Half the slots (rounded up) prefer stable members, so long-running nodes form - // a backbone; the rest go by pair score alone, keeping paths short. A stable - // member enough others prefer already is skipped, so no hub grows with the swarm. - let stable_slots = (k - 2).div_ceil(2); - let preferred: Vec<&str> = candidates + let skip = [member, next, prev]; + // The stable candidates in score order (there are few). + let mut stable_candidates = scored(&stable_keyed, key, skip); + stable_candidates.sort_unstable(); + let preferred: Vec<&str> = stable_candidates .iter() .map(|(_, other)| *other) - .filter(|other| stable(other) && preferred_by.get(other).copied().unwrap_or(0) < budget) + .filter(|other| preferred_by.get(other).copied().unwrap_or(0) < budget) .take(stable_slots) .collect(); for other in preferred.iter().copied() { *preferred_by.entry(other).or_default() += 1; } + // The rest: the lowest scores among the others that aren't preferred, which are + // among the `need + preferred` lowest overall. Selecting those is linear; only + // they are sorted. + let need = k - 2 - preferred.len(); + let mut candidates = scored(&keyed, key, skip); + let lowest = (need + preferred.len()).min(candidates.len()); + if lowest < candidates.len() { + candidates.select_nth_unstable(lowest); + candidates.truncate(lowest); + } + candidates.sort_unstable(); let rest = candidates .iter() .map(|(_, other)| *other) .filter(|other| !preferred.contains(other)) - .take(k - 2 - preferred.len()); + .take(need); for partner in preferred.iter().copied().chain(rest) { link(member, partner); } @@ -339,10 +353,39 @@ pub(crate) fn graph( links } +/// `others` but those in `skip`, scored as pairs with the member whose key is `key`. +fn scored<'a>(others: &[(&'a str, u64)], key: u64, skip: [&str; 3]) -> Vec<(u64, &'a str)> { + others + .iter() + .filter(|(other, _)| !skip.contains(other)) + .map(|&(other, other_key)| (mix_pair(key, other_key), other)) + .collect() +} + /// Symmetric: the same for (a, b) and (b, a). -pub(crate) fn pair_score(a: &str, b: &str) -> [u8; 32] { +pub(crate) fn pair_score(a: &str, b: &str) -> u64 { + mix_pair(pair_key(a), pair_key(b)) +} + +/// What a member contributes to its pair scores: computed once per member. +fn pair_key(member: &str) -> u64 { + let digest = hash(PAIR_LABEL, &[member]); + u64::from_be_bytes(digest[..8].try_into().expect("8 bytes")) +} + +/// The score of a pair from its members' keys, symmetric: SplitMix64's finalizer over +/// the lower key and the mixed higher one. Keys are uniform (SHA-256), so for each member +/// the others' scores are in an order unrelated to anyone else's. +fn mix_pair(a: u64, b: u64) -> u64 { let (low, high) = if a <= b { (a, b) } else { (b, a) }; - hash(PAIR_LABEL, &[low, high]) + mix(low ^ mix(high)) +} + +fn mix(mut z: u64) -> u64 { + z = z.wrapping_add(0x9e37_79b9_7f4a_7c15); + z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9); + z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb); + z ^ (z >> 31) } fn hash(label: &[u8], fields: &[&str]) -> [u8; 32] { |