← Back to all questions
Senior / StaffSchedulingInfrastructure

Design a Distributed Job Scheduler

A Senior/Staff walkthrough of a job scheduler that places 1M+ jobs a day across 10K machines — balancing pickup latency against fair resource sharing, with leader election, lease-based exactly-once execution, cron triggers, and DAG dependencies. It leans on a durable Postgres job store and first-fit matching, then trades those choices against faster or more optimal alternatives. Follow it top to bottom, or jump to any step.

Level
Senior / Staff
Category
Scheduling · Infrastructure
Interview time
45 min
100% free · No login required
WHAT THIS QUESTION TESTS
·Leader-elected scheduler scans the queue and matches jobs to machines by resource fit and priority
·Lease + heartbeat protocol for at-least-once, idempotent execution
·Cron evaluator with a distributed lock so each schedule fires once
·DAG dependency resolution with cycle detection on submit
★ STAFF-LEVEL SIGNALS
★Picks a durable Postgres job store over volatile Redis because losing jobs is unacceptable
★Defends a single leader scheduler as the simplest path to 10K machines, with partitioning as the scale-out step
★Chooses first-fit-with-scoring over optimal bin-packing to keep scheduling latency low
★Prevents tenant starvation with per-queue quotas and round-robin fair sharing inside each priority level
1

Requirements

Functional Requirements

  • Submit jobs: Users submit tasks with resource requirements (CPU, memory, priority)
  • Schedule execution: Assign jobs to available machines based on resources and priority
  • Cron-like scheduling: Support recurring jobs (run every hour, daily, etc.)
  • Retry on failure: Automatically retry failed jobs with configurable policies
  • Job lifecycle: Track job status (queued, running, completed, failed)
  • Resource management: Fair allocation across teams/tenants
  • Dependencies: Jobs can depend on completion of other jobs (DAG)

Non-Functional Requirements

  • Scale: Schedule 1M+ jobs/day across 10K+ machines
  • Latency: Job picked up within seconds of submission
  • Reliability: No job lost — at-least-once execution guarantee
  • Fairness: No single tenant monopolizes resources
2

Back-of-envelope estimation

Metric
Estimate
Jobs submitted/day
1M
Job submission QPS
~12
Peak QPS
~50
Active machines
10K
Concurrent running jobs
50K
Recurring (cron) jobs
100K
Average job duration
10 minutes
Job metadata size
1 KB
3

API design

POST /api/v1/jobs
Body: { name, command, resources: {cpu, memory_gb}, priority, queue,
schedule: "0 */6 * * *", retry_policy: {max_retries: 3, backoff: "exponential"},
depends_on: [job_id_1, job_id_2], timeout_seconds }
Response: { job_id, status: "queued" }
 
GET /api/v1/jobs/{job_id}
Response: { job_id, status, machine_id, started_at, logs_url, attempts }
 
POST /api/v1/jobs/{job_id}/cancel
 
GET /api/v1/jobs?queue={name}&status={status}&cursor={cursor}
4

High-level architecture

┌──────────┐ ┌──────────────┐ ┌──────────────┐
│ Users / │────▶│ Job API │────▶│ PostgreSQL │
│ Services │ │ Service │ │ (job store) │
└──────────┘ └──────────────┘ └──────────────┘
│
┌──────────────┐ │
│ Scheduler │◀────────────┘
│ (leader- │
│ elected) │
└──────┬───────┘
│
┌──────────┼──────────┐
│ │ │
┌─────┴────┐ ┌──┴─────┐ ┌──┴─────┐
│ Worker │ │ Worker │ │ Worker │
│ Agent │ │ Agent │ │ Agent │
│(machine1)│ │(mach2) │ │(mach N)│
└──────────┘ └────────┘ └────────┘

Scheduler Design

Leader-elected scheduler (via ZooKeeper/etcd):

1. Scans job queue for eligible jobs (dependencies met, not over quota)

2. Matches jobs to machines based on: resource availability, locality, priority

3. Assigns job to worker agent on selected machine

4. Worker agent executes job, reports status back

Scheduling algorithm: Multi-level priority queue with fair sharing

  • Priority levels: Critical > High > Normal > Low
  • Within each level, round-robin across tenants/queues
  • Resource quotas per tenant prevent starvation
5

Deep dives

WHERE STAFF IS WON

Deep Dive 1: Exactly-Once Execution

Problem: Scheduler assigns job, but doesn’t get ACK (network issue). Is it running or not?

Solution: Lease-based execution

1. Scheduler assigns job with a lease (heartbeat timeout)

2. Worker must send heartbeat every 30 seconds

3. If no heartbeat for 90 seconds, scheduler considers job failed and reschedules

4. Worker checks lease before continuing (avoids duplicate execution after reschedule)

Deep Dive 2: Cron Scheduling

Implementation: Cron evaluator runs every minute

1. Evaluate all cron expressions against current time

2. For matching jobs, create a new job instance

3. Use distributed lock to ensure only one scheduler instance triggers each cron job

4. Store last-triggered time to handle scheduler restarts

Deep Dive 3: DAG Dependencies

Job A ──▶ Job C ──▶ Job E
Job B ──▶ Job D ──/
  • When Job A completes, check if all of Job C's dependencies are met
  • If yes, move Job C to "ready" queue
  • Cycle detection on job submission (reject cyclic DAGs)
  • If any dependency fails, mark downstream jobs as "blocked" and notify
6

Bottlenecks & tradeoffs

Decision
Option A
Option B
Choice
Scheduler
Centralized (single leader)
Distributed (partitioned)
Leader-elected single scheduler (simpler, works to 10K machines)
Job store
Redis (fast, volatile)
PostgreSQL (durable)
PostgreSQL (jobs are too important to lose)
Execution guarantee
At-most-once
At-least-once (with idempotency)
At-least-once
Resource matching
Bin-packing (optimal)
First-fit (fast)
First-fit with scoring heuristic

Monitoring

  • Job queue depth by priority: Alert if high-priority queue growing
  • Job wait time p99: Alert if > 5 minutes
  • Worker heartbeat failures: Detect dead machines
  • Scheduler failover time: Should be < 30 seconds
  • Job success rate: Alert if < 95%
★

Rubric — Senior vs Staff

Dimension
Senior signal
Staff signal
Scheduling model
Priority queue that matches jobs to free machines.
Multi-level priority with per-tenant fair sharing and quotas that stop any one tenant from monopolizing.
Execution guarantee
Retries failed jobs with a backoff policy.
Lease + heartbeat for at-least-once with idempotency; reschedules on a missed heartbeat without double-running.
Coordination
One scheduler assigns the work.
Leader election via etcd/ZooKeeper; reasons about failover time and the path to partitioned schedulers.
Dependencies & cron
Supports recurring jobs and simple dependencies.
DAG resolution with cycle detection and downstream blocking; distributed lock so each cron fires exactly once.
Durability tradeoffs
Stores jobs in a database.
Justifies Postgres over Redis and first-fit over bin-packing, naming the latency-vs-optimality cost.

Related questions

★ MORE WALKTHROUGHS

Want more breakdowns like this?

Join free early access for upcoming RAG, LLM eval, agents, and AI infrastructure walkthroughs.

Join Free Early Access →