Bin packing — fitting workloads on nodes

Bin packing is the discipline of fitting workloads on nodes. The scheduler uses a bin-packing algorithm to fit the pods on the nodes. The resource fragmentation is the unused space; the affinity and anti-affinity constrain the placement. This lesson walks the algorithm, the fragmentation, the affinity, and the production patterns.

The bin-packing algorithm

The scheduler uses a bin-packing algorithm to fit the pods on the nodes:

flowchart LR
    A[Pods to schedule] --> B[Scheduler]
    B --> C[Node 1 capacity]
    B --> D[Node 2 capacity]
    B --> E[Node 3 capacity]
    C --> F[Pod A: 1 vCPU, 2Gi]
    D --> G[Pod B: 1 vCPU, 2Gi]
    D --> H[Pod C: 1 vCPU, 2Gi]
    E --> I[Pod D: 1 vCPU, 2Gi]

The scheduler iterates through the pods and nodes; it fits each pod on the first node that has sufficient capacity.

The LeastAllocated strategy

The default scheduler strategy is LeastAllocated:

Node 1: 8 vCPU, 16Gi memory (4 vCPU used)
Node 2: 8 vCPU, 16Gi memory (2 vCPU used)

Pod to schedule: 1 vCPU, 2Gi memory

LeastAllocated: prefer Node 2 (more space available)

The LeastAllocated strategy spreads the pods across the nodes.

The MostAllocated strategy

The MostAllocated strategy is the opposite:

Node 1: 8 vCPU, 16Gi memory (4 vCPU used)
Node 2: 8 vCPU, 16Gi memory (2 vCPU used)

Pod to schedule: 1 vCPU, 2Gi memory

MostAllocated: prefer Node 1 (less space available)

The MostAllocated strategy packs the pods. The benefit is fewer nodes (cost savings); the risk is uneven distribution.

The resource fragmentation

The resource fragmentation is the unused space on a node:

Node 1 capacity: 8 vCPU, 32Gi memory
Pods on Node 1: 4 vCPU, 16Gi memory
Free: 4 vCPU, 16Gi memory

A new pod requires 6 vCPU, 2Gi memory.
The pod does not fit on Node 1 (6 vCPU > 4 vCPU available).
The pod is scheduled on Node 2.

Node 1: 4 vCPU wasted (fragmentation)

The fragmentation is the cost of the bin-packing.

The bin-packing score

The scheduler computes a bin-packing score per node:

Node 1: (4/8) * 100 = 50% CPU used
Node 2: (2/8) * 100 = 25% CPU used

Score (LeastAllocated): 100 - 50 = 50 for Node 1; 100 - 25 = 75 for Node 2
Node 2 wins (higher score).

The scheduler chooses the node with the highest score.

The affinity

The affinity constrains the bin-packing:

spec:
  affinity:
    podAntiAffinity:
      preferredDuringSchedulingIgnoredDuringExecution:
      - weight: 100
        podAffinityTerm:
          labelSelector:
            matchLabels:
              app: nginx
          topologyKey: kubernetes.io/hostname

The pod prefers to be on a different node than other pods with the same label. The anti-affinity spreads the pods.

The affinity and HA

The affinity and HA are intertwined:

flowchart LR
    A[HA workload] --> B{Replica count > 1?}
    B -->|yes| C[Use anti-affinity]
    B -->|no| D[No constraint]
    C --> E[Spread across nodes]
    D --> F[Schedule anywhere]

The anti-affinity is the HA’s friend.

The bin-packing score with affinity

The affinity overrides the bin-packing score:

Node 1: 50% CPU used (high score)
Node 2: 25% CPU used (higher score)

Anti-affinity: prefer different node from existing nginx pod on Node 1.
Node 1: anti-affinity penalty → score reduced
Node 2: preferred → score higher

The scheduler respects the affinity.

The resource shape

The pod’s resource shape affects the bin-packing:

Pod A: 1 vCPU, 16Gi memory (memory-heavy)
Pod B: 4 vCPU, 1Gi memory (CPU-heavy)

Node 1: 8 vCPU, 16Gi memory
Pod A fits on Node 1 (1 vCPU, 16Gi memory)

Node 2: 8 vCPU, 16Gi memory
Pod B fits on Node 2 (4 vCPU, 1Gi memory)

The shape (CPU-heavy vs memory-heavy) affects the fit.

The topology spread

The topology spread constraint limits the placement across zones:

spec:
  topologySpreadConstraints:
  - maxSkew: 1
    topologyKey: topology.kubernetes.io/zone
    whenUnsatisfiable: DoNotSchedule
    labelSelector:
      matchLabels:
        app: nginx

The constraint says “spread the pods across zones with a max skew of 1.”

flowchart LR
    A[HA workload] --> B[Zone 1]
    A --> C[Zone 2]
    A --> D[Zone 3]
    B --> E[2 pods]
    C --> F[2 pods]
    D --> G[2 pods]

The topology spread is the HA’s discipline.

Cross-course references

• The Scheduler course (Part LXXI) covers the scheduling algorithm.
• The Topology Spread course (Part XXV) covers the topology constraints.
• The VPA course (Part LXXXIII) covers the right-sizing.

Quiz

Production discipline

• Use LeastAllocated for spread workloads. Most HA workloads.
• Use MostAllocated for cost optimization. When the workloads are not HA.
• Use anti-affinity for HA workloads. Spread across nodes or zones.
• Right-size the workloads. Reduce fragmentation.
• Document the bin-packing strategy. The strategy, the constraints, the rationale.
• Test the bin-packing. Use simulated load to verify the placement.

The bin-packing is the scheduler’s algorithm. Operating it well is choosing the right strategy, using affinity for HA, and right-sizing the workloads.