Distributed Task Schedulers

At 10:00 am on Class 10 results day, a state board hands an education messaging platform 2 million SMS to send, one per student. The platform runs them from a cron job on one server. At 10:04 the server's disk fills, the job dies at message 600,000, and nobody can say which students got their marks. Parents flood the board's helpline, and a small college's 50 exam reminders, booked for 10:05, sit stuck behind the board's batch. A task scheduler turns that morning into a non-event: every message is stored before it is promised, sent in small pieces that are retried when a machine dies, and shared fairly between customers.

Plenty of work does not belong inside a user's request: the board's 2 million SMS, monthly fee statements, or cancelling an unpaid exam-fee hold after 15 minutes. A task scheduler accepts descriptions of such work, called tasks or jobs, stores them safely, and makes sure each one runs at the right time on some machine, even when machines crash. The simplest scheduler is cron on one server, and results day showed what goes wrong with it:

A distributed scheduler fixes all four by splitting the problem in two: a durable store that remembers every task, and a pool of workers that can grow, shrink and crash without losing anything. We follow the education platform, and the board's 2 million messages, through the whole chapter.

Before choosing any parts, agree on what the scheduler promises to the services that use it, such as the platform's result-SMS service:

• Never lose a task once the caller has been told it was accepted.
• Run on time, usually within a few seconds of the scheduled moment.
• Survive crashes: if a worker dies mid-task, the task runs again elsewhere.
• Scale out to millions of tasks a day by adding workers.
• Be fair: one big customer must not starve everyone else.
• Be visible: show what is waiting, running, done and failed.

Tasks come in four kinds:

One design must serve all four, from 50 ms tasks to 2-hour ones.

Chains of dependent tasks, where B starts only after A succeeds, are called workflows. They build on everything in this chapter, so we keep them out of the core design; the box sketches how they extend it. First, the parts every scheduler has.

Whatever a scheduler is called, it has the same few parts, and tasks flow through them from left to right.

• Task API: services submit tasks with a type, a payload, a run time and a priority. A task counts as accepted only after it is safely written to the store.
• Task store: a replicated database and the source of truth for every task's state.
• Dispatcher: keeps finding tasks whose time has come and hands them to workers. Several dispatchers run at once, so none is a single point of failure.
• Workers: processes that run the actual code and report success or failure. When the backlog grows, you add workers.

With several dispatchers looking for due tasks at once, the first danger is two of them grabbing the same one, like two clerks reaching for the same file. The database referees: a claim is a locked or conditional update that only one caller can win.

-- Claim up to 10 due tasks for worker 17.
BEGIN;
SELECT id FROM tasks
 WHERE status = 'pending' AND run_at <= now()
 ORDER BY run_at          -- oldest due first; the index serves it
 LIMIT 10
 FOR UPDATE SKIP LOCKED;   -- rows locked by others are skipped

UPDATE tasks
   SET status = 'leased', lease_owner = 'worker-17',
       lease_until = now() + interval '30 seconds',
       attempts = attempts + 1
 WHERE id IN (/* ids from the SELECT */);
COMMIT;

-- Every few seconds, return expired leases to the pool.
UPDATE tasks SET status = 'pending', lease_owner = NULL
 WHERE status = 'leased' AND lease_until < now();

PostgreSQL syntax; MySQL 8 also supports SKIP LOCKED. Priorities come from separate queues, each with its own table or index, not from this sort.

SKIP LOCKED lets ten dispatchers claim in parallel without waiting on each other's locks. The key column is lease_until: the task belongs to worker 17 only until that moment, and then the last statement makes it claimable again.

Finishing is conditional too. The worker marks the task done with WHERE id = ... AND attempts = 1, the attempt number it claimed. If its lease expired and another worker took over, attempts is now 2, so the late report changes nothing. Every task moves through four states:

Only leased is temporary by design: it always ends, either in a report from the worker or in an expired lease.

A worker can stop at any moment: the process crashes, the machine loses power, the container is evicted. A dead worker cannot report its own death, so the scheduler never hands out a task forever. It hands out a lease: "this task is yours for 30 seconds".

A worker that needs longer sends a heartbeat every 10 seconds or so, and each heartbeat pushes lease_until forward. If heartbeats stop, the lease runs out and the task becomes available to any other worker. Here is task 17, 500 of the board's 2 million SMS, when its worker dies halfway.

Nobody had to detect the crash. The expiring lease is the failure detector, and it works the same way for a crashed process, a dead machine or a cut network cable. The price is waiting up to one lease length before the retry starts, so choosing that length is a trade-off:

30 seconds with a heartbeat every 10 is a common middle: a crash costs at most half a minute, and a healthy worker must miss three heartbeats to lose its lease.

Look again at the crash. Worker 1 had sent 250 messages and died before saying so. The scheduler cannot tell a silent worker that did nothing from one that did everything and lost the network before reporting, so its only safe move is to run the task again. That makes the guarantee at-least-once: every task runs at least once, and sometimes more than once.

The scheduler cannot promise exactly-once execution on its own. What you can build is an exactly-once effect: run the task as often as needed, but make every repeat harmless. A task with that property is idempotent. Four common tasks, made safe to repeat:

The pattern in every row: record the effect under a key the task fixes in advance, and check that record before acting again. Four habits make retries cheap as well as safe:

• Keep tasks small: the board's 2 M result SMS go in as 4,000 tasks of 500, not one giant task. A crash then re-checks at most 500 keys and delays only those 500 messages by one lease.
• Retry with backoff: after a failure, set run_at 1 s later, then 2 s, 4 s, 8 s, plus random jitter so thousands of failed tasks do not retry in lockstep.
• Cap the attempts: after, say, 5 tries the task moves to a dead-letter list for a human, instead of failing forever.
• Tell retryable errors from permanent ones: a timeout is worth retrying; an invalid phone number is not.

Retries keep tasks from being lost; the next risk is tasks running too late. On the platform, an OTP for a parent logging in to see results must go out in seconds, while a monthly attendance report can wait an hour. If both share one line, the board's 4,000 result tasks delay every OTP behind them. So schedulers keep separate queues by priority, and often by task type. A common split:

Separate queues fix order, but strict priority can starve the low queue for as long as higher-priority work keeps arriving. A common fix is weighted serving: of every 10 tasks a worker takes, 7 come from high, 2 from normal and 1 from low, whenever those queues have work. Long tasks get their own pool too, so a 2-hour transcode never sits in front of a 50 ms SMS.

Priorities decide the order of tasks that are due; many tasks are not due yet. A delayed task is a task whose run_at is in the future; the index on run_at keeps it out of the way until it is due. Many delayed tasks never run at all: when the parent pays the exam fee, the "cancel unpaid hold" task is cancelled with one update.

A recurring task is stored once as a schedule, often written in cron syntax, and the scheduler creates one ordinary task for each run.

minute  hour  day  month  weekday   meaning
0       2     *    *      *         every day at 02:00
*/5     *     *    *      *         every 5 minutes
30      9     1    *      *         09:30 on the 1st of every month
0       10    *    *      1-5       10:00, Monday to Friday

Store each schedule with its time zone, such as Asia/Kolkata, so 02:00 means 02:00 for that customer.

• Create each run exactly once: compute next_run_at in the same transaction that creates a run, and give each run a unique key like (schedule_id, 2026-10-16 02:00) so a retried creation cannot make a second copy.
• Decide what missed runs mean: if the scheduler was down at 02:00, run once on recovery, run every missed slot, or skip. A report wants one catch-up run; a reminder for a class that already started should be skipped.
• Spread the top of the hour: many jobs are written as 0 * * * *. Add a random offset of a few minutes to jobs that do not care about the exact minute.
• Watch daylight saving: India has no clock changes, but customers in many other countries do, and a run scheduled inside the hour when clocks change can be skipped or happen twice.

The platform serves many customers, called tenants: 3,000 colleges and a few state boards. At 10:00 the board submits its 2 million result SMS as 4,000 tasks of 500, and a small college submits 50 exam reminders. With a single first-in, first-out line, the college waits behind all 4,000 tasks.

The cost is real. The platform's SMS contract allows 2,000 messages per second, so 2 million messages take 1,000 seconds, nearly 17 minutes, and the college's reminders arrive 17 minutes late although they need a fraction of a second of capacity. Four tools fix it:

• A queue per tenant, served in turn: the dispatcher takes a few tasks from each tenant's queue in round robin, so the small college's 50 go out in the first seconds.
• Weights for paid plans: a tenant on a bigger plan gets 3 turns for every 1 that a free tenant gets.
• Concurrency caps: no tenant may hold more than, say, 200 running tasks at once.
• Rate limits: a token bucket per tenant, as in the rate limiter chapter, plus one shared bucket that keeps all tenants together under the provider's limit.

One table with SKIP LOCKED hands out thousands of tasks a second. Now the platform grows: it holds 1 billion class and fee reminders, and reminder times bunch up on the hour, so at 9:00 sharp, when first classes start, up to 100,000 fall due every second. Most go as app push notifications, whose providers together accept about 120,000 a second. At about 200 bytes each the tasks fill 200 GB, which one database can store; the trouble is the work. Claiming and finishing 100,000 tasks a second is 200,000 writes a second, far past one primary's tens of thousands, and every claim fights over the front of the same (status, run_at) index.

The fix is to stop searching for due work and file it instead. Give every task a bucket, its due time cut to the minute, and a shard, a hash of its id modulo 64. Each (bucket, shard) pair is one small list: (09:00, 17) holds every task due at 9:00 whose id hashes to 17. Finding due work becomes a key read, never a scan. A wide-column store keyed by (bucket, shard) fits well.

In numbers: the 9:00 minute holds up to 6 M tasks (100,000 × 60). Split 64 ways, each shard's bucket holds about 94,000, roughly 1,600 a second. A dispatcher that owns 4 shards fires about 6,250 a second and holds about 375,000 tasks for that minute, 75 MB at 200 bytes each. Spreading each minute over 64 shards also stops the 9:00 bucket from becoming one hot partition. What happens inside a dispatcher once a bucket is loaded?

A loaded bucket is up to 94,000 tasks per shard, each due at a particular second. The dispatcher needs the earliest ones on time without sorting all of them over and over.

Loaded tasks wait in memory in time order. A min-heap keeps the earliest task on top, and each insert or removal costs a little more as the heap grows. A timing wheel is cheaper still: a ring of slots, one per second, like a clock face. Each task drops into the slot for its second, and a pointer moves one slot a second, firing everything in the slot it reaches. Adding or firing a task costs the same however many are waiting.

When a task's second arrives, the dispatcher does not run it. It publishes the task to a queue, as in the message queue chapter, and marks it queued in the store. Workers consume from the queue, and the queue's visibility timeout does the job the lease did in the one-table design: if a worker dies without acknowledging, the task reappears for another worker. Retries with backoff and the dead-letter queue come with the queue too.

The timing wheel fires tasks on time while the dispatcher is healthy. The harder question is a dispatcher that is not quite dead.

A dispatcher owns its shards through a lease held in a coordination service, as the coordination chapter explains: about 10 seconds long and renewed every few seconds. Only the owner fires a shard's tasks, so two dispatchers never fire the same bucket, and each new lease carries a higher fencing token that the store checks on every write.

A lease alone cannot protect the store. A dispatcher frozen by a long pause cannot know that time passed, so it may wake up and write as if it still owned the shard. The fencing token moves the check to the place where the damage would happen:

The store keeps the highest token it has seen per shard and refuses anything lower, so a stale owner can never move a shard's progress backwards and make B skip or repeat a second of tasks. A may still have published a task in its last moments before the pause; the worker's idempotency key absorbs that duplicate. Two more cases complete the failover story:

• A dispatcher dies: its shard leases expire within about 10 seconds; other dispatchers take the shards, reload the current bucket and fire anything overdue at once. A task published just before the crash but not yet marked queued goes out twice, so workers stay idempotent.
• A task arrives late: one created at 08:59:58 for 09:00:30 misses the load a minute ahead. The API hands tasks due within the next minute straight to the shard's owner, and as a safety net each dispatcher re-reads its current bucket every few seconds; anything already due goes straight to the queue.

A scheduler's whole job is keeping promises while machines fail, so walk through the failures one at a time.

The common thread: assume any machine can stop at any instant, and rest every guarantee on two things the scheduler controls, the durable store and the lease clock.

Here is one way to spend the 40 design minutes of a 45-minute interview on "design a scheduler that sends a billion reminders".

If they push on scale, go deep on buckets, shard leases and the timing wheel. If they push on correctness, go deep on leases, fencing tokens and idempotency keys. If they mention many customers, add per-tenant queues and rate limits.