Walkthrough: Designing a Distributed Job Scheduler

The problem

You’re asked to design a distributed job scheduler — something like: “Design a system that accepts, schedules, and reliably executes tasks at scale. Support recurring cron jobs, one-off delayed tasks, and dependent task workflows.”

Sounds like a queue with a timer. It isn’t. This is a distributed coordination problem disguised as a CRUD application. The trap is the tick problem: how does the system discover which tasks are due right now without scanning millions of rows every second? Naive polling collapses under load; naive partitioning creates thundering herds at clock-aligned boundaries (midnight, top-of-hour). The design hinges on how you find due tasks efficiently and guarantee exactly-once-ish execution across unreliable workers.

Below is how I’d walk through this.

1. Requirements

Functional requirements

• R1. Users submit tasks with an execution time (immediate, delayed, or recurring).
• R2. The system triggers tasks within a bounded delay of their scheduled time.
• R3. Tasks execute at-least-once with near-idempotent semantics (no silent drops).
• R4. Users can query task status (pending, running, succeeded, failed).
• R5. Support recurring schedules (cron expressions) that auto-generate future instances.
• R6. Support task dependencies — a task runs only after its prerequisites complete.

Scope

This design covers scheduling and dispatch. Explicitly out of scope:

• The task execution runtime itself (what the task does — that’s the worker’s business)
• A full workflow UI/authoring tool (we support DAGs; building a visual editor is separate)
• Multi-tenant billing and quotas (real systems need it; not a design driver here)
• Result storage beyond status (task output goes to the caller’s storage, not ours)

Non-functional requirements

• Scale. How many tasks per day? What’s the peak-to-average ratio? Are most tasks clock-aligned (top-of-hour cron) or uniformly distributed?
• Timing precision. What latency between “due time” and “dispatch” is acceptable? Sub-second? Sub-minute? This determines whether we can batch or must stream.
• Durability. Can we lose tasks? (No.) Can we execute them twice? (Yes, if workers are idempotent — at-least-once is the contract.)
• Availability. Can the scheduler itself go down? What happens to in-flight tasks?

Say the interviewer confirms: 1B+ tasks/day, peak-to-average ratio ~10x (clock-aligned spikes), timing precision within 1 second of due time, at-least-once delivery, tasks are idempotent, support cron + delayed + DAG variants.

2. Capacity estimate

• Tasks: 1B/day ≈ 12K tasks/sec average
• Peak (clock-aligned): 10x average = 120K tasks/sec in spike windows
• Thundering herd: 30% of daily tasks fire at common boundaries (midnight, top-of-hour). That’s 300M tasks in ~3,600 one-second windows = 83K tasks/sec sustained for an hour, with microsecond-scale spikes of 300K+ at the exact boundary.
• Storage: 1B tasks/day × 500 bytes metadata × 7 days retention ≈ 3.5 TB hot storage
• State transitions: each task has 3–5 state changes (created → pending → running → done/failed). At 1B tasks/day, that’s 3–5B state writes/day ≈ 35–60K writes/sec.

I’d say out loud: “The 300K tasks/sec thundering herd at clock boundaries is THE design-shaping constraint. The triggering mechanism must handle this burst without scanning the full task table, and the dispatch layer must absorb it without overwhelming workers.”

3. High-level architecture

The job scheduler has four logical subsystems:

1. Task ingestion — accepts task submissions, validates, persists to durable storage.
2. Trigger engine — discovers which tasks are due and emits dispatch events.
3. Dispatcher — assigns due tasks to available workers with execution guarantees.
4. Worker fleet — executes tasks, reports status back.

flowchart TD
  Client[Client] --> API[API Gateway]

  API --> TaskSvc[Task Service]
  TaskSvc --> TaskDB[(Task Store)]
  TaskSvc --> TriggerEngine[Trigger Engine]

  TriggerEngine --> ReadyQueue[(Ready Queue)]
  ReadyQueue --> Dispatcher[Dispatcher]
  Dispatcher --> Workers[Worker Fleet]
  Workers -->|status| TaskSvc

The trigger engine is the part that decides the system’s character — it’s the clock that turns “scheduled” into “ready.”

4. Architecture evolution

Each level preserves the previous one as a degradation fallback — Level 4 degrades to Level 3 polling when a time-wheel partition fails; Level 3 degrades to Level 2 with smaller partitions.

I’m designing for Level 4: partitioned time-wheel triggering with pull-based dispatch. I’d say out loud: “I’m designing for Level 4. The trigger engine uses time-wheels to avoid scanning, dispatch uses pull-based assignment to handle backpressure, and DAG support is layered on top without changing the core dispatch mechanism.”

Target architecture (Level 4)

This is the complete system. Every section that follows explains one part of this diagram:

flowchart TD
  Client[Client] --> API[API Gateway]

  API --> TaskSvc[Task Service]
  TaskSvc --> TaskDB[(Task Store)]
  TaskSvc --> CronResolver[Cron Resolver]
  CronResolver --> TimeBucket[(Time Buckets)]

  TimeBucket --> TriggerEngine[Trigger Engine]
  TriggerEngine --> ReadyQueue[(Ready Queue)]

  ReadyQueue --> Dispatcher[Dispatcher]
  Dispatcher --> Workers[Worker Fleet]
  Workers -->|heartbeat + status| Dispatcher
  Dispatcher -->|state update| TaskDB

  DAGResolver[DAG Resolver] --> TaskDB
  DAGResolver -->|unblock| TimeBucket

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class TaskDB,TimeBucket,ReadyQueue store

5. Core design choice: the tick mechanism

This is the question within the question. How does the system know which tasks are due right now? Three approaches:

(a) Database polling. Every N milliseconds, query: SELECT * FROM tasks WHERE due_time <= now() AND status = 'pending' LIMIT batch_size. Simple. Doesn’t scale — at 1B tasks, even with an index on due_time, the query touches too many rows during thundering-herd windows.

(b) Redis sorted sets (ZSET). Store task IDs scored by due-time. Use ZRANGEBYSCORE to fetch due tasks. Better — O(log N) per operation. But a single ZSET can’t hold 1B entries, and clock-aligned spikes create hot-key problems on the shard holding the current time window.

(c) Hierarchical time wheel. Partition time into slots (e.g., 1-second buckets). Each bucket holds only the tasks due in that second. The trigger engine advances one slot per tick — O(1) to find due tasks, O(bucket size) to process them. Thundering herds are handled by pre-sharding the hot buckets.

How the time wheel works

Picture a clock with 3,600 slots (one per second in an hour). Each slot is a bucket holding task IDs due at that second. A pointer advances one slot per second. When it lands on a slot, all tasks in that bucket become “ready.”

For tasks more than one hour away, use hierarchical wheels: a minute wheel (60 slots), an hour wheel (24 slots), and a day wheel. A task scheduled 3 hours from now goes into the hour wheel. When that hour-slot ticks, it cascades — moving its tasks down into the appropriate second-slots of the lower wheel.

At tick time, the work is O(bucket size), not O(total tasks). For 1B daily tasks distributed uniformly, each second-bucket holds ~12K tasks. For clock-aligned spikes, a midnight bucket might hold 300K — still bounded and pre-knowable.

Tradeoff matrix

Architecture decisions

Core data structures

6. Trigger and dispatch path [R1, R2, R3]

flowchart TD
  CronResolver[Cron Resolver] -->|next instance| TimeBucket[(Time Buckets)]
  TimeBucket --> TriggerEngine[Trigger Engine]
  TriggerEngine -->|due tasks| ReadyQueue[(Ready Queue)]
  ReadyQueue --> Dispatcher[Dispatcher]
  Dispatcher --> Workers[Worker Fleet]
  Workers -->|heartbeat| Dispatcher

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class TimeBucket,ReadyQueue store

Step by step:

1. Task arrives. Task service computes the due time (immediate, delayed, or next cron instance) and inserts the task ID into the appropriate time-wheel bucket.
2. Wheel ticks. Every second, the trigger engine advances the pointer and reads the current bucket. All task IDs in that bucket become “due.”
3. Emit to ready queue. Due tasks move to the ready queue, partitioned by priority and worker type. This is the buffer between triggering and dispatch — it absorbs thundering herds.
4. Workers pull. Workers long-poll the ready queue for tasks matching their type. Each pull atomically claims a task (status: pending → running) using a compare-and-swap on the task’s version column.
5. Lease and heartbeat. The claimed task has a lease (e.g., 60 seconds). The worker must heartbeat within the lease period. If it doesn’t, the dispatcher assumes failure and re-enqueues the task.
6. Completion. Worker reports success or failure. Task state transitions to succeeded or failed. For recurring tasks, the cron resolver computes the next instance and inserts it into a future time-wheel bucket.

The state machine

Every task follows a strict state machine. Transitions are protected by optimistic concurrency (version column):

CREATED → PENDING → READY → RUNNING → SUCCEEDED
                                    → FAILED → PENDING (retry)
                         → TIMED_OUT → PENDING (re-enqueue)

Each transition is a conditional update: UPDATE task SET status = 'running', version = version + 1 WHERE task_id = ? AND version = ?. If the CAS fails, another worker already claimed it — the losing worker backs off. This gives at-most-one-active-execution without distributed locks.

7. Recurring tasks (Cron) [R5]

The cron variant is the most common interview framing. The key insight: don’t store all future instances — generate them one at a time.

flowchart TD
  TaskSvc[Task Service] --> CronResolver[Cron Resolver]
  CronResolver --> TimeBucket[(Time Buckets)]
  TimeBucket --> TriggerEngine[Trigger Engine]
  TriggerEngine -->|fires| ReadyQueue[(Ready Queue)]
  ReadyQueue --> Workers[Worker Fleet]
  Workers -->|done| TaskSvc
  TaskSvc -->|next instance| CronResolver

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class TimeBucket,ReadyQueue store

How it works:

1. User submits a cron expression (e.g., 0 0 * * * — daily at midnight).
2. Cron resolver parses the expression and computes the next due time only.
3. One task instance is placed in the corresponding time-wheel bucket.
4. When it fires and completes (or fails), the cron resolver computes the next instance and inserts it into a future bucket.
5. This chain continues indefinitely until the user disables the schedule.

Why generate-one-at-a-time: a cron job that runs every minute for a year would create 525,600 task instances upfront. At 1M recurring schedules, that’s 525B rows — absurd. Generate only the next instance; the chain is self-sustaining.

Thundering-herd mitigation for cron

The problem: 0 * * * * (every hour) is the most common cron expression. At the top of every hour, millions of tasks fire simultaneously.

Mitigations:

• Jitter injection. Add random jitter (0–30 seconds) to clock-aligned cron tasks unless the user explicitly requires exact timing. Transform the spike from a vertical wall into a 30-second ramp.
• Pre-warming. The trigger engine inspects the next few buckets in advance. If the 00:00:00 bucket has 300K tasks, it begins pre-staging them in the ready queue seconds before the tick — spreading the dispatch load.
• Sharded trigger nodes. Different trigger engine nodes own different time-wheel partitions. The midnight bucket is split across nodes, each firing their subset independently.

8. Delay queue and DAG variants [R1, R6]

Delay queue (event-driven scheduling)

A delayed task is simpler than cron: compute now() + delay, insert into the corresponding time-wheel bucket. No chaining, no next-instance logic.

The interesting case is high-volume delayed tasks with fragmented due times (e.g., millions of “remind user 2 hours before flight” tasks, each at a different second). The time wheel handles this naturally — each task lands in its own second-bucket, no clustering, no hot spots.

DAG orchestration (dependency-driven)

For tasks with dependencies (Task B runs only after Task A succeeds), add a DAG resolver layer:

1. When a task completes, the DAG resolver checks: “Does this unblock any downstream tasks?”
2. For each unblocked task (all predecessors succeeded), insert it into the time-wheel with due_time = now (immediate execution).
3. The unblocked task flows through the normal trigger → ready queue → dispatch path.

task_dependency:
  partition key:  task_id (the downstream task)
  columns:        predecessor_ids[], satisfied_count, total_predecessors

On each predecessor completion: UPDATE task_dependency SET satisfied_count = satisfied_count + 1 WHERE task_id = ? IF satisfied_count < total_predecessors. When satisfied_count == total_predecessors, the task is unblocked.

Variant comparison

For the real-time dispatcher variant (ride-hailing), the time wheel is irrelevant — tasks need immediate matching, not scheduled firing. I’d mention this variant as out-of-scope for this design and note it requires a fundamentally different architecture (spatial indexing, real-time bidding).

9. API design [R1, R4, R5, R6]

POST /api/tasks                              [R1 — submit a task]
  body:    { task_type, payload, schedule: { type: "immediate"|"delayed"|"cron",
             due_time?, cron_expression?, delay_seconds? },
             dependencies?: [task_id, ...],
             idempotency_key }
  returns: { task_id, status: "created", due_time }

GET /api/tasks/{task_id}                     [R4 — query status]
  returns: { task_id, status, created_at, started_at?, completed_at?,
             attempts, last_error? }

DELETE /api/tasks/{task_id}                   [R5 — cancel/disable]
  returns: { ok, cancelled_instances: count }

GET /api/tasks/{task_id}/history             [R4 — execution history for recurring]
  query:   ?limit=20&next_token=<opaque>
  returns: { executions: [...], next_token }

Non-obvious decision: idempotency key on submission. Without it, a client retry after a timeout creates duplicate tasks. The scheduler deduplicates on (idempotency_key, task_type) with a 24-hour window. This is load-bearing because at-least-once delivery means workers may see a task twice — but scheduling a task twice is worse (it runs twice on separate schedules, not just twice in one execution).

The API abstracts over all scheduling variants — the client doesn’t know whether the task goes through a time wheel, a DAG resolver, or immediate dispatch. The schedule object is the only thing that differs, and the backend routes accordingly.

10. Data model and storage

Requirements → components

Access frequency

Storage technology choices

Access pattern matrix

Schemas

Tasks [R1, R3, R4]

tasks (PostgreSQL, partitioned by created_week):
  task_id          UUID PRIMARY KEY
  idempotency_key  TEXT UNIQUE (within 24h window)
  task_type        TEXT
  payload          JSONB
  status           ENUM(created, pending, ready, running, succeeded, failed, cancelled)
  version          INT DEFAULT 0
  schedule_type    ENUM(immediate, delayed, cron)
  cron_expression  TEXT NULL
  due_time         TIMESTAMP
  lease_expires_at TIMESTAMP NULL
  attempts         INT DEFAULT 0
  max_retries      INT DEFAULT 3
  created_at       TIMESTAMP
  started_at       TIMESTAMP NULL
  completed_at     TIMESTAMP NULL
  last_error       TEXT NULL

Partitioned by created_week for cheap TTL — drop old partitions instead of deleting rows. The version column enables optimistic concurrency on state transitions.

Time buckets [R2] (Redis)

Key:    bucket:{wheel_level}:{slot_index}
Type:   Sorted Set
Score:  task priority (lower = higher priority)
Member: task_id
TTL:    slot_width + grace period (auto-cleanup)

Each bucket lives for exactly one tick cycle plus a grace period for late processing. Redis handles the ephemeral nature perfectly — no manual cleanup needed.

Task dependencies [R6]

task_dependencies (PostgreSQL):
  downstream_task_id  UUID (PK, FK → tasks)
  predecessor_ids     UUID[]
  satisfied_count     INT DEFAULT 0
  total_predecessors  INT

The atomic operation: UPDATE task_dependencies SET satisfied_count = satisfied_count + 1 WHERE downstream_task_id = ? AND satisfied_count < total_predecessors RETURNING satisfied_count, total_predecessors. When they’re equal, unblock.

11. Deep dives

Lease mechanism and failure detection

When a worker claims a task, it gets a lease (default: 60 seconds). The worker must send heartbeats to extend the lease. If the lease expires without a heartbeat, the dispatcher assumes the worker crashed and re-enqueues the task.

How it works step by step:

1. Worker pulls task. Dispatcher sets lease_expires_at = now() + 60s and status = running.
2. Worker sends heartbeat every 15 seconds: UPDATE tasks SET lease_expires_at = now() + 60s WHERE task_id = ? AND version = ?.
3. A background reaper scans for WHERE status = 'running' AND lease_expires_at < now(). These are zombies — re-enqueue them to the ready queue with attempts += 1.
4. If attempts > max_retries, move to failed permanently.

The 60-second lease is a tradeoff: too short and healthy workers get their tasks stolen during GC pauses; too long and crashed-worker tasks sit idle. 60 seconds with 15-second heartbeats gives 4 missed heartbeats before reclaim — enough to ride out transient issues.

Exactly-once semantics (why we don’t promise it)

True exactly-once execution across distributed systems requires either:

• Distributed transactions between scheduler and worker (2PC — too expensive at 12K/sec)
• Worker-side deduplication with a global execution log (adds latency to every task)

Instead, the contract is at-least-once delivery + idempotent workers. The scheduler guarantees every task runs at least once. Workers guarantee that running twice produces the same result as running once. This is the same contract used by AWS SQS, Google Cloud Tasks, and most production job schedulers.

Duplicate execution happens in two scenarios:

1. Worker completes task but crashes before reporting success → lease expires → re-enqueue.
2. Network partition: worker is alive but heartbeat doesn’t reach dispatcher → reclaim.

Both are rare (< 0.01% of tasks) and handled by worker-side idempotency.

Backpressure and worker capacity

The pull-based model is self-regulating, but during sustained thundering herds the ready queue grows unboundedly. Three layers of protection:

1. Queue depth monitoring. Alert when ready queue depth exceeds N minutes of drain time at current worker capacity. This is the earliest signal that workers can’t keep up.
2. Worker auto-scaling. Scale worker fleet based on queue depth. New workers immediately begin pulling — no configuration push needed.
3. Admission control. If the queue exceeds a critical threshold, the task service begins rejecting new submissions with HTTP 429 and a Retry-After header. This prevents cascade failure where new submissions pile on top of an already-overwhelmed system.

12. Failure modes

Timing failures

Trigger engine node crashes

Threatens: timing precision.

The time wheel advances one slot per second. If the trigger node dies, no tasks fire. Mitigation: each time-wheel partition is owned by a trigger node with a standby. Leadership is managed via ZooKeeper or etcd lease. On failover, the new leader reads the current time, catches up any missed buckets (they’re still in Redis), and resumes ticking. Missed tasks fire late — seconds, not minutes — because the buckets are durable.

Clock skew between trigger nodes

Threatens: timing precision.

Different trigger nodes own different time-wheel partitions. If their clocks disagree, tasks may fire early or late. Mitigation: all nodes sync via NTP with tight bounds (< 100ms drift). The time-wheel slot width (1 second) provides natural tolerance — 100ms skew within a 1-second bucket is invisible.

Execution failures

Worker crashes mid-task

Threatens: execution reliability.

The lease mechanism handles this: no heartbeat → lease expires → re-enqueue. The task may have partially executed. This is why the idempotency contract exists — the worker must be able to re-run safely. For non-idempotent tasks, the worker should checkpoint progress to external storage before reporting completion.

Ready queue (Kafka) partition unavailable

Threatens: execution reliability (for affected worker types).

Tasks in that partition’s worker type stop dispatching. Other worker types are unaffected. Mitigation: Kafka replication (3 replicas, min.insync = 2). On partition leader failure, Kafka elects a new leader within seconds. Tasks resume. The time wheel continues ticking and buffering into other healthy partitions.

Correctness failures

Duplicate execution after lease timeout

Threatens: correctness.

Worker A holds a task, experiences a long GC pause (> 60s). Dispatcher reclaims and gives it to Worker B. Now both are executing the same task. Mitigation: the worker checks its lease validity before committing results — UPDATE tasks SET status = 'succeeded' WHERE task_id = ? AND version = expected_version. Worker A’s commit fails (version mismatch), and it discards its result. Combined with worker-side idempotency, this bounds the blast radius.

DAG resolver misses a completion event

Threatens: correctness (downstream tasks never unblock).

If the DAG resolver crashes after a predecessor completes but before incrementing satisfied_count, the downstream task is stuck. Mitigation: completion events flow through Kafka (replayable). On DAG resolver restart, it replays recent completions and re-checks all pending dependencies. The satisfied_count increment is idempotent (bounded by total_predecessors).

13. What I’d skip, and say I’m skipping

• Worker execution runtime. How the worker actually runs the task (container, thread pool, subprocess) is the worker’s business. We define the contract (pull, heartbeat, report) — not the implementation.
• Multi-region. Real schedulers run in multiple regions for disaster recovery. The time-wheel state would need cross-region replication or per-region independent instances. Worth a sentence; not a section.
• Priority queues with preemption. We support priority via sorted-set scores in the ready queue. Preemption (killing a running low-priority task to make room) is a separate, complex problem.
• The real-time dispatch variant. Ride-hailing-style sub-second matching with spatial awareness is fundamentally different — it needs a real-time bidding system, not a time wheel. Different question, different architecture.
• Observability. Metrics, tracing, dashboards — critical in production, not a design driver in an interview.

Interview flow summary

Architecture at a glance

SUBMIT PATH                        EXECUTION PATH

Client                             Trigger Engine (time wheel tick)
 ↓                                  ↓
Task Service                       Current bucket → due tasks
 ↓                                  ↓
Task Store + Time Bucket           Ready Queue (Kafka)
                                    ↓
RECURRING PATH                     Workers pull tasks
                                    ↓
Completion event                   Execute + heartbeat
 ↓                                  ↓
Cron Resolver → next instance      Report success/failure
 ↓                                  ↓
Future time bucket                 State update (CAS)

The walkthrough order for your whiteboard

1. Requirements & scope    — pin down volume, spike distribution, precision
2. Capacity estimate       — find the 300K/sec thundering-herd constraint
3. Architecture evolution  — name Levels 1–5; target Level 4
4. Tick mechanism          — time wheel; justify over polling and ZSET
5. Trigger + dispatch      — time wheel → ready queue → pull-based workers
6. State machine           — pending → running → done, CAS transitions
7. Cron variant            — generate-one-at-a-time, jitter for herds
8. DAG variant             — completion events → unblock → re-insert
9. API                     — four endpoints, idempotency key
10. Data model             — task table, time buckets, dependency table
11. Failure modes          — timing / execution / correctness

If the interviewer pushes deeper:

14. Wrap-up

This design converts the scheduling problem from “scan all tasks every second” to “advance a pointer and process one bucket” via time wheels, protects workers from thundering herds via pull-based dispatch with backpressure, and guarantees reliable execution through lease-based failure detection with at-least-once delivery — trading the complexity of exactly-once for the simplicity of an idempotency contract.

What separates levels on this question

• SDE II names the components (queue, scheduler, workers), describes a polling-based trigger, implements a basic state machine, and handles simple retry logic. Mentions cron but may not address thundering herds.
• SDE III identifies the thundering-herd problem as the core constraint, commits to time wheels with a specific justification, separates triggering from dispatch, designs pull-based worker assignment with lease/heartbeat failure detection, and names 4+ failure scenarios with degradation paths.
• Staff/Principal frames the architecture as an evolution (Levels 1–5), explains why time wheels beat ZSET at this specific scale (pre-shardable, future-inspectable), designs the exactly-once/at-least-once boundary explicitly, shows how DAG resolution layers on top without changing the core dispatch mechanism, and addresses admission control as the last-resort backpressure valve.

The difference isn’t knowledge — it’s naming the spike. The average load (12K/sec) is easy. The clock-aligned spike (300K/sec) is what breaks naive designs, and recognizing that the distribution of due-times (not the total volume) shapes the architecture is what the question is really testing.

Further reading

• Designing Data-Intensive Applications — Kleppmann. Chapters 4 (encoding), 8 (distributed systems trouble), and 11 (stream processing) cover the messaging, failure detection, and exactly-once semantics underpinning this design.
• System Design Interview Vol. 2 — Alex Xu. Chapters on distributed message queue and task scheduler directly overlap.
• Hashed and Hierarchical Timing Wheels — Varghese & Lauck. The original paper on timing wheels — the data structure at the heart of this design.
• Uber’s Cherami — Uber’s durable task queue with pull-based dispatch, partitioned ready queues, and lease-based failure detection.
• Apache Airflow architecture — the canonical DAG orchestrator. Shows how dependency resolution layers atop a scheduler.
• Redis sorted sets — the data structure backing the time-wheel buckets in this design.
• ZooKeeper — the coordination service managing trigger-engine leader election.