Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Store topology spread constraints in metadata with labels.Selector #85157

Merged
merged 1 commit into from Nov 13, 2019
Merged

Store topology spread constraints in metadata with labels.Selector #85157

merged 1 commit into from Nov 13, 2019

Conversation

alculquicondor
Copy link
Member

@alculquicondor alculquicondor commented Nov 12, 2019 •
edited

What type of PR is this?

/kind cleanup

What this PR does / why we need it:

Stores topology spread constraints in predicates and priority metadata, also parsing labels.Selector. This allows:

  1. Single filtering of the constraints
  2. Single parsing of selectors. This will also enable setting default constraints with generated selectors.

Additionally, this improves the performance of EvenPodsSpreadPriority, making it about 2x faster:

== master ==
BenchmarkTestDefaultEvenPodsSpreadPriority/100nodes-56         	    1148	   1150543 ns/op
BenchmarkTestDefaultEvenPodsSpreadPriority/1000nodes-56        	     190	   6018880 ns/op

BenchmarkTestCalculateEvenPodsSpreadPriority/1000nodes/single-constraint-zone-56         	    3369	    343371 ns/op
BenchmarkTestCalculateEvenPodsSpreadPriority/1000nodes/single-constraint-node-56         	    3195	    353818 ns/op
BenchmarkTestCalculateEvenPodsSpreadPriority/1000nodes/two-constraints-zone-node-56      	    2323	    498521 ns/op

== this PR ==

BenchmarkTestDefaultEvenPodsSpreadPriority/100nodes-56         	    2653	    491937 ns/op
BenchmarkTestDefaultEvenPodsSpreadPriority/1000nodes-56        	     322	   3582697 ns/op

BenchmarkTestCalculateEvenPodsSpreadPriority/1000nodes/single-constraint-zone-56         	    5017	    248531 ns/op
BenchmarkTestCalculateEvenPodsSpreadPriority/1000nodes/single-constraint-node-56         	    4014	    253732 ns/op
BenchmarkTestCalculateEvenPodsSpreadPriority/1000nodes/two-constraints-zone-node-56      	    3434	    300619 ns/op

Ref #84936

Special notes for your reviewer:

Does this PR introduce a user-facing change?:

NONE

@k8s-ci-robot k8s-ci-robot added release-note-none Denotes a PR that doesn't merit a release note. kind/cleanup Categorizes issue or PR as related to cleaning up code, process, or technical debt. size/XL Denotes a PR that changes 500-999 lines, ignoring generated files. cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. needs-sig Indicates an issue or PR lacks a `sig/foo` label and requires one. needs-priority Indicates a PR lacks a `priority/foo` label and requires one. sig/scheduling Categorizes an issue or PR as relevant to SIG Scheduling. and removed needs-sig Indicates an issue or PR lacks a `sig/foo` label and requires one. labels Nov 12, 2019
Huang-Wei
Huang-Wei reviewed Nov 13, 2019
View reviewed changes
Copy link
Member

@Huang-Wei Huang-Wei left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks @alculquicondor ! Some comments below.

pkg/scheduler/algorithm/predicates/metadata.go Outdated
@@ -66,7 +66,7 @@ type criticalPath struct {
// topologyValue denotes the topology value mapping to topology key.
topologyValue string
// matchNum denotes the number of matching pods.
matchNum int32
matchNum int
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Any particular reason for this?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

just to simplify types. Were you trying to optimize memory before?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not particular for memory optimization. It was designed to be aligned with the type defined in API spec. If int32 is good enough, suggest to keep it as is.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done

pkg/scheduler/algorithm/predicates/metadata.go
tpPairToMatchNum map[topologyPair]int
}

type topologySpreadConstraint struct {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

To not confuse with v1.TopologySpreadConstraint, suggest to rename to internal TopologySpreadConstraint or similar name.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

One is just the parsed version of the other. I don't see any harm on them having the same name.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

or, let's put a comment to emphasize that (1) it's an internal version which has a particular labels.Selector field instead of metav1.Selector, (2) it's for simplifying the matching logic and performance.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done

pkg/scheduler/algorithm/predicates/metadata.go Outdated
@@ -581,57 +572,55 @@ func (m *topologyPairsMaps) clone() *topologyPairsMaps {
return copy
}

func (c *evenPodsSpreadMetadata) addPod(addedPod, preemptorPod *v1.Pod, node *v1.Node) error {
return c.updatePod(addedPod, preemptorPod, node, 1)
func (c *evenPodsSpreadMetadata) addPod(addedPod, preemptorPod *v1.Pod, node *v1.Node) {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can we rename c to epsMeta or sth. similar?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

are you ok with just m? one character for the instance variable seems like standard practice.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

m is fine.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done

pkg/scheduler/algorithm/predicates/metadata.go
var result []topologySpreadConstraint
for _, c := range constraints {
if c.WhenUnsatisfiable == v1.DoNotSchedule {
selector, err := metav1.LabelSelectorAsSelector(c.LabelSelector)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It seems this is the key perf of the improvement - LabelSelectorAsSelector doesn't sound like a cheap operation, and if we cache the result, we seem to get a lot of benefits.

A followup is to do a thorough check of "repeated usage of LabelSelectorAsSelector" and do similar refactoring. I do recall there was a PR using the same rationale improving the performance of PodAffinity, probably #79465. We should consolidate this.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

sounds like suggestion. cc @liu-cong who is looking into performance in general.

Copy link
Member

@ahg-g ahg-g Nov 13, 2019 •
edited

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We should run some benchmarks first, but we could annotate the pods in the scheduler cache with already processed Selectors for affinity and spread constraints, and so we do this conversion per pod rather than per pod per cycle.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

SG:) I was discussing with ahg-g yesterday about what can be cached per pod and this seems to fall into that category.

@ahg-g
Copy link
Member

ahg-g commented Nov 13, 2019

/milestone v1.17

@k8s-ci-robot k8s-ci-robot added this to the v1.17 milestone Nov 13, 2019
@Huang-Wei Huang-Wei mentioned this pull request Nov 13, 2019
Merged
@josiahbjorgaard
Copy link
Contributor

@ahg-g Code freeze for v1.17 is tomorrow at 5PM so this will need to be merged before then to make the milestone.

@alculquicondor
Store topology spread constraints in metadata with labels.Selector
e3bdb4b 
Signed-off-by: Aldo Culquicondor <acondor@google.com>
@alculquicondor
Copy link
Member Author

/retest

@alculquicondor
Copy link
Member Author

/test pull-kubernetes-node-e2e-containerd

1 similar comment
@alculquicondor
Copy link
Member Author

/test pull-kubernetes-node-e2e-containerd

@Huang-Wei
Copy link
Member

/retest

@Huang-Wei
Copy link
Member

/lgtm
/approve

@k8s-ci-robot k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Nov 13, 2019
@k8s-ci-robot
Copy link
Contributor

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: alculquicondor, Huang-Wei

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:

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 k8s-ci-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Nov 13, 2019
@k8s-ci-robot k8s-ci-robot merged commit 209c025 into kubernetes:master Nov 13, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@Huang-Wei Huang-Wei Huang-Wei left review comments

@liu-cong liu-cong liu-cong left review comments

@ahg-g ahg-g ahg-g left review comments

@hex108 hex108 Awaiting requested review from hex108

Assignees

@Huang-Wei Huang-Wei

Labels
approved Indicates a PR has been approved by an approver from all required OWNERS files. cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. kind/cleanup Categorizes issue or PR as related to cleaning up code, process, or technical debt. lgtm "Looks good to me", indicates that a PR is ready to be merged. needs-priority Indicates a PR lacks a `priority/foo` label and requires one. release-note-none Denotes a PR that doesn't merit a release note. sig/scheduling Categorizes an issue or PR as relevant to SIG Scheduling. size/XL Denotes a PR that changes 500-999 lines, ignoring generated files.
Projects
None yet
Milestone
v1.17
Development

Successfully merging this pull request may close these issues.

None yet
6 participants
@alculquicondor @ahg-g @josiahbjorgaard @Huang-Wei @k8s-ci-robot @liu-cong