This is an automated email from the ASF dual-hosted git repository.
ccondit pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/yunikorn-core.git
The following commit(s) were added to refs/heads/master by this push:
new fd411a5f [YUNIKORN-2769] Properly handle preemption betweeen sibling
queues (#923)
fd411a5f is described below
commit fd411a5fa61f1e645e2a16f2c0a6fc75bf6c19b6
Author: Manikandan R <[email protected]>
AuthorDate: Mon Aug 12 15:00:39 2024 -0500
[YUNIKORN-2769] Properly handle preemption betweeen sibling queues (#923)
Handle the case where preemptor is under guaranteed limit and parent is
above guaranteed limits.
Closes: #923
Signed-off-by: Craig Condit <[email protected]>
---
pkg/common/resources/resources.go | 62 +++++-
pkg/common/resources/resources_test.go | 65 +++++++
pkg/scheduler/objects/preemption.go | 8 +
pkg/scheduler/objects/preemption_queue_test.go | 249 ++++++++++++++++---------
pkg/scheduler/objects/preemption_test.go | 65 +++++++
pkg/scheduler/objects/queue.go | 23 ++-
6 files changed, 367 insertions(+), 105 deletions(-)
diff --git a/pkg/common/resources/resources.go
b/pkg/common/resources/resources.go
index 23cad7b5..1b2a036b 100644
--- a/pkg/common/resources/resources.go
+++ b/pkg/common/resources/resources.go
@@ -629,12 +629,11 @@ func compareShares(lshares, rshares []float64) int {
return 0
}
-// Compare the resources equal returns the specific values for following cases:
-// left right return
-// nil nil true
-// nil <set> false
-// <set> nil false
-// <set> <set> true/false *based on the individual Quantity values
+// Equals Compare the resources based on common resource type available in
both left and right Resource
+// Resource type available in left Resource but not in right Resource and vice
versa is not taken into account
+// False in case anyone of the resources is nil
+// False in case resource type value differs
+// True in case when resource type values of left Resource matches with right
Resource if resource type is available
func Equals(left, right *Resource) bool {
if left == right {
return true
@@ -649,13 +648,39 @@ func Equals(left, right *Resource) bool {
return false
}
}
-
for k, v := range right.Resources {
if left.Resources[k] != v {
return false
}
}
+ return true
+}
+// DeepEquals Compare the resources based on resource type existence and its
values as well
+// False in case anyone of the resources is nil
+// False in case resource length differs
+// False in case resource type existed in left Resource not exist in right
Resource
+// False in case resource type value differs
+// True in case when all resource type and its values of left Resource matches
with right Resource
+func DeepEquals(left, right *Resource) bool {
+ if left == right {
+ return true
+ }
+ if left == nil || right == nil {
+ return false
+ }
+ if len(right.Resources) != len(left.Resources) {
+ return false
+ }
+ for k, v := range left.Resources {
+ if val, ok := right.Resources[k]; ok {
+ if val != v {
+ return false
+ }
+ } else {
+ return false
+ }
+ }
return true
}
@@ -882,6 +907,29 @@ func ComponentWiseMin(left, right *Resource) *Resource {
return out
}
+// MergeIfNotPresent Returns a new Resource by merging resource type values
present in right with left
+// only if resource type not present in left.
+// If either Resource passed in is nil the other Resource is returned
+// If a Resource type is missing from one of the Resource, it is considered
empty and the quantity from the other Resource is returned
+func MergeIfNotPresent(left, right *Resource) *Resource {
+ if right == nil && left == nil {
+ return nil
+ }
+ if left == nil {
+ return right.Clone()
+ }
+ if right == nil {
+ return left.Clone()
+ }
+ out := left.Clone()
+ for k, v := range right.Resources {
+ if _, ok := left.Resources[k]; !ok {
+ out.Resources[k] = v
+ }
+ }
+ return out
+}
+
// ComponentWiseMinOnlyExisting Returns a new Resource with the smallest value
for resource type
// existing only in left but not vice versa.
func ComponentWiseMinOnlyExisting(left, right *Resource) *Resource {
diff --git a/pkg/common/resources/resources_test.go
b/pkg/common/resources/resources_test.go
index 05e603a7..49df426a 100644
--- a/pkg/common/resources/resources_test.go
+++ b/pkg/common/resources/resources_test.go
@@ -532,6 +532,46 @@ func TestComponentWiseMinOnlyExisting(t *testing.T) {
}
}
+func TestMergeIfNotPresent(t *testing.T) {
+ testCases := []struct {
+ name string
+ left map[string]Quantity
+ right map[string]Quantity
+ expected map[string]Quantity
+ }{
+ {"Min of nil resources should be nil", nil, nil, nil},
+ {"Min of empty resources should be empty resource ",
map[string]Quantity{}, map[string]Quantity{}, map[string]Quantity{}},
+ {"Min of positive resource and nil resource",
map[string]Quantity{"first": 5}, nil, map[string]Quantity{"first": 5}},
+ {"Min of nil resource and positive resource", nil,
map[string]Quantity{"first": 5}, map[string]Quantity{"first": 5}},
+ {"Min of two positive resources", map[string]Quantity{"first":
5}, map[string]Quantity{"first": 10}, map[string]Quantity{"first": 5}},
+ {"Min of two positive resources", map[string]Quantity{"first":
10}, map[string]Quantity{"first": 5}, map[string]Quantity{"first": 10}},
+ {"Min of positive resource and negative resource",
map[string]Quantity{"first": 5}, map[string]Quantity{"first": -5},
map[string]Quantity{"first": 5}},
+ {"Min of positive resource and negative resource",
map[string]Quantity{"first": -5}, map[string]Quantity{"first": 5},
map[string]Quantity{"first": -5}},
+ {"Min of two positive resources with extra resource types",
map[string]Quantity{"first": 10}, map[string]Quantity{"first": 5, "second":
15}, map[string]Quantity{"first": 10, "second": 15}},
+ {"Min of two positive resources with extra resource types",
map[string]Quantity{"first": 5, "second": 15}, map[string]Quantity{"first":
10}, map[string]Quantity{"first": 5, "second": 15}},
+ {"Min of positive resource and negative resource with extra
resource types", map[string]Quantity{"first": 10}, map[string]Quantity{"first":
-5, "second": 15}, map[string]Quantity{"first": 10, "second": 15}},
+ {"Min of positive resource and negative resource with extra
resource types", map[string]Quantity{"first": -5, "second": 15},
map[string]Quantity{"first": 10}, map[string]Quantity{"first": -5, "second":
15}},
+ }
+ for _, tc := range testCases {
+ var left *Resource
+ var right *Resource
+ var expected *Resource
+ if tc.left != nil {
+ left = NewResourceFromMap(tc.left)
+ }
+ if tc.right != nil {
+ right = NewResourceFromMap(tc.right)
+ }
+ if tc.expected != nil {
+ expected = NewResourceFromMap(tc.expected)
+ }
+ t.Run(tc.name, func(t *testing.T) {
+ result := MergeIfNotPresent(left, right)
+ assert.DeepEqual(t, result, expected)
+ })
+ }
+}
+
func TestComponentWiseMax(t *testing.T) {
type inputs struct {
res1 map[string]Quantity
@@ -1157,6 +1197,31 @@ func TestEqualsOrEmpty(t *testing.T) {
}
}
+func TestDeepEquals(t *testing.T) {
+ var tests = []struct {
+ left, right *Resource
+ want bool
+ }{
+ {nil, nil, true},
+ {nil, NewResourceFromMap(map[string]Quantity{"a": 0, "b": 1}),
false},
+ {NewResourceFromMap(map[string]Quantity{"a": 0, "b": 1}), nil,
false},
+ {nil, NewResource(), false},
+ {NewResource(), nil, false},
+ {NewResourceFromMap(map[string]Quantity{"a": 0}),
NewResourceFromMap(map[string]Quantity{"a": 0}), true},
+ {NewResourceFromMap(map[string]Quantity{"a": 0, "b": 1}),
NewResourceFromMap(map[string]Quantity{"a": 0, "b": 1}), true},
+ {NewResourceFromMap(map[string]Quantity{"a": 0}),
NewResourceFromMap(map[string]Quantity{"b": 0, "c": 1}), false},
+ {NewResourceFromMap(map[string]Quantity{"a": 0, "b": 1}),
NewResourceFromMap(map[string]Quantity{"a": 1, "b": 1}), false},
+ {NewResourceFromMap(map[string]Quantity{"a": 0, "c": 1}),
NewResourceFromMap(map[string]Quantity{"a": 0, "d": 3}), false},
+ {NewResourceFromMap(map[string]Quantity{"a": 0}),
NewResourceFromMap(map[string]Quantity{"d": 0}), false},
+ }
+
+ for _, tt := range tests {
+ if got := DeepEquals(tt.left, tt.right); got != tt.want {
+ t.Errorf("got %v, want %v", got, tt.want)
+ }
+ }
+}
+
func TestFitIn(t *testing.T) {
tests := []struct {
name string
diff --git a/pkg/scheduler/objects/preemption.go
b/pkg/scheduler/objects/preemption.go
index 3303a064..6b00edab 100644
--- a/pkg/scheduler/objects/preemption.go
+++ b/pkg/scheduler/objects/preemption.go
@@ -69,6 +69,7 @@ type QueuePreemptionSnapshot struct {
MaxResource *resources.Resource // maximum resources for
this queue
GuaranteedResource *resources.Resource // guaranteed resources for
this queue
PotentialVictims []*Allocation // list of allocations
which could be preempted
+ AskQueue *QueuePreemptionSnapshot // snapshot of ask or
preemptor queue
}
// NewPreemptor creates a new preemptor. The preemptor itself is not thread
safe, and assumes the application lock is held.
@@ -760,6 +761,7 @@ func (qps *QueuePreemptionSnapshot) Duplicate(copy
map[string]*QueuePreemptionSn
MaxResource: qps.MaxResource.Clone(),
GuaranteedResource: qps.GuaranteedResource.Clone(),
PotentialVictims: qps.PotentialVictims,
+ AskQueue: qps.AskQueue,
}
copy[qps.QueuePath] = snapshot
return snapshot
@@ -825,6 +827,12 @@ func (qps *QueuePreemptionSnapshot)
GetRemainingGuaranteedResource() *resources.
used := qps.AllocatedResource.Clone()
used.SubOnlyExisting(qps.PreemptingResource)
remainingGuaranteed.SubOnlyExisting(used)
+ if qps.AskQueue != nil {
+ // In case ask queue has guaranteed set, its own values carries
higher precedence over the parent or ancestor
+ if qps.AskQueue.QueuePath == qps.QueuePath &&
!remainingGuaranteed.IsEmpty() {
+ return resources.MergeIfNotPresent(remainingGuaranteed,
parent)
+ }
+ }
return resources.ComponentWiseMin(remainingGuaranteed, parent)
}
diff --git a/pkg/scheduler/objects/preemption_queue_test.go
b/pkg/scheduler/objects/preemption_queue_test.go
index 0baaffaf..90af333f 100644
--- a/pkg/scheduler/objects/preemption_queue_test.go
+++ b/pkg/scheduler/objects/preemption_queue_test.go
@@ -123,113 +123,186 @@ func TestGetPreemptableResource(t *testing.T) {
func TestGetRemainingGuaranteedResource(t *testing.T) {
// no guaranteed and no usage. so no remaining
+ rootQ, parentQ, childQ1, childQ2, childQ3 := setup(t)
+ smallestRes :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5})
+ childRes :=
resources.NewResourceFromMap(map[string]resources.Quantity{"second": 5})
+ expectedSmallestRes :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 3})
+ expectedSmallestRes1 := smallestRes.Clone()
+ expectedSmallestRes1.MultiplyTo(float64(0))
+ var tests = []struct {
+ testName string
+ askQueue *Queue
+ childQ2Remaining *resources.Resource
+ childQ2Remaining1 *resources.Resource
+ }{
+
{"UnderGuaranteedChildQueue_Under_OverGuaranteedParentQueue_Does_Not_Have_Higher_Precedence_When_AskQueue_Is_Different_From_UnderGuaranteedChildQueue",
childQ3,
+ resources.Multiply(smallestRes, -1),
resources.Add(expectedSmallestRes1, resources.Multiply(childRes, -1))},
+
{"UnderGuaranteedChildQueue_Under_OverGuaranteedParentQueue_Has_Higher_Precedence_When_AskQueue_Is_Same_As_UnderGuaranteedChildQueue",
childQ2,
+ resources.Multiply(smallestRes, 0),
resources.Add(expectedSmallestRes, resources.Multiply(childRes, -1))},
+ }
+ for _, tt := range tests {
+ var rootRemaining, pRemaining, cRemaining1, cRemaining2
*resources.Resource
+ resetQueueResources(rootQ, parentQ, childQ1, childQ2)
+ rootRemaining, pRemaining, cRemaining1, cRemaining2 =
setAndGetRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2,
map[string]*resources.Resource{rootQ.QueuePath: nil, parentQ.QueuePath: nil,
childQ1.QueuePath: nil, childQ2.QueuePath: nil}, tt.askQueue)
+ assertZeroRemaining(t, rootRemaining, pRemaining, cRemaining1,
cRemaining2)
+
+ // no guaranteed and no usage, but max res set. so min of
guaranteed and max should be remaining
+ smallestRes :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5})
+ rootQ.maxResource = resources.Multiply(smallestRes, 4)
+ parentQ.maxResource = resources.Multiply(smallestRes, 2)
+ childQ1.maxResource = smallestRes
+ childQ2.maxResource = smallestRes
+ rootRemaining, pRemaining, cRemaining1, cRemaining2 =
setAndGetRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2,
map[string]*resources.Resource{rootQ.QueuePath: nil, parentQ.QueuePath: nil,
childQ1.QueuePath: nil, childQ2.QueuePath: nil}, tt.askQueue)
+ assertZeroRemaining(t, rootRemaining, pRemaining, cRemaining1,
cRemaining2)
+
+ // guaranteed set only for queue at specific levels but no
usage.
+ // so remaining for queues without guaranteed quota inherits
from parent queue based on min perm calculation
+ rootRemaining, pRemaining, cRemaining1, cRemaining2 =
setAndGetRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2,
map[string]*resources.Resource{rootQ.QueuePath: resources.Multiply(smallestRes,
2), parentQ.QueuePath: nil, childQ1.QueuePath: childRes, childQ2.QueuePath:
nil}, tt.askQueue)
+ assert.Assert(t, resources.Equals(rootRemaining,
resources.Multiply(smallestRes, 2)), "guaranteed set, but no usage. so all
guaranteed should be in remaining")
+ assert.Assert(t, resources.Equals(pRemaining,
resources.Multiply(smallestRes, 2)), "guaranteed not set, also no usage.
However, parent's remaining should be used")
+ assert.Assert(t, resources.Equals(cRemaining1,
resources.Add(resources.Multiply(smallestRes, 2), childRes)), "guaranteed not
set, also no usage. However, parent's remaining should be used")
+ assert.Assert(t, resources.Equals(cRemaining2,
resources.Multiply(smallestRes, 2)), "guaranteed not set, also no usage.
However, parent's remaining should be used")
+
+ // guaranteed set but no usage. so nothing to preempt
+ // clean start for the snapshot: whole hierarchy with guarantee
+ queueRes := map[string]*resources.Resource{rootQ.QueuePath:
resources.Multiply(smallestRes, 2), parentQ.QueuePath: smallestRes,
childQ1.QueuePath: childRes, childQ2.QueuePath: smallestRes}
+ rootRemaining, pRemaining, cRemaining1, cRemaining2 =
setAndGetRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2, queueRes,
tt.askQueue)
+ assert.Assert(t, resources.Equals(rootRemaining,
resources.Multiply(smallestRes, 2)), "guaranteed set, but no usage. so all
guaranteed should be in remaining")
+ assert.Assert(t, resources.Equals(pRemaining, smallestRes),
"guaranteed set, but no usage. so all guaranteed should be in remaining")
+ assert.Assert(t, resources.Equals(cRemaining1,
resources.Add(smallestRes, childRes)), "guaranteed set, but no usage. so all
guaranteed + parent remaining guaranteed should be in remaining")
+ assert.Assert(t, resources.Equals(cRemaining2, smallestRes),
"guaranteed set, but no usage. so all its guaranteed (because it is lesser than
parent's guaranteed) should be in remaining")
+
+ // clean start for the snapshot: all set guaranteed
+ // add usage to parent + root: use all guaranteed at parent
level
+ // add usage to child2: use all guaranteed set
+ // child2 remaining behaviour changes based on the ask queue.
+ // When ask queue is child2, its own values has higher
precedence over the parent or ancestor for common resource types.
+ // for extra resources available in parent or ancestor, it can
simply inherit.
+ // When ask queue is child3 (diverged from very earlier branch,
not sharing any common queue path), its remaining is min permissive of its own
values and parent or ancestor values.
+ rootQ.allocatedResource = resources.Multiply(smallestRes, 2)
+ parentQ.allocatedResource = resources.Multiply(smallestRes, 2)
+ childQ2.allocatedResource = resources.Multiply(smallestRes, 1)
+ rootRemaining, pRemaining, cRemaining1, cRemaining2 =
setAndGetRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2, queueRes,
tt.askQueue)
+ assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed
set, used completely. so all guaranteed should be in remaining")
+ assert.Assert(t, resources.Equals(pRemaining,
resources.Multiply(smallestRes, -1)), "guaranteed set, used double than
guaranteed. so remaining should be in -ve")
+ assert.Assert(t, resources.Equals(cRemaining1,
resources.Add(resources.Multiply(smallestRes, -1), childRes)), "guaranteed set,
but no usage. However remaining should include its all guaranteed + parent
remaining guaranteed")
+ assert.Assert(t, resources.Equals(cRemaining2,
tt.childQ2Remaining), "guaranteed set, used all guaranteed. remaining should be
based on ask queue")
+
+ // clean start for the snapshot: all set guaranteed
+ // add usage for all: use exactly guaranteed at parent and
child level
+ // parent guarantee used for one type child guarantee used for
second type
+ bothRes := resources.Multiply(smallestRes, 2)
+ bothRes.AddTo(childRes)
+ rootQ.allocatedResource = bothRes
+ bothRes = resources.Add(smallestRes, childRes)
+ parentQ.allocatedResource = bothRes
+ childQ1.allocatedResource = childRes
+ childQ2.allocatedResource = smallestRes
+ rootRemaining, pRemaining, cRemaining1, cRemaining2 =
setAndGetRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2, queueRes,
tt.askQueue)
+ assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed
set, used completely. usage also has extra resource types. However, no
remaining")
+ assert.Assert(t, resources.IsZero(pRemaining), "guaranteed set,
used completely. usage also has extra resource types. However, no remaining")
+ assert.Assert(t, resources.IsZero(cRemaining1), "guaranteed
set, used completely. so, no remaining")
+ assert.Assert(t, resources.IsZero(cRemaining2), "guaranteed
set, but no usage. Still, no remaining in guaranteed because of its parent
queue")
+
+ // clean start for the snapshot: all set guaranteed
+ // add usage for root + parent: use exactly guaranteed at
parent and child level
+ // add usage to child1: use double than guaranteed
+ // parent guarantee used for one type child guarantee used for
second type
+ bothRes = resources.Multiply(smallestRes, 2)
+ bothRes.AddTo(resources.Multiply(childRes, 2))
+ rootQ.allocatedResource = bothRes
+ bothRes = resources.Add(smallestRes,
resources.Multiply(childRes, 2))
+ parentQ.allocatedResource = bothRes
+ childQ1.allocatedResource = resources.Multiply(childRes, 2)
+ childQ2.allocatedResource = smallestRes
+ rootRemaining, pRemaining, cRemaining1, cRemaining2 =
setAndGetRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2, queueRes,
tt.askQueue)
+ assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed
set, used completely. usage also has extra resource types. However, no
remaining")
+ assert.Assert(t, resources.IsZero(pRemaining), "guaranteed set,
used completely. usage also has extra resource types. However, no remaining")
+ assert.Assert(t, resources.Equals(cRemaining1,
resources.Multiply(childRes, -1)), "guaranteed set, used double than
guaranteed. so remaining should be in -ve")
+ assert.Assert(t, resources.IsZero(cRemaining2), "guaranteed
set, but no usage. Still, no remaining in guaranteed because of its parent
queue")
+
+ // clean start for the snapshot: all set guaranteed
+ // add usage for root + parent: use exactly guaranteed for one
resource and over guaranteed for another resource at parent level
+ // add usage to child1: use double than guaranteed
+ // add usage to child2: use lesser than guaranteed.
+ // child2 remaining behaviour changes based on the ask queue.
+ // When ask queue is child2, its own values has higher
precedence over the parent or ancestor for common resource types.
+ // for extra resources available in parent or ancestor, it can
simply inherit.
+ // When ask queue is child3 (diverged from very earlier branch,
not sharing any common queue path), its remaining is min permissive of its own
values and parent or ancestor values.
+ childQ2.allocatedResource =
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 2})
+ rootRemaining, pRemaining, cRemaining1, cRemaining2 =
setAndGetRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2,
map[string]*resources.Resource{rootQ.QueuePath: resources.Multiply(smallestRes,
2), parentQ.QueuePath: resources.Add(smallestRes, resources.Multiply(childRes,
1)), childQ1.QueuePath: childRes, childQ2.QueuePath: smallestRes}, tt.askQueue)
+ assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed
set, used completely. usage also has extra resource types. However, no
remaining")
+ assert.Assert(t, resources.DeepEquals(pRemaining,
resources.Add(expectedSmallestRes1, resources.Multiply(childRes, -1))),
"guaranteed set, one resource type used completely. usage also has another
resource types which is used bit more. remaining should have zero for one
resource type and -ve for another")
+ assert.Assert(t, resources.DeepEquals(cRemaining1,
resources.Add(expectedSmallestRes1, resources.Multiply(childRes, -1))),
"guaranteed set, used double than guaranteed. so remaining should be in -ve")
+ assert.Assert(t, resources.DeepEquals(cRemaining2,
tt.childQ2Remaining1), "guaranteed set, used bit lesser. parent's usage also
has extra resource types. remaining should be based on ask queue")
+ }
+}
+
+func setup(t *testing.T) (rootQ, parentQ, childQ1, childQ2, childQ3 *Queue) {
rootQ, err := createRootQueue(map[string]string{})
assert.NilError(t, err)
- var parentQ, childQ1, childQ2 *Queue
+ var parent1Q *Queue
parentQ, err = createManagedQueue(rootQ, "parent", true,
map[string]string{})
assert.NilError(t, err)
+ parent1Q, err = createManagedQueue(rootQ, "parent1", true,
map[string]string{})
+ assert.NilError(t, err)
childQ1, err = createManagedQueue(parentQ, "child1", false,
map[string]string{})
assert.NilError(t, err)
childQ2, err = createManagedQueue(parentQ, "child2", false,
map[string]string{})
assert.NilError(t, err)
- rootRemaining, pRemaining, cRemaining1, cRemaining2 :=
getRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2)
- assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed and max
res not set, so no remaining")
- assert.Assert(t, resources.IsZero(pRemaining), "guaranteed and max res
not set, so no remaining")
- assert.Assert(t, resources.IsZero(cRemaining1), "guaranteed and max res
not set, so no remaining")
- assert.Assert(t, resources.IsZero(cRemaining2), "guaranteed and max res
not set, so no remaining")
+ childQ3, err = createManagedQueue(parent1Q, "child3", false,
map[string]string{})
+ assert.NilError(t, err)
+ return
+}
- // no guaranteed and no usage, but max res set. so min of guaranteed
and max should be remaining
- smallestRes :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5})
- rootQ.maxResource = resources.Multiply(smallestRes, 4)
- parentQ.maxResource = resources.Multiply(smallestRes, 2)
- childQ1.maxResource = smallestRes
- childQ2.maxResource = smallestRes
- rootRemaining, pRemaining, cRemaining1, cRemaining2 =
getRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2)
+func assertZeroRemaining(t *testing.T, rootRemaining *resources.Resource,
pRemaining *resources.Resource, cRemaining1 *resources.Resource, cRemaining2
*resources.Resource) {
assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed and max
res not set, so no remaining")
assert.Assert(t, resources.IsZero(pRemaining), "guaranteed and max res
not set, so no remaining")
assert.Assert(t, resources.IsZero(cRemaining1), "guaranteed and max res
not set, so no remaining")
assert.Assert(t, resources.IsZero(cRemaining2), "guaranteed and max res
not set, so no remaining")
+}
- // guaranteed set only for queue at specific levels but no usage.
- // so remaining for queues without guaranteed quota inherits from
parent queue based on min perm calculation
- childRes :=
resources.NewResourceFromMap(map[string]resources.Quantity{"second": 5})
- rootQ.guaranteedResource = resources.Multiply(smallestRes, 2)
- childQ1.guaranteedResource = childRes
- rootRemaining, pRemaining, cRemaining1, cRemaining2 =
getRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2)
- assert.Assert(t, resources.Equals(rootRemaining,
resources.Multiply(smallestRes, 2)), "guaranteed set, but no usage. so all
guaranteed should be in remaining")
- assert.Assert(t, resources.Equals(pRemaining,
resources.Multiply(smallestRes, 2)), "guaranteed not set, also no usage.
However, parent's remaining should be used")
- assert.Assert(t, resources.Equals(cRemaining1,
resources.Add(resources.Multiply(smallestRes, 2), childRes)), "guaranteed not
set, also no usage. However, parent's remaining should be used")
- assert.Assert(t, resources.Equals(cRemaining2,
resources.Multiply(smallestRes, 2)), "guaranteed not set, also no usage.
However, parent's remaining should be used")
-
- // guaranteed set but no usage. so nothing to preempt
- // clean start for the snapshot: whole hierarchy with guarantee
- rootQ.guaranteedResource = resources.Multiply(smallestRes, 2)
- parentQ.guaranteedResource = smallestRes
- childQ2.guaranteedResource = smallestRes
- childQ1.guaranteedResource = childRes
- rootRemaining, pRemaining, cRemaining1, cRemaining2 =
getRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2)
- assert.Assert(t, resources.Equals(rootRemaining,
resources.Multiply(smallestRes, 2)), "guaranteed set, but no usage. so all
guaranteed should be in remaining")
- assert.Assert(t, resources.Equals(pRemaining, smallestRes), "guaranteed
set, but no usage. so all guaranteed should be in remaining")
- assert.Assert(t, resources.Equals(cRemaining1,
resources.Add(smallestRes, childRes)), "guaranteed set, but no usage. so all
guaranteed + parent remaining guaranteed should be in remaining")
- assert.Assert(t, resources.Equals(cRemaining2, smallestRes),
"guaranteed set, but no usage. so all its guaranteed (because it is lesser than
parent's guaranteed) should be in remaining")
-
- // clean start for the snapshot: all set guaranteed
- // add usage to parent + root: use all guaranteed at parent level
- // add usage to child2: use double than guaranteed
- rootQ.allocatedResource = resources.Multiply(smallestRes, 2)
- parentQ.allocatedResource = resources.Multiply(smallestRes, 2)
- childQ2.allocatedResource = resources.Multiply(smallestRes, 2)
- rootRemaining, pRemaining, cRemaining1, cRemaining2 =
getRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2)
- assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed set, used
completely. so all guaranteed should be in remaining")
- assert.Assert(t, resources.Equals(pRemaining,
resources.Multiply(smallestRes, -1)), "guaranteed set, used double than
guaranteed. so remaining should be in -ve")
- assert.Assert(t, resources.Equals(cRemaining1,
resources.Add(resources.Multiply(smallestRes, -1), childRes)), "guaranteed set,
but no usage. However remaining should include its all guaranteed + parent
remaining guaranteed")
- assert.Assert(t, resources.Equals(cRemaining2,
resources.Multiply(smallestRes, -1)), "guaranteed set, used double than
guaranteed. so remaining should be in -ve")
-
- // clean start for the snapshot: all set guaranteed
- // add usage for all: use exactly guaranteed at parent and child level
- // parent guarantee used for one type child guarantee used for second
type
- bothRes := resources.Multiply(smallestRes, 2)
- bothRes.AddTo(childRes)
- rootQ.allocatedResource = bothRes
- bothRes = resources.Add(smallestRes, childRes)
- parentQ.allocatedResource = bothRes
- childQ1.allocatedResource = childRes
- childQ2.allocatedResource = smallestRes
- rootRemaining, pRemaining, cRemaining1, cRemaining2 =
getRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2)
- assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed set, used
completely. usage also has extra resource types. However, no remaining")
- assert.Assert(t, resources.IsZero(pRemaining), "guaranteed set, used
completely. usage also has extra resource types. However, no remaining")
- assert.Assert(t, resources.IsZero(cRemaining1), "guaranteed set, used
completely. so, no remaining")
- assert.Assert(t, resources.IsZero(cRemaining2), "guaranteed set, but no
usage. Still, no remaining in guaranteed because of its parent queue")
-
- // clean start for the snapshot: all set guaranteed
- // add usage for root + parent: use exactly guaranteed at parent and
child level
- // add usage to child1: use double than guaranteed
- // parent guarantee used for one type child guarantee used for second
type
- bothRes = resources.Multiply(smallestRes, 2)
- bothRes.AddTo(resources.Multiply(childRes, 2))
- rootQ.allocatedResource = bothRes
- bothRes = resources.Add(smallestRes, resources.Multiply(childRes, 2))
- parentQ.allocatedResource = bothRes
- childQ1.allocatedResource = resources.Multiply(childRes, 2)
- childQ2.allocatedResource = smallestRes
- rootRemaining, pRemaining, cRemaining1, cRemaining2 =
getRemainingGuaranteed(rootQ, parentQ, childQ1, childQ2)
- assert.Assert(t, resources.IsZero(rootRemaining), "guaranteed set, used
completely. usage also has extra resource types. However, no remaining")
- assert.Assert(t, resources.IsZero(pRemaining), "guaranteed set, used
completely. usage also has extra resource types. However, no remaining")
- assert.Assert(t, resources.Equals(cRemaining1,
resources.Multiply(childRes, -1)), "guaranteed set, used double than
guaranteed. so remaining should be in -ve")
- assert.Assert(t, resources.IsZero(cRemaining2), "guaranteed set, but no
usage. Still, no remaining in guaranteed because of its parent queue")
+func resetQueueResources(rootQ *Queue, parentQ *Queue, childQ1 *Queue, childQ2
*Queue) {
+ rootQ.guaranteedResource = nil
+ parentQ.guaranteedResource = nil
+ childQ1.guaranteedResource = nil
+ childQ2.guaranteedResource = nil
+ rootQ.allocatedResource = nil
+ parentQ.allocatedResource = nil
+ childQ1.allocatedResource = nil
+ childQ2.allocatedResource = nil
+ rootQ.preemptingResource = nil
+ parentQ.preemptingResource = nil
+ childQ1.preemptingResource = nil
+ childQ2.preemptingResource = nil
}
-func createQPSCache(rootQ *Queue, parentQ *Queue, childQ1 *Queue, childQ2
*Queue) (*QueuePreemptionSnapshot, *QueuePreemptionSnapshot,
*QueuePreemptionSnapshot, *QueuePreemptionSnapshot) {
+func createQPSCache(rootQ *Queue, parentQ *Queue, childQ1 *Queue, childQ2
*Queue, askQueue *Queue) (*QueuePreemptionSnapshot, *QueuePreemptionSnapshot,
*QueuePreemptionSnapshot, *QueuePreemptionSnapshot) {
cache := make(map[string]*QueuePreemptionSnapshot)
- qpsRoot := rootQ.createPreemptionSnapshot(cache)
- qpsParent := parentQ.createPreemptionSnapshot(cache)
- qpsChild1 := childQ1.createPreemptionSnapshot(cache)
- qpsChild2 := childQ2.createPreemptionSnapshot(cache)
+ askQueuePath := ""
+ if askQueue != nil {
+ askQueuePath = askQueue.QueuePath
+ askQueue.createPreemptionSnapshot(cache, askQueue.QueuePath)
+ c := askQueue
+ // set the ask queue for all queues in the ask queue hierarchy
+ for c.parent != nil {
+ cache[c.QueuePath].AskQueue = cache[askQueue.QueuePath]
+ c = c.parent
+ }
+ }
+ qpsRoot := rootQ.createPreemptionSnapshot(cache, askQueuePath)
+ qpsParent := parentQ.createPreemptionSnapshot(cache, askQueuePath)
+ qpsChild1 := childQ1.createPreemptionSnapshot(cache, askQueuePath)
+ qpsChild2 := childQ2.createPreemptionSnapshot(cache, askQueuePath)
return qpsRoot, qpsParent, qpsChild1, qpsChild2
}
-func getRemainingGuaranteed(rootQ *Queue, parentQ *Queue, childQ1 *Queue,
childQ2 *Queue) (*resources.Resource, *resources.Resource, *resources.Resource,
*resources.Resource) {
- qpsRoot, qpsParent, qpsChild1, qpsChild2 := createQPSCache(rootQ,
parentQ, childQ1, childQ2)
+func setAndGetRemainingGuaranteed(rootQ *Queue, parentQ *Queue, childQ1
*Queue, childQ2 *Queue, queueRes map[string]*resources.Resource, askQueue
*Queue) (*resources.Resource, *resources.Resource, *resources.Resource,
*resources.Resource) {
+ rootQ.guaranteedResource = queueRes[rootQ.QueuePath]
+ parentQ.guaranteedResource = queueRes[parentQ.QueuePath]
+ childQ2.guaranteedResource = queueRes[childQ2.QueuePath]
+ childQ1.guaranteedResource = queueRes[childQ1.QueuePath]
+ qpsRoot, qpsParent, qpsChild1, qpsChild2 := createQPSCache(rootQ,
parentQ, childQ1, childQ2, askQueue)
rootRemaining := qpsRoot.GetRemainingGuaranteedResource()
pRemaining := qpsParent.GetRemainingGuaranteedResource()
cRemaining1 := qpsChild1.GetRemainingGuaranteedResource()
@@ -238,7 +311,7 @@ func getRemainingGuaranteed(rootQ *Queue, parentQ *Queue,
childQ1 *Queue, childQ
}
func getPreemptableResource(rootQ *Queue, parentQ *Queue, childQ1 *Queue,
childQ2 *Queue) (*resources.Resource, *resources.Resource, *resources.Resource,
*resources.Resource) {
- qpsRoot, qpsParent, qpsChild1, qpsChild2 := createQPSCache(rootQ,
parentQ, childQ1, childQ2)
+ qpsRoot, qpsParent, qpsChild1, qpsChild2 := createQPSCache(rootQ,
parentQ, childQ1, childQ2, nil)
rootRemaining := qpsRoot.GetPreemptableResource()
pRemaining := qpsParent.GetPreemptableResource()
cRemaining1 := qpsChild1.GetPreemptableResource()
diff --git a/pkg/scheduler/objects/preemption_test.go
b/pkg/scheduler/objects/preemption_test.go
index a7903e5c..04eb6a05 100644
--- a/pkg/scheduler/objects/preemption_test.go
+++ b/pkg/scheduler/objects/preemption_test.go
@@ -292,6 +292,71 @@ func TestTryPreemptionOnNode(t *testing.T) {
assert.Check(t, alloc2.IsPreempted(), "alloc2 not preempted")
}
+// TestTryPreemptionOnNodeWithOGParentAndUGPreemptor Test try preemption on
node with simple queue hierarchy. Since Node doesn't have enough resources to
accomodate, preemption happens because of node resource constraint.
+// Guaranteed and Max resource set on both victim queue path and preemptor
queue path in 2 levels. victim and preemptor queue are siblings.
+// Parent is over guaranteed whereas preemptor is under guaranteed with
pending pods. Parent is over guaranteed because of another child.
+// Setup:
+// Nodes are Node1 and Node2. Nodes are full. No space to accommodate the ask.
+// root.parent. Guaranteed set on parent, first: 2. Usage is first: 6. So over
guaranteed.
+// root.parent.child1. No Guaranteed set. Usage is first: 6. 6 Allocations
(belongs to single app) are running. Each Allocation usage is first:1. Total
usage is first:6.
+// root.parent.child2. Guaranteed set, first: 1. Ask of first:1 is waiting for
resources.
+// 1 Allocation on root.parent.child1 should be preempted to free up resources
for ask arrived in root.parent.child2.
+func TestTryPreemptionOnNodeWithOGParentAndUGPreemptor(t *testing.T) {
+ node1 := newNode(nodeID1, map[string]resources.Quantity{"first": 3,
"pods": 1})
+ node2 := newNode(nodeID2, map[string]resources.Quantity{"first": 3,
"pods": 1})
+ iterator := getNodeIteratorFn(node1, node2)
+ rootQ, err := createRootQueue(nil)
+ assert.NilError(t, err)
+ parentQ, err := createManagedQueueGuaranteed(rootQ, "parent", true,
map[string]string{"first": "20"}, map[string]string{"first": "2"})
+ assert.NilError(t, err)
+ childQ1, err := createManagedQueueGuaranteed(parentQ, "child1", false,
nil, nil)
+ assert.NilError(t, err)
+ childQ2, err := createManagedQueueGuaranteed(parentQ, "child2", false,
map[string]string{"first": "10"}, map[string]string{"first": "1"})
+ assert.NilError(t, err)
+ app1 := newApplication(appID1, "default", "root.parent.child1")
+ app1.SetQueue(childQ1)
+ childQ1.applications[appID1] = app1
+
+ for i := 1; i <= 6; i++ {
+ ask1 := newAllocationAsk("alloc"+strconv.Itoa(i), appID1,
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}))
+ ask1.createTime = time.Now().Add(time.Duration(i*-1) *
time.Minute)
+ assert.NilError(t, app1.AddAllocationAsk(ask1))
+ if i%2 == 0 {
+ alloc1 := markAllocated(nodeID1, ask1)
+ app1.AddAllocation(alloc1)
+ assert.Check(t, node1.TryAddAllocation(alloc1), "node
alloc1 failed")
+ assert.NilError(t,
childQ1.IncAllocatedResource(ask1.GetAllocatedResource(), false))
+ } else {
+ alloc1 := markAllocated(nodeID2, ask1)
+ app1.AddAllocation(alloc1)
+ assert.Check(t, node2.TryAddAllocation(alloc1), "node
alloc1 failed")
+ assert.NilError(t,
childQ1.IncAllocatedResource(ask1.GetAllocatedResource(), false))
+ }
+ }
+ app2 := newApplication(appID2, "default", "root.parent.child2")
+ app2.SetQueue(childQ2)
+ childQ2.applications[appID2] = app2
+ ask3 := newAllocationAsk("alloc7", appID2,
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1}))
+ assert.NilError(t, app2.AddAllocationAsk(ask3))
+ headRoom :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10, "pods":
3})
+ preemptor := NewPreemptor(app2, headRoom, 30*time.Second, ask3,
iterator(), false)
+
+ // register predicate handler
+ preemptions := []mock.Preemption{
+ mock.NewPreemption(true, "alloc7", nodeID2, []string{"alloc1"},
0, 0),
+ }
+ plugin := mock.NewPreemptionPredicatePlugin(nil, nil, preemptions)
+ plugins.RegisterSchedulerPlugin(plugin)
+ defer plugins.UnregisterSchedulerPlugins()
+
+ result, ok := preemptor.TryPreemption()
+ assert.Assert(t, result != nil, "no result")
+ assert.Assert(t, ok, "no victims found")
+ assert.Equal(t, "alloc7", result.Request.allocationKey, "wrong alloc")
+ assert.Equal(t, nodeID2, result.NodeID, "wrong node")
+ assert.Check(t, node2.GetAllocation("alloc1").IsPreempted(), "alloc1
preempted")
+}
+
// TestTryPreemptionOnQueue Test try preemption on queue with simple queue
hierarchy. Since Node has enough resources to accomodate, preemption happens
because of queue resource constraint.
// Guaranteed and Max resource set on both victim queue path and preemptor
queue path in 2 levels. victim and preemptor queue are siblings.
// Request (Preemptor) resource type matches with all resource types of the
victim. But Guaranteed set only on specific resource type. 2 Victims are
available, but 1 should be preempted because further preemption would make
usage go below the guaranteed quota
diff --git a/pkg/scheduler/objects/queue.go b/pkg/scheduler/objects/queue.go
index a905fdd1..35993238 100644
--- a/pkg/scheduler/objects/queue.go
+++ b/pkg/scheduler/objects/queue.go
@@ -1712,6 +1712,15 @@ func (sq *Queue) FindEligiblePreemptionVictims(queuePath
string, ask *Allocation
return nil
}
+ // create snapshot for ask or preemptor queue
+ sq.createPreemptionSnapshot(results, queuePath)
+ c := sq
+ // set the ask queue for all queues in the ask queue hierarchy
+ for c.parent != nil {
+ results[c.QueuePath].AskQueue = results[queuePath]
+ c = c.parent
+ }
+
// walk the subtree contained within the preemption fence and collect
potential victims organized by nodeID
fence.findEligiblePreemptionVictims(results, queuePath, ask,
priorityMap, queuePriority, false)
@@ -1719,7 +1728,7 @@ func (sq *Queue) FindEligiblePreemptionVictims(queuePath
string, ask *Allocation
}
// createPreemptionSnapshot is used to create a snapshot of the current
queue's resource usage and potential preemption victims
-func (sq *Queue) createPreemptionSnapshot(cache
map[string]*QueuePreemptionSnapshot) *QueuePreemptionSnapshot {
+func (sq *Queue) createPreemptionSnapshot(cache
map[string]*QueuePreemptionSnapshot, askQueuePath string)
*QueuePreemptionSnapshot {
if sq == nil {
return nil
}
@@ -1729,7 +1738,7 @@ func (sq *Queue) createPreemptionSnapshot(cache
map[string]*QueuePreemptionSnaps
return snapshot
}
- parentSnapshot := sq.parent.createPreemptionSnapshot(cache)
+ parentSnapshot := sq.parent.createPreemptionSnapshot(cache,
askQueuePath)
sq.RLock()
defer sq.RUnlock()
snapshot = &QueuePreemptionSnapshot{
@@ -1741,6 +1750,7 @@ func (sq *Queue) createPreemptionSnapshot(cache
map[string]*QueuePreemptionSnaps
MaxResource: sq.maxResource.Clone(),
GuaranteedResource: sq.guaranteedResource.Clone(),
PotentialVictims: make([]*Allocation, 0),
+ AskQueue: cache[askQueuePath],
}
cache[sq.QueuePath] = snapshot
return snapshot
@@ -1750,20 +1760,13 @@ func (sq *Queue) findEligiblePreemptionVictims(results
map[string]*QueuePreempti
if sq == nil {
return
}
-
- // if this is the target queue, return it but with an empty victim list
so we can use it in calculations
- if sq.QueuePath == queuePath {
- sq.createPreemptionSnapshot(results)
- return
- }
-
if sq.IsLeafQueue() {
// leaf queue, skip queue if preemption is disabled
if sq.GetPreemptionPolicy() ==
policies.DisabledPreemptionPolicy {
return
}
- victims := sq.createPreemptionSnapshot(results)
+ victims := sq.createPreemptionSnapshot(results, queuePath)
// skip this queue if we are within guaranteed limits
remaining :=
results[sq.QueuePath].GetRemainingGuaranteedResource()
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
