Repository: kubernetes/kubernetes (language: go)

Issue:
Scheduler throughput reduced when many gated pods
### What happened?

When handling a delete pod event, we attempt to remove pods from the unscheduablePods pool [1], taking a lock while doing so [2]. Gated pods reside in this unscheduable pool, and we process all of them for each delete event. Scheduling throughput is affected, likely because ScheduleOne also takes a lock [3]

[1] https://github.com/kubernetes/kubernetes/blob/00117569f3ab6456791c4e65fc4543a4278d1332/pkg/scheduler/eventhandlers.go#L244-L249

[2] https://github.com/kubernetes/kubernetes/blob/00117569f3ab6456791c4e65fc4543a4278d1332/pkg/scheduler/internal/queue/scheduling_queue.go#L1093-L1097

[3] https://github.com/kubernetes/kubernetes/blob/00117569f3ab6456791c4e65fc4543a4278d1332/pkg/scheduler/schedule_one.go#L69


### What did you expect to happen?

Scheduling throughput should not reduce when there are many gated pods. We eventually decide against moving these pods, but after some processing. https://github.com/kubernetes/kubernetes/blob/be4b7176dc131ea842cab6882cd4a06dbfeed12a/pkg/scheduler/internal/queue/scheduling_queue.go#L1178-L1183

### How can we reproduce it (as minimally and precisely as possible)?

Create many (~10000) gated pods. Then, create non-gated pods which eventually terminate. As these pods finish and pod delete events are processed, scheduling throughput decreases

### Anything else we need to know?

_No response_

### Kubernetes version

<details>

```console
$ kubectl version
Server Version: v1.29.1-gke.1589017
```
</details>


### Cloud provider

<details>
Google Cloud - GKE
</details>


### OS version

_No response_

### Install tools

_No response_

### Container runtime (CRI) and version (if applicable)

_No response_

### Related plugins (CNI, CSI, ...) and versions (if applicable)

_No response_


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>
cc @alculquicondor
/sig scheduling
@Huang-Wei, do you remember what the justification was to put the gated pods in the same unschedulable pool of pods?

I think we should just keep them entirely separate, so that gated pods truly don't affect scheduling throughput.
/cc
I don't think we need to take a lock before checking `isPodWorthRequeuing`. 
Can we just refactor `movePodsToActiveOrBackoffQueue` so that it takes the lock after `isPodWorthRequeuing` is done, rather than requiring lock before `movePodsToActiveOrBackoffQueue` is called?
I tried to create 10,000 gated-pods, and then whether I changed the gated-pods to non-gated-pods or created normal pods, I did not find that the throughput was reduced. Is there something I am missing? I think the scheduling is well.

![image](https://github.com/kubernetes/kubernetes/assets/30427474/cb584364-d074-4ad6-b4be-5b12a58987b9)
![image](https://github.com/kubernetes/kubernetes/assets/30427474/d0f68c51-361c-4d7e-b8d9-ea79f7e4ae15)

This should not be a bug, because if you want lock to affect throughput, the number of pods should be much more than 10,000.

> @Huang-Wei, do you remember what the justification was to put the gated pods in the same unschedulable pool of pods?

It's mainly for keeping the queueing code maintainable. Given the transition among activeQ/backoffQ/unschedulableQ is already complex, adding another internal queue doesn't sound a good idea by that time.

> I think we should just keep them entirely separate, so that gated pods truly don't affect scheduling throughput.

I doubt if throughput is really impacted... In terms of the re-queuing check on gated pods, (I haven't went through the latest code w/ schedulingHint), the original version is fairly straightforward - a PodDeletion event won't interest the gated pod at all, so it simply return. Even if the throughput is degraded, it's suspicious that the dominant factor is iterating gated pods. Needless to say, all re-queueing check happens in a separate goroutine.

So if throughput is proven impacted, I'd suggest to narrow down the real problem; otherwise moving gated pods to a separate struct won't benefit that much.

> Can we just refactor movePodsToActiveOrBackoffQueue so that it takes the lock after isPodWorthRequeuing is done, rather than requiring lock before movePodsToActiveOrBackoffQueue is called?

We should pin-point the specific issue by crafting a reproducible test, and then work on the solution. Maybe it's lock, maybe it's other things.
Here is a test I ran which reproduces the issue:

Create 10k gated pods
Create 30k pods at rate of 50/s, which sleep for 5 minutes each

Observe pods scheduling at ~50/s for first 5 minutes. When pods start terminating, the scheduler throughput decreases, and a backlog of pods builds up

![gated_performance_10k](https://github.com/kubernetes/kubernetes/assets/15304068/d922494c-7bd5-49af-9e1a-a9abb7e3a83f)


60s pprof sample with same experiment setup as comment directly above, after pods started terminating:
![pprof](https://github.com/kubernetes/kubernetes/assets/15304068/46d6edfb-666d-4f14-8862-30a3896faba7)

61.7% of samples are from deletePodFromCache, with 55.3% attributable to these 4 lines:
* 15.8% [scheduling_queue.go#L421](https://github.com/kubernetes/kubernetes/blob/00117569f3ab6456791c4e65fc4543a4278d1332/pkg/scheduler/internal/queue/scheduling_queue.go#L421)
* 14.5% [scheduling_queue.go#L434](https://github.com/kubernetes/kubernetes/blob/00117569f3ab6456791c4e65fc4543a4278d1332/pkg/scheduler/internal/queue/scheduling_queue.go#L434)
* 13.2% [scheduling_queue.go#L1149](https://github.com/kubernetes/kubernetes/blob/00117569f3ab6456791c4e65fc4543a4278d1332/pkg/scheduler/internal/queue/scheduling_queue.go#L1149)
* 11.8% [scheduling_queue.go#L443](https://github.com/kubernetes/kubernetes/blob/00117569f3ab6456791c4e65fc4543a4278d1332/pkg/scheduler/internal/queue/scheduling_queue.go#L443)

The smallest change would be to filter gated pods inline [here](https://github.com/kubernetes/kubernetes/blob/00117569f3ab6456791c4e65fc4543a4278d1332/pkg/scheduler/internal/queue/scheduling_queue.go#L1082). Could also use a preCheck function, but that is more than one line :)

/assign gabesaba

Fix patch:
diff --git a/pkg/scheduler/internal/queue/scheduling_queue.go b/pkg/scheduler/internal/queue/scheduling_queue.go
index 115f81afc13db..93a8333a4a5f2 100644
--- a/pkg/scheduler/internal/queue/scheduling_queue.go
+++ b/pkg/scheduler/internal/queue/scheduling_queue.go
@@ -1175,6 +1175,11 @@ func (p *PriorityQueue) movePodsToActiveOrBackoffQueue(logger klog.Logger, podIn
 
 	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 == 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 e160b89a4e90d..dd7a9ad84c5c1 100644
--- a/pkg/scheduler/internal/queue/scheduling_queue_test.go
+++ b/pkg/scheduler/internal/queue/scheduling_queue_test.go
@@ -93,6 +93,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 {
@@ -1451,6 +1456,14 @@ func TestPriorityQueue_MoveAllToActiveOrBackoffQueueWithQueueingHint(t *testing.
 			hint:      queueHintReturnSkip,
 			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, error) {
+				return framework.Queue, fmt.Errorf("QueueingHintFn should not be called as pod is gated")
+			},
+			expectedQ: unschedulablePods,
+		},
 	}
 
 	for _, test := range tests {
@@ -2732,7 +2745,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/plugins/plugins_test.go b/test/integration/scheduler/plugins/plugins_test.go
index 8993b78126e19..5b8250738b7da 100644
--- a/test/integration/scheduler/plugins/plugins_test.go
+++ b/test/integration/scheduler/plugins/plugins_test.go
@@ -2677,7 +2677,7 @@ func TestSchedulingGatesPluginEventsToRegister(t *testing.T) {
 		{
 			name:          "preEnqueue plugin with event registered",
 			enqueuePlugin: &SchedulingGatesPluginWithEvents{SchedulingGates: schedulinggates.SchedulingGates{}},
-			count:         3,
+			count:         2,
 		},
 	}
 
diff --git a/test/integration/scheduler/queue_test.go b/test/integration/scheduler/queue_test.go
index 3f452473a1d1a..46914c97eee81 100644
--- a/test/integration/scheduler/queue_test.go
+++ b/test/integration/scheduler/queue_test.go
@@ -57,11 +57,11 @@ import (
 
 func TestSchedulingGates(t *testing.T) {
 	tests := []struct {
-		name                  string
-		pods                  []*v1.Pod
-		want                  []string
-		rmPodsSchedulingGates []int
-		wantPostGatesRemoval  []string
+		name     string
+		pods     []*v1.Pod
+		schedule []string
+		delete   []string
+		rmGates  []string
 	}{
 		{
 			name: "regular pods",
@@ -69,7 +69,7 @@ func TestSchedulingGates(t *testing.T) {
 				st.MakePod().Name("p1").Container("pause").Obj(),
 				st.MakePod().Name("p2").Container("pause").Obj(),
 			},
-			want: []string{"p1", "p2"},
+			schedule: []string{"p1", "p2"},
 		},
 		{
 			name: "one pod carrying scheduling gates",
@@ -77,7 +77,7 @@ func TestSchedulingGates(t *testing.T) {
 				st.MakePod().Name("p1").SchedulingGates([]string{"foo"}).Container("pause").Obj(),
 				st.MakePod().Name("p2").Container("pause").Obj(),
 			},
-			want: []string{"p2"},
+			schedule: []string{"p2"},
 		},
 		{
 			name: "two pod carrying scheduling gates, and remove gates of one pod",
@@ -86,9 +86,18 @@ func TestSchedulingGates(t *testing.T) {
 				st.MakePod().Name("p2").SchedulingGates([]string{"bar"}).Container("pause").Obj(),
 				st.MakePod().Name("p3").Container("pause").Obj(),
 			},
-			want:                  []string{"p3"},
-			rmPodsSchedulingGates: []int{1}, // remove gates of 'p2'
-			wantPostGatesRemoval:  []string{"p2"},
+			schedule: []string{"p3"},
+			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(),
+			},
+			schedule: []string{"p2"},
+			delete:   []string{"p2"},
+			rmGates:  []string{"p1"},
 		},
 	}
 
@@ -107,6 +116,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 {
@@ -122,30 +140,42 @@ func TestSchedulingGates(t *testing.T) {
 				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)
+			// Schedule pods.
+			for _, podName := range tt.schedule {
+				testCtx.Scheduler.ScheduleOne(testCtx.Ctx)
+				if err := wait.PollUntilContextTimeout(ctx, time.Millisecond*200, wait.ForeverTestTimeout, false, testutils.PodScheduled(cs, ns, podName)); 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
+			// Ensure gated pods are not in ActiveQ
+			if len(testCtx.Scheduler.SchedulingQueue.PodsInActiveQ()) > 0 {
+				t.Fatal("Expected no schedulable pods")
 			}
+
 			// 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)
+
+			// Schedule pods which no longer have gates.
+			for _, podName := range tt.rmGates {
+				testCtx.Scheduler.ScheduleOne(testCtx.Ctx)
+				if err := wait.PollUntilContextTimeout(ctx, time.Millisecond*200, wait.ForeverTestTimeout, false, testutils.PodScheduled(cs, ns, podName)); err != nil {
+					t.Fatalf("Failed to schedule %s", podName)
 				}
 			}
 		})