Implementing kubernetes node bin packing

George E. P. Box's quote, "All models are wrong, but some are useful," serves as a reminder when discussing node rightsizing in Kubernetes. Node rightsizing is akin to vector bin packing, where pods are sorted by a single size number before placement. However, this approach can leave capacity on the table if some workloads rely heavily on CPU while others depend on memory.

The packing algorithm is greedy, meaning the savings reported should be considered a floor rather than a ceiling. The ultimate goal is to determine if fewer nodes are needed, but this often requires a whiteboard to identify which nodes can be removed. This post aims to provide a clear explanation of the process, covering how cost graphs answer the question, the capacity of a node, the size of a pod, and why the simple sorting method falls short.

A node represents the bin, but it is smaller than the instance you pay for. The kubelet holds back CPU and memory for itself and the OS, maintains an eviction buffer, and DaemonSets consume a portion of each node before scheduling application pods. Consequently, the actual capacity of a node is closer to 3.4 vCPU, 12.9 GiB, 58 pods, 0 GPUs, and 90 GiB of ephemeral disk.

The problem of node rightsizing is formally classified as the d-dimensional Vector Bin Packing problem, where d is the number of dimensions (CPU, memory, pod count, GPUs, and disk). This problem is NP-hard for every d, and for d≥2, it is APX-hard, indicating that no polynomial-time algorithm can get arbitrarily close to the optimal solution unless P=NP. Therefore, heuristics are employed to tackle the problem.

The best-known heuristic for one-dimensional bin packing is First Fit Decreasing (FFD), which sorts items from largest to smallest and places each item into the first bin that fits. While FFD guarantees at most 119 OPT+1 bins, where OPT is the optimal packing, it becomes inefficient in multi-dimensional scenarios. Panigrahy, Talwar, Uyeda, and Wieder demonstrated this inefficiency through an example involving CPU-heavy and memory-heavy pods. In such cases, FFD can lead to more nodes being used than necessary.