Fair and capacity scheduling
What does fair mean with several resources, and why is a capacity guarantee only as fast as its reclaim?
Fair scheduling
Fair scheduling means max-min fairness: maximize the smallest allocation, then repeat the same step on what is left.
In a cluster with one resource, this is well defined. In a real cluster it is not, because jobs want different mixes of resources. Tenant A's tasks need a lot of CPU and little memory, tenant B's the opposite. "Half the cluster" has no meaning.
Dominant Resource Fairness (DRF) solves this. For each tenant, find the resource of which it uses the biggest share of the cluster. That is its dominant resource. Then equalize each tenant's dominant share.
DRF gives A 3 tasks (3 CPU, 12 GB, so a dominant share of 12/18 = 67%) and B 2 tasks (6 CPU, 2 GB, dominant share 6/9 = 67%). Both tenants have the same dominant share. The cluster uses 9 of 9 CPU and 14 of 18 GB, so 4 GB of memory stays unused.
DRF is the only allocation in common use with a defensible set of properties:
- sharing incentive: each tenant does at least as well as with a private equal slice of the cluster;
- envy-freeness: no tenant prefers another tenant's allocation;
- strategy-proofness: a tenant cannot gain by lying about its demand.
But DRF is not the packing-optimal allocation. Fairness leaves resources stranded that a bin-packer would use (the 4 GB above). This is isolation versus utilization in its purest form.
Fairness is undefined until you say "fair in what." With multiple resources, the only stable answer is "an equal share of your own dominant one."
Capacity scheduling
Capacity scheduling gives each pool a guaranteed floor plus the right to borrow idle capacity above it. The interesting mechanism is not the guarantee. It is the reclaim.
A guarantee you cannot take back is not a guarantee. When the owner of the floor shows up and the borrower is using its slots, you have two choices:
- Preempt the borrower (stop its tasks now), or
- Wait for the borrower's tasks to finish naturally.
If you wait, your restoration time is about the p99 task duration of the borrower, not your promised service level. That is exactly what happened to the finance team. It is also why cluster systems impose maximum task lengths, and why long-running tasks corrode every quota system they touch. A guarantee is only as fast as the granularity at which resources are returned. (This is the "coarse unit" mismatch from storage, now in the control plane: you cannot take back less than a whole task.)
A guarantee is only as quick as the grain at which resources are handed back.
Comparing the five policies
| Policy | Info needed | Mean wait | Tail | Starvation |
|---|---|---|---|---|
| FIFO | none | poor | low variance | impossible |
| SRPT (ideal) | exact size | optimal | bad for large jobs | possible |
| MLFQ | none (observed) | near-SRPT | bad for large jobs | needs aging |
| Fair / DRF | current demand | middling | bounded | impossible |
| Capacity | declared quota | middling | bounded per pool | pool-level only |
A correction to folklore: "shortest-first starves big jobs"
People repeat that shortest-first scheduling starves big jobs, as if it were always true. It is not. Under heavy-tailed size distributions (which is what real query and job workloads look like), SRPT improves response time for most jobs, including most large ones. The reason: the huge mass of tiny jobs clears so quickly that large jobs face a nearly empty queue.
The starvation result holds when sizes have low variance. High variance is exactly when size-based scheduling is safest. That is the opposite of the intuition. (FIFO versus SRPT, on heavy-tailed and on steady job sizes lets you measure this.)