Repository: kubernetes
Issue: scheduler plugin podTopologySpread performs not well enough in a disaster recovery scenario
Labels: kind/bug,sig/scheduling,needs-triage

### What happened?

I ran a disaster recovery scenario with 2000 kwok fake nodes, 100,000 pending pods recently.

Each pod has topologySpreadConstraints specified as below
`
                "topologySpreadConstraints": [
                    {
                        "labelSelector": {
                            "matchLabels": {
                                "app": "fake-pod"
                            }
                        },
                        "maxSkew": 1,
                        "topologyKey": "topology.kubernetes.io/region", 
                        "whenUnsatisfiable": "ScheduleAnyway"
                    },
                    {
                        "labelSelector": {
                            "matchLabels": {
                                "app": "fake-pod"
                            }
                        },
                        "maxSkew": 1,
                        "topologyKey": "kubernetes.io/hostname",
                        "whenUnsatisfiable": "ScheduleAnyway"
                    }
                ]
`

The overall performance of kube-scheduler degrades as the number of pods on each node increases.
![scheduler_attempts](https://github.com/user-attachments/assets/236aa4f0-2534-40af-8780-a40bd5f5a377)

As I digged further with pprof ,  the most time-consuming process was found in podTopologySpead, within the PreScore stage, in below 2 functions:
- countPodsMatchSelector  
- PodMatchesNodeSelectorAndAffinityTerms
![scheduler_pprof](https://github.com/user-attachments/assets/00d57008-172c-4469-b39e-bc3e4983144a)



 


### What did you expect to happen?

rate(scheduler_schedule_attempts_total[1m]) should keep steady during the test run

### How can we reproduce it (as minimally and precisely as possible)?

1. Create a cluster with 2000 nodes, stop kube-scheduler first
2. Create a deployment with 100,000 replicas,  topologySpreadConstraints described as above
3. Start kube-scheduler and watch the deployment status and kube-scheduler metrics, until all pods are scheduled

### Anything else we need to know?

countPodsMatchSelector is also called in Score stage. It can be a good starting point to boost overall performance.

In most scenarios, pod has an owner (rs/dp/ds/sts etc),  and topologySpread is applied to all pods with the same owner.

So based on the above theory, this can be optimized to an O(1) procedure, after we apply some tricks on it:

- add a cache (map[UID][]*PodInfo) in nodeInfo, indexed by the pod's owner Id
- the cache will be updated with the Add/Update/Del callback of pod informer
- in countPodsMatchSelector
   * If the pod has an owner, we use owner's Id to find the pre-aggregated count.
   * If it doesn't, fallback to the old ways.

Any comments are welcomed. 

If this is feasible without defects, I can try to create a PR for this. 

The improvement can be (in a same test baseline):
- 100,000 pod scheduled total time:  drops from 7min30s to 4min
- rate(scheduler_schedule_attempts_total[1m]) keeps steady above 420 compared to an avg of 220
![image](https://github.com/user-attachments/assets/3eaf43d5-6bc8-47d5-8603-dab22dc65689)




### Kubernetes version

1.20.7 but also applies to the lastest release

### Cloud provider

not specific to any cloud provider

### OS version

not specific to any os version

### Install tools

<details>

</details>


### Container runtime (CRI) and version (if applicable)

<details>

</details>


### Related plugins (CNI, CSI, ...) and versions (if applicable)

<details>

</details>