perf: replace O(n⁴) rack lookup with TopologyIndex and eliminate double topology scan in planner

[SckyzO]

perf: replace O(n⁴) rack lookup with TopologyIndex and eliminate double topology scan in planner

Symptom

Two hot paths in the backend scan the topology in suboptimal ways, despite the existence of a TopologyIndex precisely designed to make these lookups O(1).

Hot path 1 — GET /api/racks/{rack_id}

The endpoint is hit on every Rack view open and on every auto-refresh tick. It currently traverses the full topology hierarchy in nested loops to find a single rack by ID — exactly the search pattern that TopologyIndex.racks_by_id was built to eliminate.

Hot path 2 — TelemetryPlanner._recompute()

The planner is called on every topology reload and on every config change. Inside _recompute, the helper _collect_topology_ids(topology) is invoked twice: once to purge stale entries from _pending_states, then again to build the new query batches. Both passes iterate the entire topology tree.

Technical Analysis

PERF-01 — get_rack_details ignores the index

src/rackscope/api/routers/topology.py:580-597

@router.get("/api/racks/{rack_id}", response_model=Rack)
async def get_rack_details(rack_id: str, topology: Annotated[Topology, Depends(get_topology)]):
    """Get rack details and devices."""
    # Find rack using index if available, O(n) fallback otherwise
    # In production, we would index racks by ID on load
    for site in topology.sites:
        for room in site.rooms:
            for aisle in room.aisles:
                for rack in aisle.racks:
                    if rack.id == rack_id:
                        return rack
            for rack in room.standalone_racks:
                ...

The comment "In production, we would index racks by ID on load" acknowledges the issue. The index exists already: src/rackscope/api/dependencies.py exposes get_topology_index and TopologyIndex.racks_by_id is a dict[str, Rack] rebuilt on every topology reload (src/rackscope/model/domain.py).

Complexity: O(sites × rooms × aisles × racks) per request. On a topology with 10 sites × 5 rooms × 4 aisles × 10 racks = 2000 iterations to find one rack. Multiplied by N concurrent clients × refresh rate, this becomes a measurable CPU cost on larger deployments.

PERF-02 — _recompute calls _collect_topology_ids twice

src/rackscope/telemetry/planner.py:146 and :165

# Around line 146 — purge stale pending states
if self._pending_states:
    collected_for_purge = _collect_topology_ids(topology)  # pass 1
    # ... purge logic ...

# Around line 165 — build new query batches
collected_for_queries = _collect_topology_ids(topology)    # pass 2
# ... build queries ...

Both passes are O(sites × rooms × aisles × racks × devices) over the entire topology. On a topology of 10 000 instances, this doubles the planner cost for no functional reason.

Proposed Fix

Fix PERF-01

 @router.get("/api/racks/{rack_id}", response_model=Rack)
-async def get_rack_details(rack_id: str, topology: Annotated[Topology, Depends(get_topology)]):
+async def get_rack_details(
+    rack_id: str,
+    topology_index: Annotated[TopologyIndex, Depends(get_topology_index)],
+):
     """Get rack details and devices."""
-    # Find rack using index if available, O(n) fallback otherwise
-    # In production, we would index racks by ID on load
-    for site in topology.sites:
-        for room in site.rooms:
-            for aisle in room.aisles:
-                for rack in aisle.racks:
-                    if rack.id == rack_id:
-                        return rack
-            for rack in room.standalone_racks:
-                if rack.id == rack_id:
-                    return rack
-    raise HTTPException(status_code=404, detail="Rack not found")
+    rack = topology_index.racks_by_id.get(rack_id)
+    if rack is None:
+        raise HTTPException(status_code=404, detail="Rack not found")
+    return rack

get_topology_index is the existing dependency that exposes the rebuilt index. The function body collapses from ~17 lines to 4 lines. Complexity goes from O(sites × rooms × aisles × racks) to O(1).

Fix PERF-02

 def _recompute(self, topology: Topology) -> None:
+    collected = _collect_topology_ids(topology)
+
     if self._pending_states:
-        collected = _collect_topology_ids(topology)
-        # purge logic using `collected`
-        ...
+        # purge logic using `collected`
+        ...

-    collected = _collect_topology_ids(topology)
+    # reuse the same `collected` for query building
     # build queries using `collected`
     ...

One pass over the topology instead of two. The _pending_states check still gates the purge work (no behaviour change), but the topology traversal is shared between purge and query building.

Audit of other duplicate scans (optional, in this PR)

While in planner.py, grep for any other patterns that re-traverse the topology in the same function. If trivial duplicates surface, fix them here. Otherwise, file a follow-up.

Test Checklist

Unit tests

• tests/unit/api/test_get_rack_details.py: rack found → returns Rack object identical to the one in the topology (golden compare)
• tests/unit/api/test_get_rack_details.py: rack not found → 404 with detail="Rack not found" (matches existing contract)
• tests/unit/api/test_get_rack_details.py: standalone rack (in room.standalone_racks, not in any aisle) → still found via the index
• tests/unit/telemetry/test_planner_recompute.py: _recompute is called with a topology, _collect_topology_ids is invoked exactly once (mock + call count assertion)
• tests/unit/telemetry/test_planner_recompute.py: _recompute with empty _pending_states → still works (no regression on the purge branch being skipped)
• tests/unit/telemetry/test_planner_recompute.py: _recompute with populated _pending_states → purge happens, then queries built, both using the same collected set

Functional / integration tests

• Existing test suite passes unchanged
• GET /api/racks/<existing-id> returns the same JSON shape pre- and post-PR (golden response compare)
• GET /api/racks/<non-existent> returns 404 with the same payload

Optional: micro-benchmark (in PR description, not committed)

Run on a synthetic topology with 1000 racks across many sites. Measure wall-clock time of 1000 GET /api/racks/{rack_id} calls before and after. Expect at least an order of magnitude improvement on the median. Not required to merge — informational only.

Impact and Severity

• Audience affected: every deployment large enough for the O(n⁴) lookup to be measurable. Small topologies (a few racks) will not see any difference. Large HPC deployments with thousands of racks across many sites will see meaningful CPU reduction on the dashboard and Rack view hot paths.
• Severity: medium (performance, not correctness). The code is functionally correct today; the fix improves headroom.
• Priority: Sprint 2 of the audit roadmap. Ships when convenient, no urgency.

Breaking Changes

None. API responses are bit-identical pre- and post-PR. The only observable change is reduced CPU usage on the hot paths.

Related

• Audit ref: PERF-01, PERF-02 in AUDIT_ARCHITECTURAL.md
• Builds on existing infrastructure (TopologyIndex already exists, get_topology_index dependency already exists)
• Does not depend on any other open issue

Out of Scope

• Adding GET /api/sites/{id}, /api/rooms/{id}, etc. with similar index-backed lookups — only fix get_rack_details here; other endpoints may already use the index, audit separately if needed.
• Adding a cache layer on top of the index — the index is already rebuilt on every topology reload and is in-memory; further caching is unnecessary.
• query_range() caching in PrometheusClient (audit PERF-03) — separate concern, separate issue if escalated.