| @@ -0,0 +1,45 @@ | |||
| 1 | + | # System Design Interview: Designing a Distributed Job Scheduler | |
| 2 | + | ||
| 3 | + | "Run this job every hour" or "run this once at 3 pm" for millions of jobs, with each run happening once and on time. | |
| 4 | + | ||
| 5 | + | ## Requirements | |
| 6 | + | ||
| 7 | + | - Users register one-off and recurring (cron) jobs with a payload and a target (HTTP call or a queue message). | |
| 8 | + | - Jobs fire within a few seconds of their scheduled time. | |
| 9 | + | - Each run happens at least once, ideally exactly once; failures retry with backoff. | |
| 10 | + | ||
| 11 | + | ## Data model | |
| 12 | + | ||
| 13 | + | - `job(id, owner, schedule, payload, next_run_at, status)` | |
| 14 | + | - `job_run(job_id, scheduled_for, attempt, status, started_at, finished_at)` | |
| 15 | + | ||
| 16 | + | ## Finding due jobs | |
| 17 | + | ||
| 18 | + | Index `next_run_at`. Scheduler nodes repeatedly claim a batch: | |
| 19 | + | ||
| 20 | + | ```sql | |
| 21 | + | UPDATE job SET status = 'CLAIMED', claimed_by = :node, claimed_at = now() | |
| 22 | + | WHERE id IN ( | |
| 23 | + | SELECT id FROM job | |
| 24 | + | WHERE next_run_at <= now() + interval '5 seconds' AND status = 'SCHEDULED' | |
| 25 | + | ORDER BY next_run_at LIMIT 500 | |
| 26 | + | FOR UPDATE SKIP LOCKED) | |
| 27 | + | RETURNING id; | |
| 28 | + | ``` | |
| 29 | + | ||
| 30 | + | `SKIP LOCKED` lets many schedulers poll without fighting over the same rows. For very large scale, partition jobs by hash across shards and give each scheduler a set of shards. | |
| 31 | + | ||
| 32 | + | A time-bucketed approach also works: put job IDs into a sorted set or a bucket per minute and pop the current bucket. | |
| 33 | + | ||
| 34 | + | ## Executing | |
| 35 | + | ||
| 36 | + | Claimed jobs are pushed to a **work queue**; stateless workers execute them and record the `job_run`. For a recurring job, compute the next `next_run_at` from the cron expression and reset it to SCHEDULED in the same transaction that records the run. | |
| 37 | + | ||
| 38 | + | ## Reliability | |
| 39 | + | ||
| 40 | + | - If a scheduler dies after claiming, a reaper resets claims older than a timeout. | |
| 41 | + | - Workers may run a job twice after a timeout, so pass a run ID (job_id + scheduled_for) to the target as an idempotency key. | |
| 42 | + | - Retries with exponential backoff and a dead-letter state after N attempts. | |
| 43 | + | ||
| 44 | + | --- | |
| 45 | + | *Disclosure: I'm on the team behind [Linkjob AI](https://www.linkjob.ai/), an AI tool for job interviews.* | |
linkjobai / System Design Interview: Designing a Distributed Job Scheduler
Last active 5 days ago
Interview prep notes
linkjobai revised this gist 5 days ago · 769d7ab
1 file changed, 45 insertions