This is an automated email from the ASF dual-hosted git repository.
mani pushed a commit to branch branch-1.8
in repository https://gitbox.apache.org/repos/asf/yunikorn-core.git
The following commit(s) were added to refs/heads/branch-1.8 by this push:
new 10f50b2b [YUNIKORN-3113] Resource-wise preemption (#1029) (#1060)
10f50b2b is described below
commit 10f50b2b9b300d7991e95365ccbf8012e495997a
Author: Manikandan R <[email protected]>
AuthorDate: Tue Jan 13 15:46:44 2026 +0530
[YUNIKORN-3113] Resource-wise preemption (#1029) (#1060)
Introduced FitInActual() method to decide whether the ask would fit into
the ask queue or not instead of using strict based methods to avoid
problems due to, from the asks' resource requirement perspective, unreleated
res types with negative values
Introduced two more methods in Preemptor to decide ask queue is under
guaranteed and victim queue is over guranateed or not from ask resource
requirement perspective. Used these methods in appropriate places to
simplify
the decision making Added tests for the same.
Closes: #1029
(cherry picked from commit 54a2a2566ee27e51c8d28588dc9a884e0ba4b48f)
Signed-off-by: Wilfred Spiegelenburg <[email protected]>
---
pkg/common/resources/resources.go | 19 +-
pkg/common/resources/resources_test.go | 71 ++++++++
pkg/scheduler/objects/preemption.go | 118 ++++++++----
pkg/scheduler/objects/preemption_test.go | 303 ++++++++++++++++++++++++++++++-
4 files changed, 459 insertions(+), 52 deletions(-)
diff --git a/pkg/common/resources/resources.go
b/pkg/common/resources/resources.go
index bb3df50a..290ba022 100644
--- a/pkg/common/resources/resources.go
+++ b/pkg/common/resources/resources.go
@@ -446,20 +446,27 @@ func subNonNegative(left, right *Resource) (*Resource,
string) {
// Types not defined in resource this is called against are considered 0 for
Quantity
// A nil resource is treated as an empty resource (no types defined)
func (r *Resource) FitIn(smaller *Resource) bool {
- return r.fitIn(smaller, false)
+ return r.fitIn(smaller, false, false)
}
// FitInMaxUndef checks if smaller fits in the defined resource
// Types not defined in resource this is called against are considered the
maximum value for Quantity
// A nil resource is treated as an empty resource (no types defined)
func (r *Resource) FitInMaxUndef(smaller *Resource) bool {
- return r.fitIn(smaller, true)
+ return r.fitIn(smaller, true, false)
+}
+
+// FitInActual checks if smaller fits in the defined resource based on the
actual values. Negative values too are compared as is.
+// Types not defined in resource this is called against are skipped
+// A nil resource is treated as an empty resource (no types defined)
+func (r *Resource) FitInActual(smaller *Resource) bool {
+ return r.fitIn(smaller, true, true)
}
// Check if smaller fits in the defined resource
-// Negative values will be treated as 0
+// Negative values will be treated as 0 if actual flag is false. Otherwise,
use the value as is and do the comparison later
// A nil resource is treated as an empty resource, behaviour defined by
skipUndef
-func (r *Resource) fitIn(smaller *Resource, skipUndef bool) bool {
+func (r *Resource) fitIn(smaller *Resource, skipUndef bool, actual bool) bool {
if r == nil {
r = Zero // shadows in the local function not seen by the
callers.
}
@@ -475,7 +482,9 @@ func (r *Resource) fitIn(smaller *Resource, skipUndef bool)
bool {
if skipUndef && !ok {
continue
}
- largerValue = max(0, largerValue)
+ if !actual {
+ largerValue = max(0, largerValue)
+ }
if v > largerValue {
return false
}
diff --git a/pkg/common/resources/resources_test.go
b/pkg/common/resources/resources_test.go
index 4375a076..5c3b844d 100644
--- a/pkg/common/resources/resources_test.go
+++ b/pkg/common/resources/resources_test.go
@@ -1381,6 +1381,77 @@ func TestFitInSkip(t *testing.T) {
}
}
+func TestFitInActual(t *testing.T) {
+ tests := []struct {
+ larger *Resource
+ smaller *Resource
+ expected bool
+ message string
+ }{
+ {
+ larger: NewResource(),
+ smaller: &Resource{Resources: map[string]Quantity{"a":
1}},
+ expected: true,
+ message: "defined resource %+v should fit in empty
(skip undefined)",
+ },
+ {
+ larger: NewResourceFromMap(map[string]Quantity{"a":
5}),
+ smaller: &Resource{Resources: map[string]Quantity{"a":
1}},
+ expected: true,
+ message: "fitin smaller resource with value %+v should
fit in larger %+v (skip undefined)",
+ },
+ {
+ smaller: &Resource{Resources: map[string]Quantity{"a":
1}},
+ larger: &Resource{Resources:
map[string]Quantity{"not-in-smaller": 1}},
+ expected: true,
+ message: "different type in smaller %+v should fit in
larger %+v (skip undefined)",
+ },
+ {
+ larger: &Resource{Resources:
map[string]Quantity{"not-in-smaller": 1}},
+ smaller: &Resource{Resources:
map[string]Quantity{"not-in-larger": 1}},
+ expected: true,
+ message: "different type in smaller %+v should fit in
larger %+v (skip undefined)",
+ },
+ {
+ larger: &Resource{Resources: map[string]Quantity{"a":
-10}},
+ smaller: &Resource{Resources: map[string]Quantity{"a":
0, "b": -10}},
+ expected: false,
+ message: "fitin smaller resource with zero or neg
values %+v should not fit in larger %+v (skip undefined)",
+ },
+ {
+ larger: &Resource{Resources: map[string]Quantity{"a":
-5}},
+ smaller: &Resource{Resources: map[string]Quantity{"a":
0, "b": 10}},
+ expected: false,
+ message: "fitin smaller resource with value %+v should
not fit in larger %+v (skip undefined)",
+ },
+ {
+ larger: &Resource{Resources: map[string]Quantity{"a":
-5}},
+ smaller: &Resource{Resources: map[string]Quantity{"a":
-4, "b": 10}},
+ expected: false,
+ message: "fitin smaller resource with lesser neg value
%+v should not fit in larger %+v (skip undefined)",
+ },
+ {
+ larger: &Resource{Resources: map[string]Quantity{"a":
-5}},
+ smaller: &Resource{Resources: map[string]Quantity{"a":
-6, "b": 10}},
+ expected: true,
+ message: "fitin smaller resource with higher neg value
%+v should fit in larger %+v (skip undefined)",
+ },
+ {
+ larger: &Resource{Resources: map[string]Quantity{"a":
-5}},
+ smaller: &Resource{Resources: map[string]Quantity{"a":
-5, "b": 10}},
+ expected: true,
+ message: "fitin smaller resource with equal neg value
%+v should fit in larger %+v (skip undefined)",
+ },
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.message, func(t *testing.T) {
+ result := tc.larger.FitInActual(tc.smaller)
+ assert.Equal(t, result, tc.expected, tc.message,
tc.smaller, tc.larger)
+ })
+ }
+}
+
//nolint:funlen // thorough test
func TestGetFairShare(t *testing.T) {
// 0 guarantee should be treated as absence of a gurantee
diff --git a/pkg/scheduler/objects/preemption.go
b/pkg/scheduler/objects/preemption.go
index f2aa91dc..4849c8d0 100644
--- a/pkg/scheduler/objects/preemption.go
+++ b/pkg/scheduler/objects/preemption.go
@@ -218,7 +218,10 @@ func (p *Preemptor) checkPreemptionQueueGuarantees() bool {
zap.String("queuePath", p.queuePath))
return false
}
-
+ oldRemaining := currentQueue.GetRemainingGuaranteedResource()
+ if oldRemaining != nil &&
oldRemaining.FitInActual(p.ask.GetAllocatedResource()) {
+ return true
+ }
currentQueue.AddAllocation(p.ask.GetAllocatedResource())
// remove each allocation in turn, validating that at some point we
free enough resources to allow this ask to fit
@@ -226,7 +229,9 @@ func (p *Preemptor) checkPreemptionQueueGuarantees() bool {
for _, alloc := range snapshot.PotentialVictims {
snapshot.RemoveAllocation(alloc.GetAllocatedResource())
remaining :=
currentQueue.GetRemainingGuaranteedResource()
- if remaining != nil &&
resources.StrictlyGreaterThanOrEquals(remaining, resources.Zero) {
+
+ // Is all ask's res types in ask queue still under
guaranteed?
+ if remaining != nil &&
isAskQueueUnderGuaranteed(p.ask.GetAllocatedResource(), remaining) {
return true
}
}
@@ -268,26 +273,24 @@ func (p *Preemptor) calculateVictimsByNode(nodeAvailable
*resources.Resource, po
// check to see if removing this task will keep queue above
guaranteed amount; if not, skip to the next one
if qv, ok := p.queueByAlloc[victim.GetAllocationKey()]; ok {
if queueSnapshot, ok2 :=
allocationsByQueueSnap[qv.QueuePath]; ok2 {
- oldRemaining :=
queueSnapshot.GetRemainingGuaranteedResource()
+ remaining :=
queueSnapshot.GetRemainingGuaranteedResource()
queueSnapshot.RemoveAllocation(victim.GetAllocatedResource())
preemptableResource :=
queueSnapshot.GetPreemptableResource()
- // Did removing this allocation still keep the
queue over-allocated?
+ // Did removing this allocation still keep the
victim queue over-allocated?
// At times, over-allocation happens because of
resource types in usage but not defined as guaranteed.
- // So, as an additional check, -ve remaining
guaranteed resource before removing the victim means
- // some really useful victim is there.
+ // So, as an additional check, res types used
by ask should be either -ve or zero in victim queue remaining guaranteed
resource to confirm
+ // some relevant useful victim is there.
// In case of victims densely populated on any
specific node, checking/honouring the guaranteed quota on ask or preemptor queue
// acts as early filtering layer to carry
forward only the required victims.
// For other cases like victims spread over
multiple nodes, this doesn't add great value.
if
resources.StrictlyGreaterThanOrEquals(preemptableResource, resources.Zero) &&
- (oldRemaining == nil ||
resources.StrictlyGreaterThan(resources.Zero, oldRemaining)) {
- // add the current victim into the ask
queue
-
askQueue.AddAllocation(victim.GetAllocatedResource())
- askQueueNewRemaining :=
askQueue.GetRemainingGuaranteedResource()
-
- // Did adding this allocation make the
ask queue over - utilized?
- if askQueueNewRemaining != nil &&
resources.StrictlyGreaterThan(resources.Zero, askQueueNewRemaining) {
-
askQueue.RemoveAllocation(victim.GetAllocatedResource())
+ (remaining == nil ||
isVictimQueueOverGuaranteed(p.ask.GetAllocatedResource(), remaining)) {
+ // Does victimQueue have space
equivalent to the resource used by the victim?
+ askQueueRemaining :=
askQueue.GetRemainingGuaranteedResource()
+ if askQueueRemaining != nil &&
askQueueRemaining.FitInActual(victim.GetAllocatedResource()) {
+
askQueue.AddAllocation(victim.GetAllocatedResource())
+ } else {
queueSnapshot.AddAllocation(victim.GetAllocatedResource())
break
}
@@ -340,17 +343,17 @@ func (p *Preemptor) calculateVictimsByNode(nodeAvailable
*resources.Resource, po
// check to see if removing this task will keep queue above
guaranteed amount; if not, skip to the next one
if qv, ok := p.queueByAlloc[victim.GetAllocationKey()]; ok {
if queueSnapshot, ok2 :=
allocationsByQueueSnap[qv.QueuePath]; ok2 {
- oldRemaining :=
queueSnapshot.GetRemainingGuaranteedResource()
+ remaining :=
queueSnapshot.GetRemainingGuaranteedResource()
queueSnapshot.RemoveAllocation(victim.GetAllocatedResource())
preemptableResource :=
queueSnapshot.GetPreemptableResource()
- // Did removing this allocation still keep the
queue over-allocated?
+ // Did removing this allocation still keep the
victim queue over-allocated?
// At times, over-allocation happens because of
resource types in usage but not defined as guaranteed.
- // So, as an additional check, -ve remaining
guaranteed resource before removing the victim means
- // some really useful victim is there.
+ // So, as an additional check, res types used
by ask should be either -ve or zero in victim queue remaining guaranteed
resource to confirm
+ // some relevant useful victim is there.
// Similar checks could be added even on the
ask or preemptor queue to prevent being over utilized.
if
resources.StrictlyGreaterThanOrEquals(preemptableResource, resources.Zero) &&
- (oldRemaining == nil ||
resources.StrictlyGreaterThan(resources.Zero, oldRemaining)) {
+ (remaining == nil ||
isVictimQueueOverGuaranteed(p.ask.GetAllocatedResource(), remaining)) {
// removing task does not violate queue
constraints, adjust queue and node
nodeCurrentAvailable.AddTo(victim.GetAllocatedResource())
// check if ask now fits and we haven't
had this happen before
@@ -499,29 +502,28 @@ func (p *Preemptor)
calculateAdditionalVictims(nodeVictims []*Allocation) ([]*Al
// check to see if removing this task will keep queue above
guaranteed amount; if not, skip to the next one
if qv, ok := p.queueByAlloc[victim.GetAllocationKey()]; ok {
if queueSnapshot, ok2 :=
allocationsByQueueSnap[qv.QueuePath]; ok2 {
- oldRemaining :=
queueSnapshot.GetRemainingGuaranteedResource()
+ remaining :=
queueSnapshot.GetRemainingGuaranteedResource()
queueSnapshot.RemoveAllocation(victim.GetAllocatedResource())
- // Did removing this allocation still keep the
queue over-allocated?
+ // Did removing this allocation still keep the
victim queue over-allocated?
// At times, over-allocation happens because of
resource types in usage but not defined as guaranteed.
- // So, as an additional check, -ve remaining
guaranteed resource before removing the victim means
- // some really useful victim is there.
+ // So, as an additional check, res types used
by ask should be either -ve or zero in victim queue remaining guaranteed
resource to confirm
+ // some relevant useful victim is there.
preemptableResource :=
queueSnapshot.GetPreemptableResource()
if
resources.StrictlyGreaterThanOrEquals(preemptableResource, resources.Zero) &&
- (oldRemaining == nil ||
resources.StrictlyGreaterThan(resources.Zero, oldRemaining)) {
- askQueueRemainingAfterVictimRemoval :=
askQueue.GetRemainingGuaranteedResource()
-
- // add the current victim into the ask
queue
-
askQueue.AddAllocation(victim.GetAllocatedResource())
- askQueueNewRemaining :=
askQueue.GetRemainingGuaranteedResource()
- // Did adding this allocation make the
ask queue over - utilized?
- if askQueueNewRemaining != nil &&
resources.StrictlyGreaterThan(resources.Zero, askQueueNewRemaining) {
-
askQueue.RemoveAllocation(victim.GetAllocatedResource())
+ (remaining == nil ||
isVictimQueueOverGuaranteed(p.ask.GetAllocatedResource(), remaining)) {
+ // Does victimQueue have space
equivalent to the resource used by the victim?
+ askQueueRemaining :=
askQueue.GetRemainingGuaranteedResource()
+ if askQueueRemaining != nil &&
askQueueRemaining.FitInActual(victim.GetAllocatedResource()) {
+
askQueue.AddAllocation(victim.GetAllocatedResource())
+ } else {
queueSnapshot.AddAllocation(victim.GetAllocatedResource())
break
}
+ askQueueNewRemaining :=
askQueue.GetRemainingGuaranteedResource()
+
// check to see if the shortfall on the
queue has changed
- if
!resources.EqualsOrEmpty(askQueueRemainingAfterVictimRemoval,
askQueueNewRemaining) {
+ if
!resources.EqualsOrEmpty(askQueueRemaining, askQueueNewRemaining) {
// remaining capacity changed,
so we should keep this task
victims = append(victims,
victim)
} else {
@@ -536,12 +538,17 @@ func (p *Preemptor)
calculateAdditionalVictims(nodeVictims []*Allocation) ([]*Al
}
}
}
- // At last, did the ask queue usage under or equals guaranteed quota?
- finalRemainingRes := askQueue.GetRemainingGuaranteedResource()
- if finalRemainingRes != nil &&
resources.StrictlyGreaterThanOrEquals(finalRemainingRes, resources.Zero) {
- return victims, true
+
+ // At last, did the ask queue usage under or equals guaranteed quota
after finding the additional victims?
+ if len(victims) > 0 {
+ finalRemainingRes := askQueue.GetRemainingGuaranteedResource()
+ if finalRemainingRes != nil &&
isAskQueueUnderGuaranteed(p.ask.GetAllocatedResource(), finalRemainingRes) {
+ return victims, true
+ } else {
+ return victims, false
+ }
}
- return nil, false
+ return nil, true
}
// tryNodes attempts to find potential nodes for scheduling. For each node,
potential victims are passed to
@@ -678,7 +685,7 @@ func (p *Preemptor) TryPreemption() (*AllocationResult,
bool) {
log.Log(log.SchedPreemption).Info("Preempting task",
zap.String("askApplicationID",
p.ask.applicationID),
zap.String("askAllocationKey",
p.ask.allocationKey),
- zap.String("askQueue", p.queue.Name),
+ zap.String("victimQueue", p.queue.Name),
zap.String("victimApplicationID",
victim.GetApplicationID()),
zap.String("victimAllocationKey",
victim.GetAllocationKey()),
zap.Stringer("victimAllocatedResource",
victim.GetAllocatedResource()),
@@ -705,7 +712,8 @@ func (p *Preemptor) TryPreemption() (*AllocationResult,
bool) {
log.Log(log.SchedPreemption).Info("Reserving node for ask after
preemption",
zap.String("allocationKey", p.ask.GetAllocationKey()),
zap.String("nodeID", nodeID),
- zap.Int("victimCount", len(victims)))
+ zap.Int("collected victim count", len(victims)),
+ zap.Int("preempted victim count", len(finalVictims)))
return newReservedAllocationResult(nodeID, p.ask), true
}
@@ -914,3 +922,33 @@ func batchPreemptionChecks(checks
[]*si.PreemptionPredicatesArgs, batchSize int)
}
return result
}
+
+// isAskQueueUnderGuaranteed Is Ask Queue (not in general sense) under
guaranteed purely based on the ask's resource requirement?
+// Traverse each ask's res type, confirm its existence in ask queue and check
whether it has -ve or not.
+// -ve value means over guaranteed, return false to confirm the same
+// For all other cases (even if non-matching res type has -ve value), return
true
+func isAskQueueUnderGuaranteed(askResource *resources.Resource, askQueue
*resources.Resource) bool {
+ for resType := range askResource.Resources {
+ if val, ok := askQueue.Resources[resType]; ok {
+ if val < 0 {
+ return false
+ }
+ }
+ }
+ return true
+}
+
+// isVictimQueueOverGuaranteed Is Victim Queue (not in general sense) over
guaranteed purely based on the ask's resource requirement?
+// Traverse each ask's res type, confirm its existence in victim queue and
check whether it has -ve or not.
+// -ve value means over guaranteed, return true to confirm the same
+// For all other cases (even if non-matching res type has -ve value), return
false
+func isVictimQueueOverGuaranteed(askResource *resources.Resource, victimQueue
*resources.Resource) bool {
+ for resType := range askResource.Resources {
+ if val, ok := victimQueue.Resources[resType]; ok {
+ if val < 0 {
+ return true
+ }
+ }
+ }
+ return false
+}
diff --git a/pkg/scheduler/objects/preemption_test.go
b/pkg/scheduler/objects/preemption_test.go
index 017c9395..599e0f66 100644
--- a/pkg/scheduler/objects/preemption_test.go
+++ b/pkg/scheduler/objects/preemption_test.go
@@ -44,7 +44,17 @@ func creatApp1(
app1Rec map[string]resources.Quantity,
appQueueMapping *AppQueueMapping,
) (*Allocation, *Allocation, error) {
- app1 := newApplication(appID1, "default", "root.parent.child1")
+ return creatApp1WithTwoDifferentAllocations(childQ1, node1, node2,
app1Rec, app1Rec, appQueueMapping)
+}
+
+func creatApp1WithTwoDifferentAllocations(
+ childQ1 *Queue,
+ node1 *Node,
+ node2 *Node,
+ app1Rec map[string]resources.Quantity,
+ app2Rec map[string]resources.Quantity, appQueueMapping *AppQueueMapping,
+) (*Allocation, *Allocation, error) {
+ app1 := newApplication(appID1, "default", childQ1.QueuePath)
app1.SetQueue(childQ1)
childQ1.AddApplication(app1)
appQueueMapping.AddAppQueueMapping(app1.ApplicationID, childQ1)
@@ -54,7 +64,7 @@ func creatApp1(
if err := app1.AddAllocationAsk(ask1); err != nil {
return nil, nil, err
}
- ask2 := newAllocationAsk("alloc2", appID1,
resources.NewResourceFromMap(app1Rec))
+ ask2 := newAllocationAsk("alloc2", appID1,
resources.NewResourceFromMap(app2Rec))
ask2.createTime = time.Now()
if err := app1.AddAllocationAsk(ask2); err != nil {
return nil, nil, err
@@ -68,14 +78,14 @@ func creatApp1(
}
var alloc2 *Allocation
if node2 != nil {
- alloc2 = newAllocationWithKey("alloc2", appID1, nodeID2,
resources.NewResourceFromMap(app1Rec))
+ alloc2 = newAllocationWithKey("alloc2", appID1, nodeID2,
resources.NewResourceFromMap(app2Rec))
alloc2.createTime = ask2.createTime
app1.AddAllocation(alloc2)
if !node2.TryAddAllocation(alloc2) {
return nil, nil, fmt.Errorf("node alloc2 failed")
}
} else {
- alloc2 = newAllocationWithKey("alloc2", appID1, nodeID1,
resources.NewResourceFromMap(app1Rec))
+ alloc2 = newAllocationWithKey("alloc2", appID1, nodeID1,
resources.NewResourceFromMap(app2Rec))
alloc2.createTime = ask2.createTime
if !node1.TryAddAllocation(alloc2) {
return nil, nil, fmt.Errorf("node alloc2 failed")
@@ -98,7 +108,7 @@ func creatApp2(
allocID string,
appQueueMapping *AppQueueMapping,
) (*Application, *Allocation, error) {
- app2 := newApplication(appID2, "default", "root.parent.child2")
+ app2 := newApplication(appID2, "default", childQ2.QueuePath)
app2.SetQueue(childQ2)
childQ2.AddApplication(app2)
appQueueMapping.AddAppQueueMapping(app2.ApplicationID, childQ2)
@@ -226,7 +236,8 @@ func
TestCheckPreemptionQueueGuaranteesWithNoGuaranteedResources(t *testing.T) {
t.Run(tt.testName, func(t *testing.T) {
appQueueMapping := NewAppQueueMapping()
node := newNode("node1",
map[string]resources.Quantity{"first": 20})
- iterator := getNodeIteratorFn(node)
+ node2 := newNode("node2",
map[string]resources.Quantity{"first": 20})
+ iterator := getNodeIteratorFn(node, node2)
rootQ, err :=
createRootQueue(map[string]string{"first": "20"})
assert.NilError(t, err)
parentQ, err := createManagedQueueGuaranteed(rootQ,
"parent", true, map[string]string{}, tt.parentGuaranteed, appQueueMapping)
@@ -236,7 +247,7 @@ func
TestCheckPreemptionQueueGuaranteesWithNoGuaranteedResources(t *testing.T) {
childQ2, err := createManagedQueueGuaranteed(parentQ,
"child2", false, map[string]string{}, tt.childGuaranteed, appQueueMapping)
assert.NilError(t, err)
- alloc1, alloc2, err := creatApp1(childQ1, node, nil,
map[string]resources.Quantity{"first": 5}, appQueueMapping)
+ alloc1, alloc2, err := creatApp1(childQ1, node, node2,
map[string]resources.Quantity{"first": 5}, appQueueMapping)
assert.NilError(t, err)
assert.Assert(t, alloc1 != nil, "alloc1 should not be
nil")
assert.Assert(t, alloc2 != nil, "alloc2 should not be
nil")
@@ -261,6 +272,54 @@ func
TestCheckPreemptionQueueGuaranteesWithNoGuaranteedResources(t *testing.T) {
}
}
+func TestIsAskQueueUnderGuaranteed(t *testing.T) {
+ var tests = []struct {
+ testName string
+ askResource *resources.Resource
+ askQueue *resources.Resource
+ expected bool
+ }{
+ {"matching res types with +ve value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10}), true},
+ {"matching res types with zero value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 0}), true},
+ {"matching res types with -ve value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": -10}),
false},
+ {"matching res types, one with -ve value and another with +ve
value", resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1,
"second": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"second": -10}), false},
+ {"both matching res types with +ve value and non matching res
types with -ve value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"second": -10}), true},
+ {"both matching res types with -ve value and non matching res
types with +ve value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": -10,
"second": 10}), false},
+ {"both matching res types with +ve value and non matching res
types", resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1,
"third": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10}), true},
+ {"both matching res types with -ve value and non matching res
types", resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1,
"third": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": -10}),
false},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.testName, func(t *testing.T) {
+ assert.Equal(t,
isAskQueueUnderGuaranteed(tt.askResource, tt.askQueue), tt.expected)
+ })
+ }
+}
+
+func TestIsVictimQueueOverGuaranteed(t *testing.T) {
+ var tests = []struct {
+ testName string
+ askResource *resources.Resource
+ victimQueue *resources.Resource
+ expected bool
+ }{
+ {"matching res types with +ve value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10}),
false},
+ {"matching res types with zero value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 0}), false},
+ {"matching res types with -ve value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": -10}),
true},
+ {"matching res types, one with -ve value and another with +ve
value", resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1,
"second": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"second": -10}), true},
+ {"both matching res types with +ve value and non matching res
types with -ve value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"second": -10}), false},
+ {"both matching res types with -ve value and non matching res
types with +ve value",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": -10,
"second": 10}), true},
+ {"both matching res types with +ve value and non matching res
types", resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1,
"third": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10}),
false},
+ {"both matching res types with -ve value and non matching res
types", resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1,
"third": 1}),
resources.NewResourceFromMap(map[string]resources.Quantity{"first": -10}),
true},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.testName, func(t *testing.T) {
+ assert.Equal(t,
isVictimQueueOverGuaranteed(tt.askResource, tt.victimQueue), tt.expected)
+ })
+ }
+}
+
func TestTryPreemption(t *testing.T) {
appQueueMapping := NewAppQueueMapping()
node := newNode(nodeID1, map[string]resources.Quantity{"first": 10,
"pods": 5})
@@ -1957,3 +2016,233 @@ func
TestTryPreemption_OnNode_UGParent_With_UGPreemptorChild_OGVictimChild_As_Si
assert.Check(t, !alloc1.IsPreempted(), "alloc1 preempted")
assert.Check(t, alloc2.IsPreempted(), "alloc2 not preempted")
}
+
+// TestTryPreemption_VictimQueue_With_OG_And_UG_ResTypes Test try preemption
with 2 level queue hierarchy.
+// Guaranteed set on both victim queue path and preemptor queue path.
+// Victim queue has used some res types only but not all defined in guaranteed.
+// Request (Preemptor) resource type matches with victim's queue used resource
types, but not all the resource types defined in guaranteed.
+// Though not all res types defined in victim's guaranteed not being used and
not has any relevance from preemptor ask resource requirement perspective,
preemption should
+// be triggerred and consider the victim queue as candidate and kill the
victims whose resource type matches with ask res types.
+// Setup:
+// Nodes are Node1 & Node2. Node has enough space to accommodate the new ask.
+// root.parent.child1. Guaranteed set on root.parent.child1, first: 10,
second: 2 Allocations (belongs to single app) are running. Each Allocation
usage is first:10. Total usage is first:20.
+// root.parent.child2. Guaranteed set on root.parent.child2, first: 10.
Request of first: 5 is waiting for resources.
+// 1 Allocation on root.parent.child1 should be preempted to free up resources
for ask arrived in root.parent.child2 even though some guaranteed resource
types is not being used at all.
+func TestTryPreemption_VictimQueue_With_OG_And_UG_ResTypes(t *testing.T) {
+ node1 := newNode(nodeID1, map[string]resources.Quantity{"first": 10,
"second": 2})
+ node2 := newNode(nodeID2, map[string]resources.Quantity{"first": 10,
"second": 2})
+ iterator := getNodeIteratorFn(node1, node2)
+ appQueueMapping := NewAppQueueMapping()
+ rootQ, err := createRootQueue(map[string]string{"first": "20",
"storage": "4"})
+ assert.NilError(t, err)
+ parentQ, err := createManagedQueueGuaranteed(rootQ, "parent", true,
map[string]string{"first": "20", "second": "4"}, nil, appQueueMapping)
+ assert.NilError(t, err)
+ childQ1, err := createManagedQueueGuaranteed(parentQ, "child1", false,
nil, map[string]string{"first": "10", "second": "2"}, appQueueMapping)
+ assert.NilError(t, err)
+ childQ2, err := createManagedQueueGuaranteed(parentQ, "child2", false,
nil, map[string]string{"first": "10"}, appQueueMapping)
+ assert.NilError(t, err)
+
+ alloc1, alloc2, err := creatApp1(childQ1, node1, node2,
map[string]resources.Quantity{"first": 10}, appQueueMapping)
+ assert.NilError(t, err)
+
+ app2, ask3, err := creatApp2(childQ2,
map[string]resources.Quantity{"first": 5}, "alloc3", appQueueMapping)
+ assert.NilError(t, err)
+
+ headRoom :=
resources.NewResourceFromMap(map[string]resources.Quantity{"second": 4})
+ preemptor := NewPreemptor(app2, headRoom, 30*time.Second, ask3,
iterator(), false)
+
+ result, ok := preemptor.TryPreemption()
+ assert.Assert(t, result != nil, "unexpected result")
+ assert.Equal(t, ok, true, "victims found")
+ assert.Check(t, alloc1.IsPreempted() || alloc2.IsPreempted(), "alloc1
or alloc2 preempted")
+}
+
+// TestTryPreemption_VictimQueue_Under_Diff_Parent_With_OG_And_UG_ResTypes
Test try preemption with 3 level queue hierarchy.
+// Guaranteed set on both victim queue path and preemptor queue path.
+// Victim queue has used some res types only but not all defined in guaranteed.
+// Request (Preemptor) resource type matches with victim's queue used resource
types, but not all the resource types defined in guaranteed.
+// Though not all res types defined in victim's guaranteed not being used and
not has any relevance from preemptor ask resource requirement perspective,
preemption should
+// be triggerred and consider the victim queue as candidate and kill the
victims whose resource type matches with ask res types.
+// Setup:
+// Nodes are Node1 & Node2. Node has enough space to accommodate the new ask.
+// root.parent.parent1.child1. Guaranteed set on root.parent.parent1.child1,
first: 10, second: 2 Allocations (belongs to single app) are running. Each
Allocation usage is first:10. Total usage is first:20.
+// root.parent.parent2.child2. Guaranteed set on root.parent.parent2.child2,
first: 10. Request of first: 5 is waiting for resources.
+// 1 Allocation on root.parent.parent1.child1 should be preempted to free up
resources for ask arrived in root.parent.parent2.child2 even though some
guaranteed resource types of parent2 is not being used at all.
+func TestTryPreemption_VictimQueue_Under_Diff_Parent_With_OG_And_UG_ResTypes(t
*testing.T) {
+ var tests = []struct {
+ testName string
+ victimParentGuaranteed map[string]string
+ askParentGuaranteed map[string]string
+ victimChildGuaranteed map[string]string
+ askChildGuaranteed map[string]string
+ }{
+ {"victim queue under parent different from ask queue with some
OG res types", map[string]string{"first": "10", "second": "2"},
map[string]string{"first": "10"}, nil, nil},
+ {"victim queue with some OG res types under parent different
from ask queue", nil, nil, map[string]string{"first": "10", "second": "2"},
map[string]string{"first": "10"}},
+ }
+ for _, tt := range tests {
+ t.Run(tt.testName, func(t *testing.T) {
+ node1 := newNode(nodeID1,
map[string]resources.Quantity{"first": 10, "second": 2})
+ node2 := newNode(nodeID2,
map[string]resources.Quantity{"first": 10, "second": 2})
+ iterator := getNodeIteratorFn(node1, node2)
+ appQueueMapping := NewAppQueueMapping()
+ rootQ, err :=
createRootQueue(map[string]string{"first": "20", "storage": "4"})
+ assert.NilError(t, err)
+ parentQ, err := createManagedQueueGuaranteed(rootQ,
"parent", true, map[string]string{"first": "20", "second": "4"}, nil,
appQueueMapping)
+ assert.NilError(t, err)
+ parentQ1, err := createManagedQueueGuaranteed(parentQ,
"parent1", true, nil, tt.victimParentGuaranteed, appQueueMapping)
+ assert.NilError(t, err)
+ parentQ2, err := createManagedQueueGuaranteed(parentQ,
"parent2", true, nil, tt.askParentGuaranteed, appQueueMapping)
+ assert.NilError(t, err)
+ childQ1, err := createManagedQueueGuaranteed(parentQ1,
"child1", false, nil, tt.victimChildGuaranteed, appQueueMapping)
+ assert.NilError(t, err)
+ childQ2, err := createManagedQueueGuaranteed(parentQ2,
"child2", false, nil, tt.askChildGuaranteed, appQueueMapping)
+ assert.NilError(t, err)
+
+ alloc1, alloc2, err := creatApp1(childQ1, node1, node2,
map[string]resources.Quantity{"first": 10}, appQueueMapping)
+ assert.NilError(t, err)
+
+ app2, ask3, err := creatApp2(childQ2,
map[string]resources.Quantity{"first": 5}, "alloc3", appQueueMapping)
+ assert.NilError(t, err)
+
+ headRoom :=
resources.NewResourceFromMap(map[string]resources.Quantity{"second": 4})
+ preemptor := NewPreemptor(app2, headRoom,
30*time.Second, ask3, iterator(), false)
+
+ result, ok := preemptor.TryPreemption()
+ assert.Assert(t, result != nil, "unexpected result")
+ assert.Equal(t, ok, true, "victims found")
+ assert.Check(t, alloc1.IsPreempted() ||
alloc2.IsPreempted(), "alloc1 or alloc2 preempted")
+ })
+ }
+}
+
+// TestTryPreemption_AskQueue_With_OG_And_UG_ResTypes Test try preemption with
2 level queue hierarchy.
+// Guaranteed set on both victim queue path and preemptor queue path.
+// Ask queue has overused some res types only but not all defined in
guaranteed, looking for UG resources.
+// Though some res types defined in ask queue's guaranteed has been overused
and not has any relevance from preemptor ask resource requirement perspective,
preemption should
+// be triggerred and pass through preliminary checkPreemptionQueueGuarantees
checks. Just because ask has some OG res types, checkPreemptionQueueGuarantees
should not fail.
+// Setup:
+// Nodes are Node1 & Node2. Node has enough space to accommodate the new ask.
+// root.parent.child1. Guaranteed set on root.parent.child1, first: 10. 2
Allocations (belongs to single app) are running. First Allocation usage is
first:10, Second Allocation usage is first:5. Total usage is first:15.
+// root.parent.child2. Guaranteed set on root.parent.child2, first: 10,
second: 2. 1 Allocation is running with usage as first:5, second: 3 (OG).
Request of first: 5, third: 10 is waiting for resources.
+// 1 Allocation on root.parent.child1 should be preempted to free up resources
for ask arrived in root.parent.child2 even though it has overused few
guaranteed resource types.
+func TestTryPreemption_AskQueue_With_OG_And_UG_ResTypes(t *testing.T) {
+ node1 := newNode(nodeID1, map[string]resources.Quantity{"first": 10,
"second": 3, "third": 10})
+ node2 := newNode(nodeID2, map[string]resources.Quantity{"first": 10,
"second": 3, "third": 10})
+ iterator := getNodeIteratorFn(node1, node2)
+ appQueueMapping := NewAppQueueMapping()
+ rootQ, err := createRootQueue(map[string]string{"first": "20",
"second": "6"})
+ assert.NilError(t, err)
+ parentQ, err := createManagedQueueGuaranteed(rootQ, "parent", true,
map[string]string{"first": "20", "second": "6"}, nil, appQueueMapping)
+ assert.NilError(t, err)
+ childQ1, err := createManagedQueueGuaranteed(parentQ, "child1", false,
nil, map[string]string{"first": "10"}, appQueueMapping)
+ assert.NilError(t, err)
+ childQ2, err := createManagedQueueGuaranteed(parentQ, "child2", false,
nil, map[string]string{"first": "10", "second": "2"}, appQueueMapping)
+ assert.NilError(t, err)
+
+ alloc1, alloc2, err := creatApp1WithTwoDifferentAllocations(childQ1,
node1, node2, map[string]resources.Quantity{"first": 10},
map[string]resources.Quantity{"first": 5}, appQueueMapping)
+ assert.NilError(t, err)
+
+ alloc3Res :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5,
"second": 3})
+ app2, ask3, err := creatApp2(childQ2,
map[string]resources.Quantity{"first": 5, "second": 3}, "alloc3",
appQueueMapping)
+ assert.NilError(t, err)
+
+ alloc3 := newAllocationWithKey("alloc3", appID2, nodeID2, alloc3Res)
+ alloc3.createTime = ask3.createTime
+ app2.AddAllocation(alloc3)
+ if !node2.TryAddAllocation(alloc3) {
+ t.Fatal("node alloc3 failed")
+ }
+ if err = childQ2.TryIncAllocatedResource(ask3.GetAllocatedResource());
err != nil {
+ t.Fatal("inc queue resource failed")
+ }
+ app3 := newApplication(appID3, "default", "root.parent.child2")
+ app3.SetQueue(childQ2)
+ childQ2.applications[appID3] = app3
+
+ ask4 := newAllocationAsk("alloc4", appID3,
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5, "third":
10}))
+ err = app3.AddAllocationAsk(ask4)
+ assert.NilError(t, err)
+
+ headRoom :=
resources.NewResourceFromMap(map[string]resources.Quantity{"second": 6})
+ preemptor := NewPreemptor(app3, headRoom, 30*time.Second, ask4,
iterator(), false)
+
+ result, ok := preemptor.TryPreemption()
+ assert.Assert(t, result != nil, "unexpected result")
+ assert.Equal(t, ok, true, "victims found")
+ assert.Check(t, alloc1.IsPreempted() || alloc2.IsPreempted(), "alloc1
or alloc2 preempted")
+}
+
+// TestTryPreemption_AskQueue_Under_DiffParent_With_OG_And_UG_ResTypes Test
try preemption with 3 level queue hierarchy.
+// Guaranteed set on both victim queue path and preemptor queue path.
+// Ask queue has overused some res types only but not all defined in
guaranteed, looking for UG resources.
+// Though some res types defined in ask queue's guaranteed has been overused
and not has any relevance from preemptor ask resource requirement perspective,
preemption should
+// be triggerred and pass through preliminary checkPreemptionQueueGuarantees
checks. Just because ask has some OG res types, checkPreemptionQueueGuarantees
should not fail.
+// Setup:
+// Nodes are Node1 & Node2. Node has enough space to accommodate the new ask.
+// root.parent.parent1.child1. Guaranteed set on root.parent.parent1.child1,
first: 10. 2 Allocations (belongs to single app) are running. First Allocation
usage is first:10, Second Allocation usage is first:5. Total usage is first:15.
+// root.parent.parent2.child2. Guaranteed set on root.parent.parent2.child2,
first: 10, second: 2. 1 Allocation is running with usage as first:5, second: 3
(OG). Request of first: 5, third: 10 is waiting for resources.
+// 1 Allocation on root.parent.parent1.child1 should be preempted to free up
resources for ask arrived in root.parent.parent2.child2 even though it has
overused few guaranteed resource types.
+func TestTryPreemption_AskQueue_Under_DiffParent_With_OG_And_UG_ResTypes(t
*testing.T) {
+ var tests = []struct {
+ testName string
+ victimParentGuaranteed map[string]string
+ askParentGuaranteed map[string]string
+ victimChildGuaranteed map[string]string
+ askChildGuaranteed map[string]string
+ }{
+ {"ask queue under parent different from victim queue with some
OG res types", map[string]string{"first": "10"}, map[string]string{"first":
"10", "second": "2"}, nil, nil},
+ {"ask queue with some OG res types under parent different from
victim queue", nil, nil, map[string]string{"first": "10"},
map[string]string{"first": "10", "second": "2"}},
+ }
+ for _, tt := range tests {
+ t.Run(tt.testName, func(t *testing.T) {
+ node1 := newNode(nodeID1,
map[string]resources.Quantity{"first": 10, "second": 3, "third": 10})
+ node2 := newNode(nodeID2,
map[string]resources.Quantity{"first": 10, "second": 3, "third": 10})
+ iterator := getNodeIteratorFn(node1, node2)
+ appQueueMapping := NewAppQueueMapping()
+ rootQ, err :=
createRootQueue(map[string]string{"first": "20", "second": "6"})
+ assert.NilError(t, err)
+ parentQ, err := createManagedQueueGuaranteed(rootQ,
"parent", true, map[string]string{"first": "20", "second": "6"}, nil,
appQueueMapping)
+ assert.NilError(t, err)
+ parentQ1, err := createManagedQueueGuaranteed(parentQ,
"parent1", true, nil, tt.victimParentGuaranteed, appQueueMapping)
+ assert.NilError(t, err)
+ parentQ2, err := createManagedQueueGuaranteed(parentQ,
"parent2", true, nil, tt.askParentGuaranteed, appQueueMapping)
+ assert.NilError(t, err)
+ childQ1, err := createManagedQueueGuaranteed(parentQ1,
"child1", false, nil, tt.victimChildGuaranteed, appQueueMapping)
+ assert.NilError(t, err)
+ childQ2, err := createManagedQueueGuaranteed(parentQ2,
"child2", false, nil, tt.askChildGuaranteed, appQueueMapping)
+ assert.NilError(t, err)
+
+ alloc1, alloc2, err :=
creatApp1WithTwoDifferentAllocations(childQ1, node1, node2,
map[string]resources.Quantity{"first": 10},
map[string]resources.Quantity{"first": 5}, appQueueMapping)
+ assert.NilError(t, err)
+
+ alloc3Res :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5,
"second": 3})
+ app2, ask3, err := creatApp2(childQ2,
map[string]resources.Quantity{"first": 5, "second": 3}, "alloc3",
appQueueMapping)
+ assert.NilError(t, err)
+
+ alloc3 := newAllocationWithKey("alloc3", appID2,
nodeID2, alloc3Res)
+ alloc3.createTime = ask3.createTime
+ app2.AddAllocation(alloc3)
+ if !node2.TryAddAllocation(alloc3) {
+ t.Fatal("node alloc3 failed")
+ }
+ if err =
childQ2.TryIncAllocatedResource(ask3.GetAllocatedResource()); err != nil {
+ t.Fatal("inc queue resource failed")
+ }
+ app3 := newApplication(appID3, "default",
"root.parent.child2")
+ app3.SetQueue(childQ2)
+ childQ2.applications[appID3] = app3
+
+ ask4 := newAllocationAsk("alloc4", appID3,
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5, "third":
10}))
+ err = app3.AddAllocationAsk(ask4)
+ assert.NilError(t, err)
+
+ headRoom :=
resources.NewResourceFromMap(map[string]resources.Quantity{"second": 6})
+ preemptor := NewPreemptor(app3, headRoom,
30*time.Second, ask4, iterator(), false)
+
+ result, ok := preemptor.TryPreemption()
+ assert.Assert(t, result != nil, "unexpected result")
+ assert.Equal(t, ok, true, "victims found")
+ assert.Check(t, alloc1.IsPreempted() ||
alloc2.IsPreempted(), "alloc1 or alloc2 preempted")
+ })
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
