Design a Distributed Job Scheduler

Plenty of systems need work to happen later: send a reminder in 24 hours, run a report every night at 2am, retry a failed webhook in 5 minutes, bill every subscription monthly. “Design a job scheduler” (or a distributed cron, or a delayed-task queue) tests whether you can separate deciding what’s due from running it reliably — and whether you can do the first part without scanning millions of rows every second.

Understanding the Problem

Functional Requirements

1. Schedule a job — Submit a one-off job to run at a specific time, or a recurring job with a cron expression.
2. Execute at (or after) the scheduled time — Run the job close to when it is due.
3. Reliability — A job runs even if a scheduler or worker crashes (at-least-once).
4. Retries — A failed job is retried with backoff, and dead-lettered after N attempts.
5. Cancel / update — A pending job can be cancelled or rescheduled.
6. Status — Query whether a job is pending, running, succeeded, or failed.

Non-Functional Requirements

Scale Estimation

• 100M active scheduled jobs stored.
• Suppose peak of 5M jobs due in the same minute (e.g. “run at midnight”) → ~83K enqueues/sec, bursty.
• Each job record is small (~1 KB) → ~100 GB of job metadata, comfortably sharded across a database.

The bursty “everything at midnight” pattern is the tell: the scheduler must find and enqueue a huge batch of due jobs quickly, and the execution layer must absorb the spike without being overwhelmed.

Core Entities and APIs

Data Model

Job = {
    job_id:       uuid
    type:         string        # what to run (handler name)
    payload:      json          # arguments
    schedule:     string|null   # cron expr for recurring; null for one-off
    next_run_at:  timestamp     # THE field everything is indexed by
    status:       enum          # PENDING | QUEUED | RUNNING | SUCCEEDED | FAILED
    attempts:     int
    max_attempts: int
    lock_until:   timestamp     # visibility timeout while running
    owner:        string|null   # which worker holds it
}

# Critical index:
INDEX idx_due ON Job (next_run_at) WHERE status = 'PENDING'

The whole design hinges on next_run_at and its index. Everything else is bookkeeping.

API Design

POST /jobs
  body: { type, payload, run_at? , cron? }
  response: { job_id }

DELETE /jobs/{job_id}        # cancel a pending job
PATCH  /jobs/{job_id}        # reschedule
GET    /jobs/{job_id}        # status + attempt history

High-Level Design

The system splits cleanly into two halves:

• The scheduler decides what is due now. A due poller wakes up every second or so, asks the schedule store for jobs with next_run_at <= now, and enqueues them onto a task queue. It does not run the jobs itself.
• The execution layer actually runs the work. A task queue (SQS, Kafka, or a Redis list) buffers due jobs; a worker pool pulls jobs, executes the handler, and records the outcome in the status store with retries.

This separation is the single most important idea. The scheduler is a lightweight timer; the workers are the scalable, isolated compute. Because they’re decoupled by a queue, a flood of midnight jobs piles up in the queue and drains at the workers’ pace — no job is lost, and the scheduler never blocks on slow work.

Deep Dive: Finding What’s Due Without Scanning Everything

The naive design — scan all jobs each tick and check whether each is due — is O(total jobs) per tick and dies at scale. The fix is to keep jobs ordered by their next run time so the poller only touches the ones that are actually due.

• Database index. Index PENDING jobs on next_run_at. The poll becomes SELECT ... WHERE next_run_at <= now() AND status = 'PENDING' LIMIT 1000 — an index range scan that reads only due rows. Simple, durable, and usually enough.
• Redis sorted set (ZSET). Store job_id with next_run_at as the score. ZRANGEBYSCORE jobs -inf now returns due jobs in time order, and ZPOPMIN pops the soonest — all O(log n). Great for a very high-throughput, low-latency timer, backed by the database for durability.
• Hierarchical time wheel. For in-memory schedulers (think a single node’s timers), a time wheel buckets jobs by when they fire and advances a cursor, giving O(1) insertion and expiry. Used inside systems like Kafka for purgatory/timeouts.

For a one-off job, next_run_at is just its run time. For a recurring job, when it fires you compute the next occurrence from its cron expression and write it back — so a cron job is simply a one-off job that reschedules itself after each run.

Deep Dive: Reliable, Isolated Execution

Once a job is on the queue, the execution layer must run it exactly as reliably as any task-queue system (this is the Managing Long-running Tasks pattern).

• At-least-once + idempotency. Deliver each job at least once and make handlers idempotent (dedupe on job_id + attempt, or make the effect naturally repeatable). A worker that crashes mid-job must be safe to retry.
• Visibility timeout / lease. When a worker claims a job it sets lock_until = now + timeout and status = RUNNING. If it finishes, it marks the job done; if it dies, the lease expires and another worker picks the job back up. This is how you survive worker crashes without a job vanishing or running forever.
• Retries with backoff and a DLQ. On failure, increment attempts, and if under max_attempts, reschedule with exponential backoff and jitter; otherwise move it to a dead-letter queue for inspection. Backoff keeps a persistently failing dependency from being hammered.
• Isolation. A slow or poisoned job must not starve others. Separate queues (or priorities) per job type, and bounded concurrency per type, keep one bad job from blocking the fleet.

# Worker loop
job = queue.poll()
if store.claim(job.id, lease=30):          # atomic: set RUNNING + lock_until
    try:
        if not store.already_done(job.id): # idempotency guard
            run_handler(job.type, job.payload)
        store.complete(job.id)
    except Exception:
        store.fail_with_backoff(job.id)    # retry or dead-letter

Deep Dive: Exactly-Once Enqueue Across Many Schedulers

For availability you run multiple scheduler instances — but then two of them could read the same due job and enqueue it twice. At-least-once execution tolerates a duplicate, but you still want to minimise it, and some setups need near-exactly-once enqueue. Options:

• Atomic claim. When the poller reads a due job, it conditionally updates it in the same operation — UPDATE ... SET status='QUEUED' WHERE id=? AND status='PENDING'. Only one scheduler’s update succeeds, so only one enqueues it. With a Redis ZSET, ZPOPMIN is atomic and pops each job to exactly one caller.
• Sharding / leader election. Partition the job space (by hash of job_id) across scheduler instances so each shard has a single owner, using a coordination service (ZooKeeper/etcd) for leader election and failover. Each job is thus the responsibility of exactly one scheduler at a time.
• Idempotent enqueue key. Enqueue with a dedup key of job_id + scheduled_time so even a duplicate enqueue collapses to one queue entry.

In an interview, call out the duplicate-enqueue hazard explicitly and resolve it with an atomic conditional claim plus idempotent workers — that combination gives correct behavior without a heavyweight distributed transaction.

Key Takeaways

A job scheduler is deceptively deep: the “schedule a job” API is trivial, but the interview lives in two places — finding due jobs without a full scan (index by next-run-time) and enqueueing each exactly once while executing at-least-once (atomic claim + idempotent workers). Draw the scheduler/queue/worker split first, then go deep on those two, and you’ve covered what matters.