Repository: kubernetes
Issue: Priority-based preemption can easily violate PDBs even when unnecessary due to multiple issues with the implementation
Labels: kind/bug,sig/scheduling,lifecycle/frozen

<!-- Please use this template while reporting a bug and provide as much info as possible. Not doing so may result in your bug not being addressed in a timely manner. Thanks!

If the matter is security related, please disclose it privately via https://kubernetes.io/security/
-->


**What happened**:

A scale-up of a deployment with pods that were configured with a high priority resulted in the scheduler violating the PodDisruptionBudget of another workload, even though there were multiple other candidates for preemption whose PDBs still allowed for disruption.

**What you expected to happen**:

According to the [Pod Priority and Preemption](https://kubernetes.io/docs/concepts/configuration/pod-priority-preemption/#poddisruptionbudget-is-supported-but-not-guaranteed) documentation, the scheduler respects PDBs when evicting other pods and only violates them as a last resort.

**How to reproduce it (as minimally and precisely as possible)**:

It's a bit hard to reproduce, because the root cause seems to be a race condition between the scheduler and the PDB controller in controller-manager. The original incident happened in a cluster that had lots of pods and PDBs, and reproducing it in smaller clusters might take more time. It's easier to emulate a hiccup in the PDB controller by temporarily disabling it. Here's how I reproduce it:

1. Provision 3 nodes that will not have any other workloads. Autoscaling should also be disabled.
2. Deploy 2 victim deployments, corresponding PDBs and a deployment with 0 replicas that will trigger the eviction. You can use [this YAML](https://gist.github.com/aermakov-zalando/0d88251dd4b38c272a5db87ec8d0f449), but don't forget to update the node selector and resource requirements. You want to ensure that each of the 3 nodes will run one pod from `victim-a`, one pod from `victim-b` and that the evictor pod would not fit without kicking one of the existing pods out.
3. Wait until the pods are fully started and ready, and the PDBs are marked as allowing 1 disruption.
4. The bug requires the PDB controller to be slower than the scheduler, which is hard to reproduce, but you can certainly try. Scaling up the `evictor` deployment to 2 replicas should, according to the documentation, force an eviction of one pod from `victim-a` and one pod from `victim-b`, and this is what happens in practice most of the time. It might still be possible to reproduce with enough iterations (scale up to 2, check what was evicted, scale down to 0 if the bug is not triggered, try again).
5. To reproduce it more reliably, it's easier to emulate the hiccup. After both victim deployments are ready and the PDBs are updated, restart the controller-manager with `--controllers=*,-disruption`.
6. Scale up the `evictor` deployment to 2 pods again. There's a very high chance that you'll see that the scheduler has evicted two pods of one of the victim deployments while not touching the other. If this doesn't happen, scale down to 0 and try again.

**Anything else we need to know?**:

The root cause of the issue seems to be in how the scheduler implements eviction. The implementation unfortunately has multiple issues, resulting in the scheduler easily violating PDBs. That's not the case for normal eviction, which is implemented correctly.

Here's how normal pod eviction works:
 1. A user tries to create an `Eviction` for a given pod.
 2. The eviction API handler [checks](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/registry/core/pod/storage/eviction.go#L133) if the pod was already terminated.
 3. It then [checks](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/registry/core/pod/storage/eviction.go#L144) if there are multiple PDBs matching the same pod since this is not a supported configuration.
 4. It then runs [`checkAndDecrement`](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/registry/core/pod/storage/eviction.go#L207) in a loop:
    1. It updates the PDB to ensure that it operates on the latest state.
    2. It [fails](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/registry/core/pod/storage/eviction.go#L208) if the PDB hasn't been updated by the controller.
    3. It [fails](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/registry/core/pod/storage/eviction.go#L217) if the PDB doesn't allow for further disruptions. Note that this checks for pods that the PDB controller hasn't processed yet, see the next item.
    4. It records the name of the disrupted pod in the PDB's status and tries to update the PDB. If the update fails because someone else updated the PDB already, it then retries everything again, otherwise the eviction is considered successful, and the handler proceeds with deleting the pod. **This is the most important part**, because it ensures that even if the PDB controller is down, slow to react or otherwise unavailable, the disruption will be recorded in the PDB resource and further disruptions will be forbidden.

The scheduler implements this completely differently, though:
 1. A pod can't fit on any of the existing nodes, so the scheduler calls [`preempt`](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/scheduler/scheduler.go#L627) to try and free up some space (my IDE also shows that errors from it are ignored, but this is not relevant for the current issue).
 2. `preempt` calls `Algorithm.Preempt()` which returns the node where preemption should happen and the list of pods that should be preempted. This performs a bunch of checks and then [fetches](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/scheduler/core/generic_scheduler.go#L349) all PDBs from the cluster, expecting them to reflect the up-to-date state.
 3. It then [builds](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/scheduler/core/generic_scheduler.go#L1002) a list of candidate nodes, recording the number of PDB violations that eviction will cause on each. This is done by virtually evicting pods in order of priority first, and then trying to [reprieve](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/scheduler/core/generic_scheduler.go#L1160) pods whose eviction would violate the PDB. **Here's the first problem, however**: the scheduler doesn't consider its own evictions and only checks if the PDBs it fetched previously allow for at least one disruption. This means that if we have a PDB that currently allows one disruption, and the scheduler needs to evict two pods matched by this PDB, it'll consider that evicting both is a non-violating operation even though it's definitely not the case. **Second problem**: it also pays no attention to the PDB violations that haven't been applied yet by the PDB controller (those recorded in `pdb.status.disruptedPods`).
 4. After a candidate node is selected, the scheduler then proceeds with the eviction by simply [deleting the pod](https://github.com/kubernetes/kubernetes/blob/v1.17.5/pkg/scheduler/scheduler.go#L477), instead of using the eviction API.
 5. It then proceeds to the next unscheduled pod and runs the same algorithm again. **Third problem**: the whole logic described above assumes that after the pod was deleted in the previous step, the disruption controller has already reacted and updated the PDB status with the new number of allowed violations. This is not how distributed systems should be designed, because the disruption controller can be temporarily down, experience a hiccup (due to a GC pause or networking issues) or just be overloaded, preventing it from updating the PDB in time.

**Environment**:
- Kubernetes version (use `kubectl version`):

      Client Version: version.Info{Major:"1", Minor:"17", GitVersion:"v1.17.5", GitCommit:"e0fccafd69541e3750d460ba0f9743b90336f24f", GitTreeState:"clean", BuildDate:"2020-04-16T11:44:03Z", GoVersion:"go1.13.9", Compiler:"gc", Platform:"darwin/amd64"}
      Server Version: version.Info{Major:"1", Minor:"17", GitVersion:"v1.17.4", GitCommit:"8d8aa39598534325ad77120c120a22b3a990b5ea", GitTreeState:"clean", BuildDate:"2020-03-12T20:55:23Z", GoVersion:"go1.13.8", Compiler:"gc", Platform:"linux/amd64"}

- Cloud provider or hardware configuration: AWS
- OS (e.g: `cat /etc/os-release`): `Ubuntu 18.04.4 LTS`
- Kernel (e.g. `uname -a`): `Linux …4.15.0-1063-aws #67-Ubuntu SMP Mon Mar 2 07:24:29 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux`
- Install tools: custom, [kubernetes-on-aws](https://github.com/zalando-incubator/kubernetes-on-aws)