Even Pods Spread - 2. Calculating Predicates Metadata #77760

Huang-Wei · 2019-05-10T21:08:46Z

What type of PR is this?

/sig scheduling
/hold

/assign @bsalamat
/cc @krmayankk

What this PR does / why we need it:

This is the 2nd PR of the "Even Pods Spread" KEP implementation.

build a new topologyPairsPodSpreadMap into PredicateMetadata
update ShallowCopy()
unit tests
a new set of utils using "chained" pattern to build API objects

Which issue(s) this PR fixes:

Part of #77284.

Special notes for your reviewer:

Does this PR introduce a user-facing change?:

(will document all the changes in one place)

NONE

Huang-Wei · 2019-05-10T21:09:19Z

/kind feature
/priority important-soon

Huang-Wei · 2019-05-21T20:19:26Z

/retest

Huang-Wei · 2019-05-21T21:01:13Z

/retest

Huang-Wei · 2019-06-14T06:50:39Z

/retest

draveness · 2019-07-20T06:58:54Z

pkg/scheduler/algorithm/predicates/metadata.go

 }

-func (topologyPairsMaps *topologyPairsMaps) removePod(deletedPod *v1.Pod) {
+// add a topology pair holder if needed


nit: this comment should start with the function name.

It's usually tolerant for private functions.

draveness · 2019-07-20T07:12:16Z

pkg/scheduler/algorithm/predicates/metadata.go

 	podFullName := schedutil.GetPodFullName(pod)
-	if topologyPairsMaps.topologyPairToPods[pair] == nil {
-		topologyPairsMaps.topologyPairToPods[pair] = make(map[*v1.Pod]struct{})
+	if m.topologyPairToPods[pair] == nil {


nit: Could we replace this we addTopologyPairWithoutPods?

draveness · 2019-07-20T07:14:01Z

pkg/scheduler/algorithm/predicates/utils.go

@@ -19,7 +19,7 @@ package predicates
 import (
 	"strings"

-	v1 "k8s.io/api/core/v1"


Can we revert this change since there is nothing updates else in this file and it is not a restriction that we should import without v1 prefix

draveness · 2019-07-20T07:14:41Z

pkg/scheduler/util/utils.go

@@ -21,7 +21,7 @@ import (

 	"time"

-	v1 "k8s.io/api/core/v1"


alculquicondor · 2019-07-22T18:27:12Z

That discussion was based on the context of switching to the {tpPair:count} solution. In that case, we don't hold a {podName:tpPairSet} structure.

I don't think we suggested that. Only to get rid of {tpPair:podSet}. I think we should still be able to hold {podName:tpPairSet}, which can even point to the same map (same address) for all the pods in the same node.

Huang-Wei · 2019-07-22T18:34:26Z

I don't think we suggested that. Only to get rid of {tpPair:podSet}. I think we should still be able to hold {podName:tpPairSet}, which can even point to the same map (same address) for all the pods in the same node.

That's an option. Let's see how it can benefit upon eliminating {tpPair:podSet}.

alculquicondor · 2019-07-22T19:03:53Z

I don't think we suggested that. Only to get rid of {tpPair:podSet}. I think we should still be able to hold {podName:tpPairSet}, which can even point to the same map (same address) for all the pods in the same node.

That's an option. Let's see how it can benefit upon eliminating {tpPair:podSet}.

sgtm

- build a new `topologyPairsPodSpreadMap` into PredicateMetadata - update ShallowCopy() - unit tests

- update minMatchMap from []int32 to map[string]int32

- move "chanined" utils to pkg/scheduler/testing/utils.go so as to be re-used by all scheduler tests

- see more discussion at kubernetes#77760 (comment)

Huang-Wei · 2019-07-23T05:23:27Z

/retest

Huang-Wei · 2019-07-23T07:28:18Z

/retest

alculquicondor · 2019-07-23T12:38:20Z

/lgtm

k8s-ci-robot · 2019-07-23T12:38:27Z

@alculquicondor: changing LGTM is restricted to collaborators

In response to this:

/lgtm

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

ahg-g

/lgtm

Thanks for modifying it.

ahg-g · 2019-07-23T18:46:43Z

pkg/scheduler/algorithm/predicates/metadata.go

+					errCh.SendErrorWithCancel(err, cancel)
+					return
+				}
+				if ok {
 					// constraint.TopologyKey is already guaranteed to be present
 					pair := topologyPair{key: constraint.TopologyKey, value: node.Labels[constraint.TopologyKey]}


You may also want to add that since we restrict a toplogyKey to exist in a single hard constraint, using topolgyKey as the key in this map is good enough to identify which exact constraint this pod is counted against (because otherwise the key to the map should be some sort of an identifier that combines the topologyKey and the label selector)

Huang-Wei · 2019-07-23T19:55:28Z

/hold cancel

fejta-bot · 2019-07-23T20:02:03Z

This PR may require API review.

If so, when the changes are ready, complete the pre-review checklist and request an API review.

Status of requested reviews is tracked in the API Review project.

fejta-bot · 2019-07-24T00:05:02Z

/retest
This bot automatically retries jobs that failed/flaked on approved PRs (send feedback to fejta).

Review the full test history for this PR.

Silence the bot with an /lgtm cancel or /hold comment for consistent failures.

tedyu · 2019-07-24T01:49:52Z

pkg/scheduler/algorithm/predicates/metadata.go

+	for _, constraint := range constraints {
+		topologyPairsPodSpreadMap.topologyKeyToMinPodsMap[constraint.TopologyKey] = math.MaxInt32
+	}
+	for pair, podSet := range topologyPairsPodSpreadMap.topologyPairToPods {


Is it possible that value of some topologyPairsPodSpreadMap.topologyKeyToMinPodsMap is
math.MaxInt32 at the end of this loop ?

Nope. The logic below ensures for each tp pair, they're valued with either empty podSet, or a concrete podSet:

kubernetes/pkg/scheduler/algorithm/predicates/metadata.go

Lines 260 to 272 in 5993ec5

// If needed, append topology pair without entry of pods.

// For example, on node-x, there is no pod matching spread constraints,

// but node-x should be also considered as a match (with match number 0)

// i.e. <node: node-x>: {}

for _, constraint := range constraints {

// constraint.TopologyKey is already guaranteed to be present

pair := topologyPair{

key: constraint.TopologyKey,

value: node.Labels[constraint.TopologyKey],

}

// addTopologyPairWithoutPods is a non-op if other pods match this pair

nodeTopologyMaps.addTopologyPairWithoutPods(pair)

}

Then in the above loop, the default value (MaxInt32) will be compared with len(podSet), so they won't remain MaxInt32 at the end of the loop.

tedyu · 2019-07-24T02:40:37Z

pkg/scheduler/algorithm/predicates/metadata.go

+		topologyPairsPodSpreadMap.topologyKeyToMinPodsMap[constraint.TopologyKey] = math.MaxInt32
+	}
+	for pair, podSet := range topologyPairsPodSpreadMap.topologyPairToPods {
+		// TODO(Huang-Wei): short circuit unvisited portions of <topologyKey: any value>


I wonder what type of short circuiting you were thinking about.
Without short circuiting, the following comparison is performed and we continue to the next pair:

l < topologyPairsPodSpreadMap.topologyKeyToMinPodsMap[pair.key]

- see more discussion at kubernetes#77760 (comment)

k8s-ci-robot added do-not-merge/hold Indicates that a PR should not merge because someone has issued a /hold command. release-note-none Denotes a PR that doesn't merit a release note. labels May 10, 2019

k8s-ci-robot assigned bsalamat May 10, 2019

k8s-ci-robot added size/XXL Denotes a PR that changes 1000+ lines, ignoring generated files. sig/scheduling Categorizes an issue or PR as relevant to SIG Scheduling. labels May 10, 2019

k8s-ci-robot requested a review from krmayankk May 10, 2019 21:08

k8s-ci-robot added cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. needs-kind Indicates a PR lacks a `kind/foo` label and requires one. needs-priority Indicates a PR lacks a `priority/foo` label and requires one. labels May 10, 2019

Huang-Wei mentioned this pull request May 10, 2019

Umbrella issue for Even Pods Spread [Alpha] #77284

Closed

9 tasks

Huang-Wei force-pushed the eps-pred-meta branch 2 times, most recently from d6a656b to 5ae8ed5 Compare May 11, 2019 07:20

Huang-Wei mentioned this pull request May 13, 2019

Even Pods Spread - 3. Predicates Core #77828

Merged

Huang-Wei changed the title ~~Even Pods Spread - 2 Calculating Predicates Metadata~~ Even Pods Spread - 2. Calculating Predicates Metadata May 13, 2019

Huang-Wei force-pushed the eps-pred-meta branch from 5ae8ed5 to ccc0d59 Compare May 21, 2019 20:12

Huang-Wei force-pushed the eps-pred-meta branch from ccc0d59 to 7c98b44 Compare May 21, 2019 20:30

k8s-ci-robot added the needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. label May 31, 2019

Huang-Wei force-pushed the eps-pred-meta branch from 7c98b44 to f1115ba Compare June 14, 2019 05:27

k8s-ci-robot removed the needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. label Jun 14, 2019

Huang-Wei mentioned this pull request Jun 15, 2019

Even Pods Spread - 4. Preemption Support #79062

Merged

k8s-ci-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Jul 20, 2019

Huang-Wei mentioned this pull request Jul 20, 2019

prow: label "kind/api-change" isn't removed properly kubernetes/test-infra#13526

Closed

draveness reviewed Jul 20, 2019

View reviewed changes

Huang-Wei added 6 commits July 22, 2019 17:34

EvenPodsSpread: PredicateMetadata initilization

a242e37

- build a new `topologyPairsPodSpreadMap` into PredicateMetadata - update ShallowCopy() - unit tests

EvenPodsSpread: refactor topologyPairsPodSpreadMap

3dbef99

- update minMatchMap from []int32 to map[string]int32

EvenPodsSpread: refactor "chained" utils

dce6686

- move "chanined" utils to pkg/scheduler/testing/utils.go so as to be re-used by all scheduler tests

fixup: fix comments and use a channel to pass err

249752c

[eps-pred-meta] auto-gen files

c23aef4

EvenPodsSpread: match selector of each constraint independently

f822487

- see more discussion at kubernetes#77760 (comment)

Huang-Wei force-pushed the eps-pred-meta branch from d5e205a to f822487 Compare July 23, 2019 00:53

ahg-g reviewed Jul 23, 2019

View reviewed changes

k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Jul 23, 2019

k8s-ci-robot removed the do-not-merge/hold Indicates that a PR should not merge because someone has issued a /hold command. label Jul 23, 2019

k8s-ci-robot merged commit 87c3f51 into kubernetes:master Jul 24, 2019

Huang-Wei deleted the eps-pred-meta branch July 24, 2019 00:31

tedyu reviewed Jul 24, 2019

View reviewed changes

alculquicondor mentioned this pull request Jul 24, 2019

REQUEST: New membership for alculquicondor kubernetes/org#1042

Closed

6 tasks

yuxiangqian pushed a commit to yuxiangqian/kubernetes that referenced this pull request Jul 31, 2019

EvenPodsSpread: match selector of each constraint independently

2de4394

- see more discussion at kubernetes#77760 (comment)

Huang-Wei mentioned this pull request Aug 7, 2019

scheduler: internal data structure optimization #81068

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Even Pods Spread - 2. Calculating Predicates Metadata #77760

Even Pods Spread - 2. Calculating Predicates Metadata #77760

Huang-Wei commented May 10, 2019 •

edited

Loading

Huang-Wei commented May 10, 2019

Huang-Wei commented May 21, 2019

Huang-Wei commented May 21, 2019

Huang-Wei commented Jun 14, 2019

draveness Jul 20, 2019

Huang-Wei Jul 23, 2019

draveness Jul 20, 2019

Huang-Wei Jul 23, 2019

draveness Jul 20, 2019

draveness Jul 20, 2019

alculquicondor commented Jul 22, 2019

Huang-Wei commented Jul 22, 2019

alculquicondor commented Jul 22, 2019

Huang-Wei commented Jul 23, 2019

Huang-Wei commented Jul 23, 2019

alculquicondor commented Jul 23, 2019

k8s-ci-robot commented Jul 23, 2019

ahg-g left a comment

ahg-g Jul 23, 2019

Huang-Wei commented Jul 23, 2019

fejta-bot commented Jul 23, 2019

fejta-bot commented Jul 24, 2019

tedyu Jul 24, 2019

Huang-Wei Jul 24, 2019

tedyu Jul 24, 2019

	// If needed, append topology pair without entry of pods.
	// For example, on node-x, there is no pod matching spread constraints,
	// but node-x should be also considered as a match (with match number 0)
	// i.e. <node: node-x>: {}
	for _, constraint := range constraints {
	// constraint.TopologyKey is already guaranteed to be present
	pair := topologyPair{
	key: constraint.TopologyKey,
	value: node.Labels[constraint.TopologyKey],
	}
	// addTopologyPairWithoutPods is a non-op if other pods match this pair
	nodeTopologyMaps.addTopologyPairWithoutPods(pair)
	}

Even Pods Spread - 2. Calculating Predicates Metadata #77760

Even Pods Spread - 2. Calculating Predicates Metadata #77760

Conversation

Huang-Wei commented May 10, 2019 • edited Loading

Huang-Wei commented May 10, 2019

Huang-Wei commented May 21, 2019

Huang-Wei commented May 21, 2019

Huang-Wei commented Jun 14, 2019

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

alculquicondor commented Jul 22, 2019

Huang-Wei commented Jul 22, 2019

alculquicondor commented Jul 22, 2019

Huang-Wei commented Jul 23, 2019

Huang-Wei commented Jul 23, 2019

alculquicondor commented Jul 23, 2019

k8s-ci-robot commented Jul 23, 2019

ahg-g left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Huang-Wei commented Jul 23, 2019

fejta-bot commented Jul 23, 2019

fejta-bot commented Jul 24, 2019

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Huang-Wei commented May 10, 2019 •

edited

Loading