Prompt and context
A shared compute cluster runs interactive jobs, batch work, and preemptible training. Tenants may burst, but no tenant may hold unlimited CPU, memory, or GPU. High-priority work needs lower wait time while low-priority tenants must not starve.
Design queues, a resource ledger, scheduling policy, preemption, and recovery. Kubernetes separates PriorityClass, ResourceQuota, and preemption; IETF queue-management guidance likewise treats fairness and congestion control as related constraints rather than a single global FIFO.
What the interviewer is testing
- Separating tenant quota, job priority, and node feasibility.
- Defining fairness that cannot starve low-priority work.
- Bounding preemption side effects, retry amplification, and fragmentation.
- Recovering from scheduler failure, duplicate dispatch, and worker loss.
- Proving fairness with tenant-level metrics instead of cluster averages.
Clarifying questions
- Are resources CPU, memory, GPU, or heterogeneous nodes with local disks?
- Are quotas scoped by tenant, project, queue, or organization?
- May priority preempt work, and what is checkpoint recovery cost?
- Can jobs split, cancel, or retry, and are result writes idempotent?
- Is fairness max-min share, weighted share, or a wait-time bound?
Thirty-second answer
I would maintain quota, usage, and expiring borrow capacity per tenant, then place jobs in tenant-level queues. After filtering node constraints, the scheduler selects the most underserved tenant by weighted fair service; aging raises effective priority so work cannot starve. Preemption is allowed only when policy, quota, and recovery make it safe. Reservations, leases, and fencing tokens are durable, and metrics are sliced by tenant, queue, and resource type.
Step-by-step design
Step 1: Build the resource and quota ledger
Represent CPU, memory, GPU, and node labels as a resource vector. Long-lived usage consumes tenant quota; burst borrowing expires. Reserve resources atomically before dispatch and return them on completion, cancellation, or lease expiry. Enforce quota at admission and scheduling so a caller cannot bypass it with a high priority.
Step 2: Use hierarchical queues and fair selection
Layer organization, tenant, and job class, then select among runnable tenants by weight. Track virtual service or recent resource use and choose the underserved tenant; add bounded aging after a wait threshold. A global priority queue can let a large tenant own the head forever, while tenant-level rotation makes the fairness boundary explicit.
Step 3: Bound priority, borrowing, and preemption
Priority represents urgency, not unlimited capacity. Borrowing is limited to idle capacity or an explicit window. Before preempting, estimate released resources, checkpoint cost, and victim budget; prefer low-priority recoverable work. If recovery is not provably safe, let the urgent job wait instead of risking duplicate side effects.
Step 4: Filter nodes and control fragmentation
Filter architecture, GPU model, zone, affinity, and capacity before scoring nodes. Mixing large and small requests in one queue creates fragments; reserve a bounded pool for large shapes and set a wait limit. Record rejection causes separately: total capacity, shape mismatch, and exhausted quota.
Step 5: Dispatch with leases and idempotent recovery
Persist a versioned reservation. Workers claim a short lease with a fencing token. A duplicate dispatch is checked by (job_id, attempt); only a newer token may take over an expired lease. Release the reservation after result commit. On scheduler restart, rebuild unfinished jobs from the log or database rather than guessing from memory.
Step 6: Handle failure, cancellation, and retries
Mark a lost worker unknown first, then reclaim after the lease and heartbeat window. Resume recoverable jobs from checkpoints; non-idempotent effects require status lookup or compensation. Retries consume tenant and job budgets with capped backoff. Recovery must not re-dispatch every timed-out task at once.
Step 7: Scale capacity and change policy
Publish versioned policy when nodes or weights change. Keep the old policy for already queued jobs and migrate new work gradually; a weight change must not instantly revoke promised share. Track scarce GPU, zone, and local-disk resources separately, with audit events for borrowing and reclamation.
Step 8: Verify fairness and efficiency
Load-test synthetic and real workloads: one saturated tenant, several slow tenants, random node loss, checkpoint recovery, and hot policy changes. Measure tenant wait p50/p95, resource share, maximum starvation interval, preemptions, duplicate execution, queue age, fragmentation, and recovery time. Compare FIFO, strict priority, and fair scheduling to show the trade-off.
High-quality sample answer
I would separate quota, priority, and node feasibility. Tenant queues are chosen by weighted underserved service plus bounded aging. Borrowing uses expiring idle capacity; preemption requires a recovery proof, quota check, and checkpoint budget. Every assignment persists a reservation, lease, and fencing token, while results are idempotent by attempt. The scheduler rebuilds from its log and retries consume tenant budgets. Failure tests create a noisy neighbor and worker loss, then compare tenant wait, share, starvation, duplicate work, fragmentation, and recovery time.
Common mistakes
- One global priority queue → a large tenant owns the head → choose a tenant before a tenant-local job.
- Treating quota as priority → urgent work bypasses limits → keep quota checks atomic and independent.
- Unbounded preemption → checkpoint cost and duplicate effects explode → add budgets and cooldowns.
- Memory-only queues → restart duplicates or loses dispatch → persist reservations, leases, and tokens.
- Cluster averages only → a tenant can starve invisibly → slice wait and share by tenant.
- Immediate retry after worker loss → the old execution may still run → wait for fencing or use an idempotent path.
Follow-up questions
How do you prove no starvation?
Reserve a minimum service share for every runnable tenant and cap aging. Under fixed capacity and continuously schedulable work, verify that maximum wait stays within the policy bound.
How do you avoid duplicate billing after preemption?
Bill the logical job or committed stage, not every attempt. External effects use an idempotency key and status lookup.
What if quota conflicts with idle capacity?
Allow expiring borrowing and record reclaimable capacity. Stop new borrowing first, then wait for completion or preempt only recoverable work.
Does the scheduler need strong consistency?
Reservations, leases, and fencing need linearizable conditional updates; dashboards may be asynchronous. A stale cache must not allocate the final GPU.
When is fair scheduling unnecessary?
For one tenant, fixed batch windows, or strict priority where starvation is accepted, a simple priority queue is easier to verify.
What triggers rollback?
Duplicate execution, failed recovery, a wait bound breach, or a tenant share outside budget stops the new policy. Restore the old version and retain reservation logs for replay.