[Bug]: no-capacity retry backoff is anti-correlated with wait time, so priority inverts among schedulable runs

[jonathanwhen]

Steps to reproduce

SSH fleet, one host with blocks: 8.

1. Saturate the fleet so every block is busy.
2. Submit ~6 single-block tasks at priority: 50, each with a short payload:

type: task
name: prio-lo-0
priority: 50
max_duration: 20m
retry:
  on_events: [no-capacity]
  duration: 2h
commands:
  - sleep 20
resources:
  gpu: 1

3. Submit ~6 identical tasks at priority: 51.
4. Wait ~15 minutes, so the waiting runs climb the retry ladder.
5. Free blocks one at a time and record, for each placement, which run was placed and how many higher-priority runs were still pending.

Actual behaviour

Lower-priority runs take capacity from higher-priority runs that have been waiting longer.

On a saturated fleet a waiting run is not queued. It cycles PENDING → SUBMITTED → terminated (no capacity) → PENDING, sleeping between attempts under _PENDING_RETRY_DELAYS = [15s, 30s, 1m, 2m, 5m, 10m] (last rung repeats). Because the delay grows with the attempt count, the longer a run waits, the less often it competes — a fresh run retries every 15 s, an hour-old run every 10 min, roughly 40× fewer attempts. RunModel.priority is only read during an attempt.

Measured on our pool, from the server's events table:

SUBMITTED → PENDING (bounced, no capacity)	32,480
SUBMITTED → PROVISIONING (placed)	1,369
median time spent in SUBMITTED before bouncing	4.98 s (n=8,878, p90 10.2 s)

96% of entries into SUBMITTED bounce straight back, after about five seconds. So a run at the 10-minute rung is a placement candidate for ~5 s out of every ~605 — under 1% of the time — while a freshly submitted run is a candidate ~25% of the time.

Running the reproduction above: of 13 placements, 4 were of a priority: 50 run while a priority: 51 run was still pending. All 4 of the placements where an inversion was possible were inversions. The other 9 could not have been — 7 were top-tier runs, 2 had no higher-priority run waiting.

One detail worth stating: the first task placed, before any backoff had accumulated, was priority: 51 — correctly. With resubmission_attempt = 0 every run is eligible and priority behaves as documented. The inversions begin only once runs start sleeping.

Expected behaviour

Retry frequency should not be inversely proportional to how long a run has already waited, so that among runs which are all schedulable, priority still decides who gets a freeing block.

The smallest fix we can see: wake PENDING runs on capacity release. The hint emitted when a job frees a block goes to the instance pipeline (jobs_terminating.py:293); extending it to the run pipeline and bypassing the backoff for that one pass would leave retries rate-limited in the steady state, while making every waiting run a candidate at the moment capacity appears — at which point the existing .order_by(RunModel.priority.desc(), ...) decides.

We read #2635 as accepting that a high-priority run which cannot be scheduled should not block others. This is a different case: the runs here can all be scheduled, and lose because of when they happen to be awake. So we think it is addressable without revisiting that decision.

dstack version

0.21.1 (server + CLI). The relevant code is unchanged at tag 0.21.3.

Server logs

The server's own events table is more precise than the logs for this, since it
records every state transition with a timestamp:

  SELECT message, COUNT(*) FROM events
  WHERE message LIKE 'Run status changed SUBMITTED%'
  GROUP BY message;

Happy to provide full server logs at --log-level=debug if useful.

Additional information

Where priority is read. RunModel.priority appears at one site in the scheduler, background/pipeline_tasks/jobs_submitted.py:268, over jobs in SUBMITTED at that instant:

.order_by(RunModel.priority.desc(), JobModel.last_processed_at.asc())

A capacity-starved job does not wait there — it is terminated on its first pass, and the run returns to PENDING with resubmission_attempt += 1 (runs/active.py:438-441), then sleeps behind the gate at runs/pending.py:63,128-153. Nothing wakes it early: the backoff is a wall-clock check inside the run worker rather than in its fetch, so a capacity-release hint would not currently reach it.

Scope. Only affects runs with retry configured — without it a run fails outright rather than waiting, so queuing for capacity is the retry loop. Reproduced on a single SSH fleet; we have not tested cloud backends, where offers come from a provider rather than a fixed block pool.

A script to check this on any server. Reads the DB read-only, pure stdlib, no dstack import; prints pending runs in wake order beside their priority. [attach dstack_priority_probe.py]

[r4victor]

@jonathanwhen, yes, this is a problem that priority only prioritizes provisioning among non-delayed runs. The described fix with backoff bypass on released capacity makes sense, but we need to ensure that it does not lead to an overload when all the queued runs become eligible for provisioning.