Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Bin packing versus spread placement

Why can a cluster not be packed tight and spread for failure at the same time?

Two objectives contend over one decision.

  • Packing tight maximizes , enables scale-in and scale-to-zero, and directly saves money.
  • Spreading maximizes failure independence and minimizes interference between tasks.

You cannot have both. The conflict is not subtle: (everything fails together when one machine does).

Two things people get wrong:

  1. NP-hardness is irrelevant here. Bin packing is NP-hard (no known fast exact algorithm). But the simple first-fit-decreasing heuristic (sort items from largest to smallest, put each in the first bin it fits) lands within 11/9 of the optimal number of bins, and nobody's bottleneck is the packing search.
  2. The scheduler packs against requested resources, while the machine fails against used resources. Requests are chosen by the person who is not billed for the shortfall. The (promising more than the machine has, betting that not everyone will use their full request) is the knob that trades off this gap. The cost of setting it wrong is paid by the co-tenant, not by the over-requester. This is two principles at once: independence assumed (tasks will not all peak together) and false; and cost relocated onto a different party, who here is structurally silent.

Packing degrades over time, the way any memory allocator does. Long-lived tasks leave holes that no new task fits, and defragmenting a cluster means draining and rescheduling, which costs . This has the same structure as compaction in storage engines (rewriting files to remove dead space): placement that is hard to change, plus churn, produces fragmentation, and fragmentation needs a collector to clean it up.

Packing buys utilization against declared numbers, and pays in correlated failure against the real ones.