Skip to content

[Bug]: Every turn start on a long thread runs a quadratic restart-note check on the event loop #39231

Closed

Description

@navidnadali

Note

Written by Claude Opus 5.5 on behalf of Navid

Before submitting

  • I searched existing issues and did not find a duplicate.
  • I included enough detail to reproduce or investigate the problem.

Area

apps/server

Steps to reproduce

In the app: a long thread on one provider thread where some runs did not complete (messages removed from the queue
before they started, runs stopped with Stop, failed runs). Send one more message.

Every run start goes from the provider-turn.start effect (apps/server/src/orchestration-v2/EffectWorker.ts:238-239)
into ProviderTurnStartService.start, which reads every run, attempt and provider turn of the thread
(getTurnStartContext, apps/server/src/orchestration-v2/ProjectionStore.ts:5396-5421). Once the provider session is open, it calls
isRestartNoteContinuation and pendingRestartCancelledBackgroundWork on all of them, synchronously
(apps/server/src/orchestration-v2/ProviderTurnStartService.ts:955-976). This happens whether or not the server ever
restarted.

Scripted, on a synthetic history: in a checkout of main with dependencies installed, save the script below as
apps/server/restart-note-scaling.mjs and run node apps/server/restart-note-scaling.mjs (Node 26). It builds one
provider thread with N runs (per 100 runs: 7 queued messages cancelled before they started, 3 stopped, 2 failed, the rest
completed; no restarts), calls the two functions the way a turn start does, and counts reads of runs, attempts and
provider turns.

restart-note-scaling.mjs
// Save as apps/server/restart-note-scaling.mjs in a checkout of main, then: node apps/server/restart-note-scaling.mjs
// A synthetic thread on one provider thread, no restarts: per 100 runs, 7 queued messages cancelled before they
// started, 3 runs stopped, 2 failed, the rest completed. Times the two calls a turn start makes, and counts how often
// they read a run, attempt or provider turn.
import * as DateTime from "effect/DateTime";
import {
  isRestartNoteContinuation,
  pendingRestartCancelledBackgroundWork,
} from "./src/orchestration-v2/RestartBackgroundNote.ts";

let reads = 0;
const counted = (record) =>
  new Proxy(record, { get: (target, key) => (reads++, Reflect.get(target, key)) });

function thread(count, wrap) {
  const providerThreadId = "provider-thread:1";
  const runs = [];
  const attempts = [];
  const providerTurns = [];
  for (let ordinal = 1; ordinal <= count + 1; ordinal++) {
    const slot = ordinal % 100;
    const status =
      ordinal > count ? "starting"
      : slot < 7 ? "cancelled"
      : slot < 10 ? "interrupted"
      : slot < 12 ? "failed"
      : "completed";
    const id = `run:${ordinal}`;
    const attemptId = `attempt:${ordinal}`;
    runs.push(wrap({
      id, ordinal, status, providerThreadId, activeAttemptId: attemptId, userMessageId: `message:${ordinal}`,
      completedAt: status === "starting" ? null : DateTime.makeUnsafe(1_700_000_000_000 + ordinal * 60_000),
    }));
    attempts.push(wrap({ id: attemptId, runId: id }));
    if (status !== "cancelled" && status !== "starting")
      providerTurns.push(wrap({ id: `turn:${ordinal}`, providerThreadId, runAttemptId: attemptId, status }));
  }
  return { runs, attempts, providerTurns, run: runs.at(-1) };
}

const plan = ({ runs, attempts, providerTurns, run }) => {
  isRestartNoteContinuation(run, runs, providerTurns, attempts);
  return pendingRestartCancelledBackgroundWork({ runs, providerTurns, attempts, run, compactionMessageIds: new Set() });
};

console.log("runs | records | reads | reads per record | ms (median of 5)");
for (const count of [2_500, 5_000, 10_000, 20_000]) {
  const fixture = thread(count, (record) => record);
  const times = [];
  for (let i = 0; i < 5; i++) {
    const start = performance.now();
    plan(fixture);
    times.push(performance.now() - start);
  }
  const proxied = thread(count, counted);
  const records = proxied.runs.length + proxied.attempts.length + proxied.providerTurns.length;
  reads = 0;
  plan(proxied);
  const ms = times.sort((a, b) => a - b)[2];
  console.log(`${count} | ${records} | ${reads} | ${(reads / records).toFixed(0)} | ${ms.toFixed(0)}`);
}

Expected behavior

The check reads each run, attempt and provider turn a bounded number of times, so a turn start's cost grows linearly
with the thread.

Actual behavior

The script's output on main @ 0317d4f. The read counts are exact and the same on macOS arm64, Linux arm64 and Linux
x86_64. The times are from a Linux arm64 container (Node 26.13.1) on a busy machine, so they vary between runs.

Runs Runs + attempts + turns Reads Per record ms
2,500 7,327 1,549,666 212 7
5,000 14,652 6,099,316 416 28
10,000 29,302 24,198,616 826 116
20,000 58,602 96,397,216 1,645 400–880

Doubling the thread quadruples the reads. Three loops in apps/server/src/orchestration-v2/RestartBackgroundNote.ts,
mostly from #15323, multiply:

  • pendingRestartCancelledBackgroundWork returns early only for a run with no provider thread, a restart continuation,
    or a compaction or goal command (:394-399). Otherwise it checks every run on the provider thread, and for each run
    whose active attempt has no completed provider turn it scans every attempt of the thread (:413-415). A queued run
    gets its attempt when it is created (Orchestrator.ts:7907-7917), so a message removed from the queue counts, and so
    do stopped and failed runs. This is the part the script measures; it needs no restart.
  • After a server restart, each restart continuation (RestartContinuation.ts:327-347) that prompted the thread calls
    isRestartNoteContinuation (:417-418). That finds its source with runs.find (:368), rebuilds two Sets over all
    provider turns and attempts (:336-341) and walks the chain with one runs.find per step (:350).
  • Each earlier run holding restart-cancelled work (ProviderRuntimeRecoveryService.ts:985-1004) is compared with every
    prompted run (prompted.some(...), :433).

So the cost is about (non-completing runs × attempts) + (continuations × (runs + attempts + turns)) + (runs with
restart work × runs), in one synchronous stretch.

We also timed it in a running server, on our build, whose two functions and call site are the same as main's: on a
synthetic 25,000-run history that also had restart continuations (about 3% of runs, in short chains) and retried
attempts, the two calls took a median 3.0 s per turn start (2.8–4.5 s over 10 starts, Linux x64 VM with no other
load), and each start's longest event-loop block was about as long.

Impact

Major degradation or frequent failure

On a long thread every turn start blocks the server's event loop, and with it every other thread's streaming and
commands, for the length of the check. The cost grows with the square of the thread's history.

Version or commit

main @ 0317d4f

Environment

Server-side; any provider (a message removed from the queue never has a provider turn). The script needs only Node 26
and the checkout's dependencies.

Workaround

Continue long work in a new thread.

Related

Possible fix: build the lookups once per turn start (runs by id, attempts by run, completed and cancelled attempts),
remember each run's continuation verdict so a chain is walked once, and compare each source only with the latest run
that prompted the thread. In our build every output stays the same as the current functions' (a differential test over
3,000 seeded histories, including chains that loop or point at missing runs), and the 25,000-run server case above takes
under 10 ms per turn start. We have a fix in our build; happy to port it to main with tests that fail there, or a
maintainer can take it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    vouch:trustedAuthor is trusted by repo permissions or the VOUCHED list.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions