Repository: kubernetes
Issue: Replicaset scaling down takes inter-pods scheduling constraints into consideration
Labels: kind/design,sig/scheduling,sig/autoscaling,kind/feature,sig/apps,priority/important-longterm,needs-triage

/sig apps
/sig scheduling
/kind feature
/assign

Want to get feedback on this proposal. I can proceed to KEP process later, if it looks worthy for it to everyone.

## Summary

Refactor Replicaset scaling down implementation for better extendability,
and take Inter-pod scheduling constraints into account during scaling down.

## Motivation

When scaling down happens, the replicaset controller determines Pod(s) to remove based on starting time etc ([ref](https://github.com/kubernetes/kubernetes/blob/master/pkg/controller/controller_utils.go#L826  )), but not scheduling constraints.

Inter-Pod scheduling constraints (PodAffinity/PodTopologySpread) depend on other Pods’ placement, but they’re honored only at the scheduling time.
It’d be more awesome if we can, at least, keep spreading or affinity _to some extent_ during scaling down in a vanilla kubernetes, that is, without installing [descheduler](https://github.com/kubernetes-sigs/descheduler) etc. 
Actually, we’ve seen _many_ issues hoping this feature; the oldest one as far as I found is https://github.com/kubernetes/kubernetes/issues/4301!

## Goal

- Refactor the replicaset controller implementation around scaling down and make it easier to implement any scaling down behavior.
  - Introduce `ScaleDownScorePlugin`/`ScaleDownNormalizeScorePlugin` interface and each scaling down factor is implemented as a plugin.
- Take Inter-pod scheduling constraints into account during replicaset scaling down.
  - Inter-pod scheduling constraints are only PodAffinity and PodTopologySpread for now.

## Non Goal

This proposal doesn't mean -
- Always honor those scheduling constraints during scaling down.
  - It'll just be best-effort.
- Take ALL Pods in a cluster into consideration when calculating the best Pod to remove.
  - If we did that, it'd be huge calculation cost.
- Take custom plugins into consideration.
  - Technically, it'd be possible to allow custom `ScaleDownScorePlugin`/`ScaleDownNormalizeScorePlugin` from users, like the scheduling framework does. But, that's out-of-scope in this proposal.

(An elaborated explanation of these Non Goal: https://github.com/kubernetes/kubernetes/issues/124306#issuecomment-2054245124)

## Proposal

We’ll introduce a new interface named `ScaleDownScorePlugin`/`ScaleDownNormalizeScorePlugin`.

```go
type ScaleDownScorePlugin interface {
  // Score scores Pods; The higher score a Node gets, the more preferable to remove the Node, from this plugin’s pov.
  // candidatesToDelete is Pods from the replicaset, which the replicaset controller is scaling down.
  // relatedPods is all pods that are owned by any ReplicaSets that is owned by the ReplicaSet's owner.
  // ref: https://github.com/kubernetes/kubernetes/blob/master/pkg/controller/replicaset/replica_set.go#L796 
  //
  // Each plugin’s Score() is executed concurrently.
  Score(ctx context.Context, candidatesToDelete []*v1.Pod, relatedPods []*v1.Pod) ([]*PodWithScore, error)
}

type ScaleDownNormalizeScorePlugin interface {
  // NormalizeScore is called after all ScaleDownScorePlugin Score() are called. 
  // A successful run of NormalizeScore will update the scores list.
  // Each plugin's NormalizeScore() is executed one by one.
  // candidatesToDelete is the aggregated result from all Score plugins.
  NormalizeScore(ctx context.Context, candidatesToDelete []*PodWithScore) error
}

type PodWithScore struct {
  Pod *v1.Pod
  TotalScore int64
}
```

1. Calculate how many Pods should be removed in the same Replicaset.
2. Call `Score` of each plugin concurrently.
3. Call `NormalizeScore` of each plugin one by one.
4. Remove Pods with higher score.

### How each plugin is implemented

We’ll implement plugins for PodAffinity / PodTopologySpread ( / [existing logic](https://github.com/kubernetes/kubernetes/blob/master/pkg/controller/controller_utils.go#L826) to determine which Pods to delete).
 
Each implementation would be like the following:

#### PodAffinity

It'll be implemented as `ScaleDownScorePlugin`.
It gives a high score to candidate Pod if a Node that the candidate Pod is running on doesn’t have a Pod matching PodAffinity of the candidate Pod.
In order to lower the cost of calculation, it’s probably better to use the scheduler’s [snapshot](https://github.com/kubernetes/kubernetes/blob/cae35dba5a3060711a2a3f958537003bc74a59c0/pkg/scheduler/internal/cache/snapshot.go#L29) in the replicaset controller too.

#### PodTopologySpread

It'll be implemented as `ScaleDownNormalizeScorePlugin`.

1. Group relatedPods based on domain of topology spread
2. Calculate the total score of all Pods’ TotalScore in each domain.
3. Normalize the scores so that each domain’s total score would be similar. 

**Example:** 

Before PodTopologySpread `NormalizeScore()`:

| Domain-a (total: 600) | Domain-b (total: 300) | Domain-c (total: 3000) |
|:---:|:---:|:---:|
| PodA: 100 | PodD: 100 | PodG: 500 |
| PodB: 200 | PodE: 100 | PodH: 1000 |
| PodC: 300 | PodF: 100 | PodI: 1500 |


After PodTopologySpread `NormalizeScore()`:

| Domain-a (total: 300) | Domain-b (total: 300) | Domain-c (total: 300) |
|:---:|:---:|:---:|
| PodA: 50 | PodD: 100 | PodG: 50 |
| PodB: 100 | PodE: 100 | PodH: 100 |
| PodC: 150 | PodF: 100 | PodI: 150 |

Before PodTopologySpread, all Pods from Domain-c could be removed, but afterwards it’s not likely that all Pods from the same domain are removed. 

When actually implementing it, we can consider more; for example, in above case, if the controller is trying to remove 5 Pods, all Pods in domain-b could be removed at the same time. So, maybe we want to avoid "all Pods have the same score" after the normalization. (e.g., change to PodD:99 PodE:100 PodF:101)

#### Existing sorting logic

And also note that [existing logic](https://github.com/kubernetes/kubernetes/blob/master/pkg/controller/controller_utils.go#L826) to determine which Pod(s) to remove (starting time, deletion-cost, etc) can be also implemented as ScaleDownScorePlugin.

## Risk(Downside) and Mitigation

### Negative impact to throughput of replicaset controller

Scaling down would be slower than the current implementation because of an additional calculation.

I believe it's not the hard/critical requirement to keep the current throughput of scaling **down**.
But, also, given the controller has workers that are run concurrently and are shared between scaling up/scaling down processes, we cannot say there'd be zero impact on scaling up throughput. 

We have to make sure whether the throughput (both scale up and down) is really acceptable after the implementation change.

### Backwards compatibility

https://github.com/kubernetes/kubernetes/issues/124306#issuecomment-2077893254

> How will the new scores interact with pod-deletion-cost?

> What about backwards-compatibility? What if users are currently relying on the fact that the first Pod to be deleted is roughly the newest one?

If we just implement the proposal and make it the default behavior, we would break an existing scaling-down behavior.

If we concern about such breaking by this proposal, we can do, for example,

1. add a new field (or annotation) somewhere to make this behaviour non-default.
2. simplify PodTopologySpread's NormalizeScore() and make the scores returned from PodAffinity smaller than other existing algorithm's plugins.
    - simplify PodTopologySpread's NormalizeScore() > e.g., modify only scores of one Pod per domain so that at least one Pod will remain per domain.

I'd prefer (1). If we choose (2), the benefit from this proposal would be small.

## Alternative

Somehow use `controller.kubernetes.io/pod-deletion-cost`, but in anyways, we'd likely end up having to update Pods frequently and I didn't choose that way. 

> Users deploy controllers that update the annotation frequently causing a significant load on the api server. 
https://github.com/kubernetes/enhancements/tree/master/keps/sig-apps/2255-pod-cost#risks-and-mitigations

(An elaborated explanation why I didn't choose deletion-cost idea: https://github.com/kubernetes/kubernetes/issues/124306#issuecomment-2071237138)

## Reference

- [Current implementation of picking Pods when scaling down](https://github.com/kubernetes/kubernetes/blob/cae35dba5a3060711a2a3f958537003bc74a59c0/pkg/controller/replicaset/replica_set.go#L822-L832)