This is an automated email from the ASF dual-hosted git repository.
mani 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 fac9b6ba [YUNIKORN-3233] Improve victim selection algorithm (#1072)
fac9b6ba is described below
commit fac9b6bae0ab703ca21e7fb6bc4d2a74dcc7e211
Author: mani <[email protected]>
AuthorDate: Tue Mar 24 14:53:43 2026 +0530
[YUNIKORN-3233] Improve victim selection algorithm (#1072)
Closes: #1072
Signed-off-by: mani <[email protected]>
---
pkg/common/resources/resources.go | 45 ++++++++++++
pkg/common/resources/resources_test.go | 69 ++++++++++++++++++
pkg/scheduler/objects/preemption_utilities.go | 58 ++++++++++++++++
pkg/scheduler/objects/preemption_utilities_test.go | 81 ++++++++++++++++++++++
pkg/scheduler/objects/quota_preemptor.go | 2 +-
5 files changed, 254 insertions(+), 1 deletion(-)
diff --git a/pkg/common/resources/resources.go
b/pkg/common/resources/resources.go
index 290ba022..33ba8d57 100644
--- a/pkg/common/resources/resources.go
+++ b/pkg/common/resources/resources.go
@@ -1209,3 +1209,48 @@ func (r *Resource) DominantResourceType(capacity
*Resource) string {
}
return dominant
}
+
+func (r *Resource) TypeMatching(other *Resource) uint64 {
+ if r == nil || other == nil {
+ return 0
+ }
+ matchingResTypes := 0
+ for k := range other.Resources {
+ if _, ok := r.Resources[k]; ok {
+ matchingResTypes++
+ }
+ }
+ return uint64(matchingResTypes * 100 / len(r.Resources))
+}
+
+// CompUsageRatioSpecificTypes Compare the left and right resources based on
the ask resources.
+// Collect resource types of both left and right resources from ask resource
perspective and ignore others.
+// Sort the shares for the collected resource types in increasing order and
decide the largest resource
+// by comparing each share starting from last index to 0th index.
+func CompUsageRatioSpecificTypes(left, right, total, specificTypes *Resource)
int {
+ lShareTypeWise := GetSharesTypeWise(left, total)
+ rShareTypeWise := GetSharesTypeWise(right, total)
+ if specificTypes != nil {
+ var lShare []float64
+ var rShare []float64
+ for k := range specificTypes.Resources {
+ lValue, lExists := lShareTypeWise[k]
+ rValue, rExists := rShareTypeWise[k]
+ if lExists {
+ lShare = append(lShare, lValue)
+ }
+ if rExists {
+ rShare = append(rShare, rValue)
+ }
+ }
+ if len(lShare) == 0 && len(rShare) == 0 {
+ return 0
+ }
+ sort.Float64s(lShare)
+ sort.Float64s(rShare)
+ return compareShares(lShare, rShare)
+ } else {
+ // fall back to usual way of comparing usage shares.
+ return CompUsageRatio(left, right, total)
+ }
+}
diff --git a/pkg/common/resources/resources_test.go
b/pkg/common/resources/resources_test.go
index 5c3b844d..24baf4fa 100644
--- a/pkg/common/resources/resources_test.go
+++ b/pkg/common/resources/resources_test.go
@@ -2470,3 +2470,72 @@ func TestResource_Prune(t *testing.T) {
})
}
}
+
+func TestTypeMatching(t *testing.T) {
+ var tests = []struct {
+ name string
+ base *Resource
+ other *Resource
+ expected uint64
+ }{
+ {"nil base resource", nil,
NewResourceFromMap(map[string]Quantity{"first": 20}), 0},
+ {"nil other resource",
NewResourceFromMap(map[string]Quantity{"first": 10}), nil, 0},
+ {"both nil resources", nil, nil, 0},
+ {"same resources",
NewResourceFromMap(map[string]Quantity{"first": 10}),
NewResourceFromMap(map[string]Quantity{"first": 20}), 100},
+ {"half of the resources matches",
NewResourceFromMap(map[string]Quantity{"first": 10, "second": 10}),
NewResourceFromMap(map[string]Quantity{"first": 10}), 50},
+ {"one third of the resources matches",
NewResourceFromMap(map[string]Quantity{"first": 10, "second": 10, "third":
10}), NewResourceFromMap(map[string]Quantity{"first": 10}), 33},
+ {"one fourth of the resources matches",
NewResourceFromMap(map[string]Quantity{"first": 10, "second": 10, "third": 10,
"fourth": 10}), NewResourceFromMap(map[string]Quantity{"first": 10}), 25},
+ {"one fourth of the resources matches, extra types in other
resource should not affect", NewResourceFromMap(map[string]Quantity{"first":
10, "second": 10, "third": 10, "fourth": 10}),
NewResourceFromMap(map[string]Quantity{"first": 10, "fifth": 10, "sixth": 10}),
25},
+ }
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ assert.Equal(t, tt.base.TypeMatching(tt.other),
tt.expected)
+ })
+ }
+}
+
+func TestCompUsageRatioSpecificTypes(t *testing.T) {
+ tests := []struct {
+ name string
+ left *Resource
+ right *Resource
+ total *Resource
+ ask *Resource
+ expected int
+ }{
+ {"nil resources", nil, nil, nil,
NewResourceFromMap(map[string]Quantity{"first": 10}), 0},
+ {"empty resource with total nil", NewResource(), NewResource(),
nil, NewResourceFromMap(map[string]Quantity{"first": 10}), 0},
+ {"empty resource", NewResource(), NewResource(), NewResource(),
NewResourceFromMap(map[string]Quantity{"first": 10}), 0},
+ {"zero valued resource but extra types differs and not present
in ask", NewResourceFromMap(map[string]Quantity{"zero": 0, "extra_a": 1}),
NewResourceFromMap(map[string]Quantity{"zero": 0, "extra_a": 2}), nil,
NewResourceFromMap(map[string]Quantity{"zero": 10, "first": 10}), 0},
+ {"negative valued resource",
NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0, "small": -2,
"extra_a": 1}), NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0,
"small": -5, "extra_a": 2}), nil,
NewResourceFromMap(map[string]Quantity{"large": 5, "small": 1}), 1},
+ {"negative valued resource on left side, ask is nil",
NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0, "small": -5}),
NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0}), nil, nil, -1},
+ {"negative valued resource on right side, ask is nil",
NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0}),
NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0, "small": -5}),
nil, nil, 1},
+ {"negative valued resource but extra types differs and not
present in ask", NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0,
"small": -5, "extra_a": 1}), NewResourceFromMap(map[string]Quantity{"large": 5,
"zero": 0, "small": -5, "extra_a": 2}), nil,
NewResourceFromMap(map[string]Quantity{"large": 5}), 0},
+ {"zero valued resource with total but extra types differs and
not present in ask", NewResourceFromMap(map[string]Quantity{"zero": 0,
"extra_a": 1}), NewResourceFromMap(map[string]Quantity{"zero": 0, "extra_a":
2}), NewResource(), NewResourceFromMap(map[string]Quantity{"zero": 0}), 0},
+ {"same resource and total but extra types differs and not
present in ask", NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0,
"small": -5, "extra_a": 1}), NewResourceFromMap(map[string]Quantity{"large": 5,
"zero": 0, "small": -5, "extra_a": 2}),
NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0, "small": -5,
"extra_a": 10}), NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0,
"small": -5}), 0},
+ {"left side has more one negative value for type present in ask
but not present in right", NewResourceFromMap(map[string]Quantity{"large": 5,
"zero": 0, "small": -5}), NewResourceFromMap(map[string]Quantity{"large": 5,
"zero": 0}), NewResourceFromMap(map[string]Quantity{"large": 10, "zero": 10}),
NewResourceFromMap(map[string]Quantity{"large": 100, "zero": 100, "small": 5}),
-1},
+ {"left side has more one negative value but not present in
ask", NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0, "small":
-5}), NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0}),
NewResourceFromMap(map[string]Quantity{"large": 10, "zero": 10}),
NewResourceFromMap(map[string]Quantity{"large": 100, "zero": 100}), 0},
+ {"right side has more one negative value for type present in
ask but not present in left", NewResourceFromMap(map[string]Quantity{"large":
5, "zero": 0}), NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0,
"small": -5}), NewResourceFromMap(map[string]Quantity{"large": 10, "zero":
10}), NewResourceFromMap(map[string]Quantity{"large": 100, "zero": 100,
"small": 5}), 1},
+ {"right side has more one negative value but not present in
ask", NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0}),
NewResourceFromMap(map[string]Quantity{"large": 5, "zero": 0, "small": -5}),
NewResourceFromMap(map[string]Quantity{"large": 10, "zero": 10}),
NewResourceFromMap(map[string]Quantity{"large": 100, "zero": 100}), 0},
+ {"left side first one bigger, last one smaller. right side vice
versa. but share wise same", NewResourceFromMap(map[string]Quantity{"first":
10, "second": 5}), NewResourceFromMap(map[string]Quantity{"first": 5, "second":
10}), NewResourceFromMap(map[string]Quantity{"first": 15, "second": 15}),
NewResourceFromMap(map[string]Quantity{"first": 1, "second": 1}), 0},
+ {"left side first one bigger, last one smaller. right side vice
versa. but share wise not same",
NewResourceFromMap(map[string]Quantity{"first": 10, "second": 5}),
NewResourceFromMap(map[string]Quantity{"first": 5, "second": 10}),
NewResourceFromMap(map[string]Quantity{"first": 15}),
NewResourceFromMap(map[string]Quantity{"first": 1, "second": 1}), -1},
+ {"left side first one bigger, last one smaller. right side vice
versa. but share wise not same. none of the ask res types match",
NewResourceFromMap(map[string]Quantity{"first": 10, "second": 5}),
NewResourceFromMap(map[string]Quantity{"first": 5, "second": 10}),
NewResourceFromMap(map[string]Quantity{"first": 15}),
NewResourceFromMap(map[string]Quantity{"third": 1, "fourth": 1}), 0},
+ {"left side first one smaller, last one bigger. right side vice
versa. but share wise not same",
NewResourceFromMap(map[string]Quantity{"first": 5, "second": 10}),
NewResourceFromMap(map[string]Quantity{"first": 10, "second": 5}),
NewResourceFromMap(map[string]Quantity{"first": 15}),
NewResourceFromMap(map[string]Quantity{"first": 1, "second": 1}), 1},
+ {"left side first one smaller, last one bigger. right side vice
versa. but share wise not same. none of the ask res types match",
NewResourceFromMap(map[string]Quantity{"first": 5, "second": 10}),
NewResourceFromMap(map[string]Quantity{"first": 10, "second": 5}),
NewResourceFromMap(map[string]Quantity{"first": 15}),
NewResourceFromMap(map[string]Quantity{"third": 1, "fourth": 1}), 0},
+ {"left side key order not same as right side which is aligned
with ask order ", NewResourceFromMap(map[string]Quantity{"second": 10, "first":
5}), NewResourceFromMap(map[string]Quantity{"first": 10, "second": 5}),
NewResourceFromMap(map[string]Quantity{}),
NewResourceFromMap(map[string]Quantity{"first": 1, "second": 1}), 0},
+ {"right side key order not same as left side which is aligned
with ask order", NewResourceFromMap(map[string]Quantity{"second": 10, "first":
5}), NewResourceFromMap(map[string]Quantity{"first": 10, "second": 5}),
NewResourceFromMap(map[string]Quantity{}),
NewResourceFromMap(map[string]Quantity{"second": 1, "first": 1}), 0},
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.name, func(t *testing.T) {
+ ratio := CompUsageRatioSpecificTypes(tc.left, tc.right,
tc.total, tc.ask)
+ if ratio != tc.expected {
+ t.Errorf("incorrect ratio, expected %v got:
%v", tc.expected, ratio)
+ }
+ if tc.ask == nil {
+ assert.Equal(t, ratio, CompUsageRatio(tc.left,
tc.right, tc.total))
+ assert.Equal(t, ratio, tc.expected)
+ }
+ })
+ }
+}
diff --git a/pkg/scheduler/objects/preemption_utilities.go
b/pkg/scheduler/objects/preemption_utilities.go
index c522ed68..660102c6 100644
--- a/pkg/scheduler/objects/preemption_utilities.go
+++ b/pkg/scheduler/objects/preemption_utilities.go
@@ -20,6 +20,7 @@ package objects
import (
"sort"
+ "time"
"github.com/apache/yunikorn-core/pkg/common/resources"
)
@@ -79,3 +80,60 @@ func SortAllocations(allocations []*Allocation) {
return true
})
}
+
+func SortAllocationsBasedOnAsk(allocations []*Allocation, total, ask
*resources.Resource) {
+ sort.SliceStable(allocations, func(i, j int) bool {
+ l := allocations[i]
+ r := allocations[j]
+
+ scoreLeft := scoreAllocationBasedOnAsk(l, ask)
+ scoreRight := scoreAllocationBasedOnAsk(r, ask)
+ if scoreLeft != scoreRight {
+ return scoreLeft > scoreRight
+ }
+
+ // sort based on the priority
+ lPriority := l.GetPriority()
+ rPriority := r.GetPriority()
+ if lPriority < rPriority {
+ return true
+ }
+ if lPriority > rPriority {
+ return false
+ }
+
+ // sort based on the age (limiting the boundary to hour max)
+ lHour := l.GetCreateTime().Truncate(time.Hour)
+ rHour := r.GetCreateTime().Truncate(time.Hour)
+ if !lHour.Equal(rHour) {
+ return lHour.After(rHour)
+ }
+
+ // sort based on the allocated resource
+ lResource := l.GetAllocatedResource()
+ rResource := r.GetAllocatedResource()
+ comp := resources.CompUsageRatioSpecificTypes(lResource,
rResource, total, ask)
+ if comp == -1 {
+ return true
+ }
+ if comp == 1 {
+ return false
+ }
+ return true
+ })
+}
+
+// scoreAllocation generates a relative score for an allocation. Lower-scored
allocations are considered more likely
+// preemption candidates. Tasks which have opted into preemption are
considered first, then tasks which are not
+// application originators.
+func scoreAllocationBasedOnAsk(allocation *Allocation, ask
*resources.Resource) uint64 {
+ var score uint64 = 0
+ if allocation.IsOriginator() {
+ score |= scoreOriginator
+ }
+ if !allocation.IsAllowPreemptSelf() {
+ score |= scoreNoPreempt
+ }
+ score += allocation.GetAllocatedResource().TypeMatching(ask)
+ return score
+}
diff --git a/pkg/scheduler/objects/preemption_utilities_test.go
b/pkg/scheduler/objects/preemption_utilities_test.go
index b63c85b3..9574af49 100644
--- a/pkg/scheduler/objects/preemption_utilities_test.go
+++ b/pkg/scheduler/objects/preemption_utilities_test.go
@@ -211,3 +211,84 @@ func TestSortAllocations(t *testing.T) {
removeAllocationAsks(node, asks)
}
+
+func TestSortAllocationsBasedOnAsk(t *testing.T) {
+ node := NewNode(&si.NodeInfo{
+ NodeID: "node",
+ Attributes: nil,
+ SchedulableResource: &si.Resource{
+ Resources: map[string]*si.Quantity{"first": {Value:
100}, "second": {Value: 100}, "third": {Value: 100}, "fourth": {Value: 100},
+ "extra_a": {Value: 100}, "extra_b": {Value:
100}, "extra_c": {Value: 100}, "extra_d": {Value: 100}, "extra_e": {Value: 100},
+ "extra_f": {Value: 100}, "extra_g": {Value:
100}, "extra_h": {Value: 100}, "extra_i": {Value: 100}, "extra_j": {Value:
100}},
+ },
+ })
+
+ type vStruct struct {
+ key string
+ allocated *resources.Resource
+ }
+
+ // Victims for res types matching comparison
+ res1 := vStruct{"ask1",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 13})}
+ res2 := vStruct{"ask2",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 12,
"second": 10})}
+ res3 := vStruct{"ask3",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 11,
"second": 10, "third": 10})}
+ res4 := vStruct{"ask4",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"second": 10, "third": 10, "fourth": 10})}
+ askWithExtraRes :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"extra_a": 10, "extra_b": 10})
+
+ // Victims for allocated resources comparison
+ res5 := vStruct{"ask4",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 13,
"extra_c": 10, "extra_d": 10})}
+ res6 := vStruct{"ask3",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 12,
"extra_e": 10, "extra_f": 10})}
+ res7 := vStruct{"ask2",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 11,
"extra_g": 10, "extra_h": 10})}
+ res8 := vStruct{"ask1",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"extra_i": 10, "extra_j": 10})}
+ res9 := vStruct{"ask4",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": -13,
"extra_c": 10, "extra_d": 10})}
+
+ res10 := vStruct{"ask2",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5,
"second": 10})}
+ res11 := vStruct{"ask1",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"second": 5})}
+ res12 := vStruct{"ask1",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 5})}
+ res13 := vStruct{"ask2",
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 10,
"second": 10})}
+ askWithExtraRes1 :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 1,
"second": 1})
+
+ total :=
resources.NewResourceFromMap(map[string]resources.Quantity{"first": 100,
"second": 100, "third": 100, "fourth": 100})
+
+ testCases := []struct {
+ name string
+ victims []vStruct
+ total *resources.Resource
+ ask *resources.Resource
+ expectedVictims []string
+ }{
+ {"100% matching victims, final order should be based on
matching % in decreasing order. ask extra res should not create any impact",
+ []vStruct{res1}, total, askWithExtraRes,
[]string{"ask1"}},
+ {"50% matching victims, final order should be based on matching
% in decreasing order. ask extra res should not create any impact",
+ []vStruct{res2, res1}, total, askWithExtraRes,
[]string{"ask1", "ask2"}},
+ {"33% matching victims, final order should be based on matching
% in decreasing order. ask extra res should not create any impact",
+ []vStruct{res3, res2, res1}, total, askWithExtraRes,
[]string{"ask1", "ask2", "ask3"}},
+ {"25% matching victims, final order should be based on matching
% in decreasing order. ask extra res should not create any impact",
+ []vStruct{res4, res3, res2, res1}, total,
askWithExtraRes, []string{"ask1", "ask2", "ask3", "ask4"}},
+ {"ordering based on matching res types, non matching res types
does not matter",
+ []vStruct{res5, res6, res7, res8}, total,
askWithExtraRes, []string{"ask1", "ask2", "ask3", "ask4"}},
+ {"negative value resource, ordering based on matching res
types, non matching res types does not matter",
+ []vStruct{res6, res7, res8, res9}, total,
askWithExtraRes, []string{"ask4", "ask1", "ask2", "ask3"}},
+ {"first victim one res type bigger and another smaller and vice
versa on second victim",
+ []vStruct{res10, res11}, total, askWithExtraRes1,
[]string{"ask1", "ask2"}},
+ {"first victim one res type bigger and another smaller and vice
versa on second victim",
+ []vStruct{res13, res12}, total, askWithExtraRes1,
[]string{"ask1", "ask2"}},
+ }
+ for _, tc := range testCases {
+ t.Run(tc.name, func(t *testing.T) {
+ var victimAllocations []*Allocation
+ for _, vRes := range tc.victims {
+ // Except victim used resources and ask
resources, have all other criteria same for all victims
+ victim := createAllocation(vRes.key, "app1",
node.NodeID, true, false, 10, false,
+ vRes.allocated)
+ assert.Assert(t, node.TryAddAllocation(victim))
+ victimAllocations = append(victimAllocations,
victim)
+ }
+ SortAllocationsBasedOnAsk(victimAllocations, tc.total,
tc.ask)
+ for index, sortedAsk := range victimAllocations {
+ assert.Equal(t, sortedAsk.GetAllocationKey(),
tc.expectedVictims[index])
+ }
+ removeAllocationAsks(node, victimAllocations)
+ })
+ }
+}
diff --git a/pkg/scheduler/objects/quota_preemptor.go
b/pkg/scheduler/objects/quota_preemptor.go
index 17a751a7..108c2ce4 100644
--- a/pkg/scheduler/objects/quota_preemptor.go
+++ b/pkg/scheduler/objects/quota_preemptor.go
@@ -231,7 +231,7 @@ func (qpc *QuotaPreemptionContext) filterAllocations() {
// sortAllocations Sort the allocations running in the queue
func (qpc *QuotaPreemptionContext) sortAllocations() {
if len(qpc.allocations) > 0 {
- SortAllocations(qpc.allocations)
+ SortAllocationsBasedOnAsk(qpc.allocations, qpc.maxResource,
qpc.preemptableResource)
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
