Design a distributed job scheduler / task queue
Expected question
"Design a distributed job scheduler / task queue. How do you enqueue, prioritize, execute, retry, and observe background work at scale?"
Variant forms
Same design, different framing:
- "Design a system like Celery/Sidekiq at company scale — millions of jobs/day."
- "How do you schedule cron jobs across a cluster without double execution?"
- "Design priority queues where paid customers' jobs preempt free tier."
- "Our workers keep picking poison messages — architect DLQ and retry with backoff."
- "Design exactly-once vs at-least-once semantics for payment reconciliation jobs."
- "How do you shard a task queue when Redis/SQS becomes the bottleneck?"
- "Design a workflow DAG executor (Airflow-style) with dependency tracking."
Where this actually gets asked
Weakly sourced for company-specific interview attribution: no confirmed Blind/Glassdoor post was found for any of the six companies asking this exact question; generic aggregator lists tag it "asked at Google, Amazon, Microsoft" without individual sourcing behind any one company — treat as an unconfirmed general archetype, not a leaked question. Strong grounding: the real-system grounding: Google's own SRE Book has a dedicated chapter, "Distributed Periodic Scheduling with Cron Service," describing Google's real internal distributed cron system built atop Borg and Paxos-based consensus — a genuine Google primary source. The Borg paper itself (Google Research, republished at EuroSys 2015) is directly relevant background. Use this question as a well-known general distributed-systems archetype, grounded in real, published Google infrastructure, rather than a confirmed company-specific interview prompt.
Executive summary
30-second thesis
I'd ship at-least-once with leases + idempotent jobs — not "exactly-once in the scheduler" — and put the dispatcher behind leader election so a crash doesn't silent-drop the fleet.
2-minute answer
Clarify cron vs one-shot queue, side-effect risk, and priority tiers. Default: enqueue with idempotency key, workers lease with token + visibility timeout sized from p99 duration (H), ack/nack, DLQ after N. Scheduler HA via Raft/etcd-style leader — one active firer, no split-brain double-fire. Poison pills quarantine; infinite retry is an outage. Overdue backlog after outage: priority catch-up, and some jobs should be skipped if stale (job-level policy). Don't design Airflow in 45 minutes unless they ask for DAGs.
What I'd refuse: at-least-once delivery without an idempotency story on the worker. Clock: lock queue + leadership + retry; skip writing etcd.
Quantitative trade-offs
| Decision | Trade-off and reversal evidence | Evidence class |
|---|---|---|
| Short vs long lease | Short → duplicates; long → stuck recovery. Reverse when p99 job time drifts past visibility timeout. | H |
| At-least-once + idempotency vs pretend exactly-once | Idempotency is the real guarantee; reverse only with transactional outbox into a single side-effect store. | R/H |
| Leader-elected cron vs multi-active fire | Leader avoids double-fire; reverse to sharded calendars when one leader can't scan the schedule volume. | H |
Migration and rollout
At-least-once without worker idempotency is a double-charge waiting to happen.
- Require idempotency keys on the scariest job types before you change the broker.
- Dual-consume: new workers with visibility timeout + heartbeat; old workers drain.
- Leadership / partition ownership last — after retry and poison (DLQ) are boring.
- Chaos: kill a worker after the side effect, before ack. If it doubles, stop.
- Rollback = previous queue. Kill switch = pause enqueue of non-idempotent types.
Org ownership and operating model
- Async platform owns the broker, visibility timeout, and DLQ.
- Job owners own idempotency at the downstream API.
- SRE owns backlog SLO and poison-pill runbooks.
- Product owns which work may be delayed vs must page.
- Security owns who may enqueue privileged jobs.
What I'd ask them
- Are job side effects naturally idempotent, or do we need dedup keys in the callee?
- Cron-at-scale or mostly async task queue?
- What's acceptable duplicate rate vs missed-run rate?
Requirements
Functional
- Schedule jobs to run at a specific time or on a recurring interval (cron-style), across a fleet of worker machines.
- Guarantee a scheduled job runs — and, critically, runs exactly once even if the scheduler or a worker fails mid-execution, not zero times (silently dropped) or multiple times (duplicated side effects).
- Support job priorities and retries with backoff for jobs that fail.
Non-functional
- The scheduler itself must not be a single point of failure — a scheduler crash shouldn't mean no jobs run until it's manually restarted.
- Jobs need to be idempotent-safe or the system needs deduplication, since distributed systems generally can't guarantee exactly-once execution without one of these.
- Scale to a very large number of scheduled jobs (Google's real cron service handles this at enormous internal scale) without the scheduling decision itself becoming a bottleneck.
Core entities
- Job definition: what to run, the schedule (cron expression or one-time timestamp), retry policy, and priority.
- Job execution: a specific instance of a job definition firing at a specific time, with a status (pending, running, succeeded, failed).
- Lease: a time-bounded claim by one worker on one job execution, preventing two workers from picking up the same execution simultaneously.
- Worker: a machine capable of executing jobs, reporting health/liveness to the scheduler.
API / interface
Auth: service accounts; workers claim with lease tokens.
POST /v1/queues/{queue}/tasks
Idempotency-Key: <uuid>
{"payload":{...},"delay_sec":0,"max_attempts":5,"timeout_sec":60}
→ 201 {"task_id":"task_...","status":"queued"}
POST /v1/queues/{queue}/lease
{"worker_id":"w_...","max_tasks":10,"lease_sec":30}
→ 200 {"tasks":[{"task_id":"...","lease_token":"lt_...","payload":{...}}]}
POST /v1/tasks/{task_id}/ack
{"lease_token":"lt_...","result":{...}} → 200 {"status":"succeeded"}
POST /v1/tasks/{task_id}/nack
{"lease_token":"lt_...","retryable":true,"error":"..."} → 200 {"status":"queued","attempt":2}
GET /v1/queues/{queue}/stats
→ {"queued":1203,"leased":80,"dlq":4,"oldest_age_sec":12}
Staff+ callout: lease/ack/nack is the correctness API — visibility timeouts without lease tokens are insufficient.
Data Flow
Enqueue → lease → worker execute → ack/nack; leases prevent double-processing under failure.
Rendering architecture diagram…
High-level design
Rendering architecture diagram…
Google's published cron pattern: the scheduler itself runs as a leader-elected, consensus-backed cluster (not a single instance) so a scheduler failure triggers leader re-election rather than a scheduling outage — and job execution uses a time-bounded lease so a worker failure mid-execution results in reassignment, not a silently lost job.
Deep dive 1: exactly-once execution — the actual hard guarantee
Distributed systems fundamentally cannot guarantee true exactly-once execution across a network that can partition or a worker that can crash mid-job — the real, practical answer is at-least-once execution plus idempotency. The scheduler leases an execution to a worker for a bounded time; if the worker doesn't report completion before the lease expires, the execution is reassigned to another worker. This means a job could run twice (the original worker was just slow, not dead, and both it and the reassigned worker complete) — so job definitions need to either be naturally idempotent (safe to run twice) or use a dedup key the job's own side-effect system checks before acting.
| Guarantee | What it actually requires | Real-world approach |
|---|---|---|
| At-most-once | Accept some jobs silently never run | Rarely acceptable for anything that matters |
| At-least-once | Retry on any doubt about completion | The real, practical default — combined with idempotency |
| Exactly-once (in effect) | At-least-once execution + idempotent job logic or a dedup check | The correct target — achieved by combining the above, not by the scheduler alone |
Trap: claiming the scheduler itself can guarantee exactly-once execution through clever engineering alone — a Staff+ answer names this as fundamentally impossible without idempotency and designs for at-least-once-plus-idempotent explicitly.
Deep dive 2: scheduler high availability via consensus
A single-instance scheduler is a hard single point of failure — if it crashes, no jobs fire until it's replaced. Google's real cron-service design (per the SRE Book) runs the scheduler as a small cluster using Paxos-based consensus for leader election: one instance is the active leader firing jobs, the others stand by ready to take over if the leader fails, with consensus ensuring only one leader is ever active at a time (avoiding a split-brain scenario where two schedulers both believe they're the leader and double-fire jobs).
Deep dive 4: lease tuning and poison pills
Too-short leases → duplicate execution; too-long → stuck recovery. Heartbeat to extend; set visibility timeout from p99 job duration. After N failures, quarantine to a DLQ with alert and a replay policy guarded by idempotency — infinite retries are an outage. In 45 minutes, cover lease/ack/idempotency; don't design a full workflow engine.
What's expected at each level
- Mid-level: proposes a single scheduler process with a jobs database, without addressing scheduler failover or exactly-once semantics.
- Senior: identifies the need for scheduler redundancy and a lease-based worker assignment mechanism to handle worker failures.
- Staff+: explicitly names exactly-once execution as unachievable without idempotency, and designs the at-least-once-plus-idempotent-or-dedup pattern rather than claiming the scheduler alone solves it.
- Principal: scheduler HA via consensus — split-brain avoidance, not 'run two instances.' Who inherits: every batch owner. Fail-closed: don't double-fire side effects. Clock: lock at-least-once + idempotency + leadership; skip writing etcd.
Follow-up questions to expect
- "Two schedulers both think they're leader after a partition?" — That's why you use consensus. Majority-ack leader election exists specifically so you don't double-fire; "we elected a leader" without quorum is cosplay.
- "Huge overdue backlog after an outage?" — Catch up by priority, not blind chronological replay. Some jobs are wrong to run late — that has to be per-job policy, not a global default.
Related
- coding/04: Concurrent bounded queue — coding-round backpressure primitive behind many schedulers
- general-system-design/01: Distributed rate limiter — a similar distributed-coordination problem at a different layer
- cloud-architecture/03: Disaster recovery for model serving — the same RTO/RPO reasoning applied to a scheduler outage specifically