Placement as Bin Packing: Multi-Dimensional Fit and the Fragmentation It Creates

A cluster can be simultaneously under-utilized and unable to accept work. The condition is not a paradox; it is the normal outcome of packing multi-dimensional objects into multi-dimensional bins without a global rearrangement step. Every scheduler that binds pods greedily creates holes whose shape does not match any future pod, and the holes persist because the objects already placed cannot move.

The fit test is a vector comparison, not a sum

A node’s remaining capacity is a vector: cores, memory bytes, ephemeral storage, and sometimes accelerators or extended resources. A pod’s requirement is a vector of the same dimension. The fit test is a component-wise comparison, and a pod fits only if every component of its requirement is less than or equal to the corresponding remaining component.

This is why free cores alone do not imply room. A node with eight free cores and two gigabytes of free memory cannot accept a pod needing one core and four gigabytes, even though the core arithmetic suggests ample room. The binding constraint is whichever dimension is scarcest relative to the pod’s shape, and the ratio between dimensions is what determines whether a pod’s shape matches a node’s hole.

Real clusters have strongly asymmetric ratios. A general-purpose node might offer sixty-four cores and two hundred fifty-six gigabytes, a ratio of four gigabytes per core. A memory-heavy workload with a ratio of sixteen gigabytes per core will exhaust the memory dimension after placing a quarter of the pods that the core dimension would allow, and the remaining cores are stranded. A compute-heavy workload with a ratio of one gigabyte per core exhausts the core dimension first and strands memory. Mixing both on one node leaves the node with a mixture of stranded cores and stranded memory that no single pod shape can consume.

Greedy packing and its bounds

The one-dimensional case is well studied. First-fit, next-fit, and best-fit all have worst-case ratios above one: for first-fit, the number of bins used is at most 1.7 times the optimum plus a constant, and the bound is tight. Best-fit has a similar guarantee. No online algorithm can do better than a constant factor worse than optimal in the worst case, because an online algorithm cannot see the future.

Schedulers are online algorithms, and they are worse than the classic ones because they also cannot rearrange. A classic bin-packing algorithm can be analyzed with the assumption that items arrive in an arbitrary order; a scheduler receives pods in the order their controllers created them, which is a function of the application’s scaling behaviour and not of the packing problem. The arrival order is therefore adversarial by accident: a controller that creates its largest pods first, or a rolling update that creates new pods before terminating old ones, produces an order that defeats a good heuristic.

The practical consequence is that the worst case is not rare. A cluster that has been running and churning for weeks accumulates a placement that no reasonable algorithm would have chosen, because each decision was locally reasonable at the time. This is why cluster operators periodically see a node that is seventy percent allocated in the scheduler’s ledger but cannot accept any pod of the size the pending queue is asking for.

Scoring functions and the density trade

When several nodes can fit a pod, the scheduler picks one by score. The score expresses a policy, and the policies pull in opposite directions.

A density-oriented score prefers the node where the pod fits most tightly, measured as the remaining capacity after placement. This is the best-fit heuristic: it packs tightly, leaving larger holes elsewhere, and it maximizes the number of schedulable pods in the short term. Its cost is that tight packing leaves no burst room: a pod that fits exactly has no headroom for a sidecar, an ephemeral volume, or a temporary spike in memory.

A spread-oriented score prefers the node where the pod leaves the most room, or where the node is least utilized. It balances load and reduces the blast radius of a node failure, and it leaves the cluster fragmented: many partially used nodes, each with a hole too small for the next large pod.

Most production schedulers default toward a balanced score that mixes both, with a preference for spreading within a topology and packing within a failure domain. The composition is a policy statement: spread across zones so that a zone loss is survivable, pack within a zone so that the zone’s nodes are used efficiently. The two halves are evaluated at different levels of the hierarchy, and the interaction between them is where most placement surprises come from.

score(node) = w_density * (1 - remaining_after / allocatable)
            + w_spread  * (used_before / allocatable)
            + w_balance * (1 - |cpu_frac - mem_frac|)

The balance term is the one that prevents the stranded-resource outcome:
it prefers nodes where the two dimensions are consumed in the same proportion.

The balance term is the interesting one, because it is the only term that looks at the shape of the remaining capacity rather than its magnitude. A node at fifty percent CPU and fifty percent memory is balanced and can accept a pod of either shape. A node at ninety percent CPU and ten percent memory is unbalanced, and placing a CPU-heavy pod on it improves the balance even though the node is nearly full.

Fragmentation in the presence of topology

The multi-dimensional problem compounds when the bins are not flat. A node’s cores are not fungible: they belong to sockets, and memory belongs to NUMA nodes, and a pod that needs a large contiguous allocation may need its cores and memory on the same socket. A node that appears to have capacity may have it split across two sockets in a way that no single pod can use.

The scheduler’s view usually abstracts this away, and the abstraction is a source of surprise at the workload level. A pod scheduled onto a node with free capacity on both sockets may have its threads spread across them, paying remote-memory access latency on a fraction of its accesses. The placement decision was correct by the scheduler’s model and suboptimal by the hardware’s. Workloads that care must express the constraint explicitly, which reduces the pool of nodes that can accept them and therefore increases fragmentation.

Topology spread constraints add another dimension to the same problem. A constraint that requires replicas to be spread evenly across zones reduces the set of feasible nodes for each replica, and as the cluster fills, the constraint becomes binding before the capacity does. The scheduler then reports pods as unschedulable for a reason that is a policy, not a shortage, and the distinction is visible only in the scheduler’s event message.

Rebalancing and why it is rare

The cure for accumulated fragmentation is to move pods, and moving pods is expensive in exactly the way that placement is cheap. A move requires creating a replacement, waiting for it to become ready, and only then removing the original — otherwise the workload loses capacity during the move. The transient cost is a doubling of the moved pod’s resource usage, which is why deschedulers move a small number of pods at a time and why they are usually configured to run rarely.

A descheduler’s value is highest in clusters whose workload mix changes over time. A cluster built for compute-heavy pods and later repurposed for memory-heavy ones will have a placement shaped by the old mix, and no amount of good scheduling will fix it because the existing pods do not move. The descheduler evicts a chosen subset, the scheduler re-places them with current information, and the fragmentation gradually resolves.

The cost is churn, and churn has second-order effects. Every eviction is a cold start for the moved workload, which matters for anything with an expensive initialization. Every eviction consumes scheduling capacity for the replacement before the original is gone, which can fail if the cluster is full. And the descheduler’s own decisions are made against the same metrics the scheduler uses, so it can move a pod into a node that will become fragmented by the next pod in the queue. The cold-start cost is the price of the move, and for stateful workloads it is not a price that can be paid casually.

Sizing the cluster against the shape, not the total

The practical conclusion is that capacity planning for a heterogeneous workload is a vector problem. The question is not how many cores the cluster has but how many pods of each shape it can hold, and that number depends on the mix.

A cluster sized to the total requests of its workloads will have stranded capacity whenever the shapes are diverse. The stranded fraction is bounded by the ratio between the largest and smallest dimension ratios in the mix, and it grows as the mix diversifies. The mitigations are to use node shapes that match the workload shapes — memory-optimized nodes for memory-heavy pods, compute-optimized for the others — and to accept that a homogeneous node pool will strand some fraction of at least one dimension. Workloads that must be placed as a unit face the same arithmetic at a larger scale, which is why all-or-nothing allocation is sensitive to fragmentation in a way that single pods are not.

The remaining lever is the pod’s own shape. A pod that requests a round number of cores and a round number of gigabytes fits more nodes than one requesting an odd fraction, simply because round numbers divide the available capacity more evenly. That is a real effect and it is why request values are sometimes rounded up to powers of two or to simple fractions of a node’s capacity. The cost is over-reservation, and it is the same trade as the request-versus-limit decision: paying for scheduling flexibility with capacity that is reserved but unused.