Design a Distributed Job Scheduler
Problem
Design a service that lets internal teams schedule work to run later. A job is either one-off (run at a specific time) or recurring (on a cron expression), and each run executes a task such as calling an HTTP endpoint or running a container. Failed runs must be retried with backoff, and users must be able to see the status and history of every run. The system should hold 10 million active schedules and trigger up to 50,000 runs per second at peak (top of the hour is the worst case), with runs starting within a few seconds of their scheduled time.
- How precise must triggering be? Is starting within 2 seconds of the scheduled time acceptable?
- Are jobs allowed to run more than once if a worker crashes mid-run, or do we need strict exactly-once?
- How long can a single run take? Seconds, or hours?
- Do jobs have dependencies on other jobs (a DAG), or is each job independent?
- Who executes the work: our own worker fleet, or the owning team's service that we call?
- Should a recurring job that is still running skip, queue, or overlap its next run?
- How long must run history be retained?
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Create, update, pause, and delete one-off and recurring jobs.
- Trigger each run at its scheduled time and dispatch it to a worker.
- Retry failed runs with exponential backoff up to a configured limit.
- Expose run status (scheduled, running, succeeded, failed) and history per job.
- Support a per-job concurrency policy for overlapping recurring runs (skip, queue, or allow).
- Support per-job timeouts and manual re-run of a past run.
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Hold 10 million active schedules; at 1 KB each that is about 10 GB of definitions.
- Trigger up to 50,000 runs per second at peak; the average is closer to 2,000 per second.
- Start runs within 2 seconds of the scheduled time at p99.
- No run may be silently dropped: at-least-once execution, with an idempotency key so tasks can deduplicate.
- Run history: about 170 million runs per day at 500 bytes each, roughly 85 GB per day, kept for 30 days (2.5 TB).
- The scheduler itself must survive the loss of any single node or availability zone without missing triggers.
Job definitions live in a relational store, and the next fire time of every job is kept in a time-bucketed trigger index partitioned across scheduler nodes. Each scheduler node owns a set of partitions through leases, scans for runs that are due, and enqueues them onto a durable queue. Workers lease runs from the queue, execute them with a heartbeat, and report results, while a reaper re-enqueues runs whose lease expired.
Loading diagram...
Create a job. The client sends POST /jobs with the task, schedule, retry policy, and timeout. The job API validates the cron expression, writes the definition to the job store, computes the next fire time, and inserts a trigger row into the partition chosen by hashing the job ID. Both writes happen in one transaction so a job never exists without its trigger.
Trigger a run. Every scheduler node polls its owned partitions once per second for triggers due in the next few seconds. For each due trigger it creates a run record with a deterministic ID (job_id + scheduled_time), publishes the run to the queue, and advances the trigger to the next fire time. Because the run ID is deterministic, a node that crashes after publishing but before advancing the trigger produces a duplicate that the run store rejects.
Execute a run. A worker takes a run from the queue, marks it running with a lease that expires in 30 seconds, and heartbeats to extend the lease while the task executes. On success it marks the run succeeded. On failure it computes the next backoff and schedules a retry trigger, or marks the run failed when attempts are exhausted.
Recover a lost run. The lease reaper scans for running runs whose lease has expired (the worker died) and re-enqueues them with an incremented attempt count.
Stateless service for managing job definitions and reading run history. It is the only writer of job definitions and initial triggers.
- Java or Go service behind a load balancer, with a cron expression library for computing fire times in the job's time zone.
API
POST /jobswith{ name, schedule, task, retryPolicy, timeoutSec, concurrency }returns{ jobId }.PATCH /jobs/:idupdates or pauses a job;DELETE /jobs/:idremoves it and its trigger.GET /jobs/:id/runs?status=&cursor=returns run history newest first.POST /jobs/:id/runstriggers an immediate manual run.
Data Model
jobs(job_id PK, owner, schedule, timezone, task_spec JSON, retry_policy JSON, timeout_sec, concurrency, paused, version)
Tradeoffs
Updating a schedule rewrites the trigger row in the same transaction and bumps version; a scheduler that already read the old trigger checks the version before enqueueing, so an edit never produces a stale run. A relational store is used for definitions because the write rate is low and transactional updates are valuable.
Stores the next fire time of every active job, organized so a scheduler can cheaply find everything due now.
- Sharded PostgreSQL or a wide-column store such as Cassandra, with 1,024 logical partitions.
Data Model
triggers(partition_id, fire_at, job_id, job_version, attempt)with primary key(partition_id, fire_at, job_id).
Scalability
The query WHERE partition_id = ? AND fire_at <= now() + 5s is a range scan on the primary key, so it stays fast regardless of total size. At the top-of-hour peak of 50,000 runs per second, 1,024 partitions mean each partition handles about 50 triggers per second, which is trivial per scan.
Tradeoffs
A single sorted set in Redis is simpler but puts every trigger on one node and risks losing triggers on failover. A delay queue in the message broker cannot be edited or cancelled efficiently when a user changes a schedule. A durable, partitioned table supports edits, deletes, and range scans at the cost of polling.
A fleet of nodes that each own a subset of trigger partitions, scan them for due triggers, and enqueue runs.
- Go service; partition ownership via leases in etcd or ZooKeeper.
Diagram
Loading diagram...
Scalability
The coordinator spreads 1,024 partitions evenly across nodes; adding nodes rebalances leases. Each node pre-fetches triggers 5 seconds ahead and holds them in an in-memory timer wheel, so the database sees one scan per partition per second while dispatch happens at the exact second. Jitter of a few hundred milliseconds is added to recurring jobs that opt in, flattening the top-of-hour spike.
Tradeoffs
Leases with fencing tokens prevent two nodes from scanning the same partition after a network partition: every enqueue carries the token, and the run store rejects writes with a stale token. A single leader that dispatches everything is simpler but caps throughput and makes failover pause all scheduling.
The queue buffers runs between the scheduler and workers; workers execute tasks and record outcomes.
- Kafka or SQS for the run queue, partitioned by job ID.
- Workers run on Kubernetes and execute HTTP calls directly or launch containers for heavy tasks.
Scalability
Workers autoscale on queue lag. Long tasks run asynchronously: the worker launches a container and keeps heartbeating, so a slot is not tied up waiting on a blocking call. Separate queues per priority tier keep a backlog of batch jobs from delaying latency-sensitive ones.
Tradeoffs
Exactly-once execution across arbitrary external targets is not achievable, so the system guarantees at-least-once and passes an idempotency key (the run ID) to every task. Targets that cannot tolerate duplicates must check that key. This is far simpler and more available than distributed transactions with every target.
Records every run, its attempts, and its status for the history API and the lease reaper.
- Cassandra or DynamoDB, with a secondary index on
(status, lease_expires_at)for the reaper.
Data Model
runs(job_id, scheduled_at, run_id, attempt, status, worker_id, lease_expires_at, started_at, finished_at, error)partitioned byjob_id, clustered byscheduled_at DESC.
Scalability
About 170 million runs per day are partitioned by job, so history reads for a job are a single partition scan. A 30-day TTL bounds the store at about 2.5 TB. The reaper queries only the small set of running rows with an expired lease.
Tradeoffs
Status transitions use conditional writes (UPDATE ... IF status = 'running' AND lease_owner = ?), so a slow worker that lost its lease cannot overwrite the result of the retry that replaced it. A relational database would give the same guarantee but would need sharding at this write volume.