Gang Scheduling: All-or-Nothing Allocation for Distributed Workloads

A workload of forty workers that must all run at once is not schedulable by a scheduler that places one pod at a time. Placing thirty-nine of them and finding no room for the fortieth leaves thirty-nine workers occupying capacity while doing nothing, blocking whatever else might have used it, and holding the job in a state that cannot make progress and will not release. The problem is not capacity; it is the order in which capacity is committed. Gang scheduling is the family of mechanisms that makes the commit atomic.

Why partial placement deadlocks

The deadlock is structural rather than accidental. Consider a cluster with two nodes and two gang jobs, each needing one slot on both nodes. A scheduler that places pods individually might put job A’s first pod on node one and job B’s first pod on node two. Neither job can complete its gang, both hold half of what they need, and neither will release because neither has failed. Every subsequent job of either shape is blocked behind them.

The condition is a classic hold-and-wait. Each job holds resources while waiting for more, and the resources it waits for are held by another job doing the same. The standard deadlock-breaking remedies apply: acquire all resources at once (atomic allocation), or allow preemption so that a holder can be forced to release, or impose a global ordering so that hold-and-wait cannot form a cycle.

The atomic approach is what gang scheduling implements. The scheduler collects all members of the gang, decides on a complete assignment, and commits all of it or none of it. The decision is harder than a single placement because it is a joint assignment over many nodes, and it must be made without holding the cluster’s scheduling lock for an unbounded time.

Two-phase placement with reservations

The practical implementation separates the decision from the commit. In the first phase the scheduler simulates placements for each member against a snapshot of the cluster’s state, without mutating anything. If every member finds a node, the scheduler has a complete assignment. If any member fails, the scheduler discards the whole simulation and the job stays pending.

The naive form of this is expensive: a gang of a thousand members requires a thousand placement decisions against a state that may change between them. Implementations avoid the cost by treating the gang as a single unit in the scheduling queue — the queue holds jobs, not pods — and by computing the aggregate demand against each node’s remaining capacity in one pass. The aggregate view is what makes the joint decision tractable, and it is also what makes it conservative: a node with enough total capacity for the gang’s members may still not have a shape that fits them individually.

If the first phase fails, the scheduler can either wait or reserve. Waiting is cheap and correct but leaves the job queued behind smaller jobs that keep consuming the capacity it needs, a condition known as starvation under continuous arrival. Reserving means the scheduler marks capacity for the pending gang and refuses to give it to other jobs, which guarantees the gang eventually runs and costs the cluster the use of that capacity until it does.

The choice between waiting and reserving is a policy about which failure is worse: a large job that never runs, or capacity that idles while a large job waits. Batch schedulers for research clusters typically reserve, because a job that never runs is a worse outcome than idle capacity. Schedulers for multi-tenant platforms typically do not, because reserving one tenant’s capacity for a job that may never fit is a denial of service against the others.

Backfill and the estimate it depends on

The reservation scheme’s efficiency depends on a technique called backfill. While a large job waits for its reservation, smaller jobs may run in the reserved capacity provided they will finish before the reservation’s start time. This keeps the cluster busy without delaying the large job, and it requires knowing how long the small jobs will take.

The estimate comes from the job’s declared duration or from a historical model, and it is the scheme’s weak point. A job that declares ten minutes and runs for an hour will still be running when the reservation begins, and the large job will be delayed or the small job will be killed. Real schedulers handle this by conservative estimates, by killing overrunning jobs, or by a checkpoint mechanism. Each is a cost: conservative estimates waste capacity, killing loses work, checkpointing requires the workload to support it.

Backfill’s benefit is bounded by the accuracy of the duration estimate. When estimates are accurate, a cluster can run near full utilization while honouring reservations. When estimates are systematically optimistic, the scheduler either has to add margin — reducing the benefit — or accept that reservations slip.

Preemption as the alternative

Instead of reserving future capacity, a scheduler can reclaim current capacity. When a gang cannot be placed, the scheduler chooses a set of running jobs whose removal would make room, evicts them, and places the gang. The evicted jobs return to the queue, possibly with their priority lowered or their place preserved.

Preemption avoids idle capacity entirely, because nothing is reserved ahead of time. Its cost is borne by the victims, and the cost is proportional to how much work they lose. A victim that can checkpoint loses little; one that cannot loses everything since its last checkpoint. The scheduler must therefore rank victims by a combination of priority and replacement cost, and the ranking is where the policy lives.

The preemption path also needs a bound on how much it will evict. A gang that requires evicting half the cluster to place is technically schedulable and practically a denial of service. Schedulers impose a maximum eviction budget, and gangs that exceed it wait instead. The budget converts the preemption decision into a policy about acceptable disruption rather than a pure optimization.

place(gang):
  if try_place(gang, snapshot) succeeds:      # phase 1: simulate
      commit(assignment)                       # phase 2: atomic bind
      return
  victims = select_victims(gang, max_budget)
  if cost(victims) <= budget:
      evict(victims); place(gang, fresh_snapshot)
  else:
      queue_with_reservation(gang)             # wait, possibly reserving

The max_budget term is what distinguishes a scheduler that behaves predictably from one that does not. Without it, a single oversized gang can churn the entire cluster; with it, the gang’s behaviour is bounded and the operator can reason about worst-case disruption.

The interaction with the rest of the compute model

Gang scheduling changes the meaning of several quantities elsewhere in the model. Utilization is no longer a simple ratio, because reserved-but-idle capacity counts as used for scheduling purposes and as free for measurement purposes. The gap between the two is the price of the guarantee, and it is invisible in most utilization dashboards.

It also changes the placement problem from a sequence of independent decisions into a single large one. Fragmentation matters more, not less: a gang needing a thousand identical slots will fail against a cluster that has a thousand slots of free capacity scattered in holes of ten. The scheduler’s aggregate view can see the total, but the fit test is still per-node, and a cluster that is fragmented cannot host a large gang no matter how much free capacity it reports.

Finally, it changes the meaning of elasticity. A workload that must run as a gang cannot shrink to fit available capacity; it either runs at its full size or not at all. This makes it the natural opposite of the autoscaling loop, which assumes a workload whose size is a free variable. Platforms that host both must decide which class gets priority when capacity is scarce, and that decision is a policy about what the platform is for.

Where the mechanism is implemented

Gang scheduling can live in the platform scheduler or in a layer above it. In the former case the scheduler understands job units natively, which makes the atomic commit efficient and the accounting exact. In the latter case a controller creates pods with a group label and a separate scheduler observes them, placing them only when the whole group can be placed; the platform scheduler is bypassed for those pods. The second arrangement is portable across platforms and pays for it with a second source of scheduling truth, which can disagree with the platform’s view of capacity.

The disagreement is the operational hazard. A gang scheduler that holds pods pending while reserving capacity in its own accounting is invisible to the platform’s autoscaler, which sees pending pods and adds nodes. The cluster grows to accommodate a gang that was never going to fit, and the extra nodes remain empty. This is why gang scheduling and cluster autoscaling are usually configured with an explicit relationship: either the gang scheduler reports its reservations to the autoscaler, or the autoscaler is told to ignore the gang’s pending pods.