The Core Algorithm
Imagine you're moving apartments and you have a set of boxes of fixed size. You want to pack all your belongings using the fewest boxes possible — both to save money on the moving truck and to avoid leaving half-empty boxes wasting space. This is the classic Bin Packing Problem in computer science, and it is NP-hard, meaning there is no known algorithm that finds the perfect solution in reasonable time for large inputs.
In Kubernetes:
* Items = Pods, with their specific CPU and Memory requests.
* Boxes = Nodes, with their total allocatable CPU and Memory capacity.
The scheduler does not attempt to solve bin packing perfectly — that would be too slow. Instead, it uses a scoring phase where each candidate Node receives a score from 0 to 100 across multiple scoring plugins. The default scoring strategy favors Nodes where placing the Pod would leave the smallest amount of fragmented, unusable resources — a heuristic called LeastAllocated or MostAllocated depending on your configuration.
LeastAllocated (default): Spread Pods across Nodes to maximize headroom. Good for resilience — if one Node fails, fewer Pods are affected.
MostAllocated (bin packing): Pack Pods tightly onto fewer Nodes, leaving other Nodes empty. Good for cost — empty Nodes can be removed by a cluster autoscaler.
Switching a cluster from the default spreading behavior to bin packing is a scheduler configuration change — swapping the NodeResourcesFit plugin's scoring strategy from LeastAllocated to MostAllocated, with weights assigned per resource type. The practical implication: if you run a cluster autoscaler, bin packing is almost always the right choice. Tightly packed Nodes allow the autoscaler to identify and remove underutilized Nodes, directly reducing your cloud bill. If you prioritize resilience over cost, spreading is safer.