TL;DR: State machine: SUBMITTED → QUEUED → PLACING → RUNNING → (CHECKPOINTING → PREEMPTED → QUEUED) or COMPLETED or FAILED, with PREEMPT_REQUESTED as the transition that gives a victim a bounded grace period to checkpoint before it is killed. The tick orders queues by fair share, takes head jobs, places gangs all-or-nothing with topology awareness, reserves for the head and backfills around it, and preempts borrowed gangs by cost T/2 + R, cheapest first. At 100k jobs the tick indexes by (tenant, size class) so it touches queues, not jobs; state lives in a durable log so a scheduler restart replays rather than loses.
How to approach it
Ask the mix (how many jobs are gangs of hundreds of GPUs, how many are single-GPU), the cluster size, whether jobs declare checkpointability, and what fairness means to the organization. Say the scheduler is three things: a state machine per job, a tick that places, and a policy for whom to evict. Draw the state machine first because the preemption path is the part that gets the follow-ups. Then the data model, the tick with its scaling argument, the preemption arithmetic and failure handling.
A strong answer
A typical situation: 16,384 GPUs, 30 teams, 100,000 jobs in the system on a busy day of which about 20,000 run at once, sizes from one GPU to 2,048, training runs that checkpoint, and evals and sweeps that are elastic. GPU Job Scheduler Design gives the loop; this answer is about making it survive preemption at this job count.
The transition that matters. PREEMPT_REQUESTED is a message to the job, not a kill. The job acknowledges, checkpoints within a grace window (say 120 s, or its declared checkpoint time), and exits; the scheduler kills it only when the window expires. Without this state, every preemption costs the full checkpoint interval; with it, a job that checkpoints in 40 s loses 40 s. A job that declared itself non-checkpointable is never preempted unless it opted into preemptible pricing.
Data model. Job (tenant, GPUs, shape, priority, checkpointable, checkpoint interval, last checkpoint time, resume pointer, max runtime, min GPUs if elastic). Node (pod, rail, GPU type, free GPUs, health, allocations). Queue (tenant, guaranteed quota, borrow limit, decayed usage). Allocation (job → set of (node, GPU), start, preemptible). The two fields that make preemption cheap are on the job: last checkpoint time and resume pointer.
The tick at 100k jobs.
naive tick: scan 80,000 queued jobs, try to place each → O(jobs × nodes) per tick, tens of seconds
indexed tick:
queues keyed by (tenant, size class: 1, 2 to 8, 9 to 64, 65 to 512, 513+), each a priority-then-age heap
free-capacity index per pod: whole free nodes, partial nodes with k free GPUs
per tick: order the ~150 (tenant, class) heaps by fair share; pop heads; for each head, query the pod index
for a fit; admit, reserve, or backfill; stop after a time budget of 2 s
work per tick ≈ heaps × log(jobs per heap) + placements × pods, well under a second
events (submit, complete, fail, node health change) trigger a tick early; otherwise every 5 s
sanity: 100,000 jobs in 150 heaps is about 700 per heap; a heap pop is 10 comparisons; the tick is
bounded by placements, not by queue length
Placement. Gang scheduling admits all-or-nothing, with the head job's reservation accumulating freed nodes so backfill cannot starve it: smaller jobs run only if they will finish before the reserved start (they need a max runtime for this). Topology: fit the gang inside one pod, then the fewest pods; pack partial-node jobs onto already-partial nodes so a 64-GPU gang does not wait behind 800 idle GPUs scattered four per node.
Whom to preempt. When team A's head job is under quota and cannot fit, evict borrowed gangs (jobs running above their team's guarantee) until it does.
victim cost = T/2 + R, or (now − last checkpoint) + R with the grace path
a sweep job checkpointing every 5 min, restart 1 min: expected loss ≈ 3.5 min × 8 GPUs ≈ 0.5 GPU-hours
a 512-GPU run checkpointing every 30 min, last checkpoint 25 min ago, restart 10 min: 35 min × 512 ≈ 300 GPU-hours
order candidates by (usage ÷ quota) descending, then by cost ascending; prefer many small cheap victims
over one expensive one when the GPU-hours lost are lower
cap: at most 2 preemptions per job per day; a job past the cap is protected until it completes
sanity: without the last-checkpoint field the scheduler cannot tell the 0.5 GPU-hour victim from the
300 GPU-hour one, and picks by priority alone
Durability and failure. Every transition is appended to a log before it takes effect; the in-memory state is a projection rebuilt at startup, so a scheduler crash loses nothing and a restart takes the time to replay a day of transitions (100k jobs × a dozen transitions is about a million records, seconds). One leader with standbys on a lease. A node death marks its allocations broken; checkpointable jobs go RUNNING → QUEUED with their resume pointer, elastic jobs shrink, and everything else fails after its retry budget.
The trade-off to commit to: preempt with a grace window rather than kill immediately. The window delays the entitled job by up to two minutes and saves the victim up to a full checkpoint interval. The reversal condition: an interactive tier (notebooks, debugging sessions) where the entitled job's wait is the SLO, which gets a small reserved slice instead of preemption rights. GPU Job Scheduler Design covers the queue structure, Gang Scheduling with Kueue and Volcano covers the admission it has to respect, and squeue or the pending reason on a job object is what a waiting user needs to see.
What interviewers probe next
- "A team submits a 2,048-GPU job at 4pm; when does it start?" Walk the loop: fair share ranks it, the reservation accumulates freed nodes, backfill keeps the cluster busy meanwhile, preemption of borrowers fires if the team is under quota; the estimate is shown to the team from the reservation.
- "What stops a job ignoring PREEMPT_REQUESTED?" The grace timer; on expiry it is killed and its last checkpoint stands, and the incident is charged to the job's preemption cap.
- "How do you avoid two head jobs deadlocking on partial gangs?" All-or-nothing admission: neither holds any GPU until the whole gang is found.
Common mistakes
- A priority queue with first-fit placement, which deadlocks on the first two gangs that arrive together.
- Preemption as SIGKILL, so the victim loses the whole checkpoint interval every time.
- Scanning the full job list per tick.
- Keeping state only in memory, so a scheduler restart orphans 20,000 running jobs.
Key takeaways
- The state machine's key transition is PREEMPT_REQUESTED → CHECKPOINTING → PREEMPTED with a bounded grace window.
- Index queues by (tenant, size class) so the tick scales with heaps and placements, not jobs.
- Victim cost = time since last checkpoint + restart; order by usage ÷ quota, then cost; cap preemptions per job.
- All-or-nothing gangs, a reservation with backfill, durable transition log, leader with standbys.