trees at runtime

8 files changed, 97 insertions, 2 deletions

diff --git a/docs/measurements.md b/docs/measurements.md
index b5c3d6e..f57db9b 100644
--- a/docs/measurements.md
+++ b/docs/measurements.md
@@ -86,6 +86,8 @@ or caught up over many small messages.
 | `relay.pulls` | `pulls_total` | Pulls of changes we lacked from a neighbour that announced them. |
 | `relay.pullsQueued` | `pulls_queued_total` | Announcements of heads we lacked that waited for the pull in progress. Many compared with `pulls`: changes arrive from several sides at once. |
 | `relay.treeForwards` | `tree_forwards_total` | Changes passed on along writers' trees ([`peers.md`](peers.md)): a sync message per child, at once, instead of an announcement and a pull. |
+| `relay.treeFromOthers` | `tree_from_others_total` | Sync messages along a writer's tree, carrying changes, from a peer other than our parent in it: a change sent twice, or the parent and the child working out the tree differently. Near zero while the trees work; against `treeForwards` swarm-wide, the share of passes that went to the wrong child. |
+| `relay.treeMissed` | `tree_missed_total` | Changes of writers in whose trees this node has a parent that came another way (pulled, with an answer, in a delta): the tree didn't bring them, or not first. Some while members come and go; growing with every write, a tree that doesn't work here. |
 | `relay.blobRequestsDropped` | `blob_requests_dropped_total` | Blob requests not answered because too many were being answered; the requester asks again or asks another peer. Also logged as a warning, at most once a minute with the count. |
 
 ## Topology
diff --git a/docs/openapi.yaml b/docs/openapi.yaml
index d9d6c04..5ca41b0 100644
--- a/docs/openapi.yaml
+++ b/docs/openapi.yaml
@@ -2050,7 +2050,7 @@ components:
               type: integer
         relay:
           type: object
-          required: [announceRounds, treelessRounds, slowRounds, pulls, pullsQueued, treeForwards, blobRequestsDropped]
+          required: [announceRounds, treelessRounds, slowRounds, pulls, pullsQueued, treeForwards, treeFromOthers, treeMissed, blobRequestsDropped]
           properties:
             announceRounds:
               type: integer
@@ -2064,6 +2064,10 @@ components:
               type: integer
             treeForwards:
               type: integer
+            treeFromOthers:
+              type: integer
+            treeMissed:
+              type: integer
             blobRequestsDropped:
               type: integer
         topology:
diff --git a/src/api/stats.rs b/src/api/stats.rs
index 2af6549..8eaff0c 100644
--- a/src/api/stats.rs
+++ b/src/api/stats.rs
@@ -146,6 +146,11 @@ struct RelayStats {
     pulls_queued: u64,
     /// Changes passed on along writers' trees, per child (`swarm::tree`).
     tree_forwards: u64,
+    /// Sync messages along a writer's tree, carrying changes, from a peer other than our
+    /// parent in it; and changes of writers in whose trees we have a parent that came
+    /// another way (`tree::note_arrival`).
+    tree_from_others: u64,
+    tree_missed: u64,
     /// Blob requests not answered: too many were being answered.
     blob_requests_dropped: u64,
 }
@@ -374,6 +379,8 @@ pub(crate) async fn collect(state: &AppState, list: &PeerListResponse) -> StatsR
             pulls: node.relay.pulls,
             pulls_queued: node.relay.pulls_queued,
             tree_forwards: node.relay.tree_forwards,
+            tree_from_others: node.relay.tree_from_others,
+            tree_missed: node.relay.tree_missed,
             blob_requests_dropped: node.blob_requests_dropped,
         },
         topology: TopologyStats {
diff --git a/src/api/stats/prometheus.rs b/src/api/stats/prometheus.rs
index fb8b890..8b8ca1c 100644
--- a/src/api/stats/prometheus.rs
+++ b/src/api/stats/prometheus.rs
@@ -669,6 +669,18 @@ pub(super) fn render(stats: &StatsResponse, list: &PeerListResponse) -> String {
         relay.tree_forwards as f64,
     );
     out.single(
+        "tree_from_others_total",
+        "counter",
+        "Sync messages along a writer's tree, carrying changes, from a peer other than our parent in it.",
+        relay.tree_from_others as f64,
+    );
+    out.single(
+        "tree_missed_total",
+        "counter",
+        "Changes of writers in whose trees we have a parent that came another way.",
+        relay.tree_missed as f64,
+    );
+    out.single(
         "blob_requests_dropped_total",
         "counter",
         "Blob requests not answered: too many were being answered.",
diff --git a/src/simtest/bench.rs b/src/simtest/bench.rs
index e8e452c..493936f 100644
--- a/src/simtest/bench.rs
+++ b/src/simtest/bench.rs
@@ -363,6 +363,8 @@ impl Totals {
             relay.pulls += stats.relay.pulls;
             relay.pulls_queued += stats.relay.pulls_queued;
             relay.tree_forwards += stats.relay.tree_forwards;
+            relay.tree_from_others += stats.relay.tree_from_others;
+            relay.tree_missed += stats.relay.tree_missed;
             relay.delivered += stats.relay.delivered;
             relay.delivered_bytes += stats.relay.delivered_bytes;
             relay.framed += stats.relay.framed;
@@ -955,6 +957,12 @@ fn report(
         (r1.pulls_queued - r0.pulls_queued) as f64 / writes,
         (r1.tree_forwards - r0.tree_forwards) as f64 / writes,
     );
+    let _ = writeln!(
+        out,
+        "    trees as the nodes see them (`/admin/stats`), per write: {:.2} sync messages along a tree from another than the parent, {:.2} changes the trees didn't bring",
+        (r1.tree_from_others - r0.tree_from_others) as f64 / writes,
+        (r1.tree_missed - r0.tree_missed) as f64 / writes,
+    );
     let per = |count: u64, bytes: u64| {
         let count = count as f64;
         (
diff --git a/src/swarm/stats.rs b/src/swarm/stats.rs
index 5cac16a..ed12888 100644
--- a/src/swarm/stats.rs
+++ b/src/swarm/stats.rs
@@ -124,6 +124,13 @@ pub(crate) struct Relay {
     /// Changes passed on along writers' trees (`swarm::tree`): a sync message asked for
     /// per child.
     pub(crate) tree_forwards: u64,
+    /// Whether the trees work, from what arrives (`tree::note_arrival`): sync messages
+    /// along a writer's tree, carrying changes, from a peer other than our parent in it
+    /// (a double send, or views of the tree that differ); and changes of writers in
+    /// whose trees we have a parent that came another way (pulled, with an answer, in
+    /// a delta: the tree didn't bring them).
+    pub(crate) tree_from_others: u64,
+    pub(crate) tree_missed: u64,
     /// Sync messages sent taken as delivered (`SyncSession::assume_delivered`), and their
     /// payload's bytes.
     pub(crate) delivered: u64,
@@ -275,6 +282,16 @@ impl NodeStats {
         self.lock().relay.tree_forwards += 1;
     }
 
+    /// A sync message along a writer's tree came from a peer other than our parent in it.
+    pub(crate) fn tree_from_other(&self) {
+        self.lock().relay.tree_from_others += 1;
+    }
+
+    /// `count` changes of a writer in whose tree we have a parent came another way.
+    pub(crate) fn tree_missed(&self, count: usize) {
+        self.lock().relay.tree_missed += count as u64;
+    }
+
     /// A blob chunk of `bytes` was served as `sent` bytes (fewer if deflated).
     pub(crate) fn chunk_served(&self, bytes: usize, sent: usize) {
         let mut inner = self.lock();
diff --git a/src/swarm/sync.rs b/src/swarm/sync.rs
index a4ad30c..66fa4a5 100644
--- a/src/swarm/sync.rs
+++ b/src/swarm/sync.rs
@@ -686,6 +686,9 @@ pub(crate) async fn handle_sync(
     state.notify_store_changed();
 
     crate::swarm::relay::pulled(state, peer);
+    if state.initial_sync_done.load(Ordering::Acquire) && !just_caught_up {
+        crate::swarm::tree::note_arrival(state, peer, writer, carried, &authors).await;
+    }
     // Caught up: our other neighbours may lack what the source had.
     if changed || just_caught_up {
         let writers: Vec<(u64, Vec<crate::document::ChangeHash>)> = authors
diff --git a/src/swarm/tree.rs b/src/swarm/tree.rs
index b9491b3..064f5b9 100644
--- a/src/swarm/tree.rs
+++ b/src/swarm/tree.rs
@@ -363,13 +363,55 @@ pub(crate) struct Latencies {
 /// neighbours said); None if we have none, or no tree is known.
 #[cfg(test)]
 pub(crate) async fn own_parent(state: &AppState, writer: &str) -> Option<String> {
-    let (graph, distance) = distances(state, topology::pair_key(writer))?;
+    our_parent(state, topology::pair_key(writer)).await
+}
+
+/// `own_parent`, of the writer by pair key.
+async fn our_parent(state: &AppState, writer: u64) -> Option<String> {
+    let (graph, distance) = distances(state, writer)?;
     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);
     parent(&graph, &distance, &reached, &round_trip, state.local_id()).map(str::to_owned)
 }
 
+/// Whether the trees work, from what arrives (`swarm::stats`, `/admin/stats`): a sync
+/// message from `peer` along `writer`'s tree that `carried` changes, where we have a
+/// parent in it and it isn't `peer` (a double send, or views of the tree that differ);
+/// the changes of `authors` (by author) that came with a message along no tree, where
+/// we have a parent in their writer's tree (the tree didn't bring them, or not first).
+/// Not while catching up, when everything comes another way.
+pub(crate) async fn note_arrival(
+    state: &AppState,
+    peer: &str,
+    writer: Option<u64>,
+    carried: bool,
+    authors: &[(String, Vec<crate::document::ChangeHash>)],
+) {
+    match writer {
+        Some(writer) if carried => {
+            if our_parent(state, writer)
+                .await
+                .is_some_and(|parent| parent != peer)
+            {
+                state.stats.tree_from_other();
+            }
+        }
+        None => {
+            for (author, changes) in authors {
+                if author != state.local_id()
+                    && our_parent(state, topology::pair_key(author))
+                        .await
+                        .is_some()
+                {
+                    state.stats.tree_missed(changes.len());
+                }
+            }
+        }
+        Some(_) => {}
+    }
+}
+
 /// Where we are in `writer`'s tree, as we see it: our distance from the writer, our
 /// parent (`parent`), and the neighbours we reach that come before us (whom we could
 /// take). None while the member list isn't known, or the writer or we aren't in it.