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.

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

Implement predicate ordering for the kubernetes scheduler #53812

Closed
yastij opened this Issue Oct 12, 2017 · 4 comments

Comments

Projects
None yet
3 participants
@yastij
Member

yastij commented Oct 12, 2017

following the design proposal on kubernetes/community#1152 this will be the issue that will track down the work to implement predicates ordering, work to be done:

  • set predicate ordering to create the proposed static ordering / tests
  • export restrictiveness as a prometheus metric
  • write docs and examples

also to be done based on customers feedback:

  • implement the end-user ordering (scheduler policy parsing + override of the static ordering) / tests

I'll create the PRs accordingly, after kubernetes/community#1152 is merged.

@gmarek @bsalamat @k82cn

@yastij

This comment has been minimized.

Show comment
Hide comment
@yastij

yastij Oct 12, 2017

Member

/sig scheduling
/assign

Member

yastij commented Oct 12, 2017

/sig scheduling
/assign

@yastij

This comment has been minimized.

Show comment
Hide comment
@yastij

yastij Oct 12, 2017

Member

@gmarek @bsalamat @k82cn - Also needs to be added to 1.10 milestone

Member

yastij commented Oct 12, 2017

@gmarek @bsalamat @k82cn - Also needs to be added to 1.10 milestone

@resouer resouer added this to the v1.10 milestone Dec 12, 2017

@resouer

This comment has been minimized.

Show comment
Hide comment
@resouer

resouer Dec 12, 2017

Member

@yastij I added the milestone, while updating your recent progress status would be helpful here.

Member

resouer commented Dec 12, 2017

@yastij I added the milestone, while updating your recent progress status would be helpful here.

@yastij

This comment has been minimized.

Show comment
Hide comment
@yastij

yastij Dec 13, 2017

Member

I'll submit a first version tomorrow, with a minimal modification to implement ordering.

Member

yastij commented Dec 13, 2017

I'll submit a first version tomorrow, with a minimal modification to implement ordering.

k8s-merge-robot added a commit that referenced this issue Dec 20, 2017

Merge pull request #57168 from yastij/predicates-ordering
Automatic merge from submit-queue (batch tested with PRs 57252, 57168). If you want to cherry-pick this change to another branch, please follow the instructions <a href="https://github.com/kubernetes/community/blob/master/contributors/devel/cherry-picks.md">here</a>.

Implementing predicates ordering

**What this PR does / why we need it**: implements predicates ordering for the scheduler

**Which issue(s) this PR fixes** : Fixes #53812 

**Special notes for your reviewer**:


@bsalamat @gmarek @resouer as discussed on slack, to implement ordering we have to choices:

- use a layered approach with a list that indexes the order of the predicates map

- change the underlying data structure used to represent a collection of predicates (a map in our case) into a list of predicates objects. 
Going with this solution might be "cleaner" but it will require a lot of changes and will increase the cost for accessing predicates from O(1) to O(n) (n being the number of predicates used by the scheduler).

we might go with this solution for now. If the number of predicates start growing, we might switch to the second option.
 
**Release note**:

```release-note
adding predicates ordering for the kubernetes scheduler.
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment