Recovery Is Not Progress

A Ray Placement Group Case Study on Partial Recovery, Queue Starvation, and Scheduler Liveness

Failure recovery sounds simple when described at a high level: preserve whatever is still alive, recover what was lost, and prioritize restoration over new work.

Each of those rules is individually reasonable. The problem begins when they interact.

While investigating Ray issue #65147, I encountered a placement-group recovery scenario where the scheduler remained extremely active, retries continued at high speed, and yet the system made almost no useful progress. Two partially recovered placement groups could remain stuck waiting on each other, while another placement group that did not depend on their resources could fail to receive even a single scheduling attempt.

The interesting part was not merely that recovery could get stuck. The deeper issue was that two different failure modes had become entangled: a resource-allocation cycle and a scheduler-liveness problem. Separating them changed both the diagnosis and the shape of the fix.

The Original Failure

Consider four one-CPU workers, each carrying either an L1 or L2 node label:

N1(L1)    N2(L2)    N3(L1)    N4(L2)

Each placement group requires two one-CPU bundles: one constrained to an L1 worker and one constrained to an L2 worker.

Two placement groups are initially placed as follows:

PG_A → N1(L1) + N2(L2)
PG_B → N3(L1) + N4(L2)

Initially, both groups are complete.

Now suppose two complementary node failures occur. N2 fails, so PG_A retains its surviving one-CPU bundle on the L1-labeled worker N1, but needs a replacement bundle on an L2-labeled worker. Then N3 fails, so PG_B retains its surviving one-CPU bundle on the L2-labeled worker N4, but needs a replacement bundle on an L1-labeled worker.

The resulting state is:

PG_A holds capacity on an L1 worker and waits for capacity on an L2 worker
PG_B holds capacity on an L2 worker and waits for capacity on an L1 worker

Or, as a wait-for graph, where an edge points from the waiting placement group to the placement group holding the capacity it needs:

PG_A -- waits for L2 capacity held by --> PG_B
PG_B -- waits for L1 capacity held by --> PG_A

Then the cycle is:

PG_A → PG_B → PG_A

Ray’s behavior here is understandable. Surviving bundles are not automatically destroyed just because another bundle in the placement group disappeared. Preserving surviving work avoids unnecessary disruption.

But that preservation also means that the surviving reservations remain part of the current allocation state. In this topology, each partially recovered placement group retains capacity that the other one needs. Repeating the same recovery attempt cannot complete either placement group unless capacity changes, one of the reservations is released, or the recovery policy itself changes.

This is a resource-allocation problem. It is real, but it is only half of the story.

When Recovery Becomes a Hot Loop

The second problem appears in the queue that decides which placement group receives the next scheduling attempt.

Fresh placement-group recovery is intentionally prioritized. When Ray detects that a created placement group has lost a bundle because of node failure, the recovery work enters the scheduling queue at rank 0.

Giving fresh recovery a high priority is not inherently problematic. In fact, it is a sensible policy: restore disrupted work before spending resources on unrelated new work.

The interesting behavior occurs after that recovery attempt has already failed.

In the path I inspected, a feasible RESCHEDULING failure was reinserted into the queue at rank 0 again, without carrying forward its existing exponential backoff. The failure callback then triggered another scheduling pass. If the allocation state had not changed, the next attempt could fail for exactly the same reason, return to rank 0, and repeat.

Conceptually, the system entered this loop:

recover
  ↓
fail
  ↓
rank 0
  ↓
recover
  ↓
fail
  ↓
rank 0
  ↓
...

The scheduler was doing work. The scheduling-attempt counters were increasing. But the state that prevented recovery from succeeding remained unchanged.

This is where a distinction that sounds trivial becomes surprisingly important:

Activity is not progress.

A retry counter moving forward does not imply that the system is moving toward a valid final state. A busy recovery loop can be perfectly active while preserving the exact condition that prevents recovery from completing.

The original reproduction made this unusually visible. Over one three-second observation window, PG_A’s scheduling-attempt counter increased from roughly 2.38 million to 2.72 million, while PG_B’s increased from roughly 9,700 to 348,000. In a separate three-second wait after PG_C was submitted, PG_C remained PENDING with scheduling_attempt == 0.

These numbers are observations from finite reproduction windows rather than a throughput benchmark, but they make the distinction between activity and forward progress difficult to miss.

But Was the New Placement Group Actually Schedulable?

There was still an ambiguity.

The new placement group in the original scenario also depended on the same labeled worker capacity involved in the recovery cycle. So although it received zero scheduling attempts, one could reasonably ask whether that mattered. Perhaps it would have failed anyway because the resources it needed were already reserved by the recovering placement groups.

That question matters because two very different explanations can produce the same surface symptom:

the scheduler considered the request,
but resources were unavailable

vs.

the scheduler never considered the request at all

Those are not equivalent failures.

To separate them, I introduced a resource that was independent of the two recovering placement groups:

PG_C_ONLY = 1

The recovering groups did not use this resource. A control task requesting exactly PG_C_ONLY could execute successfully, demonstrating that the resource was available.

Then I created a new placement group whose requirement was only PG_C_ONLY.

It still remained at:

scheduling_attempt == 0

while the recovery loop continued.

That experiment changed the interpretation of the problem. The new placement group was not losing a competition for the same capacity. It was not even being given a scheduling opportunity.

Resource unavailable is not the same as the scheduler never giving you a turn.

The independent-resource experiment isolated queue opportunity from resource contention. That was the point at which the scheduler-liveness problem became separable from the original allocation cycle.

A placement-group recovery loop can stay active without making progress: PG_A and PG_B repeatedly retry at highest priority, while an unrelated PG_C remains starved despite having independently available resources.

One Scenario, Two Different Failures

At this point, the failure becomes much easier to reason about if it is divided into two layers.

The first layer is the allocation cycle. PG_A and PG_B retain surviving reservations that the other needs. Fixing that problem requires something capable of changing the allocation itself: additional capacity, victim selection, releasing a survivor, whole-group replanning, or some form of rescheduler.

The second layer is queue starvation. Failed recovery remains at absolute scheduling priority, so unrelated due work can be prevented from receiving a scheduling attempt even when its own required resources are available.

These two failures interact, but they do not require the same fix.

This distinction also prevents an overly broad patch. A queue-level repair should not silently decide which placement group deserves to lose its surviving allocation. That would turn a retry-policy change into a disruption policy.

Conversely, a future rescheduler does not automatically answer the queue-liveness question either. Even if the resource cycle is eventually broken, the scheduler still needs a clearly defined rule for what repeated no-progress recovery is allowed to do to other queued work.

The Minimal Change

The patch I explored deliberately addresses only the second layer.

Fresh node-loss recovery still receives rank 0. The first recovery attempt therefore keeps the existing preference over ordinary pending work.

The change happens only after a feasible recovery attempt has already failed.

The original path effectively did this:

AddToPendingQueue(
    std::move(placement_group),
    /*rank=*/0);

The proposed path instead carries forward the existing backoff state:

AddToPendingQueue(
    std::move(placement_group),
    std::nullopt,
    backoff);

The existing queue logic then assigns the recovery a future eligibility time derived from the exponential backoff.

The important part is what does not change. The recovery obligation is not discarded. The surviving bundles are not released. The placement group is not falsely marked as recovered. The change only affects when the failed recovery becomes eligible for another scheduling attempt.

Get Yen-hua Chen’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The resulting control flow becomes:

node failure
    ↓
fresh recovery at rank 0
    ↓
recovery attempt fails
    ↓
retain backoff and schedule a future retry
    ↓
other due placement groups may receive a turn
    ↓
recovery becomes eligible again
    ↓
retry

This is a much narrower claim than saying that the placement-group recovery problem is solved.

The circular wait can still exist. PG_A and PG_B can still be unable to complete. What changes is that their inability to make progress no longer has to imply that every unrelated pending placement group is denied scheduling consideration.

What the Regression Test Actually Proves

The final regression test intentionally does not recreate the full two-placement-group resource cycle. That would test too many things at once.

Instead, the test focuses directly on the manager-level behavior being changed. It first verifies that fresh recovery still outranks ordinary pending work. It then causes that recovery to fail with a feasible result and checks that the retry is assigned a future rank using the configured backoff.

During that cooldown, another pending placement group is expected to receive its first scheduling attempt. Afterward, the fake clock advances exactly to the recovery’s retry time, and the recovery becomes eligible again. A subsequent failure verifies that the retry delay grows according to the configured multiplier.

That sequence matters because a good regression should prove the new contract rather than merely reproduce the old failure.

The contract being tested is not:

Recovery always succeeds.

It is:

Fresh recovery keeps its priority, failed recovery does not monopolize every subsequent scheduling opportunity, and recovery remains eligible to retry later.

Those are much more precise guarantees.

The Trade-off Is Real

Backoff improves queue liveness, but it weakens recovery’s claim on newly available capacity.

Suppose a recovering placement group requires two units of some resource, but only one unit is available right now. Another pending placement group requires a single unit and could run immediately.

If recovery retains absolute priority, the smaller placement group may remain blocked while the scheduler waits for additional capacity to appear. If another unit becomes available shortly afterward, the recovering placement group may then complete immediately.

If the failed recovery instead enters a cooldown, the smaller placement group may consume the currently available unit during that interval. Even if additional capacity appears shortly afterward, recovery may still be unable to complete because some of the usable capacity has now been assigned elsewhere.

That is a genuine trade-off.

Backoff improves queue-wide progress, but it may increase recovery latency.

The real scheduler-design question is therefore not simply whether recovery should have priority. It is:

How long should recovery retain absolute priority after it has failed to make progress?

The current implementation effectively represents one end of that design space: repeated failed recovery continues to return to rank 0.

The patch represents another point: fresh recovery gets absolute priority, while the first failed attempt begins using the existing backoff mechanism.

There are other defensible contracts. Recovery could retain strict priority for a bounded number of attempts, for a bounded time window, until a no-progress threshold is reached, or until some resource-state change wakes it again.

Those designs differ in policy, but they all require the same question to become explicit:

Is recovery priority permanent, or is it bounded?

That question cannot be answered by the existence of the current implementation alone.

A Local Policy Is Not Yet a System Invariant

This case is interesting because none of the individual rules looks obviously unreasonable.

Preserving surviving work is reasonable. Prioritizing recovery is reasonable. Retrying a feasible failure is reasonable. Avoiding unnecessary disruption is reasonable.

But local rules compose.

In this case, the combination looks roughly like this:

preserve surviving reservations
        +
retry only the missing bundles
        +
give failed recovery absolute priority
        ↓
resource cycle + queue starvation

This is a pattern that appears repeatedly in distributed systems. A behavior can be locally valid and still create a global liveness failure when composed with other locally valid behaviors.

That is why I find the following distinction useful:

A local policy is not yet a system invariant.

An implementation may reveal what the system currently does. It does not, by itself, establish that every consequence of that behavior is part of the intended contract.

The contract only becomes clear when we ask what must remain true across retries, failures, competing work, and state transitions.

Queue Policy and Rescheduling Are Different Problems

There is another boundary worth keeping explicit.

A queue policy determines when a request should be considered again.

A rescheduler determines which existing allocation is allowed to change.

Those responsibilities should not be silently collapsed.

Backoff can prevent a failed recovery from monopolizing scheduling turns, but it cannot free the resources that PG_A and PG_B hold.

A rescheduler could potentially break the allocation cycle by choosing a participant, releasing or replanning its surviving allocation, and allowing the other gang to complete. But that immediately introduces much larger questions: disruption policy, victim selection, fairness, restart behavior, and whether existing useful work is allowed to be destroyed to improve global progress.

Those are not details that should accidentally emerge from a retry patch.

The queue problem asks:

When should we try this recovery again?

The allocation problem asks:

What are we allowed to change so that the recovery can eventually succeed?

They are related, but they are not the same decision.

What Remains Unresolved

The patch does not prove starvation freedom for arbitrary workloads, and it does not establish eventual completion of the original placement groups.

PG_A and PG_B can remain mutually blocked if capacity never changes and neither survivor is released. The larger question raised by #65147 therefore remains: when preserving partial recovery prevents useful global progress, should Ray eventually disrupt one placement group and replan the gang?

That question requires a broader scheduler policy than the one examined here.

There is also a smaller policy question around wake-up behavior. If new capacity becomes available while a recovery is cooling down, should that resource-state change bypass the remaining backoff and make recovery immediately eligible again?

The narrow patch does not introduce such a rule. The existing due-time gate still determines when the queued recovery can be reconsidered.

Both questions are legitimate follow-ups, but neither changes the narrower observation: failed recovery and unrelated scheduling opportunity are distinct concerns.

Final Takeaway

What initially looked like one placement-group recovery problem turned out to contain three different phenomena:

resource-allocation deadlock
≠
retry hot loop
≠
scheduler starvation

The same investigation also exposed several distinctions that are easy to blur:

recovery priority
≠
permanent absolute priority after every failed retry


feasible
≠
currently available
scheduler activity
≠
forward progress

Once those concepts are separated, the production change becomes almost trivial.

The difficult part is not the line of code.

The difficult part is deciding what the line of code is supposed to mean.

And once that meaning is explicit, the remaining disagreement is no longer hidden inside an implementation detail. It becomes what it should have been from the beginning:

a scheduler policy decision.

Reference Implementation & Discussion

• Upstream Issue: ray-project/ray#65147
• Pull Request: ray-project/ray#65970
• The PR and its discussion explore whether repeated failed recovery should retain strict priority indefinitely or transition to bounded eligibility — an open scheduler policy decision.