System Design Reliability

Distributed Job Scheduler

At 02:03 a subscription renews, or tomorrow evening an Instagram post must publish on its own. That work must not run inside today's HTTP request, and it must still fire if a worker dies at 2 a.m.

A is a durable clock: clients enqueue; a finds what is ready; workers claim with a ; reclaim covers crashes; handlers stay .

Scheduled-post journey

Enqueue with job key

Dedupe client retries; store run_at.

Find ready work when the clock arrives.

Worker holds exclusive claim.

Reclaim on crash

Expired lease → another worker; stay idempotent.

Try it: lease, reclaim, and fencing generation

Workers claim due jobs with a time-bounded lease. Heartbeats extend the lease for long work. If a worker dies without acking, the lease expires and another worker may reclaim the same logical job. A monotonic lease generation acts as a fencing token so stale workers cannot commit after reclaim.

Lease duration: 10s

Job store row

Job: publish-post-42
Status: ready
Holder: —
Lease generation: 0
Lease until: —

Side effects

should stay idempotent

Side effects observed

Simulated wall clock: t=0s

A due job waits in the store. Claim it with a lease, optionally heartbeat to extend, or let the lease expire so another worker can reclaim.

Dual dispatch. Worker A claims, advance past the lease without heartbeats, then let Worker B reclaim. If A tries to complete with the old generation, the store rejects it. Without fencing, both could charge the customer twice.

Long work needs heartbeats. Claim with a 10s lease, advance 8s, heartbeat, then finish. That pattern keeps reclaim from firing mid-run on healthy workers.

Model scope: one job row, at-least-once delivery, and explicit generation checks. Production schedulers also dedupe on job keys at enqueue time.

What actually happens

A plain message queue moves work soon after enqueue. A scheduler adds a time axis: millions of jobs can wait cheaply and wake accurately without every service running its own fragile cron.

The hard part is not "fire a timer." It is guaranteeing due work still runs when workers die, clocks drift, and the same logical job is enqueued twice, without double-charging or double-emailing. That is why delivery is , with a unique and an for effective exactly-once effects.

Recurring calendars are two systems: a materializer expands occurrences, then a delay executor claims them. Say that out loud in interviews. It shows you will not store infinite future rows or run every tenant's cron in one process.

How to choose a scheduler vs a queue

1. Must work wait on a clock? Reminders, renewals, and deferred side effects need a , not only FIFO consume.

2. Is it recurring? Use a materializer plus delay execution; do not re-publish from every app process.

3. Need massive fan-out after due? Let the scheduler decide when, then hand the payload to a queue for competing consumers: keep time indexing separate from execution drain.

Simple rule of thumb

Prefer a scheduler when work must wait on a clock. Deliver , make handlers , dedupe with a , and watch plus lease churn. Add and jitter for midnight herds.

Requirements that actually bite

At-least-once + idempotent handlers

Leases expire; reclaim redelivers. Handlers use a unique so duplicate runs do not create duplicate side effects.

Delay accuracy

Define a timing promise in terms the product actually needs. A reminder may require 99% of jobs to start no more than five seconds after their due time; billing may additionally forbid starting early. Separate scheduled time, dispatch time, worker start time, and completion time. Polling more often reduces dispatch delay, but cannot compensate for an overloaded worker pool or a slow external provider.

Visibility timeout / lease

A lease gives a worker temporary ownership of a claimed job. Other workers avoid that job until the lease expires or completion is recorded. If the worker dies, expiry makes progress possible again. If it is merely paused, the old worker can resume after a replacement has started, so lease expiry alone cannot prevent duplicate effects. Use a lease generation and an idempotent write boundary.

Priorities

Separate lanes or weighted claim: billing renewals before analytics. Use aging or reserved capacity so low lanes are not starved forever.

Retries & DLQ

Transient failures → backoff + retry budget. Poisoned payloads → with inspection and controlled replay.

Observability

, claim latency, lease reclaim rate, success/fail, DLQ depth, and oldest overdue job age beat raw counters.

Architecture

Think API → durable job store → dispatcher that claims due rows → workers that execute and write status. Scale the store with time buckets or shard keys so due queries stay local.

Client / product API

Scheduler API

Job store

due index + status

Dispatcher / claimer

Worker pool

Workers write results

Status updates

Job store

optional partitions by time or shard key

APIStoreDispatchWorkers

Job store responsibilities

Durable enqueue with unique job key
Due index: WHERE status=ready AND run_at <= now()
Lease fields: owner, lease_until, attempt count
Terminal states: succeeded, failed, dead-lettered

Partitioning options

Time bucket: shard by minute/hour of run_at so due scans hit one hot partition at a time
Shard key: tenant / region / queue name for isolation and noisy-neighbor control
Dispatcher instances own disjoint partition sets to avoid dual claim storms

sql

-- Minimal job row shape (interview sketch)
CREATE TABLE jobs (
  job_id         UUID PRIMARY KEY,
  job_key        VARCHAR(255) UNIQUE,  -- dedupe enqueue
  queue          VARCHAR(64) NOT NULL,
  payload        JSONB NOT NULL,
  priority       INT NOT NULL DEFAULT 0,
  status         VARCHAR(20) NOT NULL, -- ready|leased|succeeded|failed|dlq
  run_at         TIMESTAMPTZ NOT NULL,
  lease_owner    VARCHAR(64),
  lease_until    TIMESTAMPTZ,
  attempts       INT NOT NULL DEFAULT 0,
  max_attempts   INT NOT NULL DEFAULT 5,
  created_at     TIMESTAMPTZ NOT NULL,
  updated_at     TIMESTAMPTZ NOT NULL
);
CREATE INDEX idx_jobs_due ON jobs (queue, status, run_at, priority DESC)
  WHERE status IN ('ready');
CREATE INDEX idx_jobs_lease_expiry ON jobs (lease_until)
  WHERE status = 'leased';

Scheduling models

Three models cover most interview questions: delay until a timestamp, expand cron-like calendars into concrete runs, and drain due work under a rate limit so midnight spikes do not melt the fleet.

Delay queue

One-off: run_at = now + delay. Sorted due index or time-hashed buckets. Best for reminders, retries, and deferred side effects.

Cron / calendar schedules

Keep the recurrence rule separate from each concrete job occurrence. A schedule such as “09:00 every day in Asia/Kolkata” has calendar meaning, while each materialized occurrence has a UTC due timestamp and a unique schedule-plus-occurrence key. Define what happens after downtime: skip missed runs, run once, or catch up all occurrences. For zones with daylight-saving changes, explicitly handle repeated or missing local times.

Rate-limited drain

Cap claim QPS or per-queue concurrency so a backlog drains smoothly. Pair with jitter so aligned cron fires do not thundering-herd workers.

Interview tip: Recurring schedules are two systems: a calendar expander and a delay executor. Say that out loud; it shows you will not store infinite future rows or run every tenant's cron in one process.

Lease / visibility timeout reclaim

A is a temporary exclusive claim. If the worker dies without completing, the lease expires and the job becomes claimable again. That is how crash recovery works without a central process tree.

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

sequenceDiagram
    participant D as Dispatcher
    participant S as Job store
    participant W1 as Worker A
    participant W2 as Worker B

    D->>S: claim due job (status=leased, lease_until=T+30s)
    S-->>W1: job payload + lease
    Note over W1: Worker A crashes mid-run
    Note over S: lease expires at T+30s
    D->>S: reclaim expired leases (status=ready again)
    S-->>W2: same job claimed by Worker B
    W2->>S: complete + ack (status=succeeded)
    Note over D,W2: At-least-once: handler must be idempotent

Claim (atomic)

Update ready → leased where run_at <= now and lease is free, returning one row. Use FOR UPDATE SKIP LOCKED or compare-and-set so two dispatchers do not dual-dispatch the same job.

Reclaim

Background sweeper: leased rows with lease_until < now → ready (or immediately re-claimable), increment attempts. Long jobs must heartbeat / extend the lease.

sql

-- Claim due work safely (sketch)
UPDATE jobs
SET status = 'leased',
    lease_owner = $worker_id,
    lease_until = now() + interval '30 seconds',
    attempts = attempts + 1,
    updated_at = now()
WHERE job_id = (
  SELECT job_id FROM jobs
  WHERE queue = $queue
    AND status = 'ready'
    AND run_at <= now()
  ORDER BY priority DESC, run_at ASC
  FOR UPDATE SKIP LOCKED
  LIMIT 1
)
RETURNING *;

The exactly-once illusion

Distributed schedulers almost never deliver true exactly-once. You get effective exactly-once by combining delivery with an and a unique .

How do we get effective exactly-once?

Delivery

At-least-once delivery

lease reclaim / retry

Dedupe

Unique job key

dedupe enqueue

Idempotent job handler

Exactly-once side effects (illusion / effective)

At-least-once

Lease reclaim, retries, and dual dispatch after network blips all redeliver. Design for duplicates.

Idempotent handler

Side effect keyed by job_key / business id. Second run is a no-op or replays the stored result. For a daily invoice, use a key based on account and billing period so two executions target the same invoice. Insert the invoice under a unique constraint inside the transaction that records the business effect. Marking a scheduler row complete before creating the invoice risks losing the effect; marking it afterwards without deduplication risks creating two invoices after a crash.

Unique job key

Enqueue dedupe: same key → return existing job. Stops client retries from creating two timers.

Say in interviews: "We provide at-least-once execution; callers make handlers idempotent; we dedupe by job key. That gives exactly-once effects where it matters."

Capacity math (back-of-envelope)

Convert jobs/day into claim QPS, lease churn, and store size. Interviewers want to see that due spikes and lease heartbeats dominate more than average enqueue rate.

plaintext

Example assumptions
  Jobs/day           = 86,400,000          (~1,000 jobs/sec average)
  Peak / avg ratio   = 10× (aligned crons) → peak due ≈ 10,000 jobs/sec
  Lease duration     = 30s
  Heartbeat interval = 10s (extend lease while running)
  Avg payload        = 2 KB; retention of completed rows = 7 days

Claim / dispatch QPS
  Steady claim ≈ arrival rate ≈ 1,000/s (if backlog ≈ 0)
  Peak claim  ≈ peak due rate ≈ 10,000/s  ← size dispatcher + due index for this
  Add reclaim QPS: expired_leases/sec (crashes + slow workers)

Lease churn
  In-flight jobs ≈ claim_rate × avg_runtime
  If avg_runtime = 5s and claim = 1,000/s → ~5,000 leased rows
  Heartbeat writes ≈ in_flight × (1 / heartbeat_interval)
                   ≈ 5,000 / 10 = 500 writes/sec (steady)
  At peak 10×: ~5,000 heartbeat writes/sec: plan for it

Store size (order of magnitude)
  Waiting + in-flight: depend on backlog depth
  History: 86.4M/day × 7 × 2 KB ≈ 1.2 TB raw (before indexes / compression)
  Due index: keep ready/leased small; archive terminal rows off the hot path

Sizing rule: provision for peak due claim QPS and lease heartbeat write QPS, not average enqueue. Use and jitter so peak due does not equal peak worker fan-out to fragile downstreams.

Failure modes

Clock skew

Workers and store disagree on "now." Prefer store time for due checks; sync NTP; treat client-supplied run_at as wall-clock intent, not trust for leases.

Thundering herd on due time

Millions of jobs at :00. Mitigate with jitter, time buckets, priority lanes, and rate-limited drain.

Poisoned jobs

Bad payload loops forever. Cap attempts → ; alert on DLQ growth; require human or automated quarantine before replay.

Lost workers

Choose a lease long enough to cover normal execution and renew it while long work continues. If typical work takes ten seconds and the lease is two seconds, healthy workers will repeatedly lose ownership; if the lease is an hour, a dead worker may delay recovery for an hour. Completion and renewal must match the current lease generation so an old worker cannot overwrite the replacement’s status.

Dual dispatch

Two claimers, expired lease while first worker still running, or non-atomic claim. Mitigate with atomic claim, / lease generation numbers, and idempotent handlers that reject stale lease generations.

Aligned due times without jitter create a claim spike; smooth it deliberately.

Many jobs due at :00

Claim QPS spike

How to smooth the herd?

Jitter

Add jitter / time buckets

Rate limit

Rate-limited drain

Shard

Shard by key / priority lane

Smoothed worker load

Scheduler vs plain message queue

Queues are great at "run soon with competing consumers." Schedulers need efficient due queries: find what should run now among a huge waiting set. So they need time indexes, not only FIFO offsets.

Dimension	Plain queue / log	Job scheduler
Primary access	Head / offset consume	Due index: `run_at <= now` + priority
Waiting cost	Messages sit in broker; delay features are limited or expensive at huge fan-in	Rows wait cheaply for hours/days; only due set is hot
Recurring work	Producer must re-publish each occurrence	Calendar / next_run materialization built in
Visibility	Visibility timeout common on task queues	Same lease idea + time-based readiness
When to combine	Scheduler decides when; on due, hand off payload to a queue for fan-out execution. Keep time indexing in the scheduler, high-throughput drain in the queue.

Production readiness

A scheduler is production-ready when you can see overdue lag, reclaim safely under failure, degrade without silent data loss, and regularly drill poison and lease-expiry paths.

Metrics & alerts

Due lag: now - min(run_at) for ready jobs (SLO)
Claim latency, claim failures, dual-claim / fencing rejects
Lease reclaim rate; unexpected reclaim spikes ⇒ worker health
Success / fail / retry / DLQ depth; oldest DLQ age
Per-queue backlog and drain rate vs enqueue rate

Degraded mode

Shed low-priority queues; keep billing / security paths
Increase drain rate limit only when store and workers healthy
Pause materialization of new recurring instances if backlog critical
Reject optional enqueues with clear backpressure errors

Testing drills

Kill workers mid-lease; assert reclaim and single logical side effect (idempotent handler)
Inject clock skew between claimer and store; assert store clock wins for due
Enqueue poison payload; assert attempt cap → DLQ, no infinite loop
Fire aligned cron herd with and without jitter; compare claim QPS and downstream errors
Replay from DLQ after fix; assert dedupe by job key

Choosing and explaining distributed job scheduler

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

API enqueues durable jobs; a due index drives claim; workers hold leases; reclaim covers crashes.

We guarantee at-least-once execution; idempotent handlers plus unique job keys give effective exactly-once effects.

Schedulers need time indexes and due queries: unlike plain queues that mainly consume from the head.

Size for peak due claim QPS and lease heartbeat churn, then add jitter and rate-limited drain for cron herds.

When it belongs

Work must run after a delay, on a calendar, or as a one-off outside the request path.

Multiple services would otherwise each run fragile local cron.

Retries, reminders, renewals, or deferred side effects appear in the design.

How it fails

Clock skew makes jobs early/late or lease reclaim incorrect.

Thundering herd when many jobs share the same run_at.

Poisoned jobs burn workers until DLQ and attempt caps exist.

Dual dispatch from non-atomic claim or lease expiry while the first worker still runs.

Trade-offs to weigh

Shorter leases recover faster but increase duplicate runs and heartbeat write load.

Tighter delay accuracy raises claim QPS and store load.

Materializing far-future cron rows wastes storage; lazy next_run needs careful expander HA.

Handing due work to a queue adds hop latency but absorbs execution fan-out.

Common misunderstandings

Calling the system exactly-once without idempotent handlers.

Using only a FIFO queue and scanning for due time (O(n) disaster).

Forgetting lease extension for long jobs.

No DLQ / retry budget: poison loops take down the fleet.

Ignoring priority starvation and midnight aligned schedules.

Deeper: scheduling correctness

Sharded timers and delay queues

A due index lets a dispatcher retrieve jobs whose run time has arrived without scanning all future jobs. Partitioning by time bucket narrows that search, while an additional shard component spreads a popular due instant across owners. Keep unfinished older buckets discoverable after the clock moves forward. Otherwise an overloaded midnight bucket can be forgotten while dispatchers happily process newer timestamps.

Fencing and duplicate recovery

Claim jobs with leases and fencing tokens. Long jobs must extend leases; expired leases reclaim work. Handlers stay idempotent under duplicate delivery.

Misfire, TZ, and DST

Define misfire policy (fire once, skip, catch up). Store schedules in UTC with explicit zone metadata, and test DST transitions so daily jobs do not double-fire or vanish.

Fairness and backfills

Fair scheduling allocates processing opportunities across tenants or classes of work. Reserve some capacity for urgent renewals and some for ordinary jobs, then use age to prevent low-priority work from waiting forever. Backfills should use the same admission controls as live work, with checkpoints and cancellation. A repair job that monopolizes all workers can create the very missed deadlines it is meant to fix.

Takeaway

A distributed job scheduler is a durable plus lease-based claim/reclaim, not a sleep in an app process. Deliver , make handlers , dedupe with unique , partition by time or shard key, and watch and lease churn. Prefer a scheduler when work must wait on a clock; hand off to a queue when you need massive competing-consumer fan-out after the due instant.

Primary sources

Schwarzkopf et al.: Omega (EuroSys 2013): cluster scheduling at scale.
RFC 5545: iCalendar: recurrence rules underpinning schedules.
Temporal Docs: Workflows: durable execution for distributed jobs.

Practice and further reading

Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.

Focus for this lesson: Schedule sharded timers with durable ownership, leases/fencing, retries, idempotency, fairness, DST correctness, backfills, and duplicate recovery.

Explain the decision

Why can “run exactly once” not rely on the scheduler alone?

Read the reasoning

A worker may complete work and crash before acknowledgement; business effects need idempotency or transactional deduplication.

Apply it to a production scenario

A daily 02:30 local-time job encounters a daylight-saving gap. What is the contract?

Read one approach

Define timezone, missing/duplicate local-time behavior, UTC storage, catch-up policy, and surface the chosen semantics to operators.

Work through the numbers

Ten million jobs are due in a 5-minute window. What average dispatch rate is required?

Read the worked calculation

About 33,333 jobs/s before retries and headroom; shard timers and admission to match worker/downstream capacity.

Reason through a failure

What must lease-based job ownership enforce?

Read the recovery reasoning

A stale worker’s fencing token is rejected before it commits effects, even if it resumes after a pause.

Sources and further study

Continue with Batch Processing Algorithms.