Repository: kubernetes
Issue: Introduce `ReevaluationHint` in QHint for a single node scheduling constraint optimization
Labels: sig/scheduling,kind/feature,needs-triage

/assign
/sig scheduling
/cc @kubernetes/sig-scheduling-misc @macsko @dom4ha 
 

## Summary

Introduce a new return value `ReevaluationHint` in QHint so that we don't have to re-evaluate all nodes at the scheduling retries.

## Motivation

We can roughly divide our scheduling constraints into two groups: "single node constraint" or "cross-node (or node unrelated) constraint".

For example, resource requirement is "single node constraint" because if node-a doesn't have enough CPU for pod-a, node-a is filtered out in the scheduling cycle, that is, node-a's filtering result is determined only by node-a's status.
And, pod topology spread is "cross-node constraint" because if domain-a, which node-a belongs to, has too many Pods matching topology spread, node-a is filtered out, that is, node-a's filtering result is determined by not only node-a's status, but also by other nodes' status too.

Let’s think about the requeueing scenarios of the resource fit plugin (single node constraints).
There are four registered events:
- Node/Add: Node is newly added. In this case, the Pod might be schedulable on the new node.
- Node/UpdateNodeAllocatable: Node got more resources. In this case, the Pod might be schedulable on the updated node.
- Pod/Delete: The running Pod is deleted, In this case, the Pod might be schedulable on the node where the deleted Pod was running on.
- Pod/UpdatePodScaleDown: 
  - The existing Pod is scaled down: In this case, the Pod might be schedulable on the node where the scaled-down pod is running on.
  - The unschedulable Pod itself is scaled down: In this case, the Pod might be schedulable on any nodes.

In all cases, we can determine which node(s) to re-evaluate in the next scheduling cycles.

Currently, every scheduling cycle (basically) always evaluates all the nodes.
If we could reduce the number of nodes to re-evaluate, that could be a significant performance optimization for the second or later scheduling cycles.

## Goals

- Allow QHint to return which node(s) to re-evaluate, change the scheduling cycles to consider them, and improve the scheduling latency for Pods with a single node scheduling constraint.

## Non-Goals

<!--
What is out of scope for this proposal? Listing non-goals helps to focus discussion
and make progress.
-->

- Cross nodes scheduling constraint is out-of-scope for now. But, see `Future ideas` section at the bottom.
  - Given the cross node scheduling constraints are only PodAffinity and PodTopologySpread in the default scheduler, we can still get a huge benefit only with a single node scheduling constraint support.

## Proposal

### Design Details

#### QHint interface change

Change QHint interface to return which node(s) to re-evaluate.

```go
type ReevaluationHint struct {
  // NodeNames has the names of nodes which should be re-evaluated in the next scheduling cycle.
  // Empty means all nodes.
  NodeNames sets.Set[string]
}

type QueueingHintFn func(logger klog.Logger, pod *v1.Pod, oldObj, newObj interface{}) (QueueingHint, ReevaluationHint, error)
```

#### Scheduling queue change

We need to run QHints for Pods that are already in backoffQ or activeQ,
otherwise some nodes that should be re-evaluated might be overlooked.

The queue would aggregate all ReevaluationHint(s) that are returned from QHints,
and store them in PodInfo or somewhere so that the next scheduling cycle can refer to them. 
### User Stories

<!--
Detail the things that people will be able to do if this proposal is implemented.
Include as much detail as possible so that people can understand the "how" of
the system. The goal here is to make this feel real for users without getting
bogged down.
-->

#### Story 1

There are 5k nodes in the cluster.
Pod-a is created, but a scheduling for Pod-a fails because all Nodes don't have enough CPU for this Pod.
A moment later, one Pod on Node-a is removed and now Node-a may have enough CPU for Pod-a, thus the scheduler retries the scheduling for this Pod.
We currently (basically) re-evaluate all nodes in the next scheduling cycle.

But, after this enhancement, QHint from the resource fit plugin returns Queue for this Pod/Delete event, and also it returns Node-a in ReevaluationHint.
And, at the next scheduling cycle, 4999 Nodes are pre-filtered out by ReevaluationHint, and the scheduling cycle only re-evaluate Node-a
We can save the calculation for 4999 Nodes.

### Risks and Mitigations

#### QHint calculation cost and possible negative impact on the scheduling throughput

As mentioned earlier, the number of QHint runs would increase because we have to run QHints for Pods in activeQ/backoffQ as well.
As we experienced recently, the latency of event handling could impact the scheduling throughput negatively, mainly because of the shared lock in the queue.

We need to carefully evaluate if this enhancement really improves the throughput with some PoC.

## Future ideas

### Cross node scheduling constraint support

Actually, we might be able to do the same for some cross node constraints too.
We can add LabelSelector in ReevaluationHint.

```go
type ReevaluationHint struct {
  // NodeNames has the names of nodes which should be re-evaluated in the next scheduling cycle.
  // Empty means all nodes.
  NodeNames sets.Set[string]
  // LabelSelector has the selector for nodes which should be re-evaluated in the next scheduling cycle.
  // Empty means all nodes.
  LabelSelector *labels.Selector
}
```

And, for example, let’s say a Pod failed with PodTopologySpread because the spreading is like: zone-a:zone-b:zone-c = 2:3:4 (maxSkew: 1). In this case, PodTopologySpread rejects all nodes in zone-b and zone-c.

And, supposing a new matching Pod is added to zone-a, which makes zone-a:zone-b:zone-c = 3:3:4.
In this case, QHint from PodTopologySpread could return the labelselector for zone-a and zone-b.

But, the problem is that, then QHint has to know the current spreading situation (2:3:4) to return the label selector.
We currently have a internal policy where QHint shouldn’t look up resources other than the ones given from the QHint paramters (= QHint should only use pod, oldObj, and newObj to return results) so that we can prevent QHints to be too complicated and slow.
So, if we want to do this, we probably have to loosen this policy.

Those are why I don’t want to include the cross node scheduling constraints in the first step.
We should see if this idea is really worthy only with single node constraints first, and then we can discuss those stuff later.

### Concurrent scheduling cycles

In the long term, this enhancement could be a first step for the concurrent scheduling cycles, our dream.
As long as `NodeNames` is not overlapped, we can run the evaluations for multiple Pods concurrently since the scheduling results won't be conflict.