compute member pair scores cheaply

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] {