Back to Notes

Design a Distributed Job Scheduler

1. Problem & Real-World Context

Design a system that schedules and executes jobs (cron-style recurring tasks, or one-off delayed jobs) reliably across a fleet of worker machines. The defining challenge is exactly-once-ish execution in a system that's fundamentally at-least-once — two scheduler instances (for high availability) must never both fire the same job at the same time, but the system also must guarantee a job isn't silently dropped if the instance that claimed it crashes mid-execution.

2. Requirements

Functional: schedule a job to run at a specific time or on a recurring cron-like schedule; execute the job on some available worker; retry failed jobs (with backoff); support job cancellation/updates.

Non-functional: a job must run at least once, and ideally not more than once for non-idempotent jobs (exactly-once execution is the aspiration, at-least-once with idempotency is the realistic guarantee — see §7); high availability (the scheduler itself can't be a single point of failure); horizontally scalable (many more jobs than any single machine can execute).

3. Capacity Estimation

  • At, say, 10M scheduled jobs across the system, with jobs distributed across time (not all firing simultaneously), the actual bottleneck is rarely raw job count — it's ensuring the claim mechanism (which worker gets to execute a given due job) doesn't itself become a contention point when many jobs come due around the same moment (e.g., a burst of jobs all scheduled for midnight).
  • Scheduler state size: 10M pending jobs, each a small record (job ID, next-run time, payload reference, retry count) — comfortably fits a horizontally-partitioned store; the interesting scaling question is query pattern ("give me all jobs due in the next N seconds"), not raw storage volume.

4. High-Level Architecture

flowchart LR
    API[Scheduling API] --> JobDB[(Job Store<br/>partitioned by next_run_time)]
    Poller[Scheduler Poller<br/>multiple instances] --> JobDB
    Poller -->|claim due jobs| Lease[Lease/Lock<br/>per job]
    Poller --> Queue[Execution Queue]
    Queue --> Workers[Worker Fleet]
    Workers -->|success/failure| JobDB
    Workers -->|failure| Retry[Retry with backoff]

Walking a job's lifecycle: a job is scheduled via the API, stored with its next_run_time → a fleet of scheduler poller instances periodically query the job store for jobs due now (or in the near future) → a poller claims a due job via a lease/lock mechanism (§5) so no other poller instance also claims it → the claimed job is pushed onto an execution queue → a worker picks it up and executes it → on success, the job's state updates (and its next_run_time is recomputed if recurring); on failure, it's retried with backoff (§6) or eventually dead-lettered.

5. The Core Problem: Exactly-One Claim Among Multiple Schedulers

Running only one scheduler instance is a single point of failure; running multiple naively risks two instances both seeing the same due job and both dispatching it — a duplicate execution. The claim must be atomic.

import time

def try_claim_job(job_id: str, worker_id: str, lease_seconds: int = 30) -> bool:
    """Atomic compare-and-set: claim only if unclaimed or the previous lease expired."""
    now = time.time()
    return job_store.conditional_update(
        job_id,
        condition="claimed_by IS NULL OR lease_expires_at < :now",
        update={"claimed_by": worker_id, "lease_expires_at": now + lease_seconds},
        params={"now": now},
    )

Why a leased claim, not a permanent one: if the poller/worker that claimed a job crashes mid-execution, a permanent claim would mean that job is stuck forever, claimed by a dead process, never retried. A lease (a claim with an expiry) means an abandoned job's claim naturally expires, and another poller can claim and retry it — this is the same lease-based-lock pattern that shows up generally in distributed coordination (analogous to how a distributed lock service like ZooKeeper/etcd sessions work), applied here specifically to job ownership. The conditional update (claimed_by IS NULL OR lease_expires_at < now) is the atomicity-critical part — this must be a single atomic operation (a compare-and-set at the storage layer), not a separate read-then-write, or two pollers could race past a plain read-based check exactly like the [[Parking Lot]] spot-allocation race.

6. Retry with Backoff

A job that fails (transient error — a downstream service was briefly down) shouldn't be retried instantly and repeatedly at full speed, nor should it be permanently abandoned after one failure.

def schedule_retry(job: dict) -> None:
    job["retry_count"] += 1
    if job["retry_count"] > job["max_retries"]:
        move_to_dead_letter(job)             # exhausted retries — needs human/ops attention
        return
    backoff_seconds = min(2 ** job["retry_count"], 3600)   # exponential, capped at 1 hour
    job["next_run_time"] = time.time() + backoff_seconds
    job_store.update(job)

This is the same exponential-backoff-plus-DLQ pattern as [[Notification System]]'s dispatch retry logic — a poison-pill job (one that will never succeed, due to a bug or permanently invalid input) must not retry forever, consuming worker capacity indefinitely; routing to a dead letter queue after a bounded number of attempts isolates the failure for manual inspection.

7. Recurring Jobs & Idempotency

For a cron-style recurring job, after each successful execution the scheduler computes the next next_run_time (from the cron expression) and reschedules — the job record persists across executions rather than being a one-shot entity.

Idempotency is the job's responsibility, not the scheduler's — the scheduler can only guarantee at-least-once execution (the lease mechanism minimizes but can't perfectly eliminate the possibility of a job running twice, e.g., if a worker completes a job but crashes before reporting success, causing a retry of an already-completed job). A job that sends an email or charges a payment must itself be idempotent (the same Idempotency-Key pattern as [[Payment System]] and [[API Design Principles]]) — the scheduler's job is minimizing duplicate execution, not eliminating the need for the job itself to tolerate rare duplicates gracefully.

8. Querying "What's Due Now" Efficiently

Partition the job store by next_run_time (or a derived time-bucket key) so "find jobs due in the next N seconds" is a range scan over a small, relevant slice of the data rather than a full scan — this is the same reasoning as the News Feed problem's Cassandra partition-by-time design, applied to scheduled jobs instead of posts. A secondary index or a time-bucketed partition scheme (e.g., one partition per minute) keeps this query cheap even as total job count grows into the millions.

9. Deep Dives / Follow-ups

  • Job priority: some jobs are more urgent than others — a priority field feeds into which jobs a poller claims first when many are simultaneously due, the same priority-queue reasoning as the Notification System's tiered queues.
  • Distributed cron (avoiding thundering herd at common times): many recurring jobs scheduled for exactly midnight/on-the-hour create a burst — jittering actual execution time slightly (e.g., ±30 seconds) for non-time-critical recurring jobs smooths this out, the same "avoid a synchronized spike" reasoning that shows up in cache TTL jitter to prevent mass simultaneous expiry.
  • Long-running jobs: a job that takes hours needs the lease to be periodically renewed (a heartbeat from the worker while it's still actively running, extending the lease) rather than using one long fixed lease upfront — otherwise a legitimately-still-running job's lease could expire and get falsely reclaimed as abandoned.

10. Interview Drill Questions

  1. Why use a leased claim instead of a permanent one when a poller claims a job? — If the claiming poller or worker crashes mid-execution, a permanent claim leaves the job stuck forever (claimed by a process that no longer exists, never retried); a lease naturally expires, letting another poller reclaim and retry the job — trading a small risk of duplicate execution (if the original process was actually still working, just slow) for guaranteed forward progress.
  2. Two scheduler poller instances query for due jobs at the same moment and both see the same job as unclaimed. What prevents both from executing it? — The claim itself must be an atomic conditional update (compare-and-set on claimed_by/lease_expires_at) at the storage layer, not a separate read-then-write — exactly the same check-then-act race and fix as [[Parking Lot]]'s spot allocation, applied to job ownership instead of physical spots.
  3. A long-running job's lease expires while it's still legitimately executing (just slow, not crashed). What happens, and how do you avoid it? — Without a fix, another poller could reclaim and re-execute the job while the original is still running — a genuine duplicate-execution risk. Fix: the worker periodically heartbeats to extend its own lease while still actively working, so the lease only expires if the worker has actually stopped reporting (crashed or hung), not merely because the job takes a long time.
  4. How do you guarantee a payment-processing job never runs twice, given the scheduler only guarantees at-least-once? — You don't rely on the scheduler for that guarantee at all — the job itself must be idempotent (the same Idempotency-Key pattern as the Payment System page), since the scheduler's lease mechanism minimizes but cannot perfectly eliminate rare duplicate execution.
  5. Thousands of recurring jobs are all scheduled for exactly 00:00:00. How do you avoid a load spike at that instant? — Add a small random jitter to each job's actual execution time (e.g., ±30 seconds) for jobs where exact timing doesn't matter — spreading a synchronized burst into a smoother distribution, the same anti-thundering-herd technique used for cache TTL jitter.

Cross-links

[[Notification System]] · [[Payment System]] · [[API Design Principles]] · [[Parking Lot]] · [[Message Queues & Kafka]]