Add a feature to the scheduler to score fewer than all nodes in every scheduling cycle #66733

bsalamat · 2018-07-28T02:24:51Z

What this PR does / why we need it:
Today, the scheduler scores all the nodes in the cluster in every scheduling cycle (every time a posd is attempted). This feature implements a mechanism in the scheduler that allows scoring fewer than all nodes in the cluster. The scheduler stops searching for more nodes once the configured number of feasible nodes are found. This can help improve the scheduler's performance in large clusters (several hundred nodes and larger).
This PR also adds a new structure to the scheduler's cache, called NodeTree, that allows scheduler to iterate over various nodes in different zones in a cluster. This is needed to avoid scoring the same set of nodes in every scheduling cycle.

Which issue(s) this PR fixes (optional, in fixes #<issue number>(, fixes #<issue_number>, ...) format, will close the issue(s) when PR gets merged):
Fixes #66627

Special notes for your reviewer:
This is a large PR, but broken into a few logical commits. Reviewing would be easier if you review by commits.

Release note:

Add a feature to the scheduler to score fewer than all nodes in every scheduling cycle. This can improve performance of the scheduler in large clusters.

k8s-github-robot · 2018-07-28T02:33:43Z

[MILESTONENOTIFIER] Milestone Pull Request: Up-to-date for process

@bsalamat

Pull Request Labels

sig/scheduling: Pull Request will be escalated to these SIGs if needed.
priority/important-soon: Escalate to the pull request owners and SIG owner; move out of milestone after several unsuccessful escalation attempts.
kind/feature: New functionality.

Help

wgliang · 2018-07-28T03:01:27Z

pkg/scheduler/core/generic_scheduler.go

+		allNodes := int32(g.cache.NodeTree().NumNodes)
+		numNodesToFind := g.numFeasibleNodesToFind(allNodes)
+		numNodesProcessed := int32(0)
+		for numNodesProcessed < allNodes {


Why not do it all at once until filteredLen >= numNodesToFind?

once you send work to parallelize you cannot stop in the middle.

Adding a parameter to parallelize to control is a solution, or just redefining an interface to implement this functionality.

Parallelize is a part of a client-go library. We cannot change its parameters, but I agree that having another Parallelize function, for example, ParallelizeUntil(..., condition) would be useful. That should be done as a separate PR though. Do you think you can add one that can be used here?

Ok, when this PR is merged I will help implement it. :)

wgliang · 2018-07-28T07:16:33Z

pkg/scheduler/core/generic_scheduler.go

@@ -45,6 +45,10 @@ import (
 	"k8s.io/kubernetes/pkg/scheduler/volumebinder"
 )

+const (
+	minFeasibleNodesToFind = 20


Why is it 20, I think we need to have relevant comments to explain.

20 is an arbitrary value. I added a comment to explain.

wgliang · 2018-07-28T07:17:32Z

pkg/scheduler/core/generic_scheduler.go

@@ -336,6 +341,20 @@ func (g *genericScheduler) getLowerPriorityNominatedPods(pod *v1.Pod, nodeName s
 	return lowerPriorityPods
 }

+// numFeasibleNodesToFind returns the number of feasible nodes that once found, the scheduler stops
+// its search for more feasible nodes.
+func (g *genericScheduler) numFeasibleNodesToFind(allNodes int32) int32 {


numAllNodes will be better.

jimangel · 2018-08-17T02:26:50Z

@bsalamat does this need/have a PR against the 1.12 docs branch? Looks like a major change. Thanks!

sttts · 2018-08-17T06:45:26Z

cmd/kube-scheduler/app/options/deprecated.go

@@ -68,6 +67,8 @@ func (o *DeprecatedOptions) AddFlags(fs *pflag.FlagSet, cfg *componentconfig.Kub
 	fs.MarkDeprecated("hard-pod-affinity-symmetric-weight", "This option was moved to the policy configuration file")
 	fs.StringVar(&cfg.FailureDomains, "failure-domains", cfg.FailureDomains, "Indicate the \"all topologies\" set for an empty topologyKey when it's used for PreferredDuringScheduling pod anti-affinity.")
 	fs.MarkDeprecated("failure-domains", "Doesn't have any effect. Will be removed in future version.")
+	fs.Int32Var(&cfg.PercentageOfNodesToScore, "percentage-of-nodes-to-score", cfg.PercentageOfNodesToScore,


Let's not add anything to the deprecated flags.

Since the componentconfig is still alpha, these options are not quite "deprecated"! 😉
Anyway, I removed it.

sttts · 2018-08-17T06:46:24Z

One comment about the flag. Otherwise sgtm.

bsalamat · 2018-08-17T17:34:20Z

@jimangel Yes, I will write/update docs.

sttts · 2018-08-17T17:50:58Z

/lgtm
/approve

k8s-ci-robot · 2018-08-17T17:51:30Z

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: bsalamat, fejta, k82cn, sttts

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Needs approval from an approver in each of these files:

~~cmd/kube-scheduler/OWNERS~~ [bsalamat,k82cn]
~~pkg/apis/componentconfig/OWNERS~~ [sttts]
~~pkg/scheduler/OWNERS~~ [bsalamat,k82cn]
~~test/OWNERS~~ [fejta,sttts]

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment

k8s-ci-robot · 2018-08-17T18:19:04Z

New changes are detected. LGTM label has been removed.

k8s-github-robot · 2018-08-17T23:01:55Z

/test all [submit-queue is verifying that this PR is safe to merge]

k8s-github-robot · 2018-08-18T00:21:32Z

Automatic merge from submit-queue. If you want to cherry-pick this change to another branch, please follow the instructions here.

@bsalamat

Automatic merge from submit-queue (batch tested with PRs 67555, 68196). If you want to cherry-pick this change to another branch, please follow the instructions here: https://github.com/kubernetes/community/blob/master/contributors/devel/cherry-picks.md. Not split nodes when searching for nodes but doing it all at once **What this PR does / why we need it**: Not split nodes when searching for nodes but doing it all at once. **Which issue(s) this PR fixes** *(optional, in `fixes #<issue number>(, fixes #<issue_number>, ...)` format, will close the issue(s) when PR gets merged)*: Fixes # **Special notes for your reviewer**: @bsalamat This is a follow up PR of #66733. #66733 (comment) **Release note**: ```release-note Not split nodes when searching for nodes but doing it all at once. ```

@bsalamat

Automatic merge from submit-queue (batch tested with PRs 67555, 68196). If you want to cherry-pick this change to another branch, please follow the instructions here: https://github.com/kubernetes/community/blob/master/contributors/devel/cherry-picks.md. Not split nodes when searching for nodes but doing it all at once **What this PR does / why we need it**: Not split nodes when searching for nodes but doing it all at once. **Which issue(s) this PR fixes** *(optional, in `fixes #<issue number>(, fixes #<issue_number>, ...)` format, will close the issue(s) when PR gets merged)*: Fixes # **Special notes for your reviewer**: @bsalamat This is a follow up PR of #66733. kubernetes/kubernetes#66733 (comment) **Release note**: ```release-note Not split nodes when searching for nodes but doing it all at once. ``` Kubernetes-commit: a0b457d0e5ed54646fd01eac877efcea5be3216d

@bsalamat

Automatic merge from submit-queue (batch tested with PRs 67555, 68196). If you want to cherry-pick this change to another branch, please follow the instructions here: https://github.com/kubernetes/community/blob/master/contributors/devel/cherry-picks.md. Not split nodes when searching for nodes but doing it all at once **What this PR does / why we need it**: Not split nodes when searching for nodes but doing it all at once. **Which issue(s) this PR fixes** *(optional, in `fixes #<issue number>(, fixes #<issue_number>, ...)` format, will close the issue(s) when PR gets merged)*: Fixes # **Special notes for your reviewer**: @bsalamat This is a follow up PR of #66733. kubernetes/kubernetes#66733 (comment) **Release note**: ```release-note Not split nodes when searching for nodes but doing it all at once. ``` Kubernetes-commit: a0b457d0e5ed54646fd01eac877efcea5be3216d

@bsalamat

Automatic merge from submit-queue (batch tested with PRs 67555, 68196). If you want to cherry-pick this change to another branch, please follow the instructions here: https://github.com/kubernetes/community/blob/master/contributors/devel/cherry-picks.md. Not split nodes when searching for nodes but doing it all at once **What this PR does / why we need it**: Not split nodes when searching for nodes but doing it all at once. **Which issue(s) this PR fixes** *(optional, in `fixes #<issue number>(, fixes #<issue_number>, ...)` format, will close the issue(s) when PR gets merged)*: Fixes # **Special notes for your reviewer**: @bsalamat This is a follow up PR of #66733. kubernetes/kubernetes#66733 (comment) **Release note**: ```release-note Not split nodes when searching for nodes but doing it all at once. ``` Kubernetes-commit: a0b457d0e5ed54646fd01eac877efcea5be3216d

@bsalamat

Automatic merge from submit-queue (batch tested with PRs 67555, 68196). If you want to cherry-pick this change to another branch, please follow the instructions here: https://github.com/kubernetes/community/blob/master/contributors/devel/cherry-picks.md. Not split nodes when searching for nodes but doing it all at once **What this PR does / why we need it**: Not split nodes when searching for nodes but doing it all at once. **Which issue(s) this PR fixes** *(optional, in `fixes #<issue number>(, fixes #<issue_number>, ...)` format, will close the issue(s) when PR gets merged)*: Fixes # **Special notes for your reviewer**: @bsalamat This is a follow up PR of #66733. kubernetes/kubernetes#66733 (comment) **Release note**: ```release-note Not split nodes when searching for nodes but doing it all at once. ``` Kubernetes-commit: a0b457d0e5ed54646fd01eac877efcea5be3216d

k8s-ci-robot requested review from davidopp and fejta July 28, 2018 02:25

bsalamat requested review from ravisantoshgudimetla and k82cn July 28, 2018 02:25

bsalamat added this to the v1.12 milestone Jul 28, 2018

k8s-github-robot added kind/api-change Categorizes issue or PR as related to adding, removing, or otherwise changing an API milestone/incomplete-labels labels Jul 28, 2018

k8s-github-robot added kind/api-change Categorizes issue or PR as related to adding, removing, or otherwise changing an API milestone/needs-approval labels Jul 28, 2018

bsalamat force-pushed the subset_nodes branch from d75dc21 to 2565a7b Compare July 28, 2018 02:31

bsalamat added the status/approved-for-milestone label Jul 28, 2018

k8s-github-robot removed the milestone/needs-approval label Jul 28, 2018

bsalamat force-pushed the subset_nodes branch from 2565a7b to cd0c0ad Compare July 28, 2018 02:35

wgliang reviewed Jul 28, 2018

View reviewed changes

bsalamat force-pushed the subset_nodes branch from cd0c0ad to c7826f3 Compare July 28, 2018 04:17

k8s-ci-robot added size/XXL Denotes a PR that changes 1000+ lines, ignoring generated files. and removed size/XL Denotes a PR that changes 500-999 lines, ignoring generated files. labels Jul 28, 2018

bsalamat force-pushed the subset_nodes branch 3 times, most recently from 4f4e26c to 3875e5b Compare July 28, 2018 04:57

wgliang reviewed Jul 28, 2018

View reviewed changes

bsalamat force-pushed the subset_nodes branch from e5518ed to 95a6273 Compare August 17, 2018 01:28

k8s-ci-robot removed the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Aug 17, 2018

sttts reviewed Aug 17, 2018

View reviewed changes

bsalamat added 2 commits August 17, 2018 09:56

Add a node tree that allows iterating over nodes in regions and zones

c1896c9

Add NodeTree to the scheduler cache

a5045d1

bsalamat force-pushed the subset_nodes branch from 95a6273 to 6fbfaa9 Compare August 17, 2018 17:30

k8s-ci-robot assigned sttts Aug 17, 2018

k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Aug 17, 2018

k8s-ci-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Aug 17, 2018

bsalamat added 2 commits August 17, 2018 11:18

Add a scheduler config argument to set the percentage of nodes to score

abb70ae

Autogenerated files

2860743

bsalamat force-pushed the subset_nodes branch from 6fbfaa9 to 2860743 Compare August 17, 2018 18:19

k8s-ci-robot removed the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Aug 17, 2018

bsalamat added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Aug 17, 2018

k8s-github-robot merged commit 8c1bfeb into kubernetes:master Aug 18, 2018

wgliang mentioned this pull request Aug 18, 2018

Not split nodes when searching for nodes but doing it all at once #67555

Merged

bsalamat mentioned this pull request Sep 8, 2018

Scheduler checks feasibility and scores a subset of all cluster nodes kubernetes/enhancements#593

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add a feature to the scheduler to score fewer than all nodes in every scheduling cycle #66733

Add a feature to the scheduler to score fewer than all nodes in every scheduling cycle #66733

bsalamat commented Jul 28, 2018

k8s-github-robot commented Jul 28, 2018

wgliang Jul 28, 2018

bsalamat Jul 28, 2018

wgliang Jul 28, 2018

bsalamat Jul 28, 2018

wgliang Jul 28, 2018

wgliang Jul 28, 2018

bsalamat Jul 28, 2018

wgliang Jul 28, 2018

jimangel commented Aug 17, 2018

sttts Aug 17, 2018

bsalamat Aug 17, 2018

sttts commented Aug 17, 2018

bsalamat commented Aug 17, 2018

sttts commented Aug 17, 2018

k8s-ci-robot commented Aug 17, 2018

k8s-ci-robot commented Aug 17, 2018

k8s-github-robot commented Aug 17, 2018

k8s-github-robot commented Aug 18, 2018

Add a feature to the scheduler to score fewer than all nodes in every scheduling cycle #66733

Add a feature to the scheduler to score fewer than all nodes in every scheduling cycle #66733

Conversation

bsalamat commented Jul 28, 2018

k8s-github-robot commented Jul 28, 2018

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

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jimangel commented Aug 17, 2018

Choose a reason for hiding this comment

Choose a reason for hiding this comment

sttts commented Aug 17, 2018

bsalamat commented Aug 17, 2018

sttts commented Aug 17, 2018

k8s-ci-robot commented Aug 17, 2018

k8s-ci-robot commented Aug 17, 2018

k8s-github-robot commented Aug 17, 2018

k8s-github-robot commented Aug 18, 2018