← Priority list

Eliminate O(N��) bookkeeping in the url:// resolver gossip/discovery layer (no per-node structure may grow N�� in node count)

Durable follow-up to the 2026-07-19 buildtest gossip-storm incident. The resolver's forwardedDiscoveredServices table is keyed by (destinationPeerId, serviceIdentifier, providerPeerId) �� inherently O(N��) in mesh nodes. The immediate fix (resolver 0.0.640) only evicts dead peers + caps at 50k; this handoff's goal is to redesign discovery/forwarding state to be O(#services) per node, never O(peer-pairs), and to audit/eliminate all other N�� structures in UrlResolver/UrlProtocol.

hf-2026-07-19-eliminate-o-n-bookkeeping-in-the-url-resolver-gossip-discovery-layer-no-per-node-structure-may-grow-n-in-node-count

Edit handoff

Title Summary Markdown body

# Eliminate O(N²) bookkeeping in the url:// resolver gossip/discovery layer

**Written:** 2026-07-19 ~07:15Z by Claude (supervisor session).
**RE-VERIFY banner:** Everything below is a write-time snapshot. Before acting, re-verify: (a) the immediate
fix's deployed versions with `~/bin/coursier resolve foundation.url:resolver:0.0.640` and the running
buildtest node's live gossip count on 198.199.106.165; (b) branch/SHA state with `git` in a fresh clone of
UrlResolver. A fresh query always wins over this document.

## Mission
Enforce a hard architectural invariant across the url:// resolver / protocol layer:

> **No per-node data structure may grow as O(N²) in the number of mesh nodes.**

Discovery/forwarding state per node must be **O(#distinct services)** (≈O(N)), never O(peer-pairs). This is the
durable follow-up to the 2026-07-19 buildtest gossip-storm incident. The incident's immediate fix bounds and
evicts the leak, but the LIVE table it fixed is *inherently* O(N²) — a 50k safety cap papers over the shape;
it does not fix it.

## What was found (incident + diagnosis)
- **Symptom:** `https://buildtest.kotlin.build/` down (hang → 503). Mesh-wide url:// gossip storm; host
  198.199.106.165 load 60→90+; every url:// node GC-thrashing; buildtest-server backends OOM-respawning
  (7 heapdumps in /root/ContainerNursery/heapdumps, 4 on 2026-07-19).
- **Dominant heap object:** `foundation.url.resolver.UrlProtocol2$ForwardedDiscoveredServiceState` — 48k–82k
  live instances per node (matched with equal-count `...Key`), surviving full GC. This is the
  `forwardedDiscoveredServices` map in `UrlResolver`.
- **The offending structure:** `ConcurrentHashMap<ForwardedDiscoveredServiceKey, ForwardedDiscoveredServiceState>`
  keyed by the TRIPLE **(destinationPeerId, serviceIdentifier, providerPeerId)** — one row per
  *(who-I-told × which-service × who-provides-it)*. It is a forwarding-dedup / relay table.
- **Why it explodes — three compounding causes:**
  1. **N² by construction:** two peer dimensions (destination × provider) → even a *healthy* live table is
     O(destinations × services × providers) ≈ O(N²). Only ~15–30 real services exist; the size is driven by
     the *peer* dimensions, not the services.
  2. **No eviction of departed peers** (the leak fixed immediately): every ephemeral build droplet / netlab
     worker is a fresh libp2p peerId; its rows were never removed when it died, so dead peers accumulated
     forever.
  3. **Replay-on-connect amplifier** (UrlResolver.kt ~line 9665): when a peer connects, the relay forwards
     ALL known announcements to it. A freshly-restarted node instantly *inherits* the accumulated stale set
     replayed from the other (unfixed) nodes — observed refill to ~47k in 3 min with **zero** live droplets.
- **Consequence proven:** restarting nodes or killing droplets cannot fix it — replay re-floods any fresh
  node from the wider mesh. A per-node eviction fix keeps ONE node healthy (it prunes what it receives), which
  is why no fleet redeploy is needed to restore a single service.

## What was done (immediate fix — necessary, NOT sufficient)
- Branch `fix/buildtest-gossip-stale-peer-amplification` on UrlResolver, head SHA `96910f90`
  ("Release UrlResolver 0.0.640"), based on top of the parallel dead-transport fix.
- Adds `removeForwardedDiscoveredServiceStateForDestination(peerId)` wired into peer prune/disconnect
  (UrlResolver.kt:2937, 8505, 9776); hard cap `maxForwardedDiscoveredServices = 50_000`; periodic prune
  (`forwardedDiscoveredServicesPruneIntervalMs = 60_000`); replay backoff
  (`discoveredServiceReplayBackoffMs = 5 min`).
- Published **foundation.url:resolver:0.0.640**; **buildtest.server:buildtest-server-service:0.0.181**
  (pins 0.0.640). Manual deploy of 0.0.181 to the buildtest node was IN FLIGHT at write time (reviews skipped
  per user for incident speed).
- Host interim mitigations (198.199.106.165): `BUILDTEST_DROPLET_LIMIT` 75→10, `MAX_LIVE_ENVIRONMENTS` 60→5
  (config.json; applied via CN restart — CN caches config at startup), all DO build/netlab droplets culled.
- **Result: the leak from DEAD peers is bounded; the LIVE table is still O(N²). The 50k cap is a ceiling, not
  the fix this handoff targets.**

## The actual goal of THIS handoff — make discovery state sub-N²
Redesign so per-node discovery/forwarding state is O(#services) (≈O(N)), never O(peer-pairs). Directions:
1. **Drop the `destinationPeerId` dimension from the forwarding dedup (smallest change, biggest win).**
   Dedup by *announcement identity* — messageId, or `(serviceIdentifier, providerPeerId, version)` — a
   per-announcement seen-set of size O(#services). Senders must NOT track every recipient; receivers dedupe
   on messageId. Collapses O(destinations × services) → O(services).
2. **Replace flood-and-remember with proper gossip / anti-entropy.** Per-node state = the current service set
   (O(#services)); fanout O(log N) per round; convergence via version vectors / Merkle-diff rather than
   per-pair bookkeeping.
3. **Consider DHT / structured-overlay discovery** (Kademlia-style): service records held at O(log N) nodes and
   looked up on demand — no node holds per-peer-pair state at all.

## Acceptance criteria
- A scale/churn test (e.g. 10→50→200 simulated peers with join/leave churn) shows per-node discovery memory
  **flat or linear**, not quadratic — assert on heap-histo counts of the discovery structures across N.
- **Audit UrlResolver AND UrlProtocol for every OTHER per-peer-pair (N²) structure** — anything keyed by
  (peerA, peerB) or (peer × peer-derived) — and eliminate/bound each. Enumerate them in the PR.
- The invariant "no per-node structure is O(N²) in node count" is documented (DocumentationRepository, url://
  resolver architecture) and guarded by the scale test above.

## Relevant refs
- Repo: https://github.com/CodexCoder21Organization/UrlResolver
- `ForwardedDiscoveredServiceKey` @ `src/foundation/url/resolver/UrlResolver.kt:545`; State @ :551;
  map decl + cap/prune fields @ ~:557.
- Add-site: `shouldForwardDiscoveredServiceToPeer` @ ~`:9680`; replay-on-connect comment @ ~`:9665`.
- Eviction hooks (immediate fix): `:2937`, `:8505`, `:9723`–`:9776`.
- Fix branch: `fix/buildtest-gossip-stale-peer-amplification` (head `96910f90`).
- Published: `foundation.url:resolver:0.0.640`, `buildtest.server:buildtest-server-service:0.0.181`.
- Related memory: `buildtest-pending-wedge-dead-transport` (parallel dead-transport fix → resolver 0.0.638).
- Incident evidence: `/root/buildtest-data/retained-run-forensics/outage-20260719T0515Z/` on 198.199.106.165
  (live + OOM heap dumps dominated by ForwardedDiscoveredService; jstacks; CN log slices).

## Next steps
1. Re-verify the immediate fix is deployed and the live buildtest node's ForwardedDiscoveredService count stays
   bounded (small/flat, not climbing) — that closes the incident; THIS handoff is the durable redesign.
2. Prototype direction (1) — drop the destination dimension — and measure per-node state vs N.
3. Run the N²-structure audit across UrlResolver + UrlProtocol; list every offender.
4. Choose gossip-anti-entropy vs DHT for the durable design; write an ADR.
5. Enforce the invariant with the scale test + documentation.

## Reusable / operational knowledge
- The "gossip messages" are forwarding-dedup **rows**, not messages: the same ~15–30 services recorded under
  thousands of distinct (mostly-dead) peer identities — a history leak, not a service explosion.
- Restarting CN / killing droplets does NOT kill the storm — replay-on-connect re-floods fresh nodes from the
  wider mesh in minutes. Only per-node eviction (immediate fix) and sub-N² redesign (this handoff) fix it.
- Host access is SSH `ssh -p 23 root@198.199.106.165` (fabric certs absent on the /code box). CN caches
  config.json at startup — config env changes need a CN restart to take effect.

## Required engineering rigor (implement it properly — do NOT shortcut like the incident fixes did)
1. **Fail-first reproducer/scale test** demonstrating the defect (FAILS before the change, PASSES after). Real
   instances, no mocks; per the Testing Architecture doc.
2. Implement the change at the owning layer.
3. **Test-comprehensiveness review** + **adversarial code review** via codex gpt-5.6-sol (high reasoning); address findings.
4. **Final review (Claude)** against the problem, CLAUDE.md, PHILOSOPHY; route findings back to codex.
5. **Drive the PR(s) to green CI and MERGE.** This handoff is NOT done until merged.

Add dependency

Complete this handoff

Moves it out of every priority list and into ArchiveArea.

Handoff document

Markdown

Eliminate O(N²) bookkeeping in the url:// resolver gossip/discovery layer

Written: 2026-07-19 ~07:15Z by Claude (supervisor session). RE-VERIFY banner: Everything below is a write-time snapshot. Before acting, re-verify: (a) the immediate fix's deployed versions with ~/bin/coursier resolve foundation.url:resolver:0.0.640 and the running buildtest node's live gossip count on 198.199.106.165; (b) branch/SHA state with git in a fresh clone of UrlResolver. A fresh query always wins over this document.

Mission

Enforce a hard architectural invariant across the url:// resolver / protocol layer:

No per-node data structure may grow as O(N²) in the number of mesh nodes.

Discovery/forwarding state per node must be O(#distinct services) (≈O(N)), never O(peer-pairs). This is the durable follow-up to the 2026-07-19 buildtest gossip-storm incident. The incident's immediate fix bounds and evicts the leak, but the LIVE table it fixed is inherently O(N²) — a 50k safety cap papers over the shape; it does not fix it.

What was found (incident + diagnosis)

Symptom: https://buildtest.kotlin.build/ down (hang → 503). Mesh-wide url:// gossip storm; host 198.199.106.165 load 60→90+; every url:// node GC-thrashing; buildtest-server backends OOM-respawning (7 heapdumps in /root/ContainerNursery/heapdumps, 4 on 2026-07-19).
Dominant heap object: foundation.url.resolver.UrlProtocol2$ForwardedDiscoveredServiceState — 48k–82k live instances per node (matched with equal-count ...Key), surviving full GC. This is the forwardedDiscoveredServices map in UrlResolver.
The offending structure: ConcurrentHashMap<ForwardedDiscoveredServiceKey, ForwardedDiscoveredServiceState> keyed by the TRIPLE (destinationPeerId, serviceIdentifier, providerPeerId) — one row per (who-I-told × which-service × who-provides-it). It is a forwarding-dedup / relay table.
Why it explodes — three compounding causes:
1. N² by construction: two peer dimensions (destination × provider) → even a healthy live table is O(destinations × services × providers) ≈ O(N²). Only ~15–30 real services exist; the size is driven by the peer dimensions, not the services.
2. No eviction of departed peers (the leak fixed immediately): every ephemeral build droplet / netlab worker is a fresh libp2p peerId; its rows were never removed when it died, so dead peers accumulated forever.
3. Replay-on-connect amplifier (UrlResolver.kt ~line 9665): when a peer connects, the relay forwards ALL known announcements to it. A freshly-restarted node instantly inherits the accumulated stale set replayed from the other (unfixed) nodes — observed refill to ~47k in 3 min with zero live droplets.
Consequence proven: restarting nodes or killing droplets cannot fix it — replay re-floods any fresh node from the wider mesh. A per-node eviction fix keeps ONE node healthy (it prunes what it receives), which is why no fleet redeploy is needed to restore a single service.

What was done (immediate fix — necessary, NOT sufficient)

Branch fix/buildtest-gossip-stale-peer-amplification on UrlResolver, head SHA 96910f90 ("Release UrlResolver 0.0.640"), based on top of the parallel dead-transport fix.
Adds removeForwardedDiscoveredServiceStateForDestination(peerId) wired into peer prune/disconnect (UrlResolver.kt:2937, 8505, 9776); hard cap maxForwardedDiscoveredServices = 50_000; periodic prune (forwardedDiscoveredServicesPruneIntervalMs = 60_000); replay backoff (discoveredServiceReplayBackoffMs = 5 min).
Published foundation.url:resolver:0.0.640; buildtest.server:buildtest-server-service:0.0.181 (pins 0.0.640). Manual deploy of 0.0.181 to the buildtest node was IN FLIGHT at write time (reviews skipped per user for incident speed).
Host interim mitigations (198.199.106.165): BUILDTEST_DROPLET_LIMIT 75→10, MAX_LIVE_ENVIRONMENTS 60→5 (config.json; applied via CN restart — CN caches config at startup), all DO build/netlab droplets culled.
Result: the leak from DEAD peers is bounded; the LIVE table is still O(N²). The 50k cap is a ceiling, not the fix this handoff targets.

The actual goal of THIS handoff — make discovery state sub-N²

Redesign so per-node discovery/forwarding state is O(#services) (≈O(N)), never O(peer-pairs). Directions:

Drop the destinationPeerId dimension from the forwarding dedup (smallest change, biggest win). Dedup by announcement identity — messageId, or (serviceIdentifier, providerPeerId, version) — a per-announcement seen-set of size O(#services). Senders must NOT track every recipient; receivers dedupe on messageId. Collapses O(destinations × services) → O(services).
Replace flood-and-remember with proper gossip / anti-entropy. Per-node state = the current service set (O(#services)); fanout O(log N) per round; convergence via version vectors / Merkle-diff rather than per-pair bookkeeping.
Consider DHT / structured-overlay discovery (Kademlia-style): service records held at O(log N) nodes and looked up on demand — no node holds per-peer-pair state at all.

Acceptance criteria

A scale/churn test (e.g. 10→50→200 simulated peers with join/leave churn) shows per-node discovery memory flat or linear, not quadratic — assert on heap-histo counts of the discovery structures across N.
Audit UrlResolver AND UrlProtocol for every OTHER per-peer-pair (N²) structure — anything keyed by (peerA, peerB) or (peer × peer-derived) — and eliminate/bound each. Enumerate them in the PR.
The invariant "no per-node structure is O(N²) in node count" is documented (DocumentationRepository, url:// resolver architecture) and guarded by the scale test above.

Relevant refs

Repo: https://github.com/CodexCoder21Organization/UrlResolver
ForwardedDiscoveredServiceKey @ src/foundation/url/resolver/UrlResolver.kt:545; State @ :551; map decl + cap/prune fields @ ~:557.
Add-site: shouldForwardDiscoveredServiceToPeer @ ~:9680; replay-on-connect comment @ ~:9665.
Eviction hooks (immediate fix): :2937, :8505, :9723–:9776.
Fix branch: fix/buildtest-gossip-stale-peer-amplification (head 96910f90).
Published: foundation.url:resolver:0.0.640, buildtest.server:buildtest-server-service:0.0.181.
Related memory: buildtest-pending-wedge-dead-transport (parallel dead-transport fix → resolver 0.0.638).
Incident evidence: /root/buildtest-data/retained-run-forensics/outage-20260719T0515Z/ on 198.199.106.165 (live + OOM heap dumps dominated by ForwardedDiscoveredService; jstacks; CN log slices).

Next steps

Re-verify the immediate fix is deployed and the live buildtest node's ForwardedDiscoveredService count stays bounded (small/flat, not climbing) — that closes the incident; THIS handoff is the durable redesign.
Prototype direction (1) — drop the destination dimension — and measure per-node state vs N.
Run the N²-structure audit across UrlResolver + UrlProtocol; list every offender.
Choose gossip-anti-entropy vs DHT for the durable design; write an ADR.
Enforce the invariant with the scale test + documentation.

Reusable / operational knowledge

The "gossip messages" are forwarding-dedup rows, not messages: the same ~15–30 services recorded under thousands of distinct (mostly-dead) peer identities — a history leak, not a service explosion.
Restarting CN / killing droplets does NOT kill the storm — replay-on-connect re-floods fresh nodes from the wider mesh in minutes. Only per-node eviction (immediate fix) and sub-N² redesign (this handoff) fix it.
Host access is SSH ssh -p 23 root@198.199.106.165 (fabric certs absent on the /code box). CN caches config.json at startup — config env changes need a CN restart to take effect.

Required engineering rigor (implement it properly — do NOT shortcut like the incident fixes did)

Fail-first reproducer/scale test demonstrating the defect (FAILS before the change, PASSES after). Real instances, no mocks; per the Testing Architecture doc.
Implement the change at the owning layer.
Test-comprehensiveness review + adversarial code review via codex gpt-5.6-sol (high reasoning); address findings.
Final review (Claude) against the problem, CLAUDE.md, PHILOSOPHY; route findings back to codex.
Drive the PR(s) to green CI and MERGE. This handoff is NOT done until merged.