search

karmada-io / karmada

Open, Multi-Cloud, Multi-Cluster Kubernetes Orchestration
https://karmada.io
Apache License 2.0
4.12k stars 807 forks source link

Optimize deprioritized policy preemption logic #4555

Closed whitewindmills closed 2 months ago

whitewindmills commented 3 months ago

What type of PR is this? /kind feature /kind cleanup

What this PR does / why we need it: Using the natural ordering properties of red-black trees to sort the listed policies to ensure the higher priority (Cluster)PropagationPolicy being processed first to avoid possible multiple preemption.

Which issue(s) this PR fixes: Fixes #

Special notes for your reviewer:

Does this PR introduce a user-facing change?:

NONE
whitewindmills commented 3 months ago

/cc @RainbowMango @chaosi-zju

codecov-commenter commented 3 months ago

Codecov Report

Attention: Patch coverage is 0% with 44 lines in your changes are missing coverage. Please review.

Project coverage is 51.40%. Comparing base (413a15a) to head (e88797b). Report is 76 commits behind head on master.

Files Patch % Lines
pkg/detector/preemption.go 0.00% 44 Missing :warning:

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #4555 +/- ## ========================================== - Coverage 51.86% 51.40% -0.47% ========================================== Files 243 250 +7 Lines 24183 24979 +796 ========================================== + Hits 12543 12840 +297 - Misses 10959 11433 +474 - Partials 681 706 +25 ``` | [Flag](https://app.codecov.io/gh/karmada-io/karmada/pull/4555/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=karmada-io) | Coverage Δ | | |---|---|---| | [unittests](https://app.codecov.io/gh/karmada-io/karmada/pull/4555/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=karmada-io) | `51.40% <0.00%> (-0.47%)` | :arrow_down: | Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=karmada-io#carryforward-flags-in-the-pull-request-comment) to find out more.

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

whitewindmills commented 3 months ago

ping @RainbowMango @chaosi-zju Kindly help to take a look, thanks.

chaosi-zju commented 3 months ago

the code in this PR looks good, thank you for your effort!

RainbowMango commented 3 months ago

Using the natural ordering properties of red-black trees to sort the listed policies to ensure the higher priority (Cluster)PropagationPolicy being processed first to avoid possible multiple preemption.

Seems this PR trying to fix a bug?

whitewindmills commented 3 months ago

Seems this PR trying to fix a bug?

More like optimization cause multiple preemptions do not affect its functionality.

whitewindmills commented 3 months ago

@chaosi-zju @RainbowMango PTAL~

whitewindmills commented 2 months ago

ping @RainbowMango

RainbowMango commented 2 months ago

/assign

RainbowMango commented 2 months ago

By the way, have you ever considered the PriorityQueue which looks like more simple than the tree.

whitewindmills commented 2 months ago

By the way, have you ever considered the PriorityQueue which looks like more simple than the tree.

Nice reminder.

whitewindmills commented 2 months ago

Their performance is almost the same(both O(logN), but using the priority queue code is more concise. @RainbowMango PTAL

RainbowMango commented 2 months ago

Seems the related testing is failing:

• [FAILED] [425.271 seconds]
[Preemption] propagation policy preemption testing when [ClusterPropagationPolicy Preemption] ClusterPropagationPolicy preempts another ClusterPropagationPolicy High-priority ClusterPropagationPolicy reduces priority to be preempted by low-priority ClusterPropagationPolicy [It] Propagate the deployment with the high-priority ClusterPropagationPolicy and then reduce it's priority to be preempted by the low-priority ClusterPropagationPolicy

https://github.com/karmada-io/karmada/actions/runs/8078521320/job/22071318982?pr=4555

whitewindmills commented 2 months ago

@RainbowMango Ready to review again.

karmada-bot commented 2 months ago

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: RainbowMango

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: - ~~[OWNERS](https://github.com/karmada-io/karmada/blob/master/OWNERS)~~ [RainbowMango] Approvers can indicate their approval by writing `/approve` in a comment Approvers can cancel approval by writing `/approve cancel` in a comment