Tetris in d dimensions: how we rightsize Kubernetes nodes

I'll walk through how CostGraph answers the question, what a node gives you, how big a pod is, why the obvious sorting approach falls short, and what we run instead.

What is a node, really?

A node is the bin, but the bin is smaller than the instance you pay for. The kubelet holds back CPU and memory for itself and the OS, keeps an eviction buffer, and every DaemonSet (your CNI, log shipper, node exporter) takes a slice of each node before an application pod is scheduled.

So a node's capacity is not "4 vCPU, 16 GiB". After reservations and DaemonSets it is closer to "3.4 vCPU, 12.9 GiB, 58 pods, 0 GPUs, 90 GiB of ephemeral disk". CPU, memory, pod count, GPUs, and disk all limit the same placement. A pod fits only when it fits within every limit. On EKS, a small instance can run out of IP addresses before it runs out of CPU.

A pod is a vector

Formally, this is the (d)-dimensional Vector Bin Packing problem. Each pod (\ell) is a vector (I^\ell \in \mathbb{R}^d) of its demand divided by node capacity, and we want the fewest nodes (B_1, \dots, B_k) such that no node overflows in any dimension,

$ \sum_{\ell \in B_j} I^\ell_i \le 1 \qquad \text{for every node } j \text{ and every dimension } i $

The problem is NP-hard for every (d), and for (d \ge 2) it is APX-hard, which means no polynomial-time algorithm can get arbitrarily close to the optimum unless (\mathrm{P} = \mathrm{NP}). At cluster scale, we use heuristics. The interesting question is which ones.

NOTE, In the demos I draw a node as a square, with CPU along the bottom and memory up the side. Pods are rectangles stacked corner to corner along the diagonal. A node is valid exactly when the staircase stays inside the square, because the widths add up to CPU used and the heights add up to memory used. A flat staircase means memory is going unused; a tall one means CPU is.

How big is a pod?

Before packing anything we need each pod's vector, and the request in the manifest is often wrong. Someone set it once, during an incident, two years ago. So the size we use depends on the question we're asking,

• Can today's nodes be consolidated? Each pod is sized at the larger of its request and its 7-day P95 usage, per dimension. We never assume a pod is smaller than the scheduler already thinks it is.
• What if workloads were rightsized too? We swap in the rightsized request, which comes from usage percentiles and how bursty the workload is.

The rightsized request is the P95 divided by a target utilisation (u). The target depends on volatility, measured by the coefficient of variation (\mathrm{CV} = \sigma / \mu) (standard deviation over mean). Steady workloads can run hot, while spiky ones need room to spike,

$ \text{request} = P_{95} \times \frac{100}{u}, \qquad u = \begin{cases} 90 & \mathrm{CV} < 0.25 \ \text{(stable)}
60 & \mathrm{CV} \ge 0.75 \ \text{(spiky)}
80 & \text{otherwise} \end{cases} $

Sizing a pod from a week of CPU usage

CV 0.04 stabletarget util 90%request 334m x 100/90 = 372mfreed vs today 628m

Two more steps happen before we trust the numbers. The 7-day and 30-day windows are merged by taking the larger of each statistic, so a monthly batch job doesn't disappear just because last week was quiet. And raw samples go through an interquartile filter that drops anything outside ([Q_1 - 1.5\,\mathrm{IQR},\ Q_3 + 1.5\,\mathrm{IQR}]), so one bad scrape doesn't buy you a bigger node.

NOTE, A request is a threshold, a fixed line drawn over a signal that rarely stays still. Click diurnal above and the same workload swings by hundreds of millicores between day and night. Deciding where that line goes is the same problem as deciding where an alert threshold goes, and I covered it in depth (percentiles, deterministic vs non-deterministic systems, sinusoidal daily load, and measuring how well a band fits) in Exploring the Math of Thresholds. The rule used here, P95 over a target utilisation, is a percentile plus a buffer, the kind of threshold that article builds up to, with the volatility class deciding how big the buffer is.

Why sorting by size is not enough

The classic answer to one-dimensional bin packing is First Fit Decreasing (FFD), which sorts items from biggest to smallest and drops each one into the first bin it fits. In one dimension it is guaranteed to use at most (\tfrac{11}{9}\,\mathrm{OPT} + 1) bins, where (\mathrm{OPT}) is the optimal packing, the fewest bins any arrangement could possibly use. If the best packing needs 9 nodes, FFD never uses more than 12. Computing (\mathrm{OPT}) at cluster scale is the NP-hard part. It is the yardstick heuristics are measured against, while FFD still works well in practice. The trouble starts when you have to decide what "biggest" means for a vector.

Panigrahy, Talwar, Uyeda and Wieder (Microsoft Research, 2011) give a simple example. Write each pod's size as (CPU, memory), each a fraction of one node. Half the pods are CPU-heavy at (\left(\tfrac13, \tfrac16\right)) and half are memory-heavy at (\left(\tfrac16, \tfrac13\right)). The optimal packing puts two of each kind in a node and fills it exactly,

$ \begin{aligned} \text{CPU,} &\quad \tfrac13 + \tfrac13 + \tfrac16 + \tfrac16 = 1
\text{memory,} &\quad \tfrac16 + \tfrac16 + \tfrac13 + \tfrac13 = 1 \end{aligned} $

But any FFD variant gives every pod of the same type the same weight, so it places all pods of one type next to each other. Three CPU-heavy pods fill the CPU and leave half the memory unused, and a fourth pod of either kind no longer fits,

$ \begin{aligned} \text{CPU,} &\quad \tfrac13 + \tfrac13 + \tfrac13 = 1
\text{memory,} &\quad \tfrac16 + \tfrac16 + \tfrac16 = \tfrac12 \end{aligned} $

The same 12 pods produce different packings

CPU-heavy: 1/3 CPU, 1/6 memorymemory-heavy: 1/6 CPU, 1/3 memorynodes used *4* half of every node stranded

Four nodes instead of three is a third more hardware for the same pods. With more dimensions, FFD can make increasingly inefficient choices. This is common in practice. A CPU-bound API next to a memory-hungry cache describes a normal cluster.

The fix is to turn the loop around. FFD is item-centric, picking the next pod and then looking for a node. The geometric heuristics are bin-centric, opening a node and then asking which pod best fills the space that is left.

The heuristics in the paper

Panigrahy, Talwar, Uyeda, and Wieder compare a family of scoring rules. Let (a_i) be a weight for each dimension, so scarce resources count more, and (r_i) the remaining capacity of the open node,

$ \begin{aligned} \textbf{FFDProd:} &\quad \text{sort by } \textstyle\prod_i I_i
\textbf{FFDAvgSum:} &\quad \text{sort by } \textstyle\sum_i a_i I_i
\textbf{Dot Product:} &\quad \text{pick } \arg\max_\ell \textstyle\sum_i a_i\, I^\ell_i\, r_i
\textbf{L2:} &\quad \text{pick } \arg\min_\ell \textstyle\sum_i a_i \left(I^\ell_i - r_i\right)^2 \end{aligned} $

Dot Product prefers pods that point in the same direction as the space they're filling. L2 prefers pods whose shape is closest to that space. The paper's main finding is that both do as well as FFD when the dimensions are positively correlated, and better when they are negatively correlated. You can check that yourself,

How correlation changes the packing result

CPU vs memory correlation-1.0

FFDProd

item-centric

26 nodes (+5)

FFDAvgSum

item-centric

26 nodes (+5)

Dot Product

bin-centric

24 nodes (+3)

L2

bin-centric

26 nodes (+5)

this draw: lower bound 21, best FFD 26, best geometric 24 geometric saves 2average of 50 draws: FFD 25.08 vs geometric 24.50 nodes

Any single draw can go either way, so the panel also shows the average of 50 draws. Across 200 seeded runs of 80 pods with CPU and memory fully anti-correlated, Dot Product needed 24.5 nodes and FFDAvgSum needed 26.2. Against the better FFD variant, the difference is usually 2 to 4 percent and largest around -0.7. At +1 every pod has the same shape, the problem collapses to one dimension, and all four tie. That matches the paper's result, a few percent in general and more on the hardest distributions.

NOTE, The lower bound is the minimum number of nodes required by the most heavily used dimension, (\left\lceil \max_i \sum_\ell I^\ell_i \right\rceil). (\mathrm{OPT}) falls between that bound and the best heuristic.

What we run in production

This is how the pipeline turns measurements into a plan. Usage becomes statistics, statistics become requests, and requests become vectors. Before a vector can count as a placement, it must pass the scheduler's rules.

What Kubernetes will allow

A placement that fits on resources but that Kubernetes would refuse produces a savings number that disappears the moment someone acts on it. So every candidate placement is checked against the hard constraints the scheduler enforces,

• resources against allocatable, in every dimension, including pod count and GPUs
• NoSchedule and NoExecute taints without a matching toleration
• nodeSelector and required node affinity
• required pod affinity and anti-affinity
• topology spread with DoNotSchedule and its maxSkew
• host ports, and the zone a persistent volume is pinned to

Some pods cannot move, including pods on local persistent volumes, static pods, bare pods with no controller, running Jobs, system-node-critical pods, and anything behind a PodDisruptionBudget that allows zero disruptions. A node holding one of those cannot be drained, and we report why instead of quietly skipping it.

Consolidation, which nodes can be emptied?

The first engine never adds new hardware. It asks how many of today's nodes could be emptied into the rest. It checks the emptiest and most expensive candidates first, then moves their pods one by one. Each pod goes to the node where it best fills the remaining capacity across all dimensions,

for node in sort(nodes, by: packed_fraction asc, cost desc):
    if any pod on node is pinned: report blocked(reason); continue
    snapshot()
    for pod in sort(node.pods, by: L2(demand / capacity) desc):
        target = argmax over other nodes that fit on every dimension
                 and pass the feasibility check,  sum_d (demand_d / cap_d) * (residual_d / cap_d)
        if no target: rollback(); report blocked(reason); next node
        residual[target] -= pod.demand
    mark node drained; nodes that received pods stay put

Here is a five-node cluster going through it. Web pods have a required anti-affinity, so each one needs its own node, and Postgres uses a local volume.

Draining a five-node cluster (4 vCPU, 16 GiB, $140/mo each)

headroom0%10%20%web anti-affinity

cpu/mem shown as % of allocatable · step *0* / 13

Press play or step to start the drain.

Turn headroom up to 10% and the second drain fails. That's why our default node-level headroom is zero, rightsized requests already include a buffer from the utilisation target, so adding node headroom on top would count the buffer twice and hide real savings. Untick anti-affinity and web-2 has more places to go. The plan changes (a different node drains) but the count stays at two. Greedy plans depend on the order they explore things in, which is another reason to treat the number as a floor.

NOTE, Every blocked node also gets a "what if". We relax the rule that blocked it (anti-affinity, affinity, spread, or a missing controller) and run the pack again, so the report can say "this node would free up if web used preferred anti-affinity" instead of just "blocked".

Node pools, which instance types should exist?

The second engine starts from an empty pool and opens nodes from the price catalogue. The question changes from "fewest nodes" to "cheapest nodes", and the nodes are no longer all the same size. For each candidate instance type (t) it tries packing the pod plus every pod that doesn't yet fit an open node, and scores the result,

$ \text{score}(t) = \frac{\text{monthly cost}(t)}{\text{dominant units packed into } t} $

The dominant resource is GPU if any pod needs one, otherwise whichever of CPU or memory is scarcer for the pool. Counting what gets packed matters because a 64-core machine has the lowest price per core in the catalogue and is still the worst possible choice for three pods.

Opening nodes for N pods of 1 vCPU each

pods*5*

first node opened: which type wins?

resulting pool

1 x 4 vCPU

1 x 2 vCPU

monthly $155cheapest-per-core only $992$837 less

At 43 pods the big machine finally wins, because it is now full enough to be cheap. In between you get mixed pools naturally, since each new node can be a different type. Candidates come straight from the price catalogue, filtered by region and zone, architecture, current generation, a minimum size of the largest pod plus DaemonSet overhead, and matching GPU model. Spot capacity is only offered when every pod in the pool tolerates it.

What this does not do (yet)

Greedy heuristics are fast and easy to explain, but they are not optimal. The current limits,

• No exact solver. The paper found LP-based approaches too slow beyond a few hundred items, and that matches our experience. The savings we report are what a greedy pass can prove, so the real number is usually higher.
• Soft constraints are ignored. Preferred affinity, ScheduleAnyway spread, priorities and NUMA don't count against a placement, and the report says so.
• Usage-based sizing covers CPU and memory only. GPU and ephemeral storage are sized from requests.
• No randomised search. The paper's Bubble Search variant saves a little more at many times the runtime. It isn't worth it yet.

Summary

Most of node rightsizing isn't the packing algorithm. It's getting the pod sizes right, getting the node capacity right, and never counting a placement the scheduler would reject. But the algorithm matters once your workloads stop looking alike, and the fix from 2011 is small, instead of asking "which pod is biggest?", ask "which pod fits the space left?"

The paper is short and worth reading, Heuristics for Vector Bin Packing (Panigrahy, Talwar, Uyeda, Wieder, 2011).

On our own cluster

Because we dog food internally, or as we often say, CostGraph runs CostGraph, it is only fair to share our own findings. We found six nodes in our production cluster, one of which could go, saving $104.71 a month.

The list underneath is the useful part. One node can be drained, with 18 pods moving onto the others. The other three stay, and each one says why. One hosts a pod whose required node affinity matches no other node, and two are short on memory. It's the same multi-dimension problem from the start of this post. The cluster requests 28% of its CPU but 62% of its memory, so memory runs out first while most of the CPU remains unused.

NOTE, The demos on this page are better than spaghetti, but pasta is pasta :-P