Distributed Task Scheduler

Problem Statement & Requirements

Design a distributed task scheduling system that reliably enqueues, schedules, and executes tasks (jobs) across a fleet of workers at massive scale — similar to Celery, Temporal, Apache Airflow, Sidekiq, or cloud-native solutions like AWS Step Functions and Google Cloud Tasks.

Functional Requirements

• One-time tasks — submit a task for immediate execution (e.g., "send this email now")
• Delayed tasks — schedule a task for a specific future time (e.g., "send reminder in 24 hours")
• Recurring / Cron tasks — periodic execution on a cron schedule (e.g., "run report every Monday 9am")
• Task priorities — high, medium, low; high-priority tasks execute before low-priority ones
• Task dependencies (DAG) — task B runs only after task A succeeds (workflow/pipeline orchestration)
• Retry with backoff — configurable retry count, exponential backoff, dead-letter queue for exhausted retries
• Task status tracking — query status: PENDING, SCHEDULED, RUNNING, SUCCEEDED, FAILED, RETRYING, DEAD
• Cancellation — cancel a pending or scheduled task before it starts
• Rate limiting — limit execution rate per task type (e.g., max 100 emails/sec)
• Timeout enforcement — kill tasks that exceed max_execution_time
• Result storage — persist task output for callers to retrieve
• Idempotency — support idempotency keys to prevent duplicate execution

Non-Functional Requirements

• Exactly-once execution — each task must execute exactly once (or at-least-once with idempotency)
• Low scheduling latency — task picked up by worker within < 100 ms of its scheduled time
• High throughput — schedule and execute millions of tasks per day
• High availability — survive node failures with zero task loss
• Horizontal scalability — add workers to increase execution throughput linearly
• Durability — submitted tasks must not be lost (persisted before ACK)
• Fairness — one tenant's burst of tasks must not starve other tenants
• Observability — metrics, logs, distributed tracing per task execution

Out of Scope

• Stream processing (Kafka Streams / Flink — different paradigm)
• Full workflow DSL (Temporal's detailed workflow-as-code semantics)
• Map-reduce / batch analytics (Spark / Hadoop territory)

Scale Estimations

Traffic

Storage

Bandwidth

Hardware Estimate

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

API Design

Submit Task

POST /api/v1/tasks
Content-Type: application/json

Request:
{
  "task_type": "send_email",
  "payload": {
    "to": "user@example.com",
    "subject": "Welcome!",
    "template_id": "onboarding-v2"
  },
  "priority": "high",                    // high | medium | low
  "scheduled_at": "2026-04-04T09:00:00Z", // null = immediate
  "max_retries": 3,
  "retry_backoff": "exponential",         // exponential | fixed | linear
  "retry_delay_seconds": 60,             // base delay between retries
  "timeout_seconds": 300,                // kill if running > 5 min
  "idempotency_key": "welcome-user-123", // prevent duplicate submission
  "queue": "email-queue",                // logical queue for routing
  "metadata": {
    "tenant_id": "acme-corp",
    "correlation_id": "req-abc"
  }
}

Response (202 Accepted):
{
  "task_id": "task-7f3a9b2c",
  "status": "SCHEDULED",
  "scheduled_at": "2026-04-04T09:00:00Z",
  "created_at": "2026-04-03T10:00:00Z"
}

Create Recurring (Cron) Task

POST /api/v1/cron-tasks
Content-Type: application/json

Request:
{
  "name": "daily-report-generation",
  "cron_expression": "0 9 * * 1-5",       // 9am weekdays
  "timezone": "America/New_York",
  "task_type": "generate_report",
  "payload": {
    "report_type": "daily_sales",
    "recipients": ["team@acme.com"]
  },
  "max_retries": 2,
  "timeout_seconds": 600,
  "overlap_policy": "skip",               // skip | queue | cancel_running
  "enabled": true
}

Response (201 Created):
{
  "cron_id": "cron-8a4b1c",
  "name": "daily-report-generation",
  "next_fire_time": "2026-04-04T09:00:00Z",
  "status": "ACTIVE"
}

Submit DAG Workflow

POST /api/v1/workflows
Content-Type: application/json

Request:
{
  "workflow_name": "user-onboarding",
  "tasks": [
    {
      "task_id": "create-account",
      "task_type": "create_account",
      "payload": {"user": "alice@example.com"},
      "dependencies": []
    },
    {
      "task_id": "send-welcome-email",
      "task_type": "send_email",
      "payload": {"template": "welcome"},
      "dependencies": ["create-account"]
    },
    {
      "task_id": "setup-defaults",
      "task_type": "setup_user_defaults",
      "payload": {},
      "dependencies": ["create-account"]
    },
    {
      "task_id": "notify-sales",
      "task_type": "notify_slack",
      "payload": {"channel": "#new-users"},
      "dependencies": ["send-welcome-email", "setup-defaults"]
    }
  ]
}

Response (202 Accepted):
{
  "workflow_id": "wf-c5d2e1",
  "status": "RUNNING",
  "tasks": {
    "create-account": "PENDING",
    "send-welcome-email": "BLOCKED",
    "setup-defaults": "BLOCKED",
    "notify-sales": "BLOCKED"
  }
}

Query Task Status

GET /api/v1/tasks/{task_id}

Response (200 OK):
{
  "task_id": "task-7f3a9b2c",
  "task_type": "send_email",
  "status": "SUCCEEDED",
  "priority": "high",
  "created_at": "2026-04-03T10:00:00Z",
  "scheduled_at": "2026-04-04T09:00:00Z",
  "started_at": "2026-04-04T09:00:00.045Z",
  "completed_at": "2026-04-04T09:00:01.230Z",
  "duration_ms": 1185,
  "attempts": 1,
  "worker_id": "worker-42",
  "result": {"message_id": "msg-xyz789"},
  "metadata": {"tenant_id": "acme-corp"}
}

Cancel Task

POST /api/v1/tasks/{task_id}/cancel

Response (200 OK):
{
  "task_id": "task-7f3a9b2c",
  "status": "CANCELLED",
  "cancelled_at": "2026-04-03T12:00:00Z"
}

Behavior:
  PENDING/SCHEDULED → immediately set to CANCELLED
  RUNNING → send cancellation signal to worker;
            worker should check cancellation flag periodically
  SUCCEEDED/FAILED → 409 Conflict (already terminal)

Data Model

Task Record

Cron Task Definition

Workflow (DAG) Record

Task State Machine

Core Design Decisions

Decision 1: How to Implement the Delayed Task Queue

The hardest problem: efficiently waking up tasks at the right time among 500 million waiting tasks.

Option A: Database Polling

Option B: Redis Sorted Set (ZSET)

Option C: Hierarchical Timing Wheel

Recommendation: Redis Sorted Set + Database Backup

Decision 2: Task Dispatch — Push vs Pull

Decision 3: Exactly-Once Execution

Detailed Flow Diagrams

Immediate Task Execution Flow

Delayed Task Flow

Cron Evaluation Flow

DAG Workflow Execution Flow

Separate finding due tasks from executing them. Index or bucket scheduling records by due time so each tick does not scan the whole task table. Dispatch in bounded batches, and apply per-tenant or per-queue concurrency limits so a large overdue batch does not starve newly due work.

Priority Queue Implementation

Multi-Level Priority Queues

Multi-Tenant Fairness

Handling Edge Cases

Clock Skew in Distributed Schedulers

Problem: Multiple scheduler nodes with slightly different clocks
  Node A (clock +2s ahead): fires cron task at T-2s (too early)
  Node B (clock -1s behind): doesn't see task as due yet

Solution:
  1. NTP sync all nodes (< 100ms drift acceptable)
  2. Cron evaluator uses single source of time (DB's NOW() function)
  3. Delayed queue poller uses Redis TIME command (server-side clock)
  4. Always compare against the same clock, not local system time

Worker Dies Mid-Execution

Problem: Worker starts processing "charge_credit_card"
         → charges the card → crashes before ACK

Scenario: Task re-enqueued → new worker charges card AGAIN

Solution: Lease + Idempotency (defense in depth)

  Layer 1: Lease-based timeout
    Worker must heartbeat every 90s (lease = 5 min)
    No heartbeat in 5 min → task re-enqueued
    → Ensures no task is stuck forever

  Layer 2: Idempotency at application level
    charge_credit_card(idempotency_key="order-123-charge")
    → Stripe sees same idempotency key → returns original result
    → No double charge even if task runs twice

  Layer 3: Checkpoint for long tasks
    Long-running tasks (e.g., 30 min data pipeline):
    → Save progress to checkpoint store every N records
    → On retry, resume from last checkpoint
    → Avoids reprocessing entire dataset

Queue Buildup / Backpressure

Problem: Producers submit 100K tasks/s, workers process 50K/s
         → Queue grows unboundedly → memory/disk exhaustion

Solution: Multi-layer backpressure

  Layer 1: Per-tenant rate limiting at API gateway
    → Max 1,000 submissions/sec per tenant
    → Return 429 Too Many Requests

  Layer 2: Queue depth alerting
    → Alert when queue depth > 100K
    → Auto-scale worker fleet (k8s HPA on queue depth metric)

  Layer 3: Queue depth limit
    → Hard cap: reject new tasks when queue > 10M
    → Return 503 Service Unavailable with Retry-After header

  Layer 4: Priority shedding
    → When overloaded, drop low-priority tasks first
    → Move to overflow queue (processed when load decreases)

Cron Double-Fire Prevention

Problem: Two cron evaluator nodes both see "next_fire_time <= now"
         → Both create task instances → duplicate execution

Solution: Optimistic locking on cron record

  Evaluator A:
    UPDATE cron_tasks
    SET last_fired_at = now(),
        next_fire_time = compute_next(cron_expr)
    WHERE cron_id = 'cron-8a4b1c'
      AND next_fire_time = '2026-04-04T09:00:00Z'  ← CAS guard
    
  → If another evaluator already updated next_fire_time,
    this UPDATE affects 0 rows → skip (no duplicate)
  → Only one evaluator wins the CAS → exactly one task created

  Combined with: FOR UPDATE SKIP LOCKED
    → Multiple evaluators process different cron jobs in parallel
    → Same cron job processed by exactly one evaluator

Tradeoffs & Design Decisions Summary

Retry & Error Handling

Retry Strategy

Dead Letter Queue

Classifying Errors

Reliability & Fault Tolerance

Single Points of Failure & Mitigations

Failure Scenarios

Scenario 1: Worker crashes mid-task
  → Lease expires (5 min) → task re-enqueued → new worker picks up
  → Idempotency key prevents duplicate side effects
  → Worst case: 5 min delay (tunable via lease duration)

Scenario 2: Redis queue node fails
  → Redis Cluster failover to replica (~5-15s)
  → During failover: workers retry BRPOP → brief delay
  → If full Redis cluster down: schedulers fall back to DB polling
    SELECT ... WHERE status='PENDING' FOR UPDATE SKIP LOCKED
  → Tasks not lost (DB is the source of truth)

Scenario 3: Scheduler node fails
  → Other scheduler nodes pick up its cron evaluations
  → FOR UPDATE SKIP LOCKED ensures no conflicts
  → Zero impact on already-queued tasks

Scenario 4: Database primary fails
  → Automatic failover to standby (30-60s typically)
  → During failover: task submissions return 503, retry with backoff
  → Workers continue executing already-dispatched tasks
  → Tasks in Redis queue continue processing

Scenario 5: Network partition (split brain)
  → Redis min-replicas-to-write prevents split-brain writes
  → DB standby promotion only if primary unreachable by quorum
  → Workers on isolated side: leases expire, tasks re-enqueued

Data Recovery

High-Level Architecture

Component Breakdown

Full System Architecture (Production-Grade)

Comparison: Task Scheduler vs Related Systems

Interview Tips

1. Start with the task lifecycle state machine — Draw the states (SUBMITTED → SCHEDULED → PENDING → RUNNING → SUCCEEDED/FAILED/RETRYING → DEAD). This immediately shows you understand the full system.

2. Delayed queue is the core challenge — Don't handwave "just use a queue." Explain why 500M delayed tasks need a sorted data structure (Redis ZSET), how the poller works (ZRANGEBYSCORE every 100ms), and why DB polling doesn't scale.

3. Pull vs Push is a key tradeoff — Explain why pull is better: workers self-regulate via backpressure, no centralized scheduler bottleneck, natural load balancing. Mention BRPOP for blocking pull (no polling waste).

4. Exactly-once is a lie (but achievable in practice) — Explain the reality: at-least-once delivery + idempotent execution = effectively exactly-once. The lease + heartbeat + idempotency key pattern is critical to understand.

5. Retry strategy with jitter — Don't just say "retry 3 times." Explain exponential backoff (60s → 120s → 240s), why jitter prevents thundering herd, and how error classification (retryable vs permanent) saves worker capacity.

6. Cron double-fire prevention — Multiple scheduler nodes evaluating crons = duplicate tasks. Solution: optimistic CAS on next_fire_time. Show the SQL: UPDATE ... WHERE next_fire_time = :expected. Only one node wins.

7. DAG execution engine — Draw the dependency graph. Explain how the engine evaluates after each task completion: "are all dependencies of X met? If yes, enqueue X." Show parallel execution of independent tasks.

8. Multi-tenant fairness — One tenant's 1M-task burst shouldn't starve others. Explain per-tenant queues with weighted round-robin dispatch. Connect to real-world: SaaS platform serving multiple customers.

9. Worker auto-scaling — Scale workers based on queue depth, not CPU. Kubernetes HPA with custom metric: queue_depth / desired_processing_rate = target_workers. Show the feedback loop.

10. End with observability — Task schedulers are notoriously hard to debug. Mention distributed tracing per task (submission → queue wait → execution), DLQ alerting (tasks that permanently fail need human attention), and cron fire accuracy monitoring.