Develop a deterministic GPU job scheduler with fairness guarantees: queue design,…
- User
Develop a deterministic GPU job scheduler with fairness guarantees: queue design, preemption strategy, telemetry, and escalation policies.
Assistant
The user wants a deterministic GPU job scheduler with fairness guarantees. This is a complex system design problem. I need to break it down into the requested components:
- Queue Design: How jobs are submitted, categorized, and prioritized.
- Preemption Strategy: How to handle resource contention (stopping lower-priority jobs for higher-priority ones) fairly.
- Telemetry: Monitoring and metrics for observability.
- Escalation Policies: Handling system failures or SLA breaches.
1. Core Concepts & Goals:
- Deterministic: Given a set of jobs and resources, the scheduler must produce the exact same allocation decision every time (assuming no state changes). This implies a strict, logical rule set rather than heuristics or randomness.
- Fairness: Resources shouldn't be hogged by a single user/group. Think Weighted Fair Queuing (WFQ) or Dominant Resource Fairness (DRF).
- GPU Context: GPUs are expensive and scarce. Fragmentation is a major issue (e.g., need 8 GPUs, only 2 available per node). NVIDIA MIG (Multi-Instance GPU) adds complexity.
2. Queue Design (The "Waiting Room"):
- Hierarchical Queues: Essential for organizational fairness.
- Level 1: Organization/Team.
- Level 2: User.
- Level 3: Job Priority.
- Queue Types:
- Guaranteed: Reserved capacity.
- Burstable: Can use idle capacity but can be preempted.
- Best-Effort: Low priority, runs only if nothing else is waiting.
- Logic: To achieve determinism, the scheduling loop shouldn't just pick the "first" job. It should calculate a "Global Score" based on
Weight+Wait Time+Resource Deficit. - Implementation: A Priority Queue based on logical timestamps (Lamport clocks or similar) to ensure strict ordering of submission events.
3. Preemption Strategy (The "Bouncer"):
- When to preempt? When a high-priority job needs resources currently held by a low-priority job.
- How to choose the victim?
- Lowest priority first.
- Most recent start time (minimize wasted work).
- Least checkpointed progress.
- The "Deterministic" aspect: The victim selection algorithm must be a strict function of job state, not random.
- Graceful vs. Forced:
- Graceful: Send SIGTERM, wait X seconds (allow checkpointing).
- Forced: SIGKILL.
- Gang Scheduling: GPUs often need all requested devices at once. Partial allocation is useless. Preemption must free up enough contiguous resources or resources across specific topologies (NVLink).
4. Telemetry (The "Cameras"):
- Need real-time data to feed the scheduler's logic.
- Metrics:
- GPU Utilization (SM, Memory, Power).
- Job Progress (epochs completed).
- Queue Depth (how many waiting).
- Wait Time.
- Tools: Prometheus, Grafana, maybe eBPF for low-level kernel metrics.
- Determinism Check: Log every decision with the state snapshot that caused it. "I picked Job A because A.score > B.score."
5. Escalation Policies (The "Manager"):
- What if the scheduler fails? Or a job is stuck?
- SLA Breaches: If a "Guaranteed" job waits > 1 hour -> Alert to Slack/PagerDuty.
- Starvation: If a "Best-Effort" job waits > 24 hours -> Temporary priority boost.
- Zombie Jobs: Job claims GPU but uses 0% utilization -> Kill.
6. Structuring the Response: I should structure this as a system design document or a technical specification.
- Architecture Overview: High-level diagram description.
- Component 1: Queueing Layer (Fairness & Determinism) -> Focus on Hierarchical Dominant Resource Fairness (HDRF).
- Component 2: Scheduling Logic (Determinism) -> The "Score" function.
- Component 3: Preemption (Resource Management) -> Graceful shutdown and victim selection.
- Component 4: Telemetry & Observability.
- Component 5: Escalation.
- Example Scenario: Walk through a conflict to prove it works.
Refining the "Deterministic" part:
- Standard schedulers often race for locks or use randomness to avoid convoy effects.
- To make it deterministic:
- Input: Sorted list of nodes (by ID), sorted list of queues (by ID).
- Algorithm: Iterate through nodes, find best fit.
- Conflict: If Job A and Job B have same score, use Job ID (Lexicographical order). This guarantees the exact same outcome every time.
Refining the "GPU" part:
- Mention MIG (Multi-Instance GPU) and Topology (NVLink). A simple bin-packing algorithm fails if it splits jobs across NUMA nodes poorly. The scheduler needs a "Topology Aware" filter.
Drafting the Content (Mental Sandbox):
- Fairness: Use DRF (Dominant Resource Fairness). If User A needs 4 GPUs and User B needs 1 GPU, User B shouldn't wait forever just because A arrived first. But how to make it deterministic? The "Dominant Share" calculation is deterministic.
- Preemption: "Kill the youngest" is usually best for efficiency, but "Kill the lowest priority" is best for SLA. Let's combine them.
Self-Correction during drafting:
- Don't just list tools (Kubernetes, Slurm). Design the logic. The user asked for a "job scheduler," which implies the algorithm/system, not just "install YuniKorn."
- Ensure the link between Telemetry and Preemption is clear. Telemetry detects "low utilization" which might trigger preemption even if priority is okay (to reclaim unused resources).
Final Plan:
- Intro: Define the constraints (Deterministic + Fair + GPU Topology).
- Queue Design: Hierarchical Fair Service (HFS) with strict ordering.
- Scheduling Algorithm: Deterministic Dominant Resource Fairness (DDRF).
- Preemption: The "Grace-Then-Force" protocol with checkpoint support.
- Telemetry: The feedback loop for utilization.
- Escalation: SLA management.
- Summary Table.
Let's write it out. Designing a deterministic GPU job scheduler requires moving away from "best-effort" heuristics (like simple priority queues) toward a state-machine approach where inputs always produce identical outputs.
Here is a comprehensive design for a Deterministic Fair-Share GPU Scheduler.
1. Architecture Overview
The scheduler operates on a Global Lock-Step Cycle. Unlike asynchronous schedulers that react immediately to events, this scheduler ticks at fixed intervals (e.g., every 5 seconds). Events (job completion, submission) are buffered and only processed at the start of the next tick. This ensures the state is consistent and reproducible.
2. Queue Design: Hierarchical Fair Service (HFS)
To guarantee fairness, we organize queues hierarchically (e.g., Team -> User -> Job). We use Start-Time Fair Queuing (SFQ) logic adapted for GPUs.
A. Structure
- Root: Total Cluster Capacity (e.g., 100 GPU-years/hour).
- Tier 1 (Org/Team): Allocated guaranteed shares (e.g., Team A: 40%, Team B: 60%).
- Tier 2 (User): Users within teams have weights.
- Tier 3 (Job): Individual workloads.
B. Deterministic Ordering
To ensure deterministic behavior when multiple jobs have identical priorities, the queue is sorted strictly by:
- Virtual Runtime (vruntime): (see below)
- Submission Time: Ties in vruntime are broken by timestamp.
- Job UUID: Lexicographical tie-breaking.
C. The "Virtual GPU" (vGPU) Model
We normalize everything to mGPU (milli-GPUs) equivalent to 1GB VRAM + 10% Compute.
- Job A: Needs 4 A100s (80GB) = 32,000 mGPU.
- Job B: Needs 1 T4 (16GB) = 4,000 mGPU.
3. Scheduling Algorithm: Deterministic Dominant Resource Fairness (DDRF)
We adapt Dominant Resource Fairness (DRF) to be deterministic.
The Logic (Per Tick
T):- Calculate Demand: Aggregate all pending jobs' requests.
- Calculate Entitlement: Determine how many mGPUs each user is entitled to based on their hierarchy weight.
- Calculate Deficit:
Deficit = Entitlement - Active_Usage.- If
Deficit > 0, the user is "under-served".
- Bin Packing (First-Fit Decreasing):
- Sort pending jobs by Deficit (High to Low).
- For the user with the highest deficit, attempt to place their oldest job.
- Topology Awareness: If the job requires NVLink, treat the required block as a single contiguous unit. If not, allow fragmentation.
4. Preemption Strategy
When a high-priority job arrives and resources are full, the scheduler must reclaim resources. Determinism requires strict rules on who gets killed.
A. The "Victim Selection" Algorithm
We do not kill randomly. We calculate a Preemption Score for every running job.
- Fairness Overuse: Jobs running for a user who is over their fair share get a high score (target for preemption).
- Runtime: Short jobs are penalized slightly less than long-running jobs (to avoid killing a job that is 99% done).
- Checkpointability: If telemetry indicates the job writes checkpoints frequently, it is safer to preempt.
The Deterministic Rule:
- Sort all running jobs by Preemption Score (Descending).
- Kill jobs one by one until the new High-Priority job fits.
- Tie-breaker: Job ID (Ascending).
B. Graceful Preemption (The 3-Stage Protocol)
- Signal
SIGTERM(Stage 1): The scheduler marks the pod as "Evicting". - Grace Period (60s): The job must catch the signal and checkpoint state to object storage.
- Signal
SIGKILL(Stage 2): Force termination.
5. Telemetry & Observability
To debug determinism, we need the Decision Log.
A. The "Why" Log
Every time a decision is made (Job X scheduled, Job Y preempted), the scheduler emits a structured log containing:
tick_id: The logical clock cycle.decision:SCHEDULE/PREEMPT/WAIT.target_job_id: The affected job.reason: "User A exceeded fair share by 20%" or "Insufficient VRAM on Node 3".state_snapshot_hash: A hash of the cluster state to verify no race conditions occurred.
B. Metrics
- Fairness Deviation:
(Actual_Usage - Entitled_Usage) / Entitled_Usage. - Preemption Churn: Rate of jobs killed per hour.
- Packing Efficiency:
(Used mGPU / Total mGPU).
6. Escalation Policies
Automation handles standard contention. Escalation handles systemic failures or SLA breaches.
Level 1: Automatic (The Scheduler)
- Trigger: Normal queue backlog.
- Action: Use Preemption Strategy.
- Deterministic Check: Is the waiting job
priority == CRITICAL? If yes, preempt immediately.
Level 2: Quota Re-balancing (The Controller)
- Trigger: A team is consistently idle, and another team is hitting quota limits.
- Action: "Quota Lending." If Team A uses < 20% of their quota for 24 hours, Team B automatically "borrows" 50% of the unused quota.
- Revocation: If Team A submits a job, the borrowed resources are flagged for reclamation immediately (Preemption Level 1).
Level 3: Manual Intervention (The Admin)
- Trigger: Starvation. A specific job waits >
MAX_WAIT_TIME(e.g., 4 hours). - Action:
- Alert fired to PagerDuty.
- Admin labels job as
scheduler-mode: bypass. - Scheduler enters Flood Mode: All non-essential jobs are checkpointed and paused to clear the queue for the bypass job.
Summary: The Determinism Checklist
Component Standard Scheduler Deterministic Scheduler Trigger Event-driven (immediate) Time-sliced (Batched ticks) Queue Priority Heap Sorted Linked List (Strict criteria) Fairness Heuristic Mathematical (DRF + vGPU math) Preemption Kill lowest priority Calculated Victim Score + Checkpointing Tie Breaker Random / Race condition Submission Time + UUID This design ensures that if you replay the same sequence of job submissions and cluster events, the scheduler will produce the exact same state at every step.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.