Design a Task Scheduler
Cron-like scheduling, priority queues, worker pools, and retry/backoff under concurrency.
Problem Statement
Design an in-memory task scheduler that accepts one-time and recurring tasks, orders them by next-run time, and executes due work using a pool of worker threads.
The scheduler must support cancellation, retry-on-failure with backoff, and safe concurrent calls from many producers while workers are consuming due tasks. The interview focus is the object model and concurrency boundary: a thread-safe time priority queue, blocking workers, retry policy, and cancellation races.
Business context
Task schedulers appear behind reminders, email campaigns, billing jobs, cache refreshes, and workflow engines. Interviewers use this problem to test whether you can combine clean LLD with practical concurrency: producers publish work, consumers block until work is due, and failures are rescheduled without corrupting shared state.
Cron parsing and distributed execution are useful extensions, but the core design is a single-process scheduler with a reliable worker model, explicit lifecycle, and small seams for retry strategy and future persistence.
Functional Requirements
Schedule one-time tasks to run after a delay or at a specific future time.
Schedule recurring tasks with an initial delay and a fixed interval between successful runs.
Maintain tasks in next-run-time order so the earliest due task is executed first.
Run due tasks through a configurable pool of worker threads.
Retry failed executions using a pluggable backoff policy.
Cancel a task by id, including recurring tasks that would otherwise be requeued.
Start and shut down the scheduler safely without leaking worker threads.
Expose the current pending task ids for debugging and operations.
Non-Functional Requirements
Thread safety
Multiple producer threads may schedule or cancel while worker threads take due tasks. Shared state must be protected by a thread-safe BlockingQueue, a concurrent map, and short lifecycle or scheduling locks.
No busy waiting
Workers should block until the next task is due instead of polling in a loop. DelayQueue gives priority-queue ordering plus blocking semantics.
Execution isolation
A failing task must not kill the worker thread or block unrelated tasks forever. The worker catches exceptions and delegates retry or removal.
Extensibility
Retry rules, future cron schedules, persistence, and task categories should be additive. The scheduler should depend on interfaces where policy changes.
Graceful lifecycle
Start should be idempotent, shutdown should interrupt blocking workers, and cancellation should be safe even if the task is already executing.
Requirement Clarification
QDo we need full cron expression support?
Not in the base design. Model one-time and fixed-interval recurring tasks first; cron can be added later as another schedule calculation strategy.
QWhat happens if a recurring task takes longer than its interval?
The base design reschedules after a successful execution using now plus interval. That prevents overlapping executions of the same task in this simple scheduler.
QCan cancellation interrupt a task that is already running?
The scheduler marks the task cancelled and prevents future retries or recurring runs. It does not forcibly stop arbitrary user code unless that code cooperates with interruption.
QHow many times should a failed task retry?
Retry count and delay are owned by RetryPolicy. The sample includes no-retry, fixed-delay, and exponential-backoff policies.
QDoes the scheduler need durable storage?
In-memory is enough for the core LLD. Production can add a repository so pending tasks survive process restarts and multiple scheduler instances can coordinate.
UML Class Diagram
Sequence Diagram
Entity Identification
Task
Command interface for user work. The scheduler stores and executes a Task without knowing whether it sends email, refreshes a cache, or runs billing.
ScheduledTask
Thread-safe queue item. It wraps a command, id, next-run time, optional interval, retry policy, failure count, and cancellation flag. It implements Delayed so the queue can order it by due time.
RetryPolicy
Backoff strategy. It receives the current failure count and exception, then returns the next retry delay or empty when retries are exhausted.
TaskScheduler
Singleton facade and aggregate root. It owns the DelayQueue, active-task map, worker lifecycle, scheduling lock, and public methods for schedule, cancel, start, and shutdown.
Worker
Consumer loop. A worker blocks on the queue, skips cancelled tasks, executes due commands, and reports success or failure back to the scheduler for requeue decisions.
DelayQueue
Thread-safe priority blocking queue from the JDK. It releases a ScheduledTask only when its delay reaches zero, removing the need for manual polling.
Design Patterns Used
Task is a command object. The scheduler can queue, execute, retry, and cancel work uniformly without depending on concrete business logic.
RetryPolicy is a strategy. Fixed delay, exponential backoff, and no-retry policies are interchangeable without changing the worker loop.
Client threads produce ScheduledTask instances into a BlockingQueue; worker threads consume due tasks with take. This naturally handles backpressure and avoids busy waiting.
TaskScheduler.getInstance provides one process-wide scheduler that owns the worker pool and queue. In a real service, dependency injection can wrap or replace this singleton for tests.
Step-by-Step Design
1Represent executable work as a command
Start with a tiny Task interface. Everything scheduled by the system is just a command with an execute method, so the scheduler never needs a switch on task type.
public interface Task { void execute() throws Exception; }2Make scheduled work comparable by due time
ScheduledTask implements Delayed, so Java's DelayQueue can order items by nextRunAt and block consumers until the head is due.
@Override public long getDelay(TimeUnit unit) { long nanos = Duration.between(Instant.now(), nextRunAt).toNanos(); return unit.convert(nanos, TimeUnit.NANOSECONDS); } @Override public int compareTo(Delayed other) { ScheduledTask task = (ScheduledTask) other; return nextRunAt.compareTo(task.nextRunAt); }3Separate retry policy from worker logic
The worker should not know exponential math or retry limits. It asks RetryPolicy for the next delay, then the scheduler requeues or removes the task.
public interface RetryPolicy { Optional<Duration> nextDelay(int failureCount, Exception error); }4Use DelayQueue as the producer-consumer boundary
Scheduling is a producer operation: validate the task, put it in the active map, then offer it to the DelayQueue. Workers are consumers blocked on take, so no thread spins while waiting for time to pass.
5Keep requeue and cancellation atomic
A task can finish at the same time another thread calls cancel. Guard map updates, queue removal, and requeue decisions with a short schedulingLock so cancelled tasks cannot be reintroduced as active work.
6Let workers report outcomes, not own policy
The worker loop executes due commands and reports complete or fail to the scheduler. The scheduler owns whether to reschedule recurring work, retry after backoff, or remove exhausted tasks.
while (accepting.get() && scheduler.isRunning()) { ScheduledTask task = scheduler.takeDueTask(); if (!task.isCancelled()) { task.execute(); scheduler.complete(task); } }
Complete Java Implementation
Explanation of Every Class
Task
Minimal command interface. Any business action can be represented as execute, which keeps the scheduler independent of concrete task types.
ScheduledTask
Queue element and task state holder. It implements Delayed for priority ordering, tracks failure attempts atomically, stores optional recurrence interval, and exposes cancellation as an atomic flag.
RetryPolicy
Strategy interface plus three concrete policies: no retry, fixed delay, and exponential backoff. It returns an optional delay, which makes retry exhaustion explicit.
TaskScheduler
Singleton aggregate root. It owns the DelayQueue, active task map, worker list, lifecycle lock, and scheduling lock. Public methods schedule, cancel, start, and shut down safely.
Worker
Consumer runnable. It blocks on take, executes due tasks, catches failures, and delegates completion or failure handling back to the scheduler.
Main
Small demo that starts two workers, schedules a retryable one-time task, schedules a recurring heartbeat, cancels it, and shuts the scheduler down.
Dry Run
Sample input
Workers: 2. Tasks: email one-time at T+100ms with exponential backoff and one planned failure; heartbeat recurring first at T+50ms then every 250ms; cancel heartbeat at about T+900ms.
| Step | Actor | Queue head | Task state | Result |
|---|---|---|---|---|
| 1 | Client schedules heartbeat | heartbeat @ T+50ms | active | Worker blocks until delay reaches zero |
| 2 | Worker runs heartbeat | email @ T+100ms | heartbeat success | Heartbeat requeued for T+300ms |
| 3 | Worker runs email | heartbeat @ T+300ms | email failure count 1 | RetryPolicy returns 100ms backoff |
| 4 | Worker retries email | heartbeat @ T+300ms | email success | One-time email is removed from active map |
| 5 | Client cancels heartbeat | none | heartbeat cancelled | Queue entry removed and future recurring runs stop |
The important state transition is step 3: failure does not escape the worker thread. The scheduler asks the strategy for a delay, updates the same ScheduledTask next-run time, and reoffers it under the scheduling lock.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| scheduleOnce / scheduleRecurring | O(log n) | O(1) | DelayQueue insertion is backed by a priority heap, and the active map insert is expected O(1). |
| worker take due task | O(log n) plus task runtime | O(1) | The queue blocks until the earliest item is due, then removes it from the heap. |
| retry or recurring requeue | O(log n) | O(1) | The worker updates next-run time and offers the same task back to the DelayQueue. |
| cancel | O(n) | O(1) | Map removal is expected O(1), but removing an arbitrary item from DelayQueue scans the heap. |
| pendingTaskIds | O(n) | O(n) | Creates a stable copy of active ids for callers. |
The hot path is queue insertion and removal, both O(log n). Cancellation is the tradeoff: arbitrary heap removal is O(n), which is acceptable for interview scale but can be optimized with tombstones or an indexed heap.
Extensibility
Cron schedules
Introduce a SchedulePolicy that computes the next run time after each success. Fixed interval and cron become strategies instead of fields on ScheduledTask.
Persistent tasks
Add a TaskRepository to persist id, payload, next-run time, retry state, and cancellation status. Scheduler startup reloads due and future tasks.
Task categories
Use multiple queues or worker pools per category such as email, billing, and reports. This prevents slow report work from starving urgent notifications.
Distributed execution
Move ownership to a database lease or distributed lock so only one scheduler instance claims a due task. The local worker model stays the same after claiming.
Alternative Designs
ExecutorService plus ScheduledExecutorService
Use JDK executors directly: a scheduled executor triggers tasks and a separate executor handles actual work.
Tradeoffs
Fast to build and production-tested, but it hides the priority queue, retry, and cancellation internals that the interview wants you to model.
Database-backed polling scheduler
Store tasks in a database table ordered by next-run time, and have workers claim rows with leases.
Tradeoffs
Survives restarts and scales across nodes, but introduces polling interval tradeoffs, transaction isolation, and operational complexity.
Hashed wheel timer
Bucket tasks by time slots rather than maintaining a strict heap. Workers scan the current slot as time advances.
Tradeoffs
Excellent for very large timer counts and coarse precision, but harder to explain and less exact for arbitrary run times.
Common Mistakes
- ×
Using a normal PriorityQueue without synchronization, causing producers and workers to corrupt heap state.
- ×
Polling the queue every few milliseconds instead of using a blocking queue that wakes only when work is due.
- ×
Letting an exception escape the worker loop, silently killing a worker thread after one bad task.
- ×
Requeueing a recurring task without checking whether it was cancelled while executing.
- ×
Hard-coding exponential backoff in the worker instead of isolating it behind RetryPolicy.
- ×
Rescheduling recurring work before execution finishes, which can overlap the same task with itself.
- ×
Forgetting that arbitrary cancellation from a heap-backed queue is not O(log n) unless an index is maintained.
Follow-up Interview Questions
QHow would you add cron expressions?
Replace the fixed interval field with a SchedulePolicy interface. After each success, the scheduler asks the policy for the next run time. Cron, fixed interval, and one-time schedules become separate strategies.
QHow do you prevent one slow task type from starving others?
Partition by task category with separate queues and worker pools, or add priority classes. The core producer-consumer loop remains the same but capacity is isolated.
QHow would cancellation work for a task currently executing?
The scheduler marks it cancelled and removes it from the active map. The running command may finish, but completion handling sees the cancelled flag and will not retry or requeue it.
QHow do you make this scheduler durable?
Persist task state and next-run time in a repository. On startup, reload active tasks into the DelayQueue; on complete, retry, cancel, and requeue, update the repository in the same transaction boundary.
QWhat if two scheduler instances run at the same time?
Use a lease or row-level claim in a shared store. A worker first atomically claims the due task, then executes it. If the worker dies, the lease expires and another instance can retry.
Production Considerations
Clock control
Inject a clock instead of calling Instant.now directly. This makes tests deterministic and allows time skew handling in production.
Task payloads and idempotency
Real tasks need payloads, idempotency keys, and deduplication so retrying after a crash does not double-charge or double-send.
Observability
Track scheduled count, due lag, execution latency, failure count, retry count, queue size, worker utilization, and cancellation rate.
Graceful shutdown
Stop accepting new tasks, interrupt blocked workers, allow in-flight tasks a deadline, then persist or requeue unfinished work.
Poison tasks
After retry exhaustion, move failed tasks to a dead-letter store with error details instead of simply dropping them.
What Interviewers Look For
Did the candidate choose a thread-safe priority blocking queue instead of hand-rolled sleep loops?
Can they explain the producer-consumer relationship between clients, queue, and workers?
Did they isolate retry policy from worker orchestration using Strategy?
Can they reason about cancellation racing with task completion and requeue?
Did they discuss one-time versus recurring semantics clearly, especially no overlap for the same recurring task?
Can they extend the design toward durability and distributed leases without rewriting the core worker model?
Quiz
0/5 answered
1.Why is **DelayQueue** a good fit for this design?
2.Which pattern is represented by the **Task** interface?
3.What should happen when a one-time task succeeds?
4.Why does cancellation need to coordinate with requeue logic?
5.What is the main benefit of **RetryPolicy**?
Practice Variants
Add cron-based scheduling
AdvancedIntroduce a schedule strategy that computes the next fire time from a cron expression, then reuse the existing worker and retry flow.
Persist tasks across restart
AdvancedAdd a repository for active tasks and retry state. On startup, reload tasks into the queue and ensure cancellation updates are durable.
Add task priorities within the same due time
IntermediateExtend ScheduledTask.compareTo so tasks due at the same instant are ordered by priority, then creation sequence for stability.
Flashcards
Cheat Sheet
Entities: Task command; ScheduledTask queue item; RetryPolicy strategy; TaskScheduler singleton facade; Worker consumer.
Queue: DelayQueue is a thread-safe BlockingQueue ordered by ScheduledTask.getDelay, so workers block until the earliest task is due.
Flows: schedule = validate and offer; execute = worker take then run; success = remove or requeue interval; failure = ask RetryPolicy then retry or remove; cancel = mark cancelled and remove.
Patterns: Command for Task, Strategy for RetryPolicy, Producer-Consumer for clients and workers, Singleton for the scheduler owner.
Concurrency: DelayQueue handles blocking priority order; ConcurrentHashMap tracks active ids; schedulingLock protects cancel versus retry or recurring requeue.
Complexity: schedule O(log n), take O(log n) plus task runtime, requeue O(log n), cancel O(n), pending ids O(n).
Extensions: cron schedule strategy, persistence repository, category-specific worker pools, distributed leases, dead-letter failed tasks.
References
- DocsJava Platform Docs — DelayQueue — Oracle
- BookJava Concurrency in Practice — Brian Goetz et al.
- DocsRefactoring Guru — Command Pattern
- DocsRefactoring Guru — Strategy Pattern