[
https://issues.apache.org/jira/browse/YUNIKORN-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Hedger Lai updated YUNIKORN-3442:
---------------------------------
Description:
h3. Problem
When preemption is triggered, the K8s shim evaluates predicate plugins (such as
PodAntiAffinity or TopologySpreadConstraints) and returns a specific list of
victim pods that must be removed for the preemptor to fit on the node.
However, in Core's {{TryPreemption()}}
({{pkg/scheduler/objects/preemption.go#L650-L663}}), the scheduler does not
honor this finalized victim list. Instead, it iterates through the victims and
only collects allocations that contribute to unsatisfied resource dimensions of
the ask:
{code:go}
for k, needVal := range p.ask.GetAllocatedResource().Resources {
if victimsTotalResource.Resources[k] < needVal && allocRes.Resources[k] > 0
{
finalVictims = append(finalVictims, victim)
victimsTotalResource.AddTo(allocRes)
break
}
}
{code}
h3. Impact
This secondary resource-based filtering breaks predicate guarantees.
Once the ask's CPU/memory demands are satisfied by earlier victims, any
subsequent victim selected by the Shim solely to resolve a PodAntiAffinity
constraint is silently dropped by the Core.
As a result:
# Innocent victims are evicted unnecessarily without allowing the preemptor to
schedule.
# The preemptor still fails predicate checks in subsequent scheduling cycles
because the anti-affinity culprit pod remains on the node.
# Preemption triggers repeatedly for the same ask, leading to victim eviction
churn and preemption livelock.
h3. Proposed Fix
Core's {{TryPreemption()}} should respect the victim list finalized by the Shim
for the target node and avoid secondary resource-based truncation, ensuring
predicate conditions verified by the Shim remain intact.
was:
h2. Description & Summary
While investigating and addressing YUNIKORN-3137 ({_}Fails to preempt more than
2 victims for a larger ask{_}), I traced the victim selection lifecycle into
downstream {{TryPreemption()}} and observed a subtle edge case case in the
post-filtering loop (originally introduced in YUNIKORN-2500) that attempts to
reduce preemption victims based purely on raw CPU/memory comparison against
{{{}p.ask{}}}.
Testing directly against clean {{master}} reveals two distinct defects:
# {*}[{{{}Design Limitation{}}}] Drops K8s Predicate Victims{*}: When the K8s
Shim reports that additional pods beyond pure capacity must be preempted to
satisfy K8s predicates (e.g. {{{}PodAntiAffinity{}}}, {{{}Taints{}}},
{{{}NodeVolumeLimits{}}}) with {{{}index > StartIndex{}}}, downstream currently
drops the predicate victims once earlier victims satisfy the ask's CPU/memory
demand. This causes preemption to succeed while leaving the node in a state
where K8s filter plugins reject the scheduled pod.
# {*}[Arithmetic Defect] Deficit Mismatch (Ignores Available Node
Capacity){*}: Downstream checks
{{StrictlyGreaterThanOnlyExisting(victimsTotalResource)}} directly against
{{{}p.ask.GetAllocatedResource(){}}}. Even though
{{p.nodeAvailableMap[nodeID]}} is already present in {{{}TryPreemption(){}}},
downstream completely ignores existing node available capacity. If a node has 2
vcores free and only needs 2 vcores from preemption for a 4-vcore ask,
downstream marks a preemption shortfall and falsely rejects preemption.
----
h2. Deep-Dive & Root Cause Analysis on master
h3. A. Bug 1: Architectural Split-Brain (Predicate Victim Truncation)
Victim selection in YuniKorn is divided across two layers:
* {*}Upstream ({{{}tryNodes(){}}} + K8s Shim {{{}PreemptionPredicates{}}}){*}:
** {{calculateVictimsByNode()}} computes {{StartIndex}} (the prefix of victims
needed for raw capacity, factoring in existing {{{}nodeAvailable{}}}).
** Shim simulates removing candidate pods starting from {{StartIndex}} and
evaluates K8s Filter plugins.
** If a predicate constraint (such as anti-affinity) exists on a pod at
{{index}} (where {{{}index > StartIndex{}}}), Shim returns {{{}index{}}}.
** In {{predicates.go:109}} ({{{}populateVictims(){}}}), upstream packages
{{{}result.victims = victimList[0..index]{}}}.
* {*}Downstream ({{{}TryPreemption(){}}}, master lines 650–662){*}:
** Downstream runs a secondary filter loop:
{code:go}
for _, victim := range victims {
if !fitIn && victim.GetNodeID() != nodeID {
continue
}
if
p.ask.GetAllocatedResource().StrictlyGreaterThanOnlyExisting(victimsTotalResource)
{
finalVictims = append(finalVictims, victim)
}
victimsTotalResource.AddTo(victim.GetAllocatedResource())
}
{code}
** {*}The Flaw{*}: Downstream is completely unaware of why upstream selected
{{{}victims[0..index]{}}}. If {{alloc0}} satisfies {{{}ask{}}}, downstream
stops appending victims, silently discarding {{alloc1}} and {{{}alloc2{}}}—even
though {{alloc2}} is the anti-affinity culprit!
h3. B. Bug 2: Deficit Mismatch with nodeAvailable
In master lines 664–668:
{code:go}
if
p.ask.GetAllocatedResource().StrictlyGreaterThanOnlyExisting(victimsTotalResource)
{
p.ask.LogAllocationFailure(common.PreemptionShortfall, true)
return nil, false
}
{code}
Notice that {{nodeCurrentAvailable := p.nodeAvailableMap[nodeID]}} is already
available in {{TryPreemption()}} (line 640), but the shortfall check completely
omits it!
Preemption only needs to cover the *deficit* ({{{}ask - nodeAvailable{}}}), not
the entire ask!
If a node has 2 vcores free and the ask needs 4 vcores, a victim freeing 2
vcores is sufficient. Downstream sees {{4 vcores > 2 vcores
(victimsTotalResource)}} and sets shortfall, aborting preemption.
----
h2. Deterministic Reproduction Unit Tests (on clean master)
I have verified two reproduction unit tests in
{{pkg/scheduler/objects/preemption_test.go}} directly on top of clean
{{master}} (commit {{{}7b3650b{}}}):
h3. Reproduction 1: TestTryPreemption_DownstreamDropsPredicateVictim
{code:go}
// Setup:
// - Node runs: alloc2 (1 vcore), alloc3 (1 vcore).
// - Ask (1 vcore) has anti-affinity against alloc2.
// - alloc3 alone satisfies capacity (StartIndex = 0).
// - Shim plugin reports index = 1 (both alloc3 and alloc2 must be preempted).
//
// Expected: alloc2 is preempted.
// Actual: alloc2.IsPreempted() is FALSE because downstream drops it!
func TestTryPreemption_DownstreamDropsPredicateVictim(t *testing.T) {
...
result, ok := preemptor.TryPreemption()
assert.Assert(t, ok, "preemption should succeed")
assert.Check(t, alloc3.IsPreempted(), "alloc3 should be preempted")
assert.Check(t, alloc2.IsPreempted(), "alloc2 MUST be preempted for
predicates to pass!") // FAILS!
}
{code}
h3. Reproduction 2: TestTryPreemption_DownstreamDeficitMismatchWithNodeAvailable
{code:go}
// Setup:
// - Node has 4 vcores capacity.
// - alloc1 runs with 2 vcores. Node has 2 vcores FREE.
// - Ask needs 4 vcores.
// - Preempting alloc1 (2 vcores) + node free (2 vcores) = 4 vcores.
//
// Expected: ok == true, alloc1 is preempted.
// Actual: ok == false, result == nil because downstream compares victimVal (2)
< ask (4)!
func TestTryPreemption_DownstreamDeficitMismatchWithNodeAvailable(t *testing.T)
{
...
result, ok := preemptor.TryPreemption()
assert.Assert(t, ok, "preemption should succeed because 2 free + 2 victim =
4 vcores") // FAILS!
}
{code}
----
h2. Architectural Alternatives & Feedback from Maintainers
I would appreciate feedback from maintainers on the preferred design direction:
h3. Point 1 (Undisputed Defect): Fix the Deficit Calculation
Regardless of the architectural decision on Point 2, downstream
{{TryPreemption()}} must factor in {{{}p.nodeAvailableMap[nodeID]{}}}:
* In the filtering loop: target need is {{{}deficit = max(0, ask -
nodeAvailable){}}}.
* In the shortfall check: preemption succeeds if {{{}nodeAvailable +
victimsTotalResource >= ask{}}}.
h3. Point 2 (Architectural Decision): How to Resolve the Predicate Truncation?
* {*}Option A (Preserve Selected Node Victims){*}:
** Ensure downstream {{TryPreemption()}} preserves all node victims selected
by {{tryNodes()}} ({{{}0..result.index{}}}), ensuring all predicate
requirements remain satisfied.
** {_}Pros{_}: Clean layer separation, zero performance overhead, immediate
bug resolution.
* {*}Option B (K8s kube-scheduler Reprieve Alignment){*}:
** In {{{}yunikorn-k8shim{}}}, implement a conditional reprieve mechanism
(when {{{}index > StartIndex{}}}) to back-test candidate pods and prune
innocent victims before returning to Core.
** {_}Pros{_}: Truly minimal victim set.
** {_}Cons{_}: Requires extending the SI callback response to pass a list of
arbitrary victim indices.
I have deterministic reproduction tests and candidate patches ready on clean
{{{}master{}}}. Any feedback or guidance on whether Option A or Option B better
fits YuniKorn's architectural roadmap would be much appreciated. I would be
very happy to take this issue on and submit the PR once we align on the
direction!
Summary: [Core] Preemptor ask may never be scheduled when encountering
pod anti-affinity (was: [Core] Downstream TryPreemption drops K8s predicate
victims and falsely rejects preemption when node has available capacity)
> [Core] Preemptor ask may never be scheduled when encountering pod
> anti-affinity
> -------------------------------------------------------------------------------
>
> Key: YUNIKORN-3442
> URL: https://issues.apache.org/jira/browse/YUNIKORN-3442
> Project: Apache YuniKorn
> Issue Type: Bug
> Components: core - scheduler
> Affects Versions: 1.6.0
> Reporter: Hedger Lai
> Assignee: Hedger Lai
> Priority: Major
>
> h3. Problem
> When preemption is triggered, the K8s shim evaluates predicate plugins (such
> as PodAntiAffinity or TopologySpreadConstraints) and returns a specific list
> of victim pods that must be removed for the preemptor to fit on the node.
> However, in Core's {{TryPreemption()}}
> ({{pkg/scheduler/objects/preemption.go#L650-L663}}), the scheduler does not
> honor this finalized victim list. Instead, it iterates through the victims
> and only collects allocations that contribute to unsatisfied resource
> dimensions of the ask:
> {code:go}
> for k, needVal := range p.ask.GetAllocatedResource().Resources {
> if victimsTotalResource.Resources[k] < needVal && allocRes.Resources[k] >
> 0 {
> finalVictims = append(finalVictims, victim)
> victimsTotalResource.AddTo(allocRes)
> break
> }
> }
> {code}
> h3. Impact
> This secondary resource-based filtering breaks predicate guarantees.
> Once the ask's CPU/memory demands are satisfied by earlier victims, any
> subsequent victim selected by the Shim solely to resolve a PodAntiAffinity
> constraint is silently dropped by the Core.
> As a result:
> # Innocent victims are evicted unnecessarily without allowing the preemptor
> to schedule.
> # The preemptor still fails predicate checks in subsequent scheduling cycles
> because the anti-affinity culprit pod remains on the node.
> # Preemption triggers repeatedly for the same ask, leading to victim eviction
> churn and preemption livelock.
> h3. Proposed Fix
> Core's {{TryPreemption()}} should respect the victim list finalized by the
> Shim for the target node and avoid secondary resource-based truncation,
> ensuring predicate conditions verified by the Shim remain intact.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
