Task orchestrator re-queries every cache miss on each coordinator loop, causing O(N²/P) remote cache hits

[Exelord]

Current Behavior

After the warm-cache perf overhaul in #35172, running a large workspace through the task orchestrator generates a quadratic number of cache lookups when most tasks are cache misses. On a workspace with ~1,500 tasks, the orchestrator issues ~88,000 cache requests — roughly 58 lookups per task. With Nx Cloud / a remote cache configured, each of those lookups also fans out to a remote HTTP retrieval inside DbCache.getBatch, so the same already-confirmed-miss hashes are pulled over the wire dozens of times.

Where it happens

packages/nx/src/tasks-runner/task-orchestrator.ts

// executeCoordinatorLoop, every iteration:
if (doNotSkipCache) {
  const resolved = await this.resolveCachedTasksBulk();
  if (resolved) continue;
}

resolveCachedTasksBulk rebuilds its candidate list from scheduledTasks every loop iteration, with no memoization of misses:

private async resolveCachedTasksBulk(): Promise<boolean> {
  const { scheduledTasks } = this.tasksSchedule.getAllScheduledTasks();
  const candidates: Task[] = [];
  for (const id of scheduledTasks) {
    const task = this.taskGraph.tasks[id];
    if (
      task.hash &&
      !task.continuous &&
      isCacheableTask(task, this.options)
    ) {
      candidates.push(task);
    }
  }
  // ...always queries cache.getBatch(candidates) regardless of whether
  // these exact hashes were just queried (and missed) one cycle ago.
}

fetchCacheHits then unconditionally calls cache.getBatch:

private async fetchCacheHits(tasks: Task[]): Promise<CacheHit[]> {
  const batchResults = await this.cache.getBatch(tasks);
  // ...
}

And DbCache.getBatch (packages/nx/src/tasks-runner/cache.ts:141) issues one remote HTTP request per local-cache miss:

if (remoteMisses.length > 0) {
  await Promise.all(
    remoteMisses.map(async (task) => {
      const res = await this.remoteCache.retrieve(task.hash, this.cache.cacheDirectory);
      // ...
    })
  );
}

Why the count blows up

Tasks in scheduledTasks are not removed when bulk-resolve confirms a miss — only when they're dispatched via tasksSchedule.nextTask() in step 5. Dispatch is parallelism-bounded, so a task can sit in scheduledTasks across many coordinator cycles waiting for a slot. Every cycle, the same hash gets pushed back through cache.getBatch — local SQL plus remote HTTP retrieve.

For a run with parallel = P and N cache-miss tasks, the number of cache lookups is roughly:

sum over iterations k = 1..N/P of (N - k * P)  ≈  N² / (2P)

With N = 1500, P = 12, that's ~93k lookups — matching the reported ~88k.

Expected Behavior

A miss confirmed in one coordinator cycle should be remembered, and the same hash should not be re-queried (locally or remotely) on subsequent cycles. The expected lookup count for N cache-miss tasks should be O(N) — one query per unique hash, regardless of how many cycles it sits in the schedule.

Reproduction

1. Workspace with ~1,500 cacheable tasks (large monorepo or generated benchmark workspace).
2. nx reset (clear local cache) so every task is a miss.
3. Configure any remote cache plugin (Nx Cloud, S3, etc.).
4. Run nx run-many -t build --parallel=12 and instrument cache.getBatch / remoteCache.retrieve call counts.

Observed: ~58× the task count in cache lookups.
Expected: ~1× the task count.

Root Cause

Regression introduced by #35172 (warm-cache perf optimization). Before that change, cache lookups happened per-task inside processTask / applyFromCacheOrRunTask, so each task hash was queried at most once per dispatch. The new bulk path runs unconditionally at the top of every coordinator cycle but doesn't track which hashes have already been queried-and-missed in the current run.

This stays hidden in the warm-cache benchmark scenarios reported in the PR because every task is a hit there — a single bulk query resolves all 1,110 tasks in one cycle and the loop exits. The pathology only shows up on cold/mixed-cache runs, exactly the runs where remote-cache HTTP cost matters most.

Proposed Fix

Track confirmed cache misses in a Set<string> keyed by hash for the lifetime of the orchestrator run. Filter fetchCacheHits and resolveCachedTasksBulk candidate lists against it.

// On the orchestrator
private cacheMissedHashes = new Set<string>();

private async fetchCacheHits(tasks: Task[]): Promise<CacheHit[]> {
  const tasksToQuery = tasks.filter(
    (t) => t.hash && !this.cacheMissedHashes.has(t.hash)
  );
  if (tasksToQuery.length === 0) return [];

  const batchResults = await this.cache.getBatch(tasksToQuery);
  const cacheHits: CacheHit[] = [];
  for (const task of tasksToQuery) {
    const cachedResult = batchResults.get(task.hash);
    if (cachedResult && cachedResult.code === 0) {
      cacheHits.push({ task, cachedResult });
    } else {
      this.cacheMissedHashes.add(task.hash);
    }
  }
  return cacheHits;
}

And in resolveCachedTasksBulk, also exclude known misses from candidates so the function early-exits when nothing new is queryable, avoiding closeGroup / openGroup churn:

if (
  task.hash &&
  !this.cacheMissedHashes.has(task.hash) &&
  !task.continuous &&
  isCacheableTask(task, this.options)
) {
  candidates.push(task);
}

Why keying by hash (not task id) is correct

• Within one orchestrator run, the only event that can change a task's cache state is that task itself completing and being put into the cache — and a task that completes is removed from the schedule, not re-queried.
• Tasks with depsOutputs are re-hashed after their deps run (applyBatchCachedResults → hashBatchTasks(tasksToRehash)). The new hash is a different key, so it isn't in cacheMissedHashes and gets queried fresh — which is the desired behavior.
• A task whose hash is null/undefined is filtered out (avoids polluting the set with a sentinel that would block future hash-less tasks).

Related

• Regression introduced by: fix(core): optimize warm cache performance for task execution #35172 (warm-cache perf optimization)
• Adjacent fix: fix(core): await queued processTask promises before cache.getBatch #35322 (await processTask before getBatch — also surfaced by fix(core): optimize warm cache performance for task execution #35172)

[EricPoul]

Just updated to NX 23 and couldn't understand why every run failed. We have almost 1k libs, and with this bug, it's just unusable. I feel like it's more of a critical one rather medium since it breaks nx commands, especially after one month of this issue being presented.

[artnikbrothers]

This is a severe regression for large monorepos. Confirmed via direct A/B benchmark on identical hardware/code: Nx 22.7.1 = ~0.9s per cacheable task, Nx 23.1.1 = ~20-25s per task, purely from the cache-write step - every typecheck target now has a 20s floor regardless of project size.

We're bumping our monorepo to 23.2.0-beta.7 specifically to pick up #36301, since we can't wait for 23.2.0 stable. Would appreciate this getting prioritized for the next stable release.