descheduler: HighNodeUtilization does nothing when all nodes are underutilized

This seems like a bug to me, probably this line was carried over from LowNodeUtilization where a check like this makes more sense. But the point of HighNodeUtilization is to try to achieve bin-packing. So when all nodes are underutilized, we should definitely be taking some action, the question is what should that be?

do you hope that if all nodes are underutilized, only evict pods on random one nodes?

I think we could take a more opinionated approach than this. Since HighNodeUtilization is specifically trying to evict the least-utilized nodes, that gives us a goal to work toward. Maybe we could sort the nodes by utilization and evict pods from the least-utilized nodes until the higher nodes become full (or at least we assume they’ll be full). Similar to the pod topology spread balancing strategy.

I wonder how many least-utilized nodes should we evict from, how many higher nodes should we target? (taking into account not just the case where all the nodes are underutilized)

If the goal of HighNodeUtilization is to bin-pack, then imo the answer is “all the nodes”. For example if you have 4 nodes with these utilizations:

10% 20% 30% 40%

Then evicting from the lowest on to the highest would follow these steps:

1. 0% 20% 30% 50%
2. 0% 0% 30% 70%
3. 0% 0% 0% 100%

Since the scheduler doesn’t have any configurable threshold for “fully-packed” (ie, it always tries for 100% utilization when configured this way), then staying in sync with the assume re-scheduling strategy would use this assumption that we want as few nodes as possible with 100% and as many as possible with 0%

I wonder what’s the percentage of fully evictable nodes compared to “fully-packed” nodes in the wild. Given the descheduler can not simulate what’s the optimal number of nodes to be left intact, we still need some artificial threshold/way of saying “this is where we stop evicting so we don’t over-flood remaining nodes”. The current algorithm is too simple and presumably sub-optimal to take into account the assumption.

I wonder if it is worth extending the current implementation towards the assumption or re-implementing it (maybe as a new strategy replacing this one) to evict pods from the lowest to the highest utilized nodes. I have not explored this path yet. Open to discussion.

Questions to think about:

• If all nodes are underutilized how can one decide which nodes should be completely drained and which should stay as potential target nodes for attracting evicted pods?

• Maybe we could sort the nodes by utilization and evict pods from the least-utilized nodes until the higher nodes become full (or at least we assume they’ll be full)

  I wonder how many least-utilized nodes should we evict from, how many higher nodes should we target? (taking into account not just the case where all the nodes are underutilized)

The threshold was introduced as a trivial solution for dividing nodes into two groups. One group of nodes for evicting pods, the other one as potential targets for collocating nodes to achieve the bin-packing (up to the kube-scheduler to decide which nodes are to be targeted). In this case the threshold is too high to evict pods from any node. So you need adaptive approach which will lower the threshold. Something like “if all nodes are underutilized, find the first X% of nodes which have the lowest utilization (wrt. native and extended resources) and dynamically adjust the threshold”. The X can be set to 50% or higher based on customer use cases. E.g.:

deschedulerPolicy:
  strategies:
    HighNodeUtilization:
      enabled: true
      params:
        nodeResourceUtilizationThresholds:
          thresholds:
            memory: 20
        adaptiveThresholdPercentages: 50 # will apply only when all nodes are underutlized
        numberOfNodes: 0
    LowNodeUtilization:
      enabled: false
schedule: 5 10 * * *

The strategy would then “just” adapt the threshold and run the strategy one more time with the new threshold. With expectation that next time there’s gonna be at least one node that is minimally utilized (on the scale [underutilized, utilized, overutilized]).

@slobo I wonder if dynamically adapting the threshold would be something applicable in your use case(s)?

if all nodes are underutilized, sort the nodes by utilization and evict pods on the least-utilized nodes. very good idea~~ could i have a try on this enhancement?

I agree, I’d expect that the least utilized node get evicted.

This is somewhat tangential, perhaps we could have an option for descheduler to aggressively force “optimal” packing by cordoning off the nodes before evicting pods from them? That way there would be no chance of pods ending back onto low utilization nodes, regardless of the scheduler configuration - i.e. you wouldn’t need to setup NodeResourcesFit = MostAllocated to get at least some effect from descheduling.