OneDrive matter-document search — bounded-concurrency tree walk — design spec

Measured problem

search_matter_documents / read_matter_document walk the mapped OneDrive deal folder live. Three serial layers stack up (measured on the dev box against the real HSE org, 2026-07-23):

1. Serial BFS. searchMatterTree awaits listChildren one folder node at a time (matter-drive-documents.ts:815) — up to MAX_VISITED_ITEMS = 500 sequential connectors-api → Graph round-trips at ~200–400 ms each.
2. Serial fan-out. Multi-matter mode loops matters one after another (:1255, up to MAX_FANOUT_MATTERS = 6); the connex auto-widen loops up to 3 sibling matters serially (:987).
3. Per-node credential fence. Every /children request runs getRefreshedBundle in connectors-api (routes/drives.ts:121) — a connector-row read plus the refreshConnectorCredentials fence per listed folder.

Live baseline (medians): SUSS-117 deep walk (67 listings) 34.7 s; ELHM-150 (55 listings) 27.6 s; 4-matter fan-out 42.4 s; small matter (TESX-102) 1.2 s. The mcp-latency spec measured matter_documents_search p95 50.5 s. read_matter_document's containment walk (findDocumentUnderMatter) pays the same serial cost on every deep-matter read.

Chosen design

1 · Level-synchronized concurrent BFS in searchMatterTree

Mapped folder roots stay serial in DB order (as today). Within one root, the walk proceeds in deterministic BFS level batches: take the frontier in FIFO order, list up to WALK_CONCURRENCY = 6 nodes concurrently (each call routed through a search-wide limiter), settle the batch, assemble children in parent order, then continue. Never an unbounded Promise.all over Graph.

This replaces the earlier free-running worker-pool draft: the plan review showed a work-conserving pool changes which nodes are visited under budget exhaustion (fast branches outrun slow same-depth siblings), whereas FIFO level batches with in-order admission visit exactly the serial BFS prefix when the budget runs out. A genuinely narrow chain gains nothing from any traversal parallelism (a child is unknowable until its parent settles) — there the win comes from the credential cache (§3).

Claim protocol (per node, inside its limiter permit, synchronously before the fetch starts):

1. stop check — pool-local abort (target found / fatal error), upstream signal, deadlineAt;
2. per-root seen check and insertion;
3. budget.remaining check-and-decrement (JS single-threaded — race-free);
4. visitedCount increment;
5. listChildren starts immediately.

Nothing reserves budget while parked in the limiter queue, no listing can start after the deadline, and visitedCount equals actual budget consumption — the three properties the review showed the reserve-then-queue ordering would break.

Two batch-mechanics clauses (re-check round):

• Budget denial is an outcome, not a disappearance. A node taken off the frontier whose permit-time budget check fails (a concurrent walk drained the shared budget while it waited) is recorded as not started / budget-blocked; the walk settles complete: false, interruption: "walk_budget". An emptied frontier alone never implies completion.
• Immediate reaction, deferred assembly. Each task scans its own response for targetItemId the moment it settles (flipping the pool-local abort immediately) and a substantive error aborts slow siblings immediately; only the normal hit/folder assembly is deferred to the indexed, parent-order pass after allSettled.

Invariants preserved:

• WalkBudget stays a hard cross-matter cap, and under budget exhaustion the visited set within a walk is byte-identical to the serial walk's.
• Deadline / timebox: stop checks at claim time and after each settle; on expiry the pool-local controller aborts in-flight listings, admission stops, the walk settles { complete: false, interruption: "timebox" } with hits collected so far. The deadline is never overshot by queued work.
• Per-folder-root seen sets — overlapping subtrees under two mapped roots are visited per root and reported under each root's path, exactly as today.
• targetItemId short-circuit: first hit flips the pool-local abort — admission stops, in-flight siblings are aborted and awaited (allSettled, no transport orphans), the walk returns { hits: [hit], complete: true }.
• Error precedence: a substantive (non-abort) listing error wins over cancellation noise; the pool aborts remaining work, awaits settle, and rethrows it — the walk still fails loud, never returns silently thin results.
• Result determinism: hits are recorded during in-parent-order batch assembly, so insertion order equals the serial walk's; the existing stable sort (compareHits) then yields byte-identical output — including equal-score ties.

searchMatterTree returns an additional visitedCount, and accepts an optional shared limiter + pool-local abort wiring so one tool call spans all its walks with ≤6 in-flight Graph listings in total.

2 · Parallel multi-matter fan-out and connex widen — one shared limiter

The ticket explicitly mandates parallelizing the fan-out and the widen under the shared budget (NOS-211 fix outline; cross-matter budget sharing per spec §5.3). Semantics, fully specified after the review:

• Resolution stays serial and walk-free. Multi-matter mode resolves every chosen matter's folders first, in input order, with the same deadline checks as today — preserving both pinned behaviors: an unauthorized_user result aborts the call before ANY OneDrive traffic, and a deadline that expires during (RLS) resolution still yields the envelope with interrupted_matter_id = the matter being resolved.
• Resolution-only outcomes are unchanged: matter_not_found / no_matter / no-folder matters render their sections and count as completed without a walk, as today.
• Walks then run concurrently across the authorized matters, all sharing the ONE WalkBudget and the ONE ≤6 limiter. Sections are assembled in input order after settling.
• Envelope under interruption: scope_covered.matter_ids = matters completed (fully walked or resolution-only). pending.matter_ids = every other requested matter. pending.interrupted_matter_id = the first matter in input order that started a walk but did not complete (several walks may be incomplete simultaneously; each incomplete matter's section carries the "visited portion" note). terminal detection keeps its meaning via the interrupted walk's own visitedCount. meta.resultIds and the coverage key remain restricted to completed scopes (interrupted sections' ids stay out, as today).
• Error precedence: a substantive Graph/connector error from any walk fails the whole call loudly (today's behavior); timebox-abort noise from sibling walks never masks it.
• Definitions (re-check round): a matter's walk counts as started once searchMatterTree was invoked for it — including a walk that ends with visitedCount = 0 because siblings drained the budget (this preserves the existing solo-retry behavior). scope_covered and pending list matters in first-seen input order; suggested_next_call.matter_ids stays "pending in input order, interrupted matter moved last". Parallel walks can yield several interruption reasons at once: reasons is their union in canonical order ["timebox", "walk_budget", "fanout_cap"]. The terminal predicate is unchanged: walk_budget present ∧ the interrupted walk's visitedCount ≥ MAX_VISITED_ITEMS ∧ the interrupted matter is the sole pending matter.

The connex widen resolves its ≤3 siblings serially (each passes the disclosure gate before any listing, unchanged) and then walks them concurrently under the same shared budget + limiter; blocks/matches assemble in candidate order.

One semantic delta, stated honestly and accepted by the ticket: when the shared budget exhausts mid-fan-out, the serial code let earlier matters starve later ones; the parallel code spreads the same ≤500 listings across in-flight walks, so per-matter coverage distribution under exhaustion is timing-dependent. Coverage reporting stays truthful per matter, the budget total is unchanged, and non-interrupted searches return byte-identical results. The pinned test "offers a solo retry when prior matters consumed the shared walk budget" is updated deliberately for this (its envelope contract — truthful completed/pending + executable continuation — is unchanged).

3 · Credential bundle: TTL + single-flight cache, /children only

connectors-api gets a small in-memory cache around getRefreshedBundle, used only by the /children route (the measured walk bottleneck — /content, /text, drive/folder listing keep per-request fences; broadening staleness for byte reads buys nothing here). lib/bundle-cache.ts, keyed organizationId:connectorId, TTL 30 s:

• Single-flight: concurrent misses for one key join one fence run; a caller's abort never cancels the shared run for other waiters. An in-flight run older than the TTL is still joined, never replaced.
• TTL from success: freshness is stamped when the fence settles successfully, not when it starts. Rejections propagate to every joined caller and evict only their own entry (identity-compared — never a newer replacement); errors are never cached. ConnectorNotFoundError surfaces unchanged (routes map it to 404).
• Honest staleness contract: the fence itself already serves a stored bundle untouched while it is outside its ~10-minute refresh budget, and provider-side revocation is only observed when a refresh actually runs. The cache therefore does NOT change revocation-detection semantics; what it adds is up to 30 s of delay in observing a DB-side credential rotation / reconnect / status flip. Bounded and acceptable for a walk that previously re-read the row per node.
• Bounded memory: expired entries are pruned opportunistically on access and the map carries a hard entry cap; plaintext bundles never linger unboundedly in a long-running process.

4 · Cancellation propagated end to end

Today an abort stops only the agent-runtime→connectors-api fetch; the Graph request (and SDK retries) keeps running server-side, so a timed-out search plus its continuation could hold 2× the intended Graph pressure. Fixed across both hops:

• agent-runtime: the single-matter search and findDocumentUnderMatter now thread config.signal into their walks (the multi-matter branch already does); every walk gets a pool-local AbortController chained to upstream signal + deadline.
• connectors-api: the /children route passes the request's abort signal (c.req.raw.signal) through listDriveItems into the Graph SDK per-request via GraphRequest.options({ signal }) (verified supported in v3.0.7).

5 · Graph throttling (429 / Retry-After)

Verified: createGraphClient uses the Graph SDK default middleware chain, which includes RetryHandler (3 retries, honors Retry-After); mapGraphError maps exhausted throttles to ConnectorRateLimitError. The bounded width (≤6 in-flight per search, enforced by the shared limiter) plus end-to-end cancellation keeps worst-case Graph pressure at 6 concurrent calls per search. A node failure after retries aborts the walk exactly as today.

Alternatives rejected

• Unbounded Promise.all per BFS level — bursts hundreds of concurrent Graph calls; explicitly banned.
• Free-running worker pool over a dynamic frontier — faster on paper for unbalanced trees, but changes the visited subset under budget exhaustion (semantic change), needs a lost-wakeup-safe idle/termination protocol, and complicates deterministic output. Rejected after plan review; level batches meet the latency target without any of that.
• Serial multi-matter fan-out kept as-is — reviewer-preferred as strictly behavior-preserving, but the ticket explicitly orders the fan-out and widen parallelized under the shared budget; the envelope contract (deadline honored, truthful coverage, executable continuation) is preserved as specified in §2.
• Caching the bundle in agent-runtime — moves credential material outside the privileged connectors-api boundary; rejected on posture.
• Graph $batch — same throttle budget, more error-mapping complexity, no latency win over 6 concurrent plain calls.
• Raising MAX_VISITED_ITEMS / fan-out caps — out of scope; speed only, coverage bounds unchanged.

Gates

• packages/agent-runtime + apps/connectors-api suites green. New tests (see the plan §tests): serial-prefix visit subset at budget exhaustion; slow same-depth sibling never lets a fast branch descend early; no listing starts after the deadline (including limiter-queued nodes); deadline during RLS resolution keeps interrupted_matter_id; one node throws while a sibling hangs → sibling aborted, substantive error wins; target found with queued+in-flight siblings → no later start, all settled; upstream cancellation through single-matter search and containment; connectors-api cancellation reaching the (mocked) Graph fetch; multiple simultaneously-incomplete matters → truthful envelope, terminal detection, section order, restricted resultIds; unauthorized matter in the batch → zero OneDrive calls; equal comparator keys across overlapping roots → deterministic output; global ≤6 concurrent listings; bundle cache: single-flight, TTL-from-success, slow-fence-past-TTL join, identity-safe rejection eviction, pruning.
• Concurrency-affected tests use URL/query-aware mocks (the existing mockResolvedValueOnce sequencing is order-dependent and unsafe under concurrency).
• bun run lint + bun run typecheck from root.
• Live before/after benchmark on SUSS-117 / ELHM-150 / TESX-102 / 4-matter fan-out in the PR body.
• Partial-state semantics: deadline honored, truthful coverage, envelope JSON schema untouched.
• No schema changes (hard rule for this branch).