[
https://issues.apache.org/jira/browse/YUNIKORN-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18112442#comment-18112442
]
Yu-Lin Chen commented on YUNIKORN-3442:
---------------------------------------
Hi [~hedger9487], you can provide the actual reproduction test code instead of
pseudocode to ease the burden of tracing.
> [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
> Priority: Major
>
> 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]
