title: CloudSlash - K8s Bin Packing Reference description: Kubernetes bin packing is a 2D problem: CPU and memory. Oracle models it as a bounded knapsack and finds consolidations your kube-scheduler misses. Optimizin...

K8s Bin Packing¶

Kubernetes bin packing is a 2D problem: CPU and memory. Oracle models it as a bounded knapsack and finds consolidations your kube-scheduler misses.

2D Vector Constraints¶

Single-dimensional bin packing breaks for Kubernetes pods because of resource asymmetry. A pod with heavy CPU requirements but minimal memory can't be reliably scheduled using scalar volume calculations alone.

Both instance capacity (CPU, Memory) and workload demand (CPU, Memory) model as 2D vectors.

BFD¶

Best Fit Decreasing

We use Best Fit Decreasing (BFD), a heuristic with a proven packing bound of \(\frac{11}{9} OPT + \frac{6}{9}\).

1. Sort items descending using the \(L_{\infty}\) norm (dominance scaling).
2. For each item, select the active bin with minimal residual capacity (tightest fit). If none fits, open a new bin.

type Item struct {
    CPUReq int64
    MemReq int64
}

type Bin struct {
    CPUCapacity int64
    MemCapacity int64
    CPUUsed     int64
    MemUsed     int64
}

L-Infinity Slack Norm¶

"Tightest fit" across two dimensions requires mapping the vector to a deterministic scalar. Simple volume (\(CPU_{rem} + RAM_{rem}\)) masks imbalances and can strand one dimension entirely.

We use the \(L_{\infty}\) norm (Chebyshev distance) to isolate the most constrained dimension:

func slackNorm(bin *Bin, item *Item) float64 {
    remCPU := float64(bin.CPUCapacity - bin.CPUUsed - item.CPUReq) / float64(bin.CPUCapacity)
    remMem := float64(bin.MemCapacity - bin.MemUsed - item.MemReq) / float64(bin.MemCapacity)

    return math.Max(remCPU, remMem)
}

A memory-heavy workload preferentially packs into a bin with the tightest memory remainder, preserving balanced bins for general-purpose workloads.