Cluster scheduling, bin packing and fairness

Why it matters

A cluster scheduler decides which work runs, where it runs and what happens when resources run out. Those decisions set utilization, cost, tail latency and fairness between users. Many cloud research questions start here, so you should be able to state placement as a constrained, multi-dimensional bin-packing problem, explain multi-resource fairness, and evaluate a policy without fooling yourself.

Core ideas

What a scheduler does. Admission (is there quota or capacity?), placement (which machine?), preemption (whom to evict for more important work?) and rescheduling after failures or rebalancing. Kubernetes splits placement into filtering feasible nodes and scoring them; Borg uses the same two phases, called feasibility checking and scoring.

Packing heuristics. Placement over several resources (CPU, memory, GPUs, disk, network) with constraints is NP-hard in general, so production systems use heuristics. Best fit packs tightly and leaves whole machines free for large tasks, but punishes misestimated requests and concentrates interference. Worst fit (spreading) keeps headroom for load spikes but fragments capacity, stranding resources that large tasks cannot use. Borg reports that a hybrid aimed at reducing stranded resources, such as CPU left on a machine whose memory is full, packs better than best fit for its workload. Kubernetes exposes similar choices through scoring strategies such as MostAllocated (pack) and LeastAllocated (spread).

Requests, limits and overcommit. Declared requests usually exceed actual use. Borg schedules production work against limits but lets batch work run in reclaimed resources, estimated from observed usage plus a safety margin. Compressible resources (CPU, I/O bandwidth) can be throttled; non-compressible ones (memory, disk) force a kill or eviction. Kubernetes QoS classes (Guaranteed, Burstable, BestEffort) encode a similar idea for eviction under node pressure. Overcommit is a statistical bet: uncorrelated workloads rarely peak together, and correlated peaks break the bet.

Priorities and quota. Higher-priority work may preempt lower-priority tasks; quota bounds how much high-priority work each user can submit, which keeps the high-priority load feasible.

Fairness across several resources. Dominant Resource Fairness gives each user a dominant share, the largest fraction they hold of any single resource, and equalizes dominant shares. Example: a cluster has 12 CPUs and 24 GB. User A's tasks need 1 CPU and 4 GB (memory-dominant, 1/6 of memory per task); user B's need 2 CPUs and 1 GB (CPU-dominant, 1/6 of the CPUs per task). Equal dominant shares mean equal task counts, and CPU caps both at 4 tasks: A gets 4 CPUs and 16 GB, B gets 8 CPUs and 4 GB, each with dominant share 2/3. DRF provides sharing incentive, strategy-proofness, envy-freeness and Pareto efficiency; asset fairness can violate sharing incentive, and competitive equilibrium from equal incomes is not strategy-proof.

Architectures (awareness). Monolithic schedulers (Borg, the default Kubernetes scheduler), two-level designs where a resource manager offers resources to framework schedulers (Mesos), and shared-state designs with optimistic concurrency (Omega). GPU clusters add gang scheduling (all workers of a job or none) and topology awareness.

Evaluation. Average utilization is a weak metric because it ignores headroom, constraints and SLOs. Borg compared policies with cell compaction: the smallest cell that still fits a fixed workload, over repeated randomized trials. Also report scheduling delay, SLO violations of latency-sensitive services, evictions, stranded resources and per-user fairness.

Common misconceptions

• "Best fit is the most efficient policy." It maximizes packing for a snapshot but raises eviction and interference risk when estimates are wrong; real schedulers blend scores.
• "Higher utilization is always better." For latency-critical services it trades against tail latency; batch work in reclaimed resources helps only if isolation holds.
• "Fair sharing of several resources means equal shares of each." Users need different mixes; DRF equalizes dominant shares instead.
• "Requests reflect real usage." They are often inflated, which is why reclamation and right-sizing exist.
• "Results on synthetic Poisson arrivals transfer to production." Real workloads have heavy tails, constraints and correlated arrivals; validate on traces and report sensitivity.

How to approach it

Compute a DRF allocation by hand, then write a small packing simulator over a trace sample and compare heuristics by machines needed and stranded resources. A typical research-interview prompt is "how would you evaluate a new packing policy?": answer with the workload source, baselines, metrics including SLO effects, methodology and threats to validity.