[
https://issues.apache.org/jira/browse/YUNIKORN-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18112582#comment-18112582
]
Hedger Lai commented on YUNIKORN-3442:
--------------------------------------
Hi [~Yu-Lin Chen],
Thanks for looking into this! Here is the reproduction unit test that can be
directly appended to `pkg/scheduler/objects/preemption_test.go` on clean master:
{code:go}
// TestTryPreemption_DownstreamDropsPredicateVictim demonstrates the issue:
// When K8s Shim requires preempting additional victims to satisfy Predicates
(index > StartIndex, e.g. PodAntiAffinity),
// downstream TryPreemption drops them because raw capacity requirements were
already satisfied by earlier victims.
func TestTryPreemption_DownstreamDropsPredicateVictim(t *testing.T) {
appQueueMapping := NewAppQueueMapping()
node := newNode(nodeID1, map[string]resources.Quantity{"vcores": 3,
"mem": 200})
iterator := getNodeIteratorFn(node)
rootQ, err := createRootQueue(map[string]string{"vcores": "3", "mem":
"200"})
assert.NilError(t, err)
parentQ, err := createManagedQueueGuaranteed(rootQ, "parent", true,
nil, nil, appQueueMapping)
assert.NilError(t, err)
parentQ1, err := createManagedQueueGuaranteed(parentQ, "parent1", true,
nil, nil, appQueueMapping)
assert.NilError(t, err)
parentQ2, err := createManagedQueueGuaranteed(parentQ, "parent2", true,
nil, nil, appQueueMapping)
assert.NilError(t, err)
childQ1, err := createManagedQueueGuaranteed(parentQ1, "child1", false,
nil, map[string]string{"vcores": "2"}, appQueueMapping)
assert.NilError(t, err)
childQ2, err := createManagedQueueGuaranteed(parentQ2, "child2", false,
nil, map[string]string{"vcores": "1"}, appQueueMapping)
assert.NilError(t, err)
app1, app2, _ := createVictimApplications(childQ2, appQueueMapping)
ask2 := newAllocationAsk("alloc2", appID2,
resources.NewResourceFromMap(map[string]resources.Quantity{"vcores": 1, "mem":
100}))
ask2.createTime = time.Now()
assert.NilError(t, app1.AddAllocationAsk(ask2))
ask3 := newAllocationAsk("alloc3", appID2,
resources.NewResourceFromMap(map[string]resources.Quantity{"vcores": 1, "mem":
100}))
ask3.createTime = time.Now()
assert.NilError(t, app1.AddAllocationAsk(ask3))
alloc2 := newAllocationWithKey("alloc2", appID2, nodeID1,
resources.NewResourceFromMap(map[string]resources.Quantity{"vcores": 1, "mem":
100}))
alloc2.createTime = ask2.createTime
app2.AddAllocation(alloc2)
assert.Check(t, node.TryAddAllocation(alloc2), "node alloc2 failed")
alloc3 := newAllocationWithKey("alloc3", appID2, nodeID1,
resources.NewResourceFromMap(map[string]resources.Quantity{"vcores": 1, "mem":
100}))
alloc3.createTime = ask3.createTime
app2.AddAllocation(alloc3)
assert.Check(t, node.TryAddAllocation(alloc3), "node alloc3 failed")
assert.NilError(t,
childQ2.TryIncAllocatedResource(ask2.GetAllocatedResource()))
assert.NilError(t,
childQ2.TryIncAllocatedResource(ask3.GetAllocatedResource()))
// Ask requests 1 vcore
app4 := newApplication("app-4", "default", "root.parent.parent1.child1")
app4.SetQueue(childQ1)
ask4 := newAllocationAsk("alloc4", "app-4",
resources.NewResourceFromMap(map[string]resources.Quantity{"vcores": 1}))
assert.NilError(t, app4.AddAllocationAsk(ask4))
headRoom :=
resources.NewResourceFromMap(map[string]resources.Quantity{"vcores": 1})
preemptor := NewPreemptor(app4, headRoom, 30*time.Second, ask4,
iterator(), false)
// In calculateVictimsByNode: alloc3 alone satisfies capacity
(StartIndex=0).
// But predicate plugin simulates K8s Shim reporting that alloc2 must
also be preempted (victimIndex=1)
// to pass predicates (such as PodAntiAffinity).
preemptions := []mock.Preemption{mock.NewPreemption(true, "alloc4",
nodeID1, []string{"alloc3", "alloc2"}, 0, 1)}
plugin := mock.NewPreemptionPredicatePlugin(preemptions, nil, false,
false)
plugins.RegisterSchedulerPlugin(plugin)
defer plugins.UnregisterSchedulerPlugins()
result, ok := preemptor.TryPreemption()
assert.NilError(t, plugin.GetPredicateError())
assert.Assert(t, ok, "preemption should succeed")
assert.Assert(t, result != nil, "result should not be nil")
// alloc3 was preempted to satisfy the 1 vcore capacity:
assert.Check(t, alloc3.IsPreempted(), "alloc3 should be preempted")
// alloc2 MUST ALSO be preempted because K8s Shim required Index=1 for
Predicates to pass.
// Currently, this fails on clean master because downstream
TryPreemption drops alloc2:
assert.Check(t, alloc2.IsPreempted(), "alloc2 MUST be preempted for
predicates to pass!")
}
{code}
Hope this helps ease the 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 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]
