Design a distributed job scheduler

I would keep every job in a replicated job store, indexed by partition and due time, with 64 partitions so the work can be spread. Pollers each own some partitions. Every second, a poller claims the due jobs with a conditional update that creates a queued run row (job id plus due time, with a queue deadline) and moves the job's next due time forward in the same update, then puts a run message on a queue. A worker that takes a message starts a 60-second lease on the run, so queue wait never counts against it, calls the target with the run id as an idempotency key, and extends the lease with heartbeats.

If a worker dies, the lease on its run row runs out and another worker repeats the run. The target uses the key to return the saved result, so a repeat does no harm. That gives at-least-once with an effect close to once. For cron jobs I compute the next run from the last scheduled time, and write it in the same update that claims the run, so the schedule survives failed runs.

The spike is the hard part: 500,000 jobs due at midnight is 8,300 starts a second, 36 times the average. I would offer jitter, preload the next minute into memory and scale workers ahead of time. The main trade-off is that runs can repeat, in exchange for never losing a job.

These numbers are assumptions for the exercise, not facts about a real system:

• 10 million active jobs, and together they run 20 million times a day.
• 5% of jobs, or 500,000, are set for exactly midnight, and their runs may start any time within a minute.
• A job record takes about 100 bytes, and a run record about 200 bytes. Run history is kept for 30 days.
• The due-job index is split into 64 partitions, and a worker starts about 100 runs a second.

The arithmetic:

Average run starts per second

20M ÷ 86,400 s ≈ 231

≈ 230/s

Midnight spike

500,000 runs ÷ 60 s ≈ 8,333/s; ÷ 231 average

≈ 8,300/s, 36 times the average

Load per partition

8,333/s ÷ 64 partitions

≈ 130 claims a second per partition at the peak

Workers for the spike

8,333/s ÷ 100 starts a second per worker

≈ 84 workers, so about 90 with headroom

Job table

10M × 100 B

1 GB, small enough for one replicated database

Run history

20M × 200 B = 4 GB a day; × 30 days

≈ 120 GB

Scanning 10 million jobs every second is out of the question. Instead, make "what is due now" a cheap range read by choosing the right index.

Index jobs by the key (partition, due time, job id). The partition is the job id hashed into one of 64 buckets, so it never changes. Within a partition, jobs sort by due time, so the due ones are the first rows. A poll is then "in my partitions, give me rows with due time at or before now, oldest first, limit 500". Most polls read nothing, which costs almost nothing. To keep even old rows out of the way, group the index in time buckets of one minute. A poller reads the current bucket and any older bucket that still has rows, which are overdue jobs.

Who polls which partition. Give each poller a set of partitions through membership in a small coordination store: with N live pollers, poller i owns the partitions p where p mod N = i, and the set moves when pollers join or leave. During a move, two pollers may briefly poll the same partition. That is why the claim itself is a conditional update. Only one update wins per job, because the claim succeeds only while the job's due time has not yet been moved forward.

Latency. Polling once a second adds up to a second of delay. Add the queue and the worker's start, and the whole path stays inside the 5-second target.

Precision on demand. For tighter timing, a poller can load the next minute's jobs for its partitions into memory shortly before the minute starts. It keeps them in a timer structure, such as a min-heap ordered by due time, and fires each at its exact time. A restart reloads the minute from the store, because nothing was claimed yet. The same preload also protects the midnight spike. The 500,000 jobs due at midnight are about 50 MB of rows, small enough to hold in memory, so the poller can queue them in the first moments after midnight without a burst of database reads.

Leases. A claim is not forever, and the lease must start when work starts. A poller's claim only creates the run row as queued, with a queue deadline such as 10 minutes. A worker that takes the message makes one conditional update: if the run is still queued, set its owner, the attempt number and a lease expiry 60 seconds ahead. Then it extends the lease every 20 seconds while it is alive. A worker that loses this update drops the message, which also absorbs duplicate messages. If a worker dies, the extensions stop and the lease passes. Pollers scan the run rows, indexed by expiry, and re-queue any running run whose lease has expired, or any queued run past its deadline, which means a message was lost. Compare lease times using the job store's own clock, not the workers' clocks, so a skewed machine cannot steal or hold a lease.

Why at-least-once, not exactly-once. A worker calls the target and then crashes before it records the result. From the scheduler's side, the target may or may not have acted, and there is no way to tell. It can either risk skipping the run or risk repeating it. A scheduler should choose repeating, because a missed job is usually worse than a duplicate.

Making a repeat harmless. Every run has a run id: the job id plus the due time. The worker sends it to the target as an idempotency key. The target stores the key with the result, for a day or longer, and on a repeat returns the saved result. Targets that cannot do that must make the work itself safe to repeat, for example by writing "set the report to sent" rather than "add one to the sent count". The scheduler's contract should say so plainly.

Stale workers. A worker may pause for longer than its lease and then wake up and try to record its result, after another worker has taken the run. Make the result write conditional on the lease owner and attempt number, so the late write is rejected.

Retries. On failure or timeout, schedule another attempt with exponential backoff and a little random jitter, such as 10 seconds, 30 seconds, then 2 minutes. Retry timeouts and server errors, and do not retry errors that cannot succeed, such as a bad request. After a limit of attempts, mark the run dead, keep its payload and alert the owner. Also cap how many workers one team may use at once, so a team with a flood of slow jobs cannot starve everyone else.

Recurrence. Store the cron expression and a time zone name. Compute the next due time from the last scheduled time, not from now, so a late run does not push the next one back and the schedule does not drift. The claim creates the run row and writes the next due time in the same update. If the next run were only created after the current one finished, a crash or a failed run would end the schedule silently. With this order, the schedule continues even when a run fails. The lease lives on the run row, apart from the job's due time, so recovering a crashed run never disturbs the schedule.

Time zones. Use zone names, not fixed offsets, and let a time zone library handle daylight saving time. On the day clocks go forward, a 02:30 job has no 02:30. Run it at the next valid time. On the day clocks go back, 01:30 happens twice. Run it once. Say these rules in the documentation.

Misfires. If the scheduler is down for two hours, an hourly job missed two runs. The right answer depends on the job, so make it a setting: run once now and move on, run every missed run, or skip to the next. Running once is a good default, since a report sent twice in a minute is no use. A billing job might need every run. Overdue rows are easy to find, because they sit in older time buckets.

The midnight pile-up. Many teams pick midnight sharp. Our assumption has 500,000 jobs due at once, which is 8,300 starts a second if they fire within a minute. There are three defences. Offer jitter: spread each job over a window, for example by the job id modulo five minutes, and make that the default for jobs that do not need precision. Over five minutes, the same 500,000 jobs need only 1,670 starts a second. Keep an exact-time option, with a quota, for jobs that truly need it. Preload the minute into memory as described earlier. And scale workers up ahead of the busy times, using a schedule or the queue depth.