Use reservoir sampling to select one host from priority list

[hainesc]

What type of PR is this?

Uncomment only one /kind <> line, hit enter to put that in a new line, and remove leading whitespaces from that line:

/kind api-change
/kind bug

/kind cleanup

/kind design
/kind documentation
/kind failing-test
/kind feature
/kind flake

What this PR does / why we need it:

The function selectHost was designed to select one host from priority list with a highest score, However, the current manner use round-robin and it has to keep a var named lastNodeIndex in the struct of genericScheduler, and it introduces a helper function findMaxScores, both are not needed if we use reservoir sampling, which is more suitable for selecting one candidate with same possibility from a set, and the code will be cleaner. For the detail of reservoir sampling, see here.

Which issue(s) this PR fixes:

Fixes #

Special notes for your reviewer:

Does this PR introduce a user-facing change?:

NONE

[k8s-ci-robot]

Hi @hainesc. Thanks for your PR.

I'm waiting for a kubernetes member to verify that this patch is reasonable to test. If it is, they should reply with /ok-to-test on its own line. Until that is done, I will not automatically test new commits in this PR, but the usual testing commands by org members will still work. Regular contributors should join the org to skip this step.

Once the patch is verified, the new status will be reflected by the ok-to-test label.

I understand the commands that are listed here.

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]

This is nice!

[hainesc]

ping @resouer @misterikkit for review and ok-to-test label

Thanks.

[hainesc]

ping @kubernetes/sig-scheduling-pr-reviews for review

[k8s-ci-robot]

@hainesc: Reiterating the mentions to trigger a notification:
@kubernetes/sig-scheduling-pr-reviews

In response to this:

ping @kubernetes/sig-scheduling-pr-reviews for review

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.

[yastij]

/lgtm
/priority backlog
/assign @misterikkit

[yastij]

@bsalamat - while i can buy the logic behind the change, I'm afraid that this might over-complicate our testing logic, thoughts ?

[hainesc]

/test pull-kubernetes-bazel-test

[k8s-ci-robot]

@hainesc: Cannot trigger testing until a trusted user reviews the PR and leaves an /ok-to-test message.

In response to this:

/test pull-kubernetes-bazel-test

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.

[hainesc]

ping @yastij for ok-to-test

[yastij]

/ok-to-test

[yastij]

re-applying lgtm per my first comment

/lgtm

[hainesc]

ping @misterikkit for approve, please take a look. Thanks.

[hainesc]

ping @yastij Can you help me ping an approver? It is a long time since the lgtm label. I don't know who is responsible for this pr.

[ahg-g]

we are in code freeze now, even if it gets approved, it is not going to be merged until the freeze is over (probably mid June).

[hainesc]

Hi @ahg-g, Can this pr get merged?

[hainesc]

ping @yastij for approve.
Thanks

[gaorong]

thanks @hainesc , I love this creative solution, but it seems this will break the previous round-robin manner to select a node and change to random selecting?

[hainesc]

it seems this will break the previous round-robin manner to select a node and change to random selecting?

@gaorong Yes, as shown by the benchmark, random selecting wins a lot against the round-robin manner in performance. And also, as you see, the code is more cleaner than the previous.

I'd like to know what's your concern when we break the round-robin? In my opinion, there should be no assumption which node(with the highest score) will be selected, the only expected thing is that the candidate should be equal in probability.

[misterikkit]

@gaorong The current "round robin" behavior doesn't actually result in round robin scheduling. Rather, the lastNodeIndex is used to index into the slice of nodes which have the highest ranking. The size of this slice is likely to be different for each pod we schedule.

@bsalamat can confirm, but the intent of this mechanic is to prevent one node from getting all the pending pods when there are other equivalent nodes.

[hainesc]

Thanks @misterikkit Yes, the input slice is likely to be different in scores and order as the cluster is dynamic.

Looking forward this PR getting merged (yeah, a long time wait), as it is proved to be better than the current code. It is approved by @ahg-g and @yastij

Thanks, all!

[gaorong]

the intent of this mechanic is to prevent one node from getting all the pending pods when there are other equivalent nodes.

thanks misterikkit@, after rethinking, I guess the lastNodeIndex should keep as it is. although it can not guarantee round-robin, it can try to provide fairer selecting among equivalent nodes than random selecting.

[ahg-g]

@Huang-Wei @bsalamat I like this PR, it allows removing a member variable of genericScheduler without compromising semantics (the minimal perf improvement is a cherry on the top).

[misterikkit]

it can try to provide fairer selecting among equivalent nodes than random selecting.

@gaorong, I took a deeper look into the code, and the filter step makes no promises about stable ordering. In fact, it evaluates nodes in parallel. So in that sense, we are already doing an arbitrary, undefined distribution with lastNodeIndex. Switching to a uniform distribution ought to increase fairness. (It is unlikely to make it noticeably worse.)

[Huang-Wei]

Thanks @misterikkit for the above comment. Simply put, we are doing (1) nodes shuffling + (2) (to some extent) fair nodes pickup by lastIndex which still results in an eventual shuffling.
So IMO it's ok to onboard this PR (which is shuffling*2).

[gaorong]

thank you guys for clarification.

[Huang-Wei]

/lgtm
/approve

Thanks, @hainesc !

[k8s-ci-robot]

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: hainesc, 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:

• pkg/scheduler/OWNERS [Huang-Wei]

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

[yb01]

/lgtm.
this change might node improve perf but it simplify the code and randomized the node selection. so let's take it.