Hedger Lai created YUNIKORN-3442:
------------------------------------
Summary: [Core] Downstream TryPreemption drops K8s predicate
victims and falsely rejects preemption when node has available capacity
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
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 an architectural edge 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:
# *[Architectural Defect] 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 blindly 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!
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
