Design a Task Scheduler (Low-Level Design)

A task scheduler runs work at a future time: send a reminder in ten minutes, refresh a token every thirty seconds, retry a failed call after a backoff. It is a favorite low-level design problem because the core is one data structure, a priority queue keyed by time, wrapped in a handful of decisions about ordering, cancellation and testing.

This article builds the scheduler as a single-threaded component with a virtual clock, so the whole behavior can be tested and printed deterministically. Executing the tasks on worker threads is a separate concern, shown at the end. The time handling is the same idea as in design a key-value store with TTL, which uses an ordered map of deadlines for the same job. The method follows the LLD interview framework.

Requirements

Functional

Schedule a task to run once after a delay.
Schedule a recurring task with a first delay and a fixed interval.
Tasks due at the same time run in priority order (high first), and equal priorities run in the order they were scheduled.
Cancel a task by ID, including a recurring one.
A run loop executes all tasks due up to a given time, in order.

Non-functional

Scheduling is O(log n). Finding the next task is O(1) when the top of the queue is live.
The loop never busy-waits: it waits until the next due time.
Fully deterministic under test: no sleeping, no dependence on thread timing.
No drift: a recurring task with a 30 ms interval runs at multiples of 30 ms, not at 30 ms plus accumulated delay.

Entities and class diagram

classDiagram
    class Ticker {
        <<interface>>
        +nowMs() long
        +waitUntil(deadlineMs)
    }
    class Scheduler {
        -ticker: Ticker
        -heap: PriorityQueue~Key~
        -tasks: Map~TaskId,Task~
        +scheduleOnce(delay, priority, job) TaskId
        +scheduleEvery(delay, every, priority, job) TaskId
        +cancel(id) boolean
        +runDue() int
        +runUntil(endMs) int
    }
    class Task {
        <<record>>
        job: Consumer~RunInfo~
        schedule: Schedule
        priority: Priority
    }
    class Schedule {
        <<sealed interface>>
        Once
        Every(ms)
    }
    class Priority {
        <<enumeration>>
        LOW
        NORMAL
        HIGH
    }
    class TaskId {
        <<record>>
        value: long
    }
    Ticker <|.. ManualTicker
    Ticker <|.. SystemTicker
    Scheduler --> Ticker : waits on
    Scheduler *-- Task : stores by id
    Task --> Priority
    Task --> Schedule
    Scheduler ..> TaskId : returns

The heap does not hold the tasks. It holds small keys (due time, priority, sequence number, task ID), and the tasks live in a HashMap by ID. Keys are cheap to compare, the job objects are never touched by heap operations, and cancellation becomes a hash map removal.

API

Java

interface Ticker {
    long nowMs();
    void waitUntil(long deadlineMs); // blocks (real) or jumps (manual)
}

// Scheduler is not thread-safe: one thread owns it.
Scheduler(Ticker ticker);
TaskId scheduleOnce(long delayMs, Priority priority, Consumer<RunInfo> job);
TaskId scheduleEvery(long firstDelayMs, long everyMs, Priority priority, Consumer<RunInfo> job);
boolean cancel(TaskId id);
int runDue();
int runUntil(long endMs);

This block is a signature sketch, so the checker skips it. A task receives a RunInfo record with its ID, the time it was scheduled for and the time it actually ran. Their difference is the lateness, which is useful for monitoring. A zero interval would make a recurring task due forever at the same instant, so the Schedule.Every record rejects it with an IllegalArgumentException. The exception fits because the caller broke a documented precondition and no caller can recover by handling it (errors in domain design). The Schedule type is a sealed interface with two records, so the run loop uses an exhaustive switch and a future Cron variant forces every switch to be updated.

Design decisions

A min-heap with a composed comparator. PriorityQueue is a min-heap: poll returns the smallest element according to its Comparator. One comparator encodes the whole ordering rule:

due ascending: earliest first.
priority descending: within one instant, the highest priority first. Priority is an enum, and enums compare by declaration order (LOW, NORMAL, HIGH), so Comparator.reverseOrder() puts HIGH first.
seq ascending: a global counter assigned at scheduling time, so equal priorities are first in, first out. Without it, the order among equals would be unspecified, because PriorityQueue does not promise a stable order for elements that compare equal.

Java

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    enum Priority { LOW, NORMAL, HIGH }

    record Entry(long due, Priority priority, long seq, String name) {}

    static final Comparator<Entry> ORDER = Comparator.comparingLong(Entry::due)
            .thenComparing(Entry::priority, Comparator.reverseOrder())
            .thenComparingLong(Entry::seq);

    public static void main(String[] args) {
        var heap = new PriorityQueue<>(ORDER);
        record Input(long due, Priority priority, String name) {}
        var inputs = List.of(
                new Input(100, Priority.NORMAL, "backup"),
                new Input(100, Priority.HIGH, "alert"),
                new Input(50, Priority.LOW, "warmup"),
                new Input(100, Priority.NORMAL, "report"),
                new Input(100, Priority.LOW, "cleanup"));
        long seq = 0;
        for (var in : inputs) {
            heap.add(new Entry(in.due(), in.priority(), seq++, in.name()));
        }
        while (!heap.isEmpty()) {
            var e = heap.poll();
            System.out.printf("due %3d %s #%d %s%n", e.due(), e.priority(), e.seq(), e.name());
        }
    }
}

Output

due  50 LOW #2 warmup
due 100 HIGH #1 alert
due 100 NORMAL #0 backup
due 100 NORMAL #3 report
due 100 LOW #4 cleanup

The earliest task comes first. At time 100, alert (HIGH) precedes the two NORMAL tasks, which run in scheduling order (backup, then report), and cleanup (LOW) is last.

Integer milliseconds, not floating point. A key must be totally ordered and must add up exactly. A double time breaks the second requirement: repeated addition of an interval accumulates rounding error, so a task meant to run every 0.1 seconds drifts off its grid. A long count of milliseconds is exact. A long also needs Long.compare (as comparingLong does) rather than a subtraction such as (int) (a - b), which overflows for large differences.

Java

public class Main {
    public static void main(String[] args) {
        double seconds = 0.1 + 0.1 + 0.1;
        System.out.println("double: " + seconds + ", equals 0.3: " + (seconds == 0.3));

        long millis = 100 + 100 + 100;
        System.out.println("long:   " + millis + ", equals 300: " + (millis == 300));
    }
}

Output

double: 0.30000000000000004, equals 0.3: false
long:   300, equals 300: true

Cancellation by lazy deletion. Removing an arbitrary element from a PriorityQueue with remove(Object) is O(n): it scans for the element. Instead, cancel removes the task from the map, and the stale key stays in the heap. When a stale key reaches the top, the loop sees that its task no longer exists and discards it. The heap may hold some dead keys, but every operation stays O(log n) amortized.

Fixed-rate recurrence. After a recurring task runs, its next due time is previous due + interval, not now + interval. The task stays on its grid and does not drift when one run is late. The consequence: if the loop falls far behind, the task runs repeatedly to catch up. The alternative policy, skipping missed runs, is a small change in runOne and is listed under extensions.

The ticker owns waiting. Ticker.waitUntil(deadline) blocks the thread for a real ticker and jumps forward for the manual one. The run loop is identical in both cases: it looks at the earliest due time, waits until then, and runs the task. This is why the same loop is deterministic in tests and correct in production. It also means the loop never polls in a busy loop. The ticker is a small interface of the scheduler's own, with times as long milliseconds since an arbitrary start, because the scheduler needs a monotonic reading and a way to wait, and java.time.Clock offers only the reading.

Jobs may call the scheduler. The run loop removes the key from the heap before it calls the job, and it updates the recurrence after the job returns. A job can therefore schedule follow-up work or cancel tasks, including itself, and the queue and the map stay consistent. If a job throws, the finally block still reschedules a recurring task, and the exception reaches the caller of runUntil. The scheduler does not catch it, because the right reaction (log, retry, stop) is the caller's decision.

The JDK has this. ScheduledThreadPoolExecutor (created by Executors.newScheduledThreadPool) offers schedule, scheduleAtFixedRate and scheduleWithFixedDelay on worker threads. It orders tasks by trigger time and then by submission order. It has no priority among tasks due at the same instant and no manual clock, which is why this design is built by hand.

Full implementation

Java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.OptionalLong;
import java.util.PriorityQueue;
import java.util.function.Consumer;

public class Main {
    interface Ticker {
        long nowMs();

        /** Returns once the ticker has reached deadlineMs. A deadline in the past returns at once. */
        void waitUntil(long deadlineMs);
    }

    /** Time that jumps forward when asked to wait. */
    static final class ManualTicker implements Ticker {
        private long now;

        void advance(long ms) {
            now += ms;
        }

        @Override public long nowMs() { return now; }

        @Override public void waitUntil(long deadlineMs) {
            if (deadlineMs > now) {
                now = deadlineMs;
            }
        }
    }

    /** Real time: sleeps the thread. */
    static final class SystemTicker implements Ticker {
        private final long startNanos = System.nanoTime();

        @Override public long nowMs() {
            return (System.nanoTime() - startNanos) / 1_000_000;
        }

        @Override public void waitUntil(long deadlineMs) {
            long remaining;
            while ((remaining = deadlineMs - nowMs()) > 0) {
                try {
                    Thread.sleep(remaining);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    throw new IllegalStateException("interrupted while waiting", e);
                }
            }
        }
    }

    enum Priority { LOW, NORMAL, HIGH }

    record TaskId(long value) {}

    sealed interface Schedule {
        record Once() implements Schedule {}

        record Every(long ms) implements Schedule {
            public Every {
                if (ms <= 0) {
                    throw new IllegalArgumentException("interval must be positive, got " + ms);
                }
            }
        }
    }

    /** What a job learns about its own run. */
    record RunInfo(TaskId id, long scheduledFor, long runAt) {}

    record Task(Consumer<RunInfo> job, Schedule schedule, Priority priority) {}

    record Key(long due, Priority priority, long seq, TaskId id) {}

    static final Comparator<Key> KEY_ORDER = Comparator.comparingLong(Key::due)
            .thenComparing(Key::priority, Comparator.reverseOrder())
            .thenComparingLong(Key::seq);

    static final class Scheduler {
        private final Ticker ticker;
        private final PriorityQueue<Key> heap = new PriorityQueue<>(KEY_ORDER);
        private final Map<TaskId, Task> tasks = new HashMap<>();
        private long nextId;
        private long seq;

        Scheduler(Ticker ticker) {
            this.ticker = Objects.requireNonNull(ticker);
        }

        private void pushKey(long due, Priority priority, TaskId id) {
            heap.add(new Key(due, priority, seq++, id));
        }

        private TaskId add(long delayMs, Schedule schedule, Priority priority, Consumer<RunInfo> job) {
            if (delayMs < 0) {
                throw new IllegalArgumentException("delay must not be negative, got " + delayMs);
            }
            Objects.requireNonNull(job);
            var id = new TaskId(nextId++);
            tasks.put(id, new Task(job, schedule, priority));
            pushKey(ticker.nowMs() + delayMs, priority, id);
            return id;
        }

        TaskId scheduleOnce(long delayMs, Priority priority, Consumer<RunInfo> job) {
            return add(delayMs, new Schedule.Once(), priority, job);
        }

        TaskId scheduleEvery(long firstDelayMs, long everyMs, Priority priority, Consumer<RunInfo> job) {
            return add(firstDelayMs, new Schedule.Every(everyMs), priority, job);
        }

        /** Lazy deletion: the heap key stays behind and is skipped when it surfaces. */
        boolean cancel(TaskId id) {
            return tasks.remove(id) != null;
        }

        int pending() {
            return tasks.size();
        }

        /** Due time of the earliest live task, discarding cancelled keys on the way. */
        private OptionalLong nextDue() {
            while (!heap.isEmpty()) {
                var top = heap.peek();
                if (tasks.containsKey(top.id())) {
                    return OptionalLong.of(top.due());
                }
                heap.poll();
            }
            return OptionalLong.empty();
        }

        /** Runs the earliest task. Call only after nextDue returned a value. */
        private void runOne() {
            var key = heap.poll();
            var task = tasks.get(key.id());
            var info = new RunInfo(key.id(), key.due(), ticker.nowMs());
            try {
                task.job().accept(info);
            } finally {
                switch (task.schedule()) {
                    case Schedule.Every every -> {
                        // Fixed rate: the next run is on the grid, and only if the job did not cancel itself.
                        if (tasks.containsKey(key.id())) {
                            pushKey(key.due() + every.ms(), key.priority(), key.id());
                        }
                    }
                    case Schedule.Once once -> tasks.remove(key.id());
                }
            }
        }

        /** Runs everything already due at the current time. */
        int runDue() {
            long now = ticker.nowMs();
            int ran = 0;
            for (var due = nextDue(); due.isPresent() && due.getAsLong() <= now; due = nextDue()) {
                runOne();
                ran++;
            }
            return ran;
        }

        /** Waits for and runs every task due up to endMs, then waits until endMs. */
        int runUntil(long endMs) {
            int ran = 0;
            for (var due = nextDue(); due.isPresent() && due.getAsLong() <= endMs; due = nextDue()) {
                ticker.waitUntil(due.getAsLong());
                runOne();
                ran++;
            }
            ticker.waitUntil(endMs);
            return ran;
        }
    }

    static Consumer<RunInfo> recorder(List<String> log, String name) {
        return info -> log.add("t=%-4d %s (due %d)".formatted(info.runAt(), name, info.scheduledFor()));
    }

    public static void main(String[] args) {
        var ticker = new ManualTicker();
        var scheduler = new Scheduler(ticker);
        var log = new ArrayList<String>();

        scheduler.scheduleOnce(100, Priority.NORMAL, recorder(log, "backup"));
        scheduler.scheduleOnce(100, Priority.HIGH, recorder(log, "alert"));
        scheduler.scheduleOnce(100, Priority.LOW, recorder(log, "cleanup"));
        scheduler.scheduleOnce(50, Priority.NORMAL, recorder(log, "warmup"));
        var doomed = scheduler.scheduleOnce(80, Priority.NORMAL, recorder(log, "never runs"));
        var heartbeat = scheduler.scheduleEvery(30, 30, Priority.NORMAL, recorder(log, "heartbeat"));
        try {
            scheduler.scheduleEvery(0, 0, Priority.LOW, info -> { });
        } catch (IllegalArgumentException e) {
            System.out.println("zero interval: " + e.getMessage());
        }
        System.out.println("cancel doomed: " + scheduler.cancel(doomed) + ", again: " + scheduler.cancel(doomed));

        int ran = scheduler.runUntil(130);
        System.out.println("ran " + ran + " tasks, clock at " + ticker.nowMs() + ", pending " + scheduler.pending());
        log.forEach(System.out::println);

        // The process was suspended for a second: the recurring task catches up.
        log.clear();
        ticker.advance(1000);
        ran = scheduler.runDue();
        System.out.println("after a 1000 ms stall: ran " + ran + ", first " + log.getFirst());
        System.out.println("last  " + log.getLast());

        System.out.println("cancel heartbeat: " + scheduler.cancel(heartbeat) + ", pending " + scheduler.pending());

        // A job may schedule more work.
        scheduler.scheduleOnce(10, Priority.NORMAL,
                info -> scheduler.scheduleOnce(5, Priority.NORMAL, recorder(log, "follow-up")));
        System.out.println("runUntil(2000): ran " + scheduler.runUntil(2000) + ", last " + log.getLast());

        // The same loop on the real ticker, with short delays.
        var real = new Scheduler(new SystemTicker());
        var order = new ArrayList<String>();
        real.scheduleOnce(20, Priority.NORMAL, info -> order.add("second"));
        real.scheduleOnce(5, Priority.NORMAL, info -> order.add("first"));
        real.runUntil(40);
        System.out.println("real ticker order: " + order);
    }
}

Output

zero interval: interval must be positive, got 0
cancel doomed: true, again: false
ran 8 tasks, clock at 130, pending 1
t=30   heartbeat (due 30)
t=50   warmup (due 50)
t=60   heartbeat (due 60)
t=90   heartbeat (due 90)
t=100  alert (due 100)
t=100  backup (due 100)
t=100  cleanup (due 100)
t=120  heartbeat (due 120)
after a 1000 ms stall: ran 33, first t=1130 heartbeat (due 150)
last  t=1130 heartbeat (due 1110)
cancel heartbeat: true, pending 0
runUntil(2000): ran 2, last t=1145 follow-up (due 1145)
real ticker order: [first, second]

The first block of output confirms the ordering rules. The cancelled task never appears, heartbeat runs at multiples of 30, and at t=100 the three tasks run as alert (HIGH), backup (NORMAL), cleanup (LOW). After the simulated stall the recurring task runs once for every missed slot, because its next due time is computed from the previous due time. Only the runAt values differ from the schedule, and only while catching up. The follow-up task is scheduled by a job while the loop runs, and it runs in the same runUntil call. The last block runs the same loop on the real ticker, and only the order is printed because real timings vary.

Running tasks concurrently

The scheduler decides when, not where. A slow job would delay every task behind it. The usual fix is to keep the timing loop on one thread and hand due jobs to a pool of workers, which is the producer-consumer pattern from blocking queue and producer-consumer. An ExecutorService is that pool: it owns a queue of submitted tasks and a set of worker threads. Since Java 19 it is AutoCloseable, and close() waits for submitted tasks to finish.

Java

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Main {
    public static void main(String[] args) throws ExecutionException, InterruptedException {
        List<Future<String>> futures = new ArrayList<>();
        try (var workers = Executors.newFixedThreadPool(3)) {
            // The scheduler thread would submit jobs as they become due.
            for (int n = 0; n < 6; n++) {
                int id = n;
                futures.add(workers.submit(() -> "task " + id + " done"));
            }
        }

        var results = new ArrayList<String>();
        for (var future : futures) {
            results.add(future.get());
        }
        results.sort(null);
        System.out.println(results);
    }
}

Output

[task 0 done, task 1 done, task 2 done, task 3 done, task 4 done, task 5 done]

Which worker runs which job varies, so the example collects the results through the futures and sorts them. Future.get returns a result in the order the futures were submitted, regardless of which worker finished first. Everything after the hand-off is ordinary concurrent code, and the scheduler itself stays deterministic.

Extensions

Follow-up question	Answer
Skip missed runs instead of catching up	In `runOne`, compute the next due as `due + every * k` for the smallest `k` that lands after `runAt`.
Jobs that schedule more jobs	Already supported in this design: the key is polled before the job runs, so a job can call `scheduleOnce` or `cancel`.
Retry with exponential backoff	The job returns an outcome (a sealed result type). On failure the scheduler reschedules with a doubled delay up to a cap.
Cron expressions	Add a `Cron` record to the sealed `Schedule` interface with a `nextAfter(time)` method. The `switch` in `runOne` then fails to compile until it handles the new case.
Sleep until a new earlier task arrives	In a threaded scheduler use a `ReentrantLock` with a `Condition`: `awaitNanos` until the earliest due time, and `signal` when a task is added with an earlier deadline.
Persistence across restarts	Store `(due, id, payload)` durably and rebuild the heap on start. Jobs become data plus a registry of handlers.
Bounded work per tick	`runDue` takes a budget, as `sweep` does in design a key-value store with TTL.
A job throws	The `finally` block keeps recurring tasks scheduled. The caller of `runUntil` decides whether to log and call it again.
Distributed scheduling	A shared store with leases so that one node claims each due task; see design a notification system.

Summary

A scheduler is a priority queue keyed by due time. In Java, PriorityQueue is a min-heap ordered by a Comparator.
Encode the full ordering in one comparator: due time, then priority descending, then a sequence number for FIFO among equals.
Keep tasks in a map by ID and only small keys in the heap. Cancel by removing the task and skip stale keys when they surface.
Use integer milliseconds. Floating-point times accumulate rounding error, and subtraction-based comparators overflow.
Reschedule recurring tasks from their previous due time so they do not drift, and decide explicitly what to do about missed runs.
Put waitUntil in a Ticker interface. The same run loop then blocks on a real ticker and jumps on a manual one, which makes tests instant and deterministic.
Model the schedule as a sealed interface so a new kind of schedule is checked by the compiler.
Keep timing and execution separate: the scheduler decides when, and an executor decides where.