Design a Distributed Task Scheduler

The ask

Other services submit jobs with a due time. A job may be due now, tonight, or once an hour on a repeating pattern. The scheduler's job is to start each job close to its due time.

Jobs run on a shared fleet of workers. No single scheduler machine is a point of failure. A scheduler crash must not lose or duplicate whole batches of work.

A job may run twice after a failure. Exactly-once running is not promised. Each job carries an idempotency key, a label the worker checks before repeating side effects.

Submitters can ask where a job stands. They can also cancel a job that has not started. Started jobs finish or fail on their own.

Estimate the scale

The scheduler takes 1,000,000,000 jobs a day.

1,000,000,000 jobs / 86,400 seconds = 11,574 jobs per second arriving.

That pace means about 694,440 jobs arrive in an average minute. Due times cluster far above the average, which shapes the dispatch design.

The average job runs 10 seconds.

11,574 jobs per second x 10 seconds = 115,740 jobs running at any moment.

The fleet has 50,000 workers. The running load averages about 2.3 jobs per worker at any moment, and each worker handles about 20,000 jobs across a day.

API and data

Submit takes a job name, a due time, the work payload and a retry count. It returns a job ID. The submitter keeps the ID for status checks and cancellation.

A repeating submission also carries the gap between runs. When one run is created, the next run's job is created with it. Repeating work is just a chain of ordinary jobs.

A job record holds the due time, the payload, the state and the attempt count. It also holds the claiming worker and the claim expiry once claimed. Status reads return that record in short form.

Job records are sharded by a hash of the job ID. No shard holds a whole day's work. Dispatchers read across shards by due time.

High-level design

Submissions land in the job store, indexed by due time. A dispatcher watches the due edge of that index. Workers pull work from the dispatcher instead of receiving pushes.

Pulling keeps slow workers safe. A worker asks for a job only when it has room. A fast worker simply asks more often.

Several dispatchers run at once, each owning a slice of the job shards. A dispatcher failure leaves its slice idle only briefly. A standby takes over the slice.

Workers report outcomes back to the dispatcher. Success closes the job. Failure schedules a retry or sets the job aside.

Due-time buckets and dispatch

The store groups jobs into one-minute due buckets. A day holds 1,440 minute buckets. The dispatcher works on the current bucket and the next one.

Buckets turn a time search into a short read. The dispatcher never scans the whole store. It reads one bucket, hands out its jobs, and moves on.

Jobs arriving with a past due time land in the current bucket. Late submission is ordinary, not an error. The job simply starts as soon as a worker is free.

Inside a bucket, jobs carry a priority. Dispatchers hand out high-priority jobs first. Priority orders a minute of work, not the whole day.

Claims, expiries and retries

A worker claims a job before running it. The claim is a lease on the job, recorded with an expiry time. While the claim lives, no other worker is offered that job.

A long job renews its claim while it runs. The renewal is a short note from worker to dispatcher. A worker that stops renewing loses the job at expiry.

An expired claim returns the job to the due pool. The next worker sees the attempt count raised. It also sees the idempotency key, so repeated side effects can be refused.

A failed job retries with a growing gap before its next attempt. The submitter sets the attempt limit. A job that uses up its attempts is set aside and reported to its submitter.

Deep dive: a million jobs due at once

Repeating jobs love round times. Midnight and the top of each hour gather huge spikes. A spike can hold many times the average minute's jobs.

The scheduler spreads flexible jobs inside a window the submitter allows. A job due at midnight with a one-hour window may start at any minute in that hour. Spreading is agreed at submission, never improvised.

Strict jobs keep their exact minute and take priority inside the bucket. Flexible jobs fill the gaps around them. Workers stay busy without a single crushing minute.

Per-team quotas guard the spike as well. One team's midnight batch cannot claim every worker. Each team holds a share of the fleet, and unused share lends out when idle.

Some lateness is accepted and stated. At a true spike, low-priority jobs start minutes late. The status record shows the delay plainly instead of hiding it.

Fairness across teams

Many teams share one scheduler. Fairness is a design feature, not a courtesy. Quotas cap how many running jobs one team can hold.

Dispatchers hand out jobs team by team in rotation within each bucket. A small team's jobs never wait behind another team's whole batch. Rotation costs a little bookkeeping per bucket.

Measurements stay per team and per job name. A team can see its own delays and failures. The scheduler's operators watch the same numbers fleet-wide.

Evaluation and trade-offs

A central scheduler gives every team the same reliability machinery. Retries, claims and fairness are built once. The cost is a critical shared service that must itself be highly available.

Pull-based dispatch trades a little start latency for safety. Workers are never pushed past their capacity. Very urgent jobs feel the pull delay most.

At-least-once running is the honest guarantee. Claims and expiries recover from crashes, and recovery can repeat a job. Idempotency keys push the last step of safety to the job itself.

Minute buckets keep dispatch simple and fast. Finer timing would need finer buckets and more dispatcher work. One-minute precision covers the stated needs.

Job states