Kubernetes Pods stuck Pending: Insufficient cpu, untolerated taints and node affinity

On a Tuesday afternoon a routine rollout of our order-pricing service stalled at 6 of 20 replicas. The new ReplicaSet had 14 Pods in Pending and the Deployment reported ProgressDeadlineExceeded after ten minutes. The old Pods kept serving, so there was no outage, but we could not ship a pricing fix that finance was waiting for.

The first Pod we described had a single event repeating:

Warning  FailedScheduling  2m  default-scheduler  0/9 nodes are available: 1 node(s) had untolerated taint {node.kubernetes.io/unschedulable: }, 2 node(s) didn't match Pod's node affinity/selector, 3 Insufficient cpu, 3 node(s) had untolerated taint {workload: batch}. preemption: 0/9 nodes are available: 3 No preemption victims found for incoming pod, 6 Preemption is not helpful for scheduling.

The confusing part: our Grafana node dashboard showed the general node pool sitting at around 30 percent CPU. Somebody said "the scheduler is broken" in the incident channel, which is almost never true.

Reproducing it

The condition was deterministic: any Pod from the new ReplicaSet stayed Pending, any Pod from the old ReplicaSet (scaled down during the rollout) was rescheduled fine if we deleted it. So the difference had to be in the Pod spec, not the cluster. A diff of the two templates showed two changes made in the same release:

• CPU request raised from 500m to 1500m, because a load test had shown throttling.
• A nodeAffinity rule added to keep the service off spot nodes, using a label key that only existed on one node pool.

What we ruled out

Real CPU exhaustion. kubectl top nodes showed the three general nodes at 28 to 35 percent usage. Usage is irrelevant to scheduling, but it ruled out a runaway process.

Cluster Autoscaler being down. Its Pod was running, and it was emitting events on our Pending Pods:

Normal  NotTriggerScaleUp  1m  cluster-autoscaler  pod didn't trigger scale-up: 1 max node group size reached, 2 node(s) had untolerated taint {workload: batch}, 1 node(s) didn't match Pod's node affinity/selector

So it was alive and had looked at every node group; none of them could fit the Pod.

A cordoned node. The node.kubernetes.io/unschedulable taint belonged to a node we had cordoned that morning for a kernel update. That accounted for one node out of nine and was expected.

Root cause

Reading the message node by node explained everything. The scheduler only places a Pod on a node where the sum of existing Pod requests plus the new Pod's request fits within the node's allocatable CPU. Our general nodes were m6i.xlarge (4 vCPU, 3920m allocatable after system reservations), and the Pods already on them requested 2600m to 2900m each, even though they used far less. A 1500m request did not fit anywhere in the general pool.

The spare capacity on the cluster lived in a new batch node pool, which carried a workload=batch:NoSchedule taint that the pricing service did not tolerate. The two remaining nodes were spot nodes, excluded by our own new affinity rule. And the general pool's Auto Scaling group was already at its configured maximum of 3, which is the "max node group size reached" line from the autoscaler. Every filter rejected every node for a different reason.

What is happening under the hood

kube-scheduler runs a filter phase over all feasible nodes. Each filter plugin can reject a node with a reason, and the final FailedScheduling message is just a histogram of those reasons. The relevant plugins here:

• NodeResourcesFit compares requests with status.allocatable minus the requests of Pods already bound to the node. It produces Insufficient cpu or Insufficient memory. Limits and real usage are ignored.
• TaintToleration rejects nodes with a NoSchedule or NoExecute taint the Pod has no toleration for, producing had untolerated taint {key: value}.
• NodeAffinity rejects nodes whose labels do not satisfy nodeSelector or requiredDuringSchedulingIgnoredDuringExecution, producing didn't match Pod's node affinity/selector.

After filtering fails, the scheduler tries preemption: can it evict lower-priority Pods to make room? Preemption is not helpful for scheduling means evicting Pods would not fix the failing filter (you cannot evict your way past a taint). No preemption victims found means there were no lower-priority Pods to evict, since all our workloads used the default priority.

Cluster Autoscaler runs a simulation with the same predicates against a template node for each node group. If no template fits, or the fitting group is at its maximum size, it records NotTriggerScaleUp and does nothing.

Environment

Minimal reproduction

On any test cluster, taint all nodes but one, fill that one with requests, then create a Pod that will not fit:

kubectl taint nodes worker-2 worker-3 workload=batch:NoSchedule
kubectl create deployment filler --image=registry.k8s.io/pause:3.10 --replicas=3
kubectl set resources deployment filler --requests=cpu=1
kubectl run probe --image=registry.k8s.io/pause:3.10 \
  --overrides='{"spec":{"containers":[{"name":"probe","image":"registry.k8s.io/pause:3.10","resources":{"requests":{"cpu":"1500m"}}}]}}'
kubectl describe pod probe | tail -3

You get the same mix of Insufficient cpu and untolerated taint reasons.

Who is affected

Any cluster where requests are generous relative to real usage, where node pools are tainted for dedicated workloads, or where autoscaling groups have tight maximums. It gets worse when two changes land together, as ours did: a bigger request and a narrower affinity each looked harmless alone.

The fix

We worked through the three reasons separately rather than reaching for one big hammer.

1. Make the request match measured need. The load test had showed throttling at the limit, not starvation from the request. We looked at the 95th percentile of real usage over a week:

kubectl -n pricing top pods -l app=order-pricing --containers

Usage peaked at about 700m. We set the request to 800m and kept the limit at 2 CPU, which removed the throttling the test had seen without reserving capacity that was never used.

 resources:
   requests:
-    cpu: 1500m
+    cpu: 800m
     memory: 512Mi
   limits:
     cpu: "2"
     memory: 1Gi

2. Fix the affinity rule. The intent was "not on spot", but the rule required a label that only the general pool had. We rewrote it to exclude spot explicitly, which keeps working when new on-demand pools appear:

affinity:
  nodeAffinity:
    requiredDuringSchedulingIgnoredDuringExecution:
      nodeSelectorTerms:
        - matchExpressions:
            - key: capacity
              operator: NotIn
              values: ["spot"]

3. Give the general pool headroom. We raised the general ASG maximum from 3 to 6 so Cluster Autoscaler can actually react next time. We deliberately did not add a toleration for workload=batch; that pool is tainted so nightly jobs are not squeezed by request-heavy services, and tolerating the taint would quietly undo that decision.

Alternatives and trade-offs

• Tolerate the batch taint. Instant capacity, but it mixes latency-sensitive Pods with CPU-saturating jobs. Only acceptable as a short incident workaround, removed afterwards.
• PriorityClass for the service. Lets preemption evict lower-priority Pods. Useful for critical services, but it does not help with taint or affinity failures, and it moves pain onto whatever gets evicted.
• Bigger nodes. Reduces fragmentation of allocatable CPU, at the cost of larger blast radius per node.

How to test the fix

Before rolling out, we checked fit with a server-side dry run and an allocation report per node:

kubectl apply -f pricing-deploy.yaml --dry-run=server
kubectl describe nodes -l capacity!=spot | grep -A6 "Allocated resources"

The allocation output shows requests as a percentage of allocatable, which is the number the scheduler actually uses:

Allocated resources:
  Resource           Requests      Limits
  --------           --------      ------
  cpu                2850m (72%)   7 (178%)
  memory             5530Mi (79%)  9Gi (131%)

With 1070m free per node, an 800m request fits; 1500m did not. We then ran the rollout in staging with the same node pool layout and confirmed all replicas were scheduled within seconds.

Confirming in production

After the deploy, the rollout completed and no Pod in the namespace was left Pending:

kubectl -n pricing rollout status deploy/order-pricing
kubectl get pods -A --field-selector=status.phase=Pending

The second command returned No resources found. We also watched the autoscaler for an hour; it added one general node when a separate team scaled up, proving the new maximum gave it room to act.

Regression guard

• An alert on Pods Pending for more than five minutes, from kube-state-metrics: sum by (namespace) (kube_pod_status_phase{phase="Pending"}) > 0 with for: 5m.
• An alert when any node group is at its configured maximum, so "max node group size reached" is visible before it blocks a rollout.
• A CI step that diffs resources.requests in pull requests and asks for a usage graph link when a request grows by more than 50 percent.

Security implications

None from the fix itself. One caution: tolerations are a scheduling control, not a security boundary. Any team that can edit a Pod spec can add a toleration and land on a dedicated pool. If a tainted pool exists for isolation reasons (sensitive data, PCI scope), enforce it with an admission policy that rejects unauthorised tolerations, not with the taint alone.

Prevention checklist

• Size requests from observed usage percentiles, not from limits or guesses.
• Read FailedScheduling messages node by node; each count maps to one filter plugin.
• Express affinity as exclusion (NotIn) when the intent is "avoid", so new pools stay eligible.
• Alert on node groups at maximum size and on Pods Pending longer than a few minutes.
• Treat taints plus tolerations as placement hints and back isolation needs with admission policy.

References

• Kubernetes documentation, Taints and Tolerations: https://kubernetes.io/docs/concepts/scheduling-eviction/taint-and-toleration/
• Kubernetes documentation, Assigning Pods to Nodes: https://kubernetes.io/docs/concepts/scheduling-eviction/assign-pod-node/
• Kubernetes documentation, Pod Priority and Preemption: https://kubernetes.io/docs/concepts/scheduling-eviction/pod-priority-preemption/
• Cluster Autoscaler FAQ: https://github.com/kubernetes/autoscaler/blob/master/cluster-autoscaler/FAQ.md