Design Distributed Task Scheduler
Cron at scale — leader election, job queue, at-least-once execution, and idempotent workers.
Interview tip Split schedule metadata store from execution queue. Mention leader for cron tick, partition jobs by shard, and visibility timeout for stuck workers.
① Functional requirements
- Register job with cron expression or fixed interval
- Trigger execution at scheduled time
- Retry failed runs with backoff
- Pause/resume and manual trigger
- View run history and status
- Optional DAG dependencies between jobs
② Non-functional requirements
- Fire within 1s of scheduled minute
- 50K concurrent executions
- At-least-once execution with idempotent workers
- Survive scheduler leader failure in <10s
- Fair scheduling across tenants
③ Back-of-the-envelope scale
Assumptions
- 10M jobs → minute tick evaluates subset via time buckets
- 50K workers pull from partitioned queues
- Metadata DB: job defs + run records
- Leader scans next 60s window every second
④ High-level architecture
Task Scheduler
API (job CRUD)
Metadata DB (jobs, runs)
Leader scheduler (elected)
Execution queues (sharded)
Worker pool
Only leader advances cron clock. Enqueues run_id to shard queue by hash(job_id). Workers ack after success; visibility timeout requeues on crash.
⑤ Data flow & execution path
Scheduled run execution
① Leader tick→② Enqueue run→③ Worker pull→④ Execute + log→⑤ Ack / retry
Leader election via etcd lease
Time bucket index for O(log n) job lookup
Idempotency key = run_id in worker
DLQ after max retries
Explain how you avoid double-fire when leader fails mid-tick — transactional outbox or lease-bound tick version.
⑥ API & interfaces
| Endpoint / flow | Purpose | Notes |
|---|---|---|
| POST /jobs | Create scheduled job | cron + payload + retry policy |
| POST /jobs/{id}/run | Manual trigger | enqueue immediately |
| GET /runs/{id} | Run status | pending|running|success|failed |
| DELETE /jobs/{id} | Remove schedule | soft delete + stop future runs |
⑦ Data model & storage
Job: id, cron, payload, tenant, next_run_at. Run: run_id, job_id, status, started_at, attempts.
| Store | What | Why |
|---|---|---|
| PostgreSQL | Job metadata + runs | ACID for schedule state |
| Redis/SQS queues | Execution queue | Sharded by job_id hash |
| etcd | Leader lock | Single active scheduler |
⑧ Deep dive — core components
Cron evaluation at 10M jobs
Bucket jobs by next_run minute in Redis sorted set. Leader pulls due bucket only — not scan 10M rows. Pre-compute next_fire on each execution.
Exactly-once vs at-least-once
True exactly-once hard — use at-least-once + idempotent workers (dedupe by run_id). Optional dedupe store with TTL for side effects.
⑨ Trade-offs & alternatives
| Decision | Option A | Option B | Pick when |
|---|---|---|---|
| Queue | Kafka | SQS | Kafka ordering per partition; SQS simpler ops |
| Leader | Single leader | Distributed tick | Single leader simpler; shard leaders for scale |
| DAG | Built-in | External orchestrator | DAG adds complexity — scope carefully |
| Storage | SQL | etcd only | SQL for history queries; etcd for small coordination |
⑩ 45-minute interview script
- 0–5 min: Cron + execution requirements
- 5–12 min: Scale — jobs vs executions/sec
- 12–22 min: Leader + queue + workers
- 22–32 min: Failure, retry, idempotency
- 32–40 min: DAG mention if time
⑪ Likely follow-up questions
| Question | Short answer |
|---|---|
| Job runs long past next schedule? | Skip or queue overlapping run based on policy; max_concurrent_runs per job |
| Timezone handling? | Store cron in UTC + tenant TZ; convert at schedule registration |
| Priority queues? | Separate queues per priority tier; workers poll high first |
⑫ Revision checklist
- Leader election
- Time-bucket job index
- Sharded execution queues
- Visibility timeout
- Idempotent run_id
- Run history audit
- Tenant fair-share
- DLQ for poison jobs