Repository: kubernetes
Issue: Preemption picks wrong victim node with higher priority pod on it after #128307
Labels: kind/bug,sig/scheduling,needs-triage

### What happened?

related: #128307

After #128307 has been merged, preemption logic picks wrong victim node with higher priority pod on it.
In the following situation, `high` pod on `worker1` not `mid` on `worker2` is evicted when `very-high` pod(Priority=10000) attempts to schedule.

- `worker1`
  - `high` pod(Priority=1000)
  - `low` pod(Priority=0, preempting it will violate PDB)
- `worker2`
    - `mid` pod(Priority=100, preempting it will violate PDB)

### What did you expect to happen?

According to here, `mid` pod on `worker2` seems to be picked as a victim.

https://github.com/kubernetes/kubernetes/blob/1148e5ee5fd95117db6c2fb92194272df574cc38/pkg/scheduler/framework/preemption/preemption.go#L411-L424

### How can we reproduce it (as minimally and precisely as possible)?

We can reproduce it by the following steps using kind.

Preparation
<details>

Use kind.
```bash
$ kind version
kind v0.25.0 go1.22.9 linux/amd64
```

Build Node image of v1.31.3.
```bash
$ kind build node-image v1.31.3 --image ndest/node:1.31.3-build
```

Prepare kind cluster config and create cluster.

`kind-config-1.31.3.yaml`
```yaml
kind: Cluster
apiVersion: "kind.x-k8s.io/v1alpha4"
name: kind-v1.31.3
nodes:
- role: control-plane
  image: ndest/node:1.31.3-build
- role: worker
  image: ndest/node:1.31.3-build
- role: worker
  image: ndest/node:1.31.3-build
```

```bash
$ kind create cluster --config kind-config-1.31.3.yaml

$ kubectl get no
NAME                         STATUS   ROLES           AGE   VERSION
kind-v1.31.3-control-plane   Ready    control-plane   33s   v1.31.3
kind-v1.31.3-worker          Ready    <none>          18s   v1.31.3
kind-v1.31.3-worker2         Ready    <none>          18s   v1.31.3
```

Add PriorityClass to DaemonSet/kindnet to prevent it from being preempted.
```bash
$ kubectl -n kube-system patch ds kindnet --patch '{"spec": {"template": {"spec": {"priorityClassName": "system-node-critical"}}}}'
```

Modify `maxPods` of `kubelet` config on `worker` and `worker2` to trigger preemption.
```bash
# worker
$ docker exec -it kind-v1.31.3-worker /bin/bash
root@kind-v1:/# echo "maxPods: 4" >> /var/lib/kubelet/config.yaml
root@kind-v1:/# systemctl restart kubelet
root@kind-v1:/# exit

# worker2
$ docker exec -it kind-v1.31.3-worker2 /bin/bash
root@kind-v1:/# echo "maxPods: 3" >> /var/lib/kubelet/config.yaml
root@kind-v1:/# systemctl restart kubelet
root@kind-v1:/# exit
```

Now, we can schedule 2 pods on `worker` and 1 pod on `worker2`.
```bash
$ k get no -A -o='custom-columns=NAME:.metadata.name,MAXPOD:.status.capacity.pods,VERSION:.status.nodeInfo.kubeletVersion'
NAME                         MAXPOD   VERSION
kind-v1.31.3-control-plane   110      v1.31.3
kind-v1.31.3-worker          4        v1.31.3
kind-v1.31.3-worker2         3        v1.31.3

$ k get po -A -owide | grep -w kind-v1.31.3-worker | wc -l
2
$ k get po -A -owide | grep -w kind-v1.31.3-worker2 | wc -l
2
```

</details>

Create `PriorityClass`, `PodDisruptionBudget`, and `Pod`.
Applying these manifests, we can see the following situation.

<details>

`high-priority.yaml`
```yaml
apiVersion: scheduling.k8s.io/v1
kind: PriorityClass
metadata:
  name: high-priority
value: 1000
globalDefault: false
description: "This priority class should be used for high priority pods."
```

`high.yaml`
```yaml
apiVersion: v1
kind: Pod
metadata:
  name: high
  labels:
    app: high
spec:
  containers:
  - name: nginx
    image: nginx
  priorityClassName: high-priority
  nodeSelector:
    kubernetes.io/hostname: kind-v1.31.3-worker
```

`mid-priority.yaml`
```yaml
apiVersion: scheduling.k8s.io/v1
kind: PriorityClass
metadata:
  name: mid-priority
value: 100
globalDefault: false
description: "This priority class should be used for mid priority pods."
```

`mid.yaml`
```yaml
apiVersion: v1
kind: Pod
metadata:
  name: mid
  labels:
    app: mid
spec:
  containers:
  - name: nginx
    image: nginx
  priorityClassName: mid-priority
  nodeSelector:
    kubernetes.io/hostname: kind-v1.31.3-worker2
```

`low-priority.yaml`
```yaml
apiVersion: scheduling.k8s.io/v1
kind: PriorityClass
metadata:
  name: low-priority
value: 0
globalDefault: false
description: "This priority class should be used for low priority pods."
```

`low.yaml`
```yaml
apiVersion: v1
kind: Pod
metadata:
  name: low
  labels:
    app: low
spec:
  containers:
  - name: nginx
    image: nginx
  priorityClassName: low-priority
  nodeSelector:
    kubernetes.io/hostname: kind-v1.31.3-worker
```


`mid-pdb.yaml`
```yaml
apiVersion: policy/v1
kind: PodDisruptionBudget
metadata:
  name: mid-pdb
spec:
  minAvailable: 1
  selector:
    matchLabels:
      app: mid
```

`low-pdb.yaml`
```yaml
apiVersion: policy/v1
kind: PodDisruptionBudget
metadata:
  name: mid-pdb
spec:
  minAvailable: 1
  selector:
    matchLabels:
      app: mid
```

`very-high-priority.yaml`
```yaml
apiVersion: scheduling.k8s.io/v1
kind: PriorityClass
metadata:
  name: very-high-priority
value: 10000
globalDefault: false
description: "This priority class should be used for very high priority pods."
```

</details>

`worker` and `worker2` habe reached their `maxPods` limit and evicting `low` or `mid` pod violates PDB.
```bash
$ k get po -o='custom-columns=NAME:.metadata.name,STATUS:.status.phase,PRIORITY:.spec.priority,NODE:.spec.nodeName'
NAME   STATUS    PRIORITY   NODE
high   Running   1000       kind-v1.31.3-worker
low    Running   0          kind-v1.31.3-worker
mid    Running   100        kind-v1.31.3-worker2

$ k get priorityclasses
NAME                      VALUE        GLOBAL-DEFAULT   AGE
high-priority             1000         false            26s
low-priority              0            false            26s
mid-priority              100          false            26s
system-cluster-critical   2000000000   false            17m
system-node-critical      2000001000   false            17m
very-high-priority        10000        false            26s

$ k get pdb
NAME      MIN AVAILABLE   MAX UNAVAILABLE   ALLOWED DISRUPTIONS   AGE
low-pdb   1               N/A               0                     47s
mid-pdb   1               N/A               0                     47s

$ k get po -A -owide | grep -w kind-v1.31.3-worker | wc -l
4
ubuntu-user@ubuntu-server01 ~/work/kubernetes/preemption $ k get po -A -owide | grep -w kind-v1.31.3-worker2 | wc -l
3
```


Now, attempt to schedule `very-high` pod.

`very-high.yaml`
```yaml
apiVersion: v1
kind: Pod
metadata:
  name: very-high
  labels:
    app: very-high
spec:
  containers:
  - name: nginx
    image: nginx
  priorityClassName: very-high-priority
```

```bash
$ k apply -f very-high.yaml
```

We can see that `high` pod on `worker` is evicted instead of `mid` pod on `worker2`.
```bash
$ k get po -owide -w
NAME   READY   STATUS    RESTARTS   AGE   IP           NODE                   NOMINATED NODE   READINESS GATES
high   1/1     Running   0          6m    10.244.1.2   kind-v1.31.3-worker    <none>           <none>
low    1/1     Running   0          6m    10.244.1.3   kind-v1.31.3-worker    <none>           <none>
mid    1/1     Running   0          6m    10.244.2.2   kind-v1.31.3-worker2   <none>           <none>


very-high   0/1     Pending   0          0s    <none>       <none>                 <none>           <none>
high        1/1     Running   0          6m9s   10.244.1.2   kind-v1.31.3-worker    <none>           <none>
high        1/1     Terminating   0          6m9s   10.244.1.2   kind-v1.31.3-worker    <none>           <none>
very-high   0/1     Pending       0          0s     <none>       <none>                 kind-v1.31.3-worker   <none>
high        1/1     Terminating   0          6m9s   10.244.1.2   kind-v1.31.3-worker    <none>                <none>
high        0/1     Completed     0          6m9s   10.244.1.2   kind-v1.31.3-worker    <none>                <none>
high        0/1     Completed     0          6m10s   10.244.1.2   kind-v1.31.3-worker    <none>                <none>
high        0/1     Completed     0          6m10s   10.244.1.2   kind-v1.31.3-worker    <none>                <none>
very-high   0/1     Pending       0          2s      <none>       kind-v1.31.3-worker    kind-v1.31.3-worker   <none>
very-high   0/1     ContainerCreating   0          2s      <none>       kind-v1.31.3-worker    <none>                <none>
very-high   1/1     Running             0          3s      10.244.1.4   kind-v1.31.3-worker    <none>                <none>

$ k get po -owide
NAME        READY   STATUS    RESTARTS   AGE     IP           NODE                   NOMINATED NODE   READINESS GATES
low         1/1     Running   0          7m23s   10.244.1.3   kind-v1.31.3-worker    <none>           <none>
mid         1/1     Running   0          7m23s   10.244.2.2   kind-v1.31.3-worker2   <none>           <none>
very-high   1/1     Running   0          74s     10.244.1.4   kind-v1.31.3-worker    <none>           <none>
```

### Anything else we need to know?

_No response_

### Kubernetes version

<details>

```console
$ kubectl version
Client Version: v1.31.0
Kustomize Version: v5.4.2
Server Version: v1.31.3
```

</details>

### Cloud provider

<details>
none
</details>

### OS version

<details>

```console
# On Linux:
$ cat /etc/os-release
# paste output here
$ uname -a
# paste output here

# On Windows:
C:\> wmic os get Caption, Version, BuildNumber, OSArchitecture
# paste output here
```

</details>


### Install tools

<details>

</details>


### Container runtime (CRI) and version (if applicable)

<details>
$ kind version
kind v0.25.0 go1.22.9 linux/amd64

</details>


### Related plugins (CNI, CSI, ...) and versions (if applicable)

<details>

</details>