Repository: kubernetes/kubernetes (language: go)

Issue:
Filter gated pods before calling isPodWorthRequeueing
#### What type of PR is this?

/kind bug

#### What this PR does / why we need it:
When there are many gated pods and many events which trigger requeueing from the unschedulable pool (e.g. [deletePodFromCache](https://github.com/kubernetes/kubernetes/blob/72524fa574c58e08a5e1f3334aad7c8a8889d5a0/pkg/scheduler/eventhandlers.go#L254)) , we observe increased scheduling latency. We mitigate this issue by exiting before hitting the hotspots identified in #124384.

#### Which issue(s) this PR fixes:
Fixes #124384

/sig scheduling
#### Special notes for your reviewer:

#### Does this PR introduce a user-facing change?
<!--
If no, just write "NONE" in the release-note block below.
If yes, a release note is required:
Enter your extended release note in the block below. If the PR requires additional action from users switching to the new release, include the string "action required".

For more information on release notes see: https://git.k8s.io/community/contributors/guide/release-notes.md
-->
```release-note
Improved scheduling latency when many gated pods
```

#### Additional documentation e.g., KEPs (Kubernetes Enhancement Proposals), usage docs, etc.:

<!--
This section can be blank if this pull request does not require a release note.

When adding links which point to resources within git repositories, like
KEPs or supporting documentation, please reference a specific commit and avoid
linking directly to the master branch. This ensures that links reference a
specific point in time, rather than a document that may change over time.

See here for guidance on getting permanent links to files: https://help.github.com/en/articles/getting-permanent-links-to-files

Please use the following format for linking documentation:
- [KEP]: <link>
- [Usage]: <link>
- [Other doc]: <link>
-->
```docs

```



Discussion / hints:
This issue is currently awaiting triage.

If a SIG or subproject determines this is a relevant issue, they will accept it by applying the `triage/accepted` label and provide further guidance.

The `triage/accepted` label can be added by org members by writing `/triage accepted` in a comment.


<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>
Welcome @gabesaba! <br><br>It looks like this is your first PR to <a href='https://github.com/kubernetes/kubernetes'>kubernetes/kubernetes</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/kubernetes has [its own contribution guidelines](https://github.com/kubernetes/kubernetes/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:
Hi @gabesaba. Thanks for your PR.

I'm waiting for a [kubernetes](https://github.com/orgs/kubernetes/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%2Fkubernetes).

<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>

/ok-to-test
@sanposhiho do you want to give it a pass?
> But, can we move `TestGatedPodSchedulableAfterEvent` and `Test_queuedPodInfo_gatedSetUponCreationAndUnsetUponUpdate` in a different PR? I cannot relate them to the core change.

I asked for a change of this nature. Since we are changing how we are processing gated pods, I wanted to make sure they are still scheduled after a delete event for a different pod.

TestGatedPodSchedulableAfterEvent is ok then, but Test_queuedPodInfo_gatedSetUponCreationAndUnsetUponUpdate doesn't go thru any changed part at all.
Right, it can be added in a separate PR, so that it's not part of the cherry-pick.
/retest
LGTM label has been added.  <details>Git tree hash: 231011af712388280ca884c98f940ed9ad17f3d9</details>
[APPROVALNOTIFIER] This PR is **APPROVED**

This pull-request has been approved by: *<a href="https://github.com/kubernetes/kubernetes/pull/124618#pullrequestreview-2048462019" title="Approved">alculquicondor</a>*, *<a href="https://github.com/kubernetes/kubernetes/pull/124618#" title="Author self-approved">gabesaba</a>*

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

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:

- ~~[pkg/scheduler/OWNERS](https://github.com/kubernetes/kubernetes/blob/master/pkg/scheduler/OWNERS)~~ [alculquicondor]
- ~~[test/integration/scheduler/OWNERS](https://github.com/kubernetes/kubernetes/blob/master/test/integration/scheduler/OWNERS)~~ [alculquicondor]

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":[]} -->

Fix patch:
diff --git a/pkg/scheduler/internal/queue/scheduling_queue.go b/pkg/scheduler/internal/queue/scheduling_queue.go
index 9d51d826eace9..0781b275412dc 100644
--- a/pkg/scheduler/internal/queue/scheduling_queue.go
+++ b/pkg/scheduler/internal/queue/scheduling_queue.go
@@ -1098,6 +1098,11 @@ func (p *PriorityQueue) requeuePodViaQueueingHint(logger klog.Logger, pInfo *fra
 func (p *PriorityQueue) movePodsToActiveOrBackoffQueue(logger klog.Logger, podInfoList []*framework.QueuedPodInfo, event framework.ClusterEvent, oldObj, newObj interface{}) {
 	activated := false
 	for _, pInfo := range podInfoList {
+		// Since there may be many gated pods and they will not move from the
+		// unschedulable pool, we skip calling the expensive isPodWorthRequeueing.
+		if pInfo.Gated {
+			continue
+		}
 		schedulingHint := p.isPodWorthRequeuing(logger, pInfo, event, oldObj, newObj)
 		if schedulingHint == framework.QueueSkip {
 			// QueueingHintFn determined that this Pod isn't worth putting to activeQ or backoffQ by this event.


Test patch:
diff --git a/pkg/scheduler/internal/queue/scheduling_queue_test.go b/pkg/scheduler/internal/queue/scheduling_queue_test.go
index 056bfa1d73494..123469c536a31 100644
--- a/pkg/scheduler/internal/queue/scheduling_queue_test.go
+++ b/pkg/scheduler/internal/queue/scheduling_queue_test.go
@@ -98,6 +98,11 @@ var (
 	}
 )
 
+func setQueuedPodInfoGated(queuedPodInfo *framework.QueuedPodInfo) *framework.QueuedPodInfo {
+	queuedPodInfo.Gated = true
+	return queuedPodInfo
+}
+
 func getUnschedulablePod(p *PriorityQueue, pod *v1.Pod) *v1.Pod {
 	pInfo := p.unschedulablePods.get(pod)
 	if pInfo != nil {
@@ -1284,6 +1289,14 @@ func TestPriorityQueue_MoveAllToActiveOrBackoffQueueWithQueueingHint(t *testing.
 			hint:      queueHintReturnQueueSkip,
 			expectedQ: unschedulablePods,
 		},
+		{
+			name:    "QueueHintFunction is not called when Pod is gated",
+			podInfo: setQueuedPodInfoGated(&framework.QueuedPodInfo{PodInfo: mustNewPodInfo(p), UnschedulablePlugins: sets.New("foo")}),
+			hint: func(logger klog.Logger, pod *v1.Pod, oldObj, newObj interface{}) framework.QueueingHint {
+				return framework.QueueImmediately
+			},
+			expectedQ: unschedulablePods,
+		},
 	}
 
 	for _, test := range tests {
@@ -2355,7 +2368,7 @@ func TestPendingPodsMetric(t *testing.T) {
 	gated := makeQueuedPodInfos(total-queueableNum, "y", failme, timestamp)
 	// Manually mark them as gated=true.
 	for _, pInfo := range gated {
-		pInfo.Gated = true
+		setQueuedPodInfoGated(pInfo)
 	}
 	pInfos = append(pInfos, gated...)
 	totalWithDelay := 20
diff --git a/test/integration/scheduler/queue_test.go b/test/integration/scheduler/queue_test.go
index 12425d65b4d95..fecfb2e7a7faa 100644
--- a/test/integration/scheduler/queue_test.go
+++ b/test/integration/scheduler/queue_test.go
@@ -56,12 +56,13 @@ import (
 
 func TestSchedulingGates(t *testing.T) {
 	tests := []struct {
-		name                  string
-		pods                  []*v1.Pod
-		featureEnabled        bool
-		want                  []string
-		rmPodsSchedulingGates []int
-		wantPostGatesRemoval  []string
+		name           string
+		pods           []*v1.Pod
+		featureEnabled bool
+		want           []string
+		delete         []string
+		unschedulable  []string
+		rmGates        []string
 	}{
 		{
 			name: "feature disabled, regular pods",
@@ -98,6 +99,7 @@ func TestSchedulingGates(t *testing.T) {
 			},
 			featureEnabled: true,
 			want:           []string{"p2"},
+			unschedulable:  []string{"p1"},
 		},
 		{
 			name: "feature enabled, two pod carrying scheduling gates, and remove gates of one pod",
@@ -106,10 +108,22 @@ func TestSchedulingGates(t *testing.T) {
 				st.MakePod().Name("p2").SchedulingGates([]string{"bar"}).Container("pause").Obj(),
 				st.MakePod().Name("p3").Container("pause").Obj(),
 			},
-			featureEnabled:        true,
-			want:                  []string{"p3"},
-			rmPodsSchedulingGates: []int{1}, // remove gates of 'p2'
-			wantPostGatesRemoval:  []string{"p2"},
+			featureEnabled: true,
+			want:           []string{"p3"},
+			unschedulable:  []string{"p1", "p2"},
+			rmGates:        []string{"p2"},
+		},
+		{
+			name: "gated pod schedulable after deleting the scheduled pod and removing gate",
+			pods: []*v1.Pod{
+				st.MakePod().Name("p1").SchedulingGates([]string{"foo"}).Container("pause").Obj(),
+				st.MakePod().Name("p2").Container("pause").Obj(),
+			},
+			featureEnabled: true,
+			want:           []string{"p2"},
+			delete:         []string{"p2"},
+			unschedulable:  []string{"p1"},
+			rmGates:        []string{"p1"},
 		},
 	}
 
@@ -130,6 +144,15 @@ func TestSchedulingGates(t *testing.T) {
 			testutils.SyncSchedulerInformerFactory(testCtx)
 
 			cs, ns, ctx := testCtx.ClientSet, testCtx.NS.Name, testCtx.Ctx
+
+			// Create node, so we can schedule pods.
+			node := st.MakeNode().Name("node").Obj()
+			if _, err := cs.CoreV1().Nodes().Create(ctx, node, metav1.CreateOptions{}); err != nil {
+				t.Fatal("Failed to create node")
+
+			}
+
+			// Create pods.
 			for _, p := range tt.pods {
 				p.Namespace = ns
 				if _, err := cs.CoreV1().Pods(ns).Create(ctx, p, metav1.CreateOptions{}); err != nil {
@@ -138,37 +161,51 @@ func TestSchedulingGates(t *testing.T) {
 			}
 
 			// Wait for the pods to be present in the scheduling queue.
-			if err := wait.Poll(time.Millisecond*200, wait.ForeverTestTimeout, func() (bool, error) {
+			if err := wait.PollUntilContextTimeout(ctx, time.Millisecond*200, wait.ForeverTestTimeout, false, func(ctx context.Context) (bool, error) {
 				pendingPods, _ := testCtx.Scheduler.SchedulingQueue.PendingPods()
 				return len(pendingPods) == len(tt.pods), nil
 			}); err != nil {
 				t.Fatal(err)
 			}
 
-			// Pop the expected pods out. They should be de-queueable.
-			for _, wantPod := range tt.want {
-				podInfo := testutils.NextPodOrDie(t, testCtx)
-				if got := podInfo.Pod.Name; got != wantPod {
-					t.Errorf("Want %v to be popped out, but got %v", wantPod, got)
+			go testCtx.Scheduler.Run(ctx)
+
+			// Verify pods scheduled.
+			for _, podName := range tt.want {
+				if err := wait.PollUntilContextTimeout(ctx, time.Millisecond*200, wait.ForeverTestTimeout, false, testutils.PodScheduled(cs, ns, podName).WithContext()); err != nil {
+					t.Fatalf("Failed to schedule %s", podName)
+				}
+			}
+
+			// Delete pods, which triggers AssignedPodDelete event in the scheduling queue.
+			for _, podName := range tt.delete {
+				if err := cs.CoreV1().Pods(ns).Delete(ctx, podName, metav1.DeleteOptions{}); err != nil {
+					t.Fatalf("Error calling Delete on %s", podName)
+				}
+				if err := wait.PollUntilContextTimeout(ctx, time.Millisecond*200, wait.ForeverTestTimeout, false, testutils.PodDeleted(ctx, cs, ns, podName)); err != nil {
+					t.Fatalf("Failed to delete %s", podName)
 				}
 			}
 
-			if len(tt.rmPodsSchedulingGates) == 0 {
-				return
+			// Verify gated pods unschedulable.
+			for _, podName := range tt.unschedulable {
+				if err := wait.PollUntilContextTimeout(ctx, time.Millisecond*200, wait.ForeverTestTimeout, false, testutils.PodSchedulingGated(cs, ns, podName).WithContext()); err != nil {
+					t.Fatalf("Failed to verify unschedulable %s", podName)
+				}
 			}
+
 			// Remove scheduling gates from the pod spec.
-			for _, idx := range tt.rmPodsSchedulingGates {
+			for _, podName := range tt.rmGates {
 				patch := `{"spec": {"schedulingGates": null}}`
-				podName := tt.pods[idx].Name
 				if _, err := cs.CoreV1().Pods(ns).Patch(ctx, podName, types.StrategicMergePatchType, []byte(patch), metav1.PatchOptions{}); err != nil {
 					t.Fatalf("Failed to patch pod %v: %v", podName, err)
 				}
 			}
-			// Pop the expected pods out. They should be de-queueable.
-			for _, wantPod := range tt.wantPostGatesRemoval {
-				podInfo := testutils.NextPodOrDie(t, testCtx)
-				if got := podInfo.Pod.Name; got != wantPod {
-					t.Errorf("Want %v to be popped out, but got %v", wantPod, got)
+
+			// Verify pods without gates scheduled.
+			for _, podName := range tt.rmGates {
+				if err := wait.PollUntilContextTimeout(ctx, time.Millisecond*200, wait.ForeverTestTimeout, false, testutils.PodScheduled(cs, ns, podName).WithContext()); err != nil {
+					t.Fatalf("Failed to schedule %s", podName)
 				}
 			}
 		})