Design: a distributed job scheduler

The prompt

"Design a distributed job scheduler" asks for cron that doesn't live on one machine. A crontab on one server is simple and a single point of failure; three servers running the same crontab run every job three times. The design is about running each job once, on time, across many machines that can fail.

1. Requirements

Functional: create, pause and delete schedules (cron expressions, fixed intervals, one-time); run each at its time on a worker; retry failures; show history per schedule.

Non-functional:

• Runs start within a few seconds of their scheduled time.
• A run never executes twice at the same time, and normally runs once.
• No single point of failure.
• 10 million schedules; tens of thousands of runs a second at peak.

2. Estimates

• Average rate: if a typical schedule runs hourly, 10 million schedules is about 2,800 runs a second.
• The spike: people write 0 * * * *. If a third of hourly schedules are due at minute 0, that's 3.3 million runs in one minute, about 55,000 a second, then quiet. The spike, not the average, sizes the system.
• History: 240 million runs a day at about 200 bytes is 48 GB a day; kept 30 days, 1.4 TB, partitioned by day.

3. Entities and API

Schedule { id, owner, spec: "0 9 * * *" | every 1 hour, time_zone, next_run_at, job: { queue, payload },
           misfire: run_once | skip, owner_lease, lease_until, fence }
Run      { schedule_id, scheduled_for, attempt, status, worker, started_at, finished_at }   unique (schedule_id, scheduled_for)

POST   /schedules            { spec, time_zone, job, misfire }    →  201 { id, next_run_at }
PATCH  /schedules/{id}       { paused: true }
GET    /schedules/{id}/runs?before=…

4. High-level design

5. Deep dives

export async function claimDue(db: pg.Pool, owner: string, limit = 10, leaseSeconds = 30) {
  const { rows } = await db.query(
    `UPDATE schedules SET owner = $1, lease_until = now() + make_interval(secs => $3), fence = fence + 1
     WHERE id IN (SELECT id FROM schedules
                  WHERE next_run_at <= now() AND (lease_until IS NULL OR lease_until < now())
                  ORDER BY next_run_at LIMIT $2 FOR UPDATE SKIP LOCKED)
     RETURNING id, next_run_at, fence`,
    [owner, limit, leaseSeconds],
  );
  return rows as { id: number; next_run_at: Date; fence: number }[];
}

export async function finish(db: pg.Pool, id: number, fence: number) {
  // Move to the next slot after now, skipping any missed while the scheduler was down.
  const { rowCount } = await db.query(
    `UPDATE schedules
     SET next_run_at = next_run_at + every * (floor(extract(epoch FROM now() - next_run_at) / extract(epoch FROM every)) + 1),
         owner = NULL, lease_until = NULL
     WHERE id = $1 AND fence = $2`,
    [id, fence],
  );
  return rowCount === 1; // false: our lease expired and someone else has the job now
}

Tested on Postgres 16 with 100 due schedules of "every minute" and four schedulers claiming in batches of 10 at the same time: all 100 were claimed, each by exactly one scheduler. With 2-second leases and nobody finishing, a fifth scheduler reclaimed all 100 once the leases expired. The original holder's finish for schedule 1 was then rejected, because its fence was stale; the new holder's finish succeeded, cleared the lease and set the next run about a minute ahead.

Tested: a per-minute schedule left 10 minutes 30 seconds overdue was claimed and run once, and finish set its next run about 30 seconds ahead, at the next whole slot, instead of queueing ten catch-up runs.

The top of the hour. When a third of all hourly jobs are due at minute 0, spread them: for schedules that don't care about the exact minute ("hourly"), pick the minute from a hash of the schedule ID, so load is even across the hour. Keep the exact spec for the ones that do care, and size workers for that smaller spike.

Executors. Long jobs send heartbeats that extend their lease; a job whose heartbeats stop is presumed dead and retried. Each job has a timeout, retries with exponential backoff and jitter, and a dead-letter queue after the last attempt. A schedule that hasn't succeeded within twice its interval raises an alert: the most dangerous failure of a scheduler is a job that silently stops running.

6. Wrap-up

What breaks first: the database behind the schedules, at tens of thousands of claims a second during a spike, so schedules are sharded and claims are batched; then time zones: "09:00 daily" in a zone with daylight saving time happens twice, or not at all, once a year, so next run times are computed with a time zone library, never by adding 24 hours.

Recap

Interview questions