Kubernetes Scheduling Is a Packing Problem

The Kubernetes scheduler is not a load balancer and it is not a "placement service with good intentions." It is a bin-packing algorithm with hard constraints and soft preferences. Every pod is an item with a requested footprint; every node is a bin with a finite capacity; the scheduler's job is to decide which bin gets which item — and the way it accounts for size is the reason your cluster is either dense and efficient or sparse and half-wasted.

The two-pass algorithm

Every scheduling decision runs through the same pipeline, once per pod:

Filter pass (predicates): eliminate nodes that cannot run the pod at all
  - insufficient allocatable CPU/memory for the pod's requests
  - nodeSelector / affinity constraints violated
  - taints that the pod's tolerations don't accept
  - port conflicts, volume zone constraints, topology spread
 
Score pass (priorities): rank the surviving nodes
  - MostAllocated: favor nodes already using the most resources
  - LeastAllocated: spread pods across nodes (default-ish behavior)
  - inter-pod affinity, taint tolerance, image locality

The kube-scheduler runs both passes against a cached view of the cluster (usually a few seconds stale), picks the top-scoring node, and binds the pod. The entire algorithm is a loop: filter -> score -> pick -> bind -> watch for the next.

Requests vs. limits: the two numbers that drive everything

Every pod declares two numbers per resource, and the scheduler reads only one of them:

apiVersion: v1
kind: Pod
metadata:
  name: api-server
spec:
  containers:
    - name: api
      image: myapp:1.2.3
      resources:
        requests:
          cpu: "500m"        # scheduler input: 500 milli-cores reserved
          memory: 512Mi
        limits:
          cpu: "2"           # scheduler ignores limits for placement
          memory: 1Gi

Requests are what the scheduler sums when deciding if a pod fits. The node's allocatable capacity (capacity minus the kubelet, system pods, and the eviction threshold) must cover the sum of all requests. Limits are the ceiling enforced at runtime by the kubelet's cgroup throttling and the OOM killer — the scheduler ignores them entirely for placement. If you set a 2-CPU limit with a 500m request, the scheduler books 500m of capacity while the pod is allowed to burn 2 cores, which means the bin-packing math assumes a footprint the pod does not actually have.

That mismatch is the source of most real clusters' two failure modes:

• Overcommit blowups. Limits much larger than requests let many pods share a node on paper — then a correlated burst (deploy day, cache invalidation, batch job) makes several pods consume up to their limits simultaneously, the node exceeds its real capacity, and the kernel's OOM killer starts terminating processes by eviction priority.
• Wasted bins. Requests far larger than real usage (the "set requests = peak usage" school) pack the cluster at 20% actual utilization because the scheduler books capacity that never gets used. The pods fit; the machines don't.

QoS classes: the eviction pecking order

The combination of requests and limits determines the pod's QoS class, which is exactly the order in which the node evicts things under memory pressure:

Guaranteed   requests == limits (all resources)
             -> never evicted except for total node failure, and only after others
 
Burstable    requests < limits, or requests set on some resources only
             -> evicted after Guaranteed, before BestEffort
 
BestEffort   no requests, no limits at all
             -> the first thing evicted when the node runs low

The kubelet also assigns a memory oom_score_adj per class: BestEffort pods get +1000 (killed first), Burstable gets a value between 0 and 1000 scaled by how far usage is above request, and Guaranteed gets −998 (essentially never OOM-killed). The packing consequence: if your latency-critical pods are Burstable with tight requests, they are by definition closer to the eviction knife than the Guaranteed pods sitting next to them.

The packing tension

A scheduler that always packs the cluster densest wins on cost and loses on resilience. A scheduler that spreads pods everywhere wins on blast radius and loses on utilization. The default scheduler leans spread: its default score plugins prefer least-allocated nodes and even spreading, so a default cluster deliberately leaves capacity scattered. If you want density, you must ask for it:

spec:
  topologySpreadConstraints:
    - maxSkew: 1          # spread replicas across nodes/zones
      topologyKey: topology.kubernetes.io/zone
      whenUnsatisfiable: DoNotSchedule

or score plugins configured with MostAllocated weight. The kube-scheduler exposes its entire decision process through scheduling events (kubectl get events shows "FailedScheduling" with reasons like Insufficient memory), and kubectl describe pod shows which node won and why — the algorithm is inspectable, not a mystery.

There is also the fragmentation problem: bin-packing with mixed sizes leaves holes. A node with 900m free can't fit a pod requesting 1 CPU, so the hole stays until a small-enough pod arrives. This is why "just add more nodes" is the default answer — it sidesteps the packing problem by making bins plentiful, and it is why a cluster with 30 nodes often packs worse than a cluster with 10 well-chosen ones.

What this means for your deployments

1. Set requests to your real baseline (p50–p70 of observed usage, not the peak) and limits to a safety ceiling. The scheduler packs on requests; the runtime enforces limits.
2. Keep latency-critical pods Guaranteed (requests == limits) so they survive node pressure — then size their requests conservatively, because that is also the packing cost you pay on every node.
3. Watch for Insufficient cpu / Insufficient memory events — they are the scheduler telling you the bin-packing has no solution, which is a requests problem, not a nodes problem.
4. Decide your packing philosophy deliberately. Spread for blast-radius protection (the default), pack for cost — and pick per-workload with scoring weights, not globally.

The runtime view

• Scheduling is filter-then-score bin-packing over requests, computed against a stale cache of node capacity.
• Limits are a runtime enforcement ceiling, invisible to the scheduler — the gap between requests and limits is where overcommit incidents live.
• QoS class = eviction order and OOM priority; it is the scheduler's accounting meeting the kernel's enforcement.
• Every FailedScheduling event is the packing problem saying "no bin fits" — and it always means requests, not nodes.