Case study: Job scheduler

Many features say "do this later". Cancel an order if it is not paid in 15 minutes. Send a reminder two hours after delivery. Make a report every night at 2:00. The interviewer asks: "Design a job scheduler that runs millions of such jobs."

A weak answer says "put a timer program on one server", or "sleep in the code for 15 minutes". The first loses jobs when the server dies, and runs them twice when you add a second server. The second wastes a worker for each waiting job. A strong answer keeps the jobs in a safe place, sorted by time. It lets workers claim due jobs so that only one gets each job. It also says what happens when a worker dies, and how a repeating job fires only once.

At SDE-2 level you should store and claim jobs. At SDE-3 level you should handle crashes, repeats, missed runs and a spike at a round time such as 9:00.

An office has a notebook of tasks. Each task has a time. Clerks look for tasks whose time has come. A clerk who takes a task writes a name and a deadline on it. If the clerk does not finish by the deadline, another clerk takes it. So a task can be done twice, and each task must be safe to do twice.

What we build

A one-off job runs once at a time: "check if order 42 is paid at 8:15 pm". A recurring job repeats: "every day at 2:00". A cron expression writes a repeating time as five fields: minute, hour, day of month, month and day of week. The text 0 2 * * * means minute 0 of hour 2, every day.

The calls are:

• POST /jobs sends the job type and the time or the cron expression. It also sends a small amount of data, the payload, such as the order id. The caller sends a key, so a retried call makes one job (lesson 61). It returns a job id.
• DELETE /jobs/{id} cancels a job that has not started. GET /jobs/{id} shows its status.

The promise is at least once: every job runs, and may run twice (lesson 60). A job never runs early. It may be a few seconds late. We keep every time in Coordinated Universal Time (UTC), the one world clock. A cron entry also keeps a zone name. Some countries move their clocks by one hour in spring and again in autumn (daylight saving time). India does not, but your users may live there. In such a zone, a local time such as 2:30 may not exist on one day a year, and on another day it happens twice. Each entry needs a rule for those days.

Part 1: where waiting jobs live

A queue (lesson 58) gives a message to a worker at once. It cannot say "not before 8:15". Amazon SQS can delay a message by at most 15 minutes. A job that waits two hours must wait somewhere else, sorted by time.

With Redis, the score is the run time. ZRANGE ... BYSCORE finds the due jobs. ZREM claims one: it returns 1 for only one worker. We choose the table. The columns are id, type, payload, run_at, status, attempts, lease_until and dedupe_key (unique). The status is waiting, running, done or dead. An index on (status, run_at) fits the question "waiting jobs, oldest time first". The equal column goes first and the range column last (lesson 20).

Part 2: workers claim jobs

Each worker asks for due jobs every second. One statement claims them:

UPDATE jobs
SET status = 'running', lease_until = now() + interval '60 seconds', attempts = attempts + 1
WHERE id IN (
  SELECT id FROM jobs
  WHERE status = 'waiting' AND run_at <= now()
  ORDER BY run_at LIMIT 10
  FOR UPDATE SKIP LOCKED)
RETURNING id, type, payload, attempts;

FOR UPDATE locks the chosen rows (lesson 22). SKIP LOCKED skips rows that another worker has locked, so workers do not wait for each other and never take the same job. The Postgres manual names this use: many consumers on a queue-like table. The time comes from now() on the database, so all workers use one clock (lesson 49).

A lease is a claim that ends by itself after a set time. The job is running until lease_until. When the worker finishes, it sets the status to done. Every 10 seconds a small job puts expired jobs back to waiting. A job with too many attempts goes to dead instead (lesson 62).

A long job extends its lease. Every one third of the lease time (20 seconds for a 60-second lease) it sends a heartbeat: a short update that moves lease_until forward. The lease length is a choice:

• Too short: the lease ends while the worker is still busy, and a second worker starts the same job.
• Too long: after a crash the job waits for the whole lease.

A worker that lost its lease must not change the row. Its done or waiting update adds AND attempts = <the number it was given>. If the claim was given to another worker, that number has changed, no row is updated, and the old worker stops.

Part 3: jobs that run twice

A job runs twice in two cases. The worker finishes the work and crashes before it writes done. Or the lease ends while the job still runs. We cannot stop these, so each job must be safe to repeat (lesson 61). The job id is the key. The job sends it to the outside service, for example the SMS provider, or saves it with a unique constraint. At least once plus a safe repeat gives one effect.

When a job fails, the worker sets it back to waiting. It sets run_at to now plus a wait that grows each time, with jitter (lesson 54). After the maximum number of attempts, the job becomes dead, an alarm rings, and a person replays it after the fix (lesson 62).

Part 4: recurring jobs

A recurring entry is not a job. It makes jobs. A schedules table keeps id, cron, zone and next_fire. A ticker is a small program that runs every second. It claims due schedules with the same SKIP LOCKED statement, in batches of 100. For each one it inserts a job and moves next_fire to the next time, in one transaction (lesson 21).

We run three tickers, so one failure does not stop the clock. The claim gives different schedules to different tickers. As a second guard, the job has dedupe_key = schedule id + fire time. The unique constraint refuses a second job for the same fire time (lesson 22).

Missed fires. If everything was down at 2:00 and returns at 2:10, next_fire is in the past. The entry says what to do. A nightly report runs once now. A "good morning" message is skipped, because it is now useless.

Round times. Many teams choose 9:00. All their jobs are due in the same second. Where the job allows it, add a random delay of a few minutes (jitter, lesson 54).

Part 5: when the table is too slow

Each job costs the database about one statement to finish, plus a share of the claim. At a high rate, the database becomes the limit, and not the workers. Three steps help:

1. Batch. Mark ten jobs done in one statement.
2. A dispatcher and a queue. A small program moves due jobs from the table into a queue (lesson 58). Workers read the queue. The table stays as the record. Keep urgent jobs on their own workers.
3. Split the table by a hash of the job id (lesson 43), when one database cannot take the writes.

SwadKart runs one scheduler for all teams.

Assumptions (made up to teach with, not real traffic):

• 5,000,000 one-off jobs per day. 100,000 recurring entries fire 1,200,000 times per day. At 9:00, 20,000 entries fire in the same second.
• A job takes 0.2 seconds of a worker. There are 200 workers, one job each at a time.
• A database statement costs 8 ms. The server has 8 cores, and we use 70%. That gives 8 x 1,000 ms x 0.7 = 5,600 ms per second. So it runs 5,600 / 8 = 700 statements per second.
• A claim takes 10 jobs. A finished job costs one statement.
• A row is 500 bytes. We keep finished jobs 7 days. One job in 10,000 crashes its worker.

Step 1: the average load. 5,000,000 / 86,400 = 57.9 jobs per second. 1,200,000 / 86,400 = 13.9. Total 71.8 per second. Busy workers: 71.8 x 0.2 = 14.4 of 200. The 200 workers can do 200 / 0.2 = 1,000 jobs per second.

Step 2: the 9:00 spike. 20,000 jobs are due. The workers need 20,000 / 1,000 = 20 seconds. But each job costs 1 statement to finish and 1 / 10 of a claim: 1.1 statements. The database allows 700 / 1.1 = 636 jobs per second. So the spike takes 20,000 / 636 = 31 seconds, and the database is the limit. If ten jobs are marked done in one statement, a job costs 0.1 + 0.1 = 0.2 statements. The database then allows 700 / 0.2 = 3,500 jobs per second, and the workers are the limit: 20 seconds. (We leave out the tickers of Part 4. Assumption: a ticker writes each batch of 100 schedules with 3 statements, so it adds 0.03 statements per job. That is small.)

Step 3: the table. Jobs per day: 5,000,000 + 1,200,000 = 6,200,000. Kept 7 days: 43,400,000 rows. 43,400,000 x 500 bytes = 21.7 GB. With 300 entries per page (lesson 20), 4 levels reach 8,100,000,000 entries, so a claim reads about 4 index pages.

Step 4: the lease. The job takes 90 seconds and the lease is 60 seconds. At second 60, the lease ends and the job goes back to waiting. A second worker takes it. The two workers run together for 30 seconds. This answers the predict box. The fix is a heartbeat every 60 / 3 = 20 seconds, which keeps the lease alive. One job in 10,000 crashes: 6,200,000 x 0.0001 = 620 jobs per day. Each waits about 60 seconds, plus up to 10 seconds until the sweep runs. With a lease of 600 seconds the wait would be about 10 minutes. Some of the 620 may have done their work before the crash. Without a safe repeat, up to 620 jobs run twice each day.

Step 5: three tickers. At 9:00, 20,000 entries are due. Suppose each ticker reads all due entries and inserts a job. That makes 3 x 20,000 = 60,000 jobs, and every entry runs three times. With the unique dedupe_key, only 20,000 inserts succeed, and 40,000 are refused. With the claim, the three tickers take different batches of 100, so there are no refused inserts: 20,000 / 100 = 200 claims.

Step 6: catch-up. All workers are down for 10 minutes. The waiting jobs: 71.76 x 600 = 43,056 (the rounded 71.8 would give 43,080). With batching, the spare speed is 1,000 - 71.76 = 928 jobs per second. The catch-up takes 43,056 / 928 = 46 seconds.

• A job table solves safe storage, cancel, search and an atomic claim. It costs database statements for each job, a delay of up to 1 second from polling, and a table that grows. I would add a dispatcher and a queue when the spike takes longer than the jobs may wait.
• A lease solves a crashed worker. It costs repeats and a wait after a crash, as long as the lease. I would use a heartbeat and a short lease, not one long lease.
• A unique key for each fire time solves double runs from several tickers. It costs one more column and refused inserts. I would still claim schedules in batches, so that most inserts are not refused.

"Cron on one server runs each job once." If the server dies, the run is lost. If you add a second server for safety, the job runs twice. You need a store, a claim and a unique fire time.

"A lease means exactly one worker." In the example, a 90-second job and a 60-second lease gave two workers for 30 seconds. The job must be safe to repeat.

"To run a job in 30 minutes, let a worker sleep for 30 minutes." Each waiting job holds a worker (lesson 54). 50,000 waiting jobs hold 50,000 workers, and a restart loses them all. Store the time and let a worker take the job when it is due.

1. What do FOR UPDATE SKIP LOCKED and a lease each do in a scheduler?
2. A scheduler runs 3,000,000 jobs per day, 0.3 seconds each. (a) How many jobs per second on average, and how many workers are busy? (b) How many workers do you need at 70% busy? (c) 30,000 jobs are due at once and there are 100 workers. How long do they take?
3. A nightly "pay restaurants" entry runs on two scheduler servers. Yesterday a restaurant was paid twice. Why, and what do you change?