testing: check that topology domain is reserved for preemptor workloads accross cycles

[Nilsachy]

What type of PR is this?

/kind cleanup
/area testing

What this PR does / why we need it:

This PR adds an integration test to verify that topology domains (nodes/blocks) allocated to a preemptor waiting for multiple evictions cannot be stolen by interim pending workloads across scheduling cycles.

This is a follow-up to #13797. While #13797 ensured that quota is reserved across scheduling cycles when a preemptor is waiting for multiple evictions, it also locked topology assignments:

1. Deterministic Topology Placement (compareDomainLevelValues):

   • In each scheduling cycle, updateAssignmentForTAS simulates the removal of remaining preemption targets (SimulateWorkloadRemoval(targets)).
   • The TAS placement algorithm (findTopologyAssignment) sorts candidate domains using sortedDomains, which falls back to compareDomainLevelValues as a deterministic lexicographical tie-breaker (comparing domain hierarchy level values, e.g., rack-1/node-1 vs rack-2/node-2).
   • Combined with the simulated removal of specific victims, this guarantees that the preemptor consistently evaluates and selects the same topology domains in every cycle while evictions are ongoing.

2. Preemptor Workload Priority & In-Memory Lock (cq.AddUsage):

   • When a workload issues preemption, it is tracked as a preemptorWorkload at the head of its ClusterQueue (providing stickiness during queue ordering).
   • With PrioritizePreemptorWorkloads enabled, e.IsPreemptor ensures the preemptor is sorted first in the scheduling iterator (makeClassicalIterator / fairSharingIterator).
   • When evaluated first in subsequent scheduling cycles, the preemptor runs cq.AddUsage(usage) in processEntry, re-locking its assigned topology domains in TASFlavorSnapshot before lower-priority or quota-abundant workloads are evaluated.
   • Any interim workload attempting to claim those domains fails cq.Fits (FitsCheckNoTAS) and is skipped.

This PR adds dedicated integration test coverage in test/integration/singlecluster/tas/tas_test.go to explicitly test and safeguard this topology locking behavior.

Which issue(s) this PR fixes:

Related to #13797

Special notes for your reviewer:

• Topology Locking Mechanism:
  Even when evictions are staggered across multiple scheduling cycles (e.g., victim 1 terminates in cycle 1, victim 2 terminates in cycle 2), the combination of:

  • SimulateWorkloadRemoval of remaining targets,
  • Deterministic domain tie-breaking via compareDomainLevelValues,
  • Queue-level stickiness and iterator prioritization (preemptorWorkload / PrioritizePreemptorWorkloads), and
  • In-cycle snapshot locking (cq.AddUsage $\rightarrow$ tasFlvCache.updateTASUsage),
    ensures the already freed topology space (e.g. node 1) cannot be stolen by interim workloads while the preemptor is still waiting for remaining victims (e.g. node 2) to drain.

• Test Scenario:

  1. Two workloads wl-a (on node 1) and wl-b (on node 2) occupy the cluster.
  2. A low-priority pending workload wl-pending arrives in clusterQueueC (has enough nominal quota to schedule on a single node).
  3. A high-priority preemptor arrives, requesting full block capacity (2 nodes) and marking both wl-a and wl-b for preemption.
  4. Only wl-a finishes eviction.
  5. The test asserts via gomega.Consistently that wl-pending is not admitted on the freed node 1 in the interim while wl-b is still draining.
  6. Once wl-b finishes eviction, preemptor is admitted across both nodes, and wl-pending remains pending.

Does this PR introduce a user-facing change?

NONE

<!-- This is an auto-generated comment: release notes by coderabbit.ai -->

## Summary by CodeRabbit

* **Tests**
  * Expanded integration coverage for workload preemption across fragmented CPU topology.
  * Added validation for quota-constrained scheduling with multiple nodes.
  * Verified that replacement workloads are admitted only after required evictions complete.
  * Confirmed pending workloads remain unreserved and report an appropriate topology-capacity waiting condition.

<!-- end of auto-generated comment: release notes by coderabbit.ai -->

[kubernetes-prow]

@Nilsachy: The label(s) kind/testing cannot be applied, because the repository doesn't have them.

Details

In response to this:

What type of PR is this?

/kind testing
/area tas

What this PR does / why we need it:

This PR adds an integration test to verify that topology domains (nodes/blocks) allocated to a preemptor waiting for multiple evictions cannot be stolen by interim pending workloads across scheduling cycles.

This is a follow-up to #13797. While #13797 ensured that quota is reserved across scheduling cycles when a preemptor is waiting for multiple evictions, it also locked topology assignments as a side effect:

1. Deterministic Topology Placement (compareDomainLevelValues):

• In each scheduling cycle, updateAssignmentForTAS simulates the removal of remaining preemption targets (SimulateWorkloadRemoval(targets)).
• The TAS placement algorithm (findTopologyAssignment) sorts candidate domains using sortedDomains, which falls back to compareDomainLevelValues as a deterministic lexicographical tie-breaker (comparing domain hierarchy level values, e.g., rack-1/node-1 vs rack-2/node-2).
• Combined with the simulated removal of specific victims, this guarantees that the preemptor consistently evaluates and selects the exact same topology domains in every cycle while evictions are ongoing.

2. Preemptor Workload Priority & In-Memory Lock (cq.AddUsage):

• When a workload issues preemption, it is tracked as a preemptorWorkload at the head of its ClusterQueue (providing stickiness during queue ordering).
• With PrioritizePreemptorWorkloads enabled, e.IsPreemptor ensures the preemptor is sorted first in the scheduling iterator (makeClassicalIterator / fairSharingIterator).
• When evaluated first in subsequent scheduling cycles, the preemptor runs cq.AddUsage(usage) in processEntry, re-locking its assigned topology domains in TASFlavorSnapshot before lower-priority or quota-abundant workloads are evaluated.
• Any interim workload attempting to claim those domains fails cq.Fits (FitsCheckNoTAS) and is skipped.

This PR adds dedicated integration test coverage in test/integration/singlecluster/tas/tas_test.go to explicitly test and safeguard this topology locking behavior.

Which issue(s) this PR fixes:

Related to #13797

Special notes for your reviewer:

• Topology Locking Mechanism:
  Even when evictions are staggered across multiple scheduling cycles (e.g., victim 1 terminates in cycle 1, victim 2 terminates in cycle 2), the combination of:

• SimulateWorkloadRemoval of remaining targets,

• Deterministic domain tie-breaking via compareDomainLevelValues,

• Queue-level stickiness and iterator prioritization (preemptorWorkload / PrioritizePreemptorWorkloads), and

• In-cycle snapshot locking (cq.AddUsage $\rightarrow$ tasFlvCache.updateTASUsage),
  ensures the already freed topology space (e.g. node 1) cannot be stolen by interim workloads while the preemptor is still waiting for remaining victims (e.g. node 2) to drain.

• Test Scenario:

1. Two workloads wl-a (on node 1) and wl-b (on node 2) occupy the cluster.
2. A low-priority pending workload wl-pending arrives in clusterQueueC (has enough nominal quota to schedule on a single node).
3. A high-priority preemptor arrives, requesting full block capacity (2 nodes) and marking both wl-a and wl-b for preemption.
4. Only wl-a finishes eviction.
5. The test asserts via gomega.Consistently that wl-pending is not admitted on the freed node 1 in the interim while wl-b is still draining.
6. Once wl-b finishes eviction, preemptor is admitted across both nodes, and wl-pending remains pending.

• AI assistance disclosure: This PR description was drafted with the assistance of AI in accordance with the Kubernetes AI Tool Usage Policy.

Does this PR introduce a user-facing change?

NONE

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes-sigs/prow repository.

[netlify]

✅ Deploy Preview for kubernetes-sigs-kueue canceled.

Name	Link
🔨 Latest commit	7deeab2
🔍 Latest deploy log	https://app.netlify.com/projects/kubernetes-sigs-kueue/deploys/6a8d95c2917a260008ed1c8b

[kubernetes-prow]

Hi @Nilsachy. Thanks for your PR.

I'm waiting for a kubernetes-sigs member to verify that this patch is reasonable to test. If it is, they should reply with /ok-to-test on its own line. Until that is done, I will not automatically test new commits in this PR, but the usual testing commands by org members will still work.

Tip

We noticed you've done this a few times! Consider joining the org to skip this step and gain /lgtm and other bot rights. We recommend asking approvers on your previous PRs to sponsor you.

Once the patch is verified, the new status will be reflected by the ok-to-test label.

I understand the commands that are listed here.

Details

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes-sigs/prow repository.

[coderabbitai]

Note

Reviews paused

It looks like this branch is under active development. To avoid overwhelming you with review comments due to an influx of new commits, CodeRabbit has automatically paused this review. You can configure this behavior by changing the reviews.auto_review.auto_pause_after_reviewed_commits setting.

Use the following commands to manage reviews:

• @coderabbitai resume to resume automatic reviews.
• @coderabbitai review to trigger a single review.

Use the checkboxes below for quick actions:

• ▶️ Resume reviews
• 🔍 Trigger review

No actionable comments were generated in the recent review. 🎉

ℹ️ Recent review info

⚙️ Run configuration

Configuration used: Path: .coderabbit.yaml

Review profile: CHILL

Plan: Pro Plus

Run ID: faf41ba5-41b3-449b-ab49-7ab00e08754c

📥 Commits

Reviewing files that changed from the base of the PR and between 7278628 and 7deeab2.

📒 Files selected for processing (1)

• test/integration/singlecluster/tas/tas_test.go

Included review availability: Your plan provides up to 8 included reviews per hour; 7 remain after this review.

---

📝 Walkthrough

Walkthrough

The integration test updates cohort preemption topology and quotas. It uses two 4-CPU preemptor pods to test fragmented capacity. It verifies pending workload conditions after each eviction and confirms preemptor admission after both evictions.

Changes

Cohort preemption

Layer / File(s)	Summary
Configure prioritized cohort queues test/integration/singlecluster/tas/tas_test.go	The test adds rack r3 with 2-CPU node x3, reduces clusterQueueC CPU quota to 5, and changes the preemptor to two 4-CPU pods.
Validate multi-eviction ordering test/integration/singlecluster/tas/tas_test.go	The test checks the pending workload after the first eviction, completes the second eviction, then verifies preemptor admission and the pending workload’s topology-fit QuotaReserved=False condition.

Estimated code review effort: 3 (Moderate) | ~20 minutes

Merge Risk: ⚪ Minimal · up to 7deea

This PR adds localized integration-test coverage without changing production behavior, and no actionable merge-blocking risk remains after normal checks and review.

Suggested reviewers: j-skiba, tomsen02, sohankunkerkar

🚥 Pre-merge checks | ✅ 5

✅ Passed checks (5 passed)

Check name	Status	Explanation
Docstring Coverage	✅ Passed	No functions found in the changed files to evaluate docstring coverage. Skipping docstring coverage check. Docstring coverage is scoped to functions touched by this diff. Analyzed 0 functions across 1…
Linked Issues check	✅ Passed	Check skipped because no linked issues were found for this pull request.
Out of Scope Changes check	✅ Passed	Check skipped because no linked issues were found for this pull request.
Description Check	✅ Passed	Check skipped - CodeRabbit’s high-level summary is enabled.
Title check	✅ Passed	The title clearly describes the main change: testing topology-domain reservation for preemptor workloads across scheduling cycles. It is relevant and specific, despite the spelling error in “accross.”

Full details: Docstring Coverage

Explanation

No functions found in the changed files to evaluate docstring coverage. Skipping docstring coverage check. Docstring coverage is scoped to functions touched by this diff. Analyzed 0 functions across 1 files.

✨ Finishing Touches

🧪 Generate unit tests (beta)

• Create PR with unit tests

---

_{Comment @coderabbitai help to get the list of available commands.}

[Nilsachy]

cc @dkaluza

[dkaluza]

Combined with the simulated removal of specific victims, this guarantees that the preemptor consistently evaluates and selects the exact same topology domains in every cycle while evictions are ongoing.

I believe this is not fully accurate/correct.

What if other workloads starts to preempt workloads in domains that are lexicographicaly first and also would satisfy the first preemptor needs? Wouldn't they replace the "reserved" ones?
Can this lead to long waiting for preemptions in the edge case that somebody is preempting lexicographically first domains all the time?

[kshalot]

/ok-to-test
/area testing

[Nilsachy]

What if other workloads starts to preempt workloads in domains that are lexicographicaly first and also would satisfy the first preemptor needs? Wouldn't they replace the "reserved" ones? Can this lead to long waiting for preemptions in the edge case that somebody is preempting lexicographically first domains all the time?

IIUC in that case whichever pending preemptor is popped first from the iterator will get the domain. So yes in theory, if another preemptor is popped first, it could steal the domain.

But in the classical case, all the preemptor workloads at the head of the queue are ordered by Nominal vs Borrowing -> Priority -> Timestamp so the order shouldn't change across cycles.

So I only see such scenario possible with fair sharing.

But this IMO is the intended behaviour. If we truly reserve a specific topology domain for a workload regardless of whether it is at the head of the queue, we run the risk of blocking the resources indefinitely (let's say the preemptor workload that reserved this domain never gets admitted because of other higher priority workloads). In that case the nodes are completely idle and unusable no?

[dkaluza]

IIUC in that case whichever pending preemptor is popped first from the iterator will get the domain. So yes in theory, if another preemptor is popped first, it could steal the domain.

No, let's imagine we have 2 workloads W1 and W2, that need to preempt to be admitted.
W1 comes and preempts workloads on nodes C & D. So it has "C & D reserved" for it in this scheduling cycle and the next one.
Then when W1 is still waiting for C & D to be preempted, W2 comes and preempts workloads on nodes A & B. They are assigned to W2 in this cycle.

Then next cycle comes, and W1 as it first in the ordering (as it started preemptions first I guess this is the case) gets assigned to A & B since they are lexicographically first. W2 is assigned to remaining C & D.

I'm not saying this is a blocker in general, and that this is bad and we have to fix it - we should just consider if this is problematic for us. I believe it may lead to prolonged waiting for preemption in some circumstances.

I think this is not depending on the Fair Sharing in any way.

But this IMO is the intended behaviour. If we truly reserve a specific topology domain for a workload regardless of whether it is at the head of the queue, we run the risk of blocking the resources indefinitely (let's say the preemptor workload that reserved this domain never gets admitted because of other higher priority workloads). In that case the nodes are completely idle and unusable no?

I don't know actually. Aren't we prioritizing the preemptor anyway? Doesn't it have the quota already locked as for the change in the previous PR? So it will still be before the higher priority workloads that do not have quota reserved yet IIUC.

I'm not stating that anything is wrong in the implementation, just pointing out that this is more tricky and we should consider edge cases as described above - cause IIUC current implementation the assigned domains can still change between cycles.

[Nilsachy]

Then next cycle comes, and W1 as it first in the ordering (as it started preemptions first I guess this is the case) gets assigned to A & B since they are lexicographically first. W2 is assigned to remaining C & D.

Oh sorry I didn't understand what you meant. Yes you're right this could happen I think. But is that a problem? Both workloads need the same topology domain so as long as both workloads get admitted do we care about this at all?

I believe it may lead to prolonged waiting for preemption in some circumstances.

IIUC the delay you're mentioning is the eviction duration for C & D? I can't think of a solution where enforcing reservation of A & B for W1 doesn't raising other kinds of problems..

I don't know actually. Aren't we prioritizing the preemptor anyway? Doesn't it have the quota already locked as for the change in the previous PR? So it will still be before the higher priority workloads that do not have quota reserved yet IIUC.

It's correct that we are prioritizing the preemptor but there can be several other preemptor workloads at the same time. I'm thinking of a scenario where those preemptors continuously evaluate before W1 in the iterator. In that case we are not locking the quota either because quota locking happens "per cycle". IMO we should let those other preemptor workloads "steal" both the quota + topology as Kueue specifically wants them to be admitted first.

[dkaluza]

IIUC the delay you're mentioning is the eviction duration for C & D? I can't think of a solution where enforcing reservation of A & B for W1 doesn't raising other kinds of problems..

The delay I had in mind is the delay of preemting the workloads. W1 started preempting first C & D.
Then it is switching to A & B (which had the preemptions started later). In the edge case situation this can reoccur multiple times. It will not lead to infinite waiting cycle, it can pessimistically be the "time we are waiting for single preemption" * "number of workloads in the cluster when we started the first preemption", so in the edge case it can still be long.

It's correct that we are prioritizing the preemptor but there can be several other preemptor workloads at the same time. I'm thinking of a scenario where those preemptors continuously evaluate before W1 in the iterator. In that case we are not locking the quota either because quota locking happens "per cycle". IMO we should let those other preemptor workloads "steal" both the quota + topology as Kueue specifically wants them to be admitted first.

Here I agree if the order says workload should be first to lock the resources we should respect the order.
But the situation that I'm describing is a little other way around - the W1 can be actually "punished" in this particular scenario for being first. But maybe this is such an edge case that we shouldn't care about this at all.

[Nilsachy]

The delay I had in mind is the delay of preemting the workloads. W1 started preempting first C & D.
Then it is switching to A & B (which had the preemptions started later).

Sorry yes I mixed up A & B and C & D but that's what I understood.

It will not lead to infinite waiting cycle, it can pessimistically be the "time we are waiting for single preemption" * "number of workloads in the cluster when we started the first preemption", so in the edge case it can still be long.

Right I see your point. I can't think of an easy fix for that though. One idea that comes to mind is before falling back to compareDomainLevelValues(a, b) we can check if domain a or b matches the workload's previously targeted topology domains and give them a "sorting boost". So yet another idea of "stickyness" in the codebase 😅

But that's probably an overkill for now.. Especially that this is the existing mechanism on main.

[kshalot]

W2 is assigned to remaining C & D.

it can pessimistically be the "time we are waiting for single preemption" * "number of workloads in the cluster when we started the first preemption", so in the edge case it can still be long.

Actually, if W1 hops onto A & B (the targets of W2), I think there is no guarantee that W2 will be admissible on C & D. For example W1 requires co-location within a block, W2 within a rack. If C & D are in different racks then they were preempted for nothing, causing a disruption.

@coderabbitai Please open a GitHub issue that summarizes the above discussion and contains the relevant links. The goal of the issue is to evaluate the problem highlighted by @dkaluza and its impact, not strictly implement a fix yet. Do not assign anyone to the issue. Add area/tas, area/feature.

[coderabbitai]

Tip

For best results, initiate chat on the files or code changes.

🧩 Analysis chain

🏁 Script executed:

#!/bin/bash
set -euo pipefail

repo="kubernetes-sigs/kueue"
pr_number="14687"

echo "Matching discussion comments:"
gh api "repos/${repo}/issues/${pr_number}/comments?per_page=100" \
  --paginate \
  --jq '.[] | select(.user.login == "kshalot") | select(.body | contains("W2 is assigned to remaining C & D")) | {url: .html_url, body: .body}'

echo
echo "Requested labels:"
gh label list --repo "$repo" --limit 200 \
  --json name \
  --jq '.[] | select(.name == "area/tas" or .name == "area/feature") | .name'

Length of output: 1667

---

🏁 Script executed:

#!/bin/bash
set -euo pipefail

repo="kubernetes-sigs/kueue"
pr_url="https://github.com/kubernetes-sigs/kueue/pull/14687"
requester_comment_url="https://github.com/kubernetes-sigs/kueue/pull/14687#issuecomment-5372450798"

dkaluza_comment_url="$(
  gh api "repos/${repo}/issues/14687/comments?per_page=100" --paginate \
    --jq '.[] | select(.user.login == "dkaluza") | select(.body | contains("The delay I had in mind is the delay of preemting the workloads")) | .html_url' \
    | head -n 1
)"

body_file="$(mktemp)"
trap 'rm -f "$body_file"' EXIT

cat >"$body_file" <<EOF
## Summary

Evaluate topology-domain reassignment across scheduling cycles while preemptions are in progress.

A preemptor can target one set of topology domains in one scheduling cycle, start evictions there, and then select a different set in a later cycle. Another preemptor can cause this change by targeting lexicographically earlier domains that also satisfy the first preemptor.

## Problem to evaluate

The reassignment can extend the time to admission. A workload can wait for evictions in one domain set, then switch to a domain set whose evictions started later. In an edge case, repeated reassignment can make the wait proportional to the eviction duration times the number of relevant workloads.

The reassignment can also make earlier evictions unnecessary. For example:

- W1 requires co-location within a block.
- W2 requires co-location within a rack.
- W1 initially preempts C and D.
- W2 initially preempts A and B.
- In the next cycle, W1 selects A and B because they sort first.
- W2 receives C and D, but C and D can be in different racks.

In this case, W2 may not be admissible on C and D. The evictions for C and D caused disruption without enabling W2 admission.

This issue is for analysis only. It must determine the frequency, impact, and acceptable behavior of this case before proposing a design or implementation change.

## Investigation areas

- Confirm how topology-domain selection, simulated victim removal, quota locking, and scheduling order interact across scheduling cycles.
- Identify workloads with different topology constraints that can make reassigned domains invalid for a waiting preemptor.
- Determine whether reassignment can cause avoidable evictions, delayed admission, starvation-like behavior, or resource underuse.
- Define tests or simulations that reproduce representative cases.

## References

- Pull request: ${pr_url}
- Request to create this issue: ${requester_comment_url}
- Discussion of the delayed-preemption case: ${dkaluza_comment_url:-${pr_url}}
EOF

issue_url="$(
  gh issue create \
    --repo "$repo" \
    --title "Evaluate topology-domain reassignment during ongoing preemptions" \
    --body-file "$body_file" \
    --label "area/tas"
)"

echo "Created issue: ${issue_url}"

Length of output: 3031

---

@kshalot Created #14723: Evaluate topology-domain reassignment during ongoing preemptions.

The issue has area/tas and no assignee. The repository does not currently have an area/feature label, so I could not add it.

_{You are interacting with an AI system.}

[Nilsachy]

Actually, if W1 hops onto A & B (the targets of W2), I think there is no guarantee that W2 will be admissible on C & D. For example W1 requires co-location within a block, W2 within a rack. If C & D are in different racks then they were preempted for nothing, causing a disruption.

My question is, why would W1 not target A & B to start with? They are first lexicographically speaking. A & B would have to not exist or be already taken by a higher priority job when W1 issued preemption but somehow became valid candidates for preemption sometime after (but before C & D are fully evicted). Which is looking like less and less likely of an edge case.

[tenzen-y]

/release-note-none

[dkaluza]

The test looks good to me right now - it confirms that basic "ordering properties" are maintained also for the topologies. I think the further improvements in the topology locking that I mentioned are not strictly required right now and we can look into those when some users reports that this is a real issue.
/lgtm

[kubernetes-prow]

LGTM label has been added.

Details

Git tree hash: 7920f44558cd59ae8a0ad74f52b9e44fa49522e6

[Nilsachy]

/assign @tenzen-y

[tenzen-y]

This looks great to me, thanks!
/lgtm
/approve

[kubernetes-prow]

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: dkaluza, Nilsachy, tenzen-y

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Details

Needs approval from an approver in each of these files:

• test/OWNERS [tenzen-y]

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment

[tenzen-y]

/cherrypick release-0.18
/cherrypick release-0.19

[k8s-infra-cherrypick-robot]

@tenzen-y: once the present PR merges, I will cherry-pick it on top of release-0.18, release-0.19 in new PRs and assign them to you.

Details

In response to this:

/cherrypick release-0.18
/cherrypick release-0.19

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes-sigs/prow repository.

[k8s-infra-cherrypick-robot]

@tenzen-y: new pull request created: #14872

Details

In response to this:

/cherrypick release-0.18
/cherrypick release-0.19

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes-sigs/prow repository.

[k8s-infra-cherrypick-robot]

@tenzen-y: new pull request created: #14873

Details

In response to this:

/cherrypick release-0.18
/cherrypick release-0.19

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes-sigs/prow repository.

[tenzen-y]

@Nilsachy, can you manually open CPs due to #14873 (review)

[Nilsachy]

@Nilsachy, can you manually open CPs due to #14873 (review)

Sure I'll do that now