Repository: kubernetes-sigs/descheduler
Pull request #1033 (2023-01-04 07:16:03)

pod anti-affinity check among nodes
Current RemovePodsViolatingInterPodAntiAffinity policy implementation evicts pods violating Pod anti-affinity only on single Node. But in general context, violation of Pod anti-affinity is not limited to single Node.

This PullRequest(PR) changes to check violation of Pod anti-affinity not only on sigle node but among different nodes.


k8s-ci-robot: Welcome @10hin! <br><br>It looks like this is your first PR to <a href='https://github.com/kubernetes-sigs/descheduler'>kubernetes-sigs/descheduler</a> 🎉. Please refer to our [pull request process documentation](https://git.k8s.io/community/contributors/guide/pull-requests.md) to help your PR have a smooth ride to approval. <br><br>You will be prompted by a bot to use commands during the review process. Do not be afraid to follow the prompts! It is okay to experiment. [Here is the bot commands documentation](https://go.k8s.io/bot-commands). <br><br>You can also check if kubernetes-sigs/descheduler has [its own contribution guidelines](https://github.com/kubernetes-sigs/descheduler/tree/master/CONTRIBUTING.md). <br><br>You may want to refer to our [testing guide](https://git.k8s.io/community/contributors/devel/sig-testing/testing.md) if you run into trouble with your tests not passing. <br><br>If you are having difficulty getting your pull request seen, please follow the [recommended escalation practices](https://github.com/kubernetes/community/blob/master/contributors/guide/pull-requests.md#why-is-my-pull-request-not-getting-reviewed). Also, for tips and tricks in the contribution process you may want to read the [Kubernetes contributor cheat sheet](https://git.k8s.io/community/contributors/guide/contributor-cheatsheet/README.md). We want to make sure your contribution gets all the attention it needs! <br><br>Thank you, and welcome to Kubernetes. :smiley:
k8s-ci-robot: Hi @10hin. Thanks for your PR.

I'm waiting for a [kubernetes-sigs](https://github.com/orgs/kubernetes-sigs/people) member to verify that this patch is reasonable to test. If it is, they should reply with `/ok-to-test` on its own line. Until that is done, I will not automatically test new commits in this PR, but the usual testing commands by org members will still work. Regular contributors should [join the org](https://git.k8s.io/community/community-membership.md#member) to skip this step.

Once the patch is verified, the new status will be reflected by the `ok-to-test` label.

I understand the commands that are listed [here](https://go.k8s.io/bot-commands?repo=kubernetes-sigs%2Fdescheduler).

<details>

Instructions for interacting with me using PR comments are available [here](https://git.k8s.io/community/contributors/guide/pull-requests.md).  If you have questions or suggestions related to my behavior, please file an issue against the [kubernetes/test-infra](https://github.com/kubernetes/test-infra/issues/new?title=Prow%20issue:) repository.
</details>

k8s-ci-robot: [APPROVALNOTIFIER] This PR is **NOT APPROVED**

This pull-request has been approved by:
**Once this PR has been reviewed and has the lgtm label**, please assign ingvagabund for approval by writing `/assign @ingvagabund` in a comment. For more information see [the Kubernetes Code Review Process](https://git.k8s.io/community/contributors/guide/owners.md#the-code-review-process).

The full list of commands accepted by this bot can be found [here](https://go.k8s.io/bot-commands?repo=kubernetes-sigs%2Fdescheduler).

<details open>
Needs approval from an approver in each of these files:

- **[OWNERS](https://github.com/kubernetes-sigs/descheduler/blob/master/OWNERS)**

Approvers can indicate their approval by writing `/approve` in a comment
Approvers can cancel approval by writing `/approve cancel` in a comment
</details>
<!-- META={"approvers":["ingvagabund"]} -->
k8s-ci-robot: [APPROVALNOTIFIER] This PR is **NOT APPROVED**

This pull-request has been approved by:
**Once this PR has been reviewed and has the lgtm label**, please assign ingvagabund for approval. For more information see [the Kubernetes Code Review Process](https://git.k8s.io/community/contributors/guide/owners.md#the-code-review-process).

The full list of commands accepted by this bot can be found [here](https://go.k8s.io/bot-commands?repo=kubernetes-sigs%2Fdescheduler).

<details open>
Needs approval from an approver in each of these files:

- **[OWNERS](https://github.com/kubernetes-sigs/descheduler/blob/master/OWNERS)**

Approvers can indicate their approval by writing `/approve` in a comment
Approvers can cancel approval by writing `/approve cancel` in a comment
</details>
<!-- META={"approvers":["ingvagabund"]} -->
k8s-ci-robot: PR needs rebase.

<details>

Instructions for interacting with me using PR comments are available [here](https://git.k8s.io/community/contributors/guide/pull-requests.md).  If you have questions or suggestions related to my behavior, please file an issue against the [kubernetes/test-infra](https://github.com/kubernetes/test-infra/issues/new?title=Prow%20issue:) repository.
</details>
k8s-ci-robot: @10hin: The following test **failed**, say `/retest` to rerun all failed tests or `/retest-required` to rerun all mandatory failed tests:

Test name | Commit | Details | Required | Rerun command
--- | --- | --- | --- | ---
pull-descheduler-test-e2e-k8s-master-1-27 | f964b418f60505ea0347cb17a541a5d72146faed | [link](https://prow.k8s.io/view/gs/kubernetes-jenkins/pr-logs/pull/kubernetes-sigs_descheduler/1033/pull-descheduler-test-e2e-k8s-master-1-27/1646048020820660224) | true | `/test pull-descheduler-test-e2e-k8s-master-1-27`

[Full PR test history](https://prow.k8s.io/pr-history?org=kubernetes-sigs&repo=descheduler&pr=1033). [Your PR dashboard](https://prow.k8s.io/pr?query=is%3Apr%20state%3Aopen%20author%3A10hin). Please help us cut down on flakes by [linking to](https://git.k8s.io/community/contributors/devel/sig-testing/flaky-tests.md#filing-issues-for-flaky-tests) an [open issue](https://github.com/kubernetes-sigs/descheduler/issues?q=is:issue+is:open) when you hit one in your PR.

<details>

Instructions for interacting with me using PR comments are available [here](https://git.k8s.io/community/contributors/guide/pull-requests.md).  If you have questions or suggestions related to my behavior, please file an issue against the [kubernetes/test-infra](https://github.com/kubernetes/test-infra/issues/new?title=Prow%20issue:) repository. I understand the commands that are listed [here](https://go.k8s.io/bot-commands).
</details>
<!-- test report -->
k8s-ci-robot: @10hin: The following tests **failed**, say `/retest` to rerun all failed tests or `/retest-required` to rerun all mandatory failed tests:

Test name | Commit | Details | Required | Rerun command
--- | --- | --- | --- | ---
pull-descheduler-test-e2e-k8s-master-1-27 | f964b418f60505ea0347cb17a541a5d72146faed | [link](https://prow.k8s.io/view/gs/kubernetes-jenkins/pr-logs/pull/kubernetes-sigs_descheduler/1033/pull-descheduler-test-e2e-k8s-master-1-27/1646048020820660224) | true | `/test pull-descheduler-test-e2e-k8s-master-1-27`
pull-descheduler-verify-master | db00e963efbc2c6ae00f60952dc61553a534ed6a | [link](https://prow.k8s.io/view/gs/kubernetes-jenkins/pr-logs/pull/kubernetes-sigs_descheduler/1033/pull-descheduler-verify-master/1663857057335349248) | true | `/test pull-descheduler-verify-master`

[Full PR test history](https://prow.k8s.io/pr-history?org=kubernetes-sigs&repo=descheduler&pr=1033). [Your PR dashboard](https://prow.k8s.io/pr?query=is%3Apr%20state%3Aopen%20author%3A10hin). Please help us cut down on flakes by [linking to](https://git.k8s.io/community/contributors/devel/sig-testing/flaky-tests.md#filing-issues-for-flaky-tests) an [open issue](https://github.com/kubernetes-sigs/descheduler/issues?q=is:issue+is:open) when you hit one in your PR.

<details>

Instructions for interacting with me using PR comments are available [here](https://git.k8s.io/community/contributors/guide/pull-requests.md).  If you have questions or suggestions related to my behavior, please file an issue against the [kubernetes/test-infra](https://github.com/kubernetes/test-infra/issues/new?title=Prow%20issue:) repository. I understand the commands that are listed [here](https://go.k8s.io/bot-commands).
</details>
<!-- test report -->
knelasevero: /lgtm
10hin: @damemi @knelasevero 
Thank you for your reviews and actions.
I'm sorry if I am wrong, but, because CI status looks wait only for adding `approved` label (see attached image), is @damemi  forgetting it? Or just wait for something?
If there are anything I can do in this PR, please tell me.

<img width="607" alt="image" src="https://github.com/kubernetes-sigs/descheduler/assets/26009549/a7abc6ef-a8eb-4a1e-a144-26277201fcd1">

k8s-ci-robot: [APPROVALNOTIFIER] This PR is **APPROVED**

This pull-request has been approved by: *<a href="https://github.com/kubernetes-sigs/descheduler/pull/1033#pullrequestreview-1462405686" title="Approved">damemi</a>*

The full list of commands accepted by this bot can be found [here](https://go.k8s.io/bot-commands?repo=kubernetes-sigs%2Fdescheduler).

The pull request process is described [here](https://git.k8s.io/community/contributors/guide/owners.md#the-code-review-process)

<details >
Needs approval from an approver in each of these files:

- ~~[OWNERS](https://github.com/kubernetes-sigs/descheduler/blob/master/OWNERS)~~ [damemi]

Approvers can indicate their approval by writing `/approve` in a comment
Approvers can cancel approval by writing `/approve cancel` in a comment
</details>
<!-- META={"approvers":[]} -->

Patch:
diff --git a/pkg/framework/plugins/removepodsviolatinginterpodantiaffinity/pod_antiaffinity.go b/pkg/framework/plugins/removepodsviolatinginterpodantiaffinity/pod_antiaffinity.go
index 85d1738f8..1284ecbce 100644
--- a/pkg/framework/plugins/removepodsviolatinginterpodantiaffinity/pod_antiaffinity.go
+++ b/pkg/framework/plugins/removepodsviolatinginterpodantiaffinity/pod_antiaffinity.go
@@ -78,24 +78,36 @@ func (d *RemovePodsViolatingInterPodAntiAffinity) Name() string {
 }
 
 func (d *RemovePodsViolatingInterPodAntiAffinity) Deschedule(ctx context.Context, nodes []*v1.Node) *frameworktypes.Status {
+	podsList, err := d.handle.ClientSet().CoreV1().Pods("").List(ctx, metav1.ListOptions{})
+	if err != nil {
+		return &frameworktypes.Status{
+			Err: fmt.Errorf("error listing all pods: %v", err),
+		}
+	}
+
+	podsInANamespace := groupByNamespace(podsList)
+
+	runningPodFilter := func(pod *v1.Pod) bool {
+		return pod.Status.Phase != v1.PodSucceeded && pod.Status.Phase != v1.PodFailed
+	}
+	podsOnANode := groupByNodeName(podsList, podutil.WrapFilterFuncs(runningPodFilter, d.podFilter))
+
+	nodeMap := createNodeMap(nodes)
+
 loop:
 	for _, node := range nodes {
 		klog.V(1).InfoS("Processing node", "node", klog.KObj(node))
-		pods, err := podutil.ListPodsOnANode(node.Name, d.handle.GetPodsAssignedToNodeFunc(), d.podFilter)
-		if err != nil {
-			return &frameworktypes.Status{
-				Err: fmt.Errorf("error listing pods: %v", err),
-			}
-		}
-		// sort the evictable Pods based on priority, if there are multiple pods with same priority, they are sorted based on QoS tiers.
+		pods := podsOnANode[node.Name]
+		// sort the evict-able Pods based on priority, if there are multiple pods with same priority, they are sorted based on QoS tiers.
 		podutil.SortPodsBasedOnPriorityLowToHigh(pods)
 		totalPods := len(pods)
 		for i := 0; i < totalPods; i++ {
-			if checkPodsWithAntiAffinityExist(pods[i], pods) && d.handle.Evictor().Filter(pods[i]) && d.handle.Evictor().PreEvictionFilter(pods[i]) {
+			if checkPodsWithAntiAffinityExist(pods[i], podsInANamespace, nodeMap) && d.handle.Evictor().Filter(pods[i]) && d.handle.Evictor().PreEvictionFilter(pods[i]) {
 				if d.handle.Evictor().Evict(ctx, pods[i], evictions.EvictOptions{}) {
 					// Since the current pod is evicted all other pods which have anti-affinity with this
 					// pod need not be evicted.
-					// Update pods.
+					// Update allPods.
+					podsInANamespace = removePodFromNamespaceMap(pods[i], podsInANamespace)
 					pods = append(pods[:i], pods[i+1:]...)
 					i--
 					totalPods--
@@ -109,8 +121,54 @@ loop:
 	return nil
 }
 
+func removePodFromNamespaceMap(podToRemove *v1.Pod, podMap map[string][]*v1.Pod) map[string][]*v1.Pod {
+	podList, ok := podMap[podToRemove.Namespace]
+	if !ok {
+		return podMap
+	}
+	for i := 0; i < len(podList); i++ {
+		podToCheck := podList[i]
+		if podToRemove.Name == podToCheck.Name {
+			podMap[podToRemove.Namespace] = append(podList[:i], podList[i+1:]...)
+			return podMap
+		}
+	}
+	return podMap
+}
+
+func groupByNamespace(pods *v1.PodList) map[string][]*v1.Pod {
+	m := make(map[string][]*v1.Pod)
+	for i := 0; i < len(pods.Items); i++ {
+		pod := &(pods.Items[i])
+		m[pod.Namespace] = append(m[pod.Namespace], pod)
+	}
+	return m
+}
+
+func groupByNodeName(pods *v1.PodList, filter podutil.FilterFunc) map[string][]*v1.Pod {
+	m := make(map[string][]*v1.Pod)
+	if filter == nil {
+		filter = func(p *v1.Pod) bool { return true }
+	}
+	for i := 0; i < len(pods.Items); i++ {
+		pod := &(pods.Items[i])
+		if filter(pod) {
+			m[pod.Spec.NodeName] = append(m[pod.Spec.NodeName], pod)
+		}
+	}
+	return m
+}
+
+func createNodeMap(nodes []*v1.Node) map[string]*v1.Node {
+	m := make(map[string]*v1.Node, len(nodes))
+	for _, node := range nodes {
+		m[node.GetName()] = node
+	}
+	return m
+}
+
 // checkPodsWithAntiAffinityExist checks if there are other pods on the node that the current pod cannot tolerate.
-func checkPodsWithAntiAffinityExist(pod *v1.Pod, pods []*v1.Pod) bool {
+func checkPodsWithAntiAffinityExist(pod *v1.Pod, pods map[string][]*v1.Pod, nodeMap map[string]*v1.Node) bool {
 	affinity := pod.Spec.Affinity
 	if affinity != nil && affinity.PodAntiAffinity != nil {
 		for _, term := range getPodAntiAffinityTerms(affinity.PodAntiAffinity) {
@@ -120,9 +178,22 @@ func checkPodsWithAntiAffinityExist(pod *v1.Pod, pods []*v1.Pod) bool {
 				klog.ErrorS(err, "Unable to convert LabelSelector into Selector")
 				return false
 			}
-			for _, existingPod := range pods {
-				if existingPod.Name != pod.Name && utils.PodMatchesTermsNamespaceAndSelector(existingPod, namespaces, selector) {
-					return true
+			for namespace := range namespaces {
+				for _, existingPod := range pods[namespace] {
+					if existingPod.Name != pod.Name && utils.PodMatchesTermsNamespaceAndSelector(existingPod, namespaces, selector) {
+						node, ok := nodeMap[pod.Spec.NodeName]
+						if !ok {
+							continue
+						}
+						nodeHavingExistingPod, ok := nodeMap[existingPod.Spec.NodeName]
+						if !ok {
+							continue
+						}
+						if hasSameLabelValue(node, nodeHavingExistingPod, term.TopologyKey) {
+							klog.V(1).InfoS("Found Pods violating PodAntiAffinity", "pod to evicted", klog.KObj(pod))
+							return true
+						}
+					}
 				}
 			}
 		}
@@ -130,6 +201,29 @@ func checkPodsWithAntiAffinityExist(pod *v1.Pod, pods []*v1.Pod) bool {
 	return false
 }
 
+func hasSameLabelValue(node1, node2 *v1.Node, key string) bool {
+	if node1.Name == node2.Name {
+		return true
+	}
+	node1Labels := node1.Labels
+	if node1Labels == nil {
+		return false
+	}
+	node2Labels := node2.Labels
+	if node2Labels == nil {
+		return false
+	}
+	value1, ok := node1Labels[key]
+	if !ok {
+		return false
+	}
+	value2, ok := node2Labels[key]
+	if !ok {
+		return false
+	}
+	return value1 == value2
+}
+
 // getPodAntiAffinityTerms gets the antiaffinity terms for the given pod.
 func getPodAntiAffinityTerms(podAntiAffinity *v1.PodAntiAffinity) (terms []v1.PodAffinityTerm) {
 	if podAntiAffinity != nil {


Test patch:
diff --git a/pkg/framework/plugins/removepodsviolatinginterpodantiaffinity/pod_antiaffinity_test.go b/pkg/framework/plugins/removepodsviolatinginterpodantiaffinity/pod_antiaffinity_test.go
index c46e761f2..9da0dc6b1 100644
--- a/pkg/framework/plugins/removepodsviolatinginterpodantiaffinity/pod_antiaffinity_test.go
+++ b/pkg/framework/plugins/removepodsviolatinginterpodantiaffinity/pod_antiaffinity_test.go
@@ -38,19 +38,27 @@ import (
 )
 
 func TestPodAntiAffinity(t *testing.T) {
-	node1 := test.BuildTestNode("n1", 2000, 3000, 10, nil)
+	node1 := test.BuildTestNode("n1", 2000, 3000, 10, func(node *v1.Node) {
+		node.ObjectMeta.Labels = map[string]string{
+			"region": "main-region",
+		}
+	})
 	node2 := test.BuildTestNode("n2", 2000, 3000, 10, func(node *v1.Node) {
 		node.ObjectMeta.Labels = map[string]string{
 			"datacenter": "east",
 		}
 	})
-
 	node3 := test.BuildTestNode("n3", 2000, 3000, 10, func(node *v1.Node) {
 		node.Spec = v1.NodeSpec{
 			Unschedulable: true,
 		}
 	})
 	node4 := test.BuildTestNode("n4", 2, 2, 1, nil)
+	node5 := test.BuildTestNode("n5", 200, 3000, 10, func(node *v1.Node) {
+		node.ObjectMeta.Labels = map[string]string{
+			"region": "main-region",
+		}
+	})
 
 	p1 := test.BuildTestPod("p1", 100, 0, node1.Name, nil)
 	p2 := test.BuildTestPod("p2", 100, 0, node1.Name, nil)
@@ -62,6 +70,7 @@ func TestPodAntiAffinity(t *testing.T) {
 	p8 := test.BuildTestPod("p8", 100, 0, node1.Name, nil)
 	p9 := test.BuildTestPod("p9", 100, 0, node1.Name, nil)
 	p10 := test.BuildTestPod("p10", 100, 0, node1.Name, nil)
+	p11 := test.BuildTestPod("p11", 100, 0, node5.Name, nil)
 	p9.DeletionTimestamp = &metav1.Time{}
 	p10.DeletionTimestamp = &metav1.Time{}
 
@@ -73,6 +82,7 @@ func TestPodAntiAffinity(t *testing.T) {
 	p5.Labels = map[string]string{"foo": "bar"}
 	p6.Labels = map[string]string{"foo": "bar"}
 	p7.Labels = map[string]string{"foo1": "bar1"}
+	p11.Labels = map[string]string{"foo": "bar"}
 	nonEvictablePod.Labels = map[string]string{"foo": "bar"}
 	test.SetNormalOwnerRef(p1)
 	test.SetNormalOwnerRef(p2)
@@ -83,6 +93,7 @@ func TestPodAntiAffinity(t *testing.T) {
 	test.SetNormalOwnerRef(p7)
 	test.SetNormalOwnerRef(p9)
 	test.SetNormalOwnerRef(p10)
+	test.SetNormalOwnerRef(p11)
 
 	// set pod anti affinity
 	setPodAntiAffinity(p1, "foo", "bar")
@@ -186,6 +197,13 @@ func TestPodAntiAffinity(t *testing.T) {
 			expectedEvictedPodCount: 0,
 			nodeFit:                 true,
 		},
+		{
+			description:             "Evict pod violating anti-affinity among different node (all pods have anti-affinity)",
+			pods:                    []*v1.Pod{p1, p11},
+			nodes:                   []*v1.Node{node1, node5},
+			expectedEvictedPodCount: 1,
+			nodeFit:                 false,
+		},
 	}
 
 	for _, test := range tests {