[
https://issues.apache.org/jira/browse/YUNIKORN-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Hedger Lai updated YUNIKORN-3442:
---------------------------------
Description:
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!
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 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!
> [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 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!
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
