LOW LEVEL DESIGN · MACHINE CODING · HARD · 9 OF 42

Design a Task Scheduler with Workers: Low-Level Design in Java

A task scheduler designed and coded: a task lifecycle as a state machine, dependencies as a DAG validated with Kahn's topological sort, unmet-dependency counters, a priority heap and a delay heap, a worker pool on one lock and condition, retries with exponential backoff, cancel with cascading to dependents, suspend and resume, and a full Java 17 solution.

Patterns usedStateObserver

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 18

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 410 lines, with a small main() demo. Save it as TaskScheduler.java, then run javac TaskScheduler.java && java TaskScheduler.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeSet;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/** A task scheduler: priorities, a dependency DAG, delays, retries with backoff, cancel and suspend. */
public final class TaskScheduler {

    // ---------- the model ----------
    enum State {
        WAITING, READY, RUNNING, SUSPENDED, SUCCEEDED, FAILED, CANCELLED;

        boolean done() { return this == SUCCEEDED || this == FAILED || this == CANCELLED; }
    }

    interface Job { void run() throws Exception; }

    /** Exponential backoff: base, 2x base, 4x base ... capped at max. */
    record RetryPolicy(int maxAttempts, long baseDelayMs, long maxDelayMs) {
        static final RetryPolicy NONE = new RetryPolicy(1, 0, 0);

        long delayFor(int failedAttempts) {
            return Math.min(maxDelayMs, baseDelayMs << Math.min(20, failedAttempts - 1));
        }
    }

    /** What the caller submits. Higher priority runs first among ready tasks. */
    record Spec(String id, int priority, List<String> dependsOn, long delayMs, RetryPolicy retry, Job job) {
        static Spec of(String id, int priority, Job job, String... deps) {
            return new Spec(id, priority, List.of(deps), 0, RetryPolicy.NONE, job);
        }

        Spec delayed(long ms) { return new Spec(id, priority, dependsOn, ms, retry, job); }

        Spec retrying(RetryPolicy r) { return new Spec(id, priority, dependsOn, delayMs, r, job); }
    }

    /** Mutable run-time record of one task. Every field is guarded by the scheduler's lock. */
    static final class Task {
        final Spec spec;
        final long seq;
        final List<Task> dependents = new ArrayList<>();
        State state = State.WAITING;
        int unmetDeps;
        int attempts;
        long notBefore;
        boolean cancelRequested;

        Task(Spec spec, long seq) {
            this.spec = spec;
            this.seq = seq;
        }
    }

    interface TaskListener { void onChange(String id, State state, String note); }

    // ---------- the scheduler ----------
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition changed = lock.newCondition();
    private final Map<String, Task> tasks = new HashMap<>();
    private final PriorityQueue<Task> ready = new PriorityQueue<>(
            Comparator.comparingInt((Task t) -> -t.spec.priority()).thenComparingLong(t -> t.seq));
    private final PriorityQueue<Task> delayed = new PriorityQueue<>(
            Comparator.comparingLong((Task t) -> t.notBefore).thenComparingLong(t -> t.seq));
    private final List<TaskListener> listeners = new CopyOnWriteArrayList<>();
    private final List<Thread> workers = new ArrayList<>();
    private int running;
    private long seq;
    private boolean shutdown;

    private static long now() { return System.nanoTime() / 1_000_000; }

    void subscribe(TaskListener l) { listeners.add(l); }

    private void set(Task t, State s, String note) {
        t.state = s;
        for (TaskListener l : listeners) l.onChange(t.spec.id(), s, note);
    }

    /**
     * Validate a batch with Kahn's algorithm: dependencies must be in the batch or already known,
     * and the batch must not contain a cycle. Tasks are registered in topological order.
     */
    List<String> submitAll(List<Spec> specs) {
        lock.lock();
        try {
            Map<String, Spec> batch = new LinkedHashMap<>();
            for (Spec s : specs) {
                if (tasks.containsKey(s.id()) || batch.put(s.id(), s) != null)
                    throw new IllegalArgumentException("duplicate task " + s.id());
            }
            Map<String, Integer> indegree = new HashMap<>();
            Map<String, List<String>> next = new HashMap<>();
            for (Spec s : batch.values()) {
                indegree.putIfAbsent(s.id(), 0);
                for (String d : s.dependsOn()) {
                    if (batch.containsKey(d)) {
                        indegree.merge(s.id(), 1, Integer::sum);
                        next.computeIfAbsent(d, k -> new ArrayList<>()).add(s.id());
                    } else if (!tasks.containsKey(d)) {
                        throw new IllegalArgumentException(s.id() + " depends on unknown task " + d);
                    }
                }
            }
            Deque<String> queue = new ArrayDeque<>();
            for (String id : batch.keySet()) if (indegree.get(id) == 0) queue.add(id);
            List<String> order = new ArrayList<>();
            while (!queue.isEmpty()) {
                String id = queue.poll();
                order.add(id);
                for (String n : next.getOrDefault(id, List.of()))
                    if (indegree.merge(n, -1, Integer::sum) == 0) queue.add(n);
            }
            if (order.size() < batch.size()) {
                TreeSet<String> stuck = new TreeSet<>(batch.keySet());
                order.forEach(stuck::remove);
                throw new IllegalArgumentException("cycle among " + stuck);
            }
            for (String id : order) register(batch.get(id));
            return order;
        } finally {
            lock.unlock();
        }
    }

    private void register(Spec s) {
        Task t = new Task(s, ++seq);
        t.notBefore = now() + s.delayMs();
        tasks.put(s.id(), t);
        String deadDep = null;
        for (String d : s.dependsOn()) {
            Task dep = tasks.get(d);
            if (dep.state == State.FAILED || dep.state == State.CANCELLED) deadDep = d;
            else if (dep.state != State.SUCCEEDED) {
                t.unmetDeps++;
                dep.dependents.add(t);
            }
        }
        if (deadDep != null) finish(t, State.CANCELLED, "dependency " + deadDep + " did not succeed");
        else if (t.unmetDeps == 0) enqueue(t);
    }

    /** Dependencies met and not suspended: into the ready heap, or the delay heap if it is not due yet. */
    private void enqueue(Task t) {
        set(t, State.READY, "");
        if (t.notBefore > now()) delayed.add(t);
        else ready.add(t);
        changed.signalAll();
    }

    /** A terminal state. Anything other than success cancels every dependent, transitively. */
    private void finish(Task t, State s, String note) {
        ready.remove(t);
        delayed.remove(t);
        set(t, s, note);
        for (Task d : t.dependents) {
            if (s == State.SUCCEEDED) {
                if (--d.unmetDeps == 0 && d.state == State.WAITING) enqueue(d);
            } else if (!d.state.done()) {
                finish(d, State.CANCELLED, "dependency " + t.spec.id() + " did not succeed");
            }
        }
        changed.signalAll();
    }

    private void afterRun(Task t, Exception error) {
        if (t.cancelRequested) {
            finish(t, State.CANCELLED, "cancelled while running");
        } else if (error == null) {
            finish(t, State.SUCCEEDED, "attempt " + t.attempts);
        } else if (t.attempts < t.spec.retry().maxAttempts()) {
            long wait = t.spec.retry().delayFor(t.attempts);
            t.notBefore = now() + wait;
            enqueue(t);
            for (TaskListener l : listeners) l.onChange(t.spec.id(), State.READY, "retry in " + wait + " ms");
        } else {
            finish(t, State.FAILED, error.getMessage());
        }
    }

    private void workLoop() {
        lock.lock();
        try {
            while (!shutdown) {
                long now = now();
                while (!delayed.isEmpty() && delayed.peek().notBefore <= now) ready.add(delayed.poll());
                Task t = ready.poll();
                if (t == null) {
                    if (delayed.isEmpty()) changed.await();
                    else changed.awaitNanos(TimeUnit.MILLISECONDS.toNanos(delayed.peek().notBefore - now));
                    continue;
                }
                t.attempts++;
                running++;
                set(t, State.RUNNING, Thread.currentThread().getName());
                Exception error = null;
                lock.unlock(); // never hold the lock while user code runs
                try {
                    t.spec.job().run();
                } catch (Exception e) {
                    error = e;
                } finally {
                    lock.lock();
                }
                running--;
                afterRun(t, error);
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.unlock();
        }
    }

    void start(int workerCount) {
        for (int i = 0; i < workerCount; i++) {
            Thread w = new Thread(this::workLoop, "worker-" + i);
            workers.add(w);
            w.start();
        }
    }

    /** Pending tasks are cancelled at once; a running one is marked and cancelled when it returns. */
    boolean cancel(String id) {
        lock.lock();
        try {
            Task t = tasks.get(id);
            if (t == null || t.state.done()) return false;
            if (t.state == State.RUNNING) t.cancelRequested = true;
            else finish(t, State.CANCELLED, "cancelled");
            return true;
        } finally {
            lock.unlock();
        }
    }

    boolean suspend(String id) {
        lock.lock();
        try {
            Task t = tasks.get(id);
            if (t == null || (t.state != State.READY && t.state != State.WAITING)) return false;
            ready.remove(t);
            delayed.remove(t);
            set(t, State.SUSPENDED, "");
            return true;
        } finally {
            lock.unlock();
        }
    }

    boolean resume(String id) {
        lock.lock();
        try {
            Task t = tasks.get(id);
            if (t == null || t.state != State.SUSPENDED) return false;
            if (t.unmetDeps == 0) enqueue(t);
            else set(t, State.WAITING, "");
            return true;
        } finally {
            lock.unlock();
        }
    }

    State state(String id) {
        lock.lock();
        try {
            return tasks.get(id).state;
        } finally {
            lock.unlock();
        }
    }

    /** Wait until nothing is running, ready or delayed (suspended and blocked tasks may remain). */
    boolean awaitQuiet(long timeoutMs) throws InterruptedException {
        long deadline = System.nanoTime() + TimeUnit.MILLISECONDS.toNanos(timeoutMs);
        lock.lock();
        try {
            while (running > 0 || !ready.isEmpty() || !delayed.isEmpty()) {
                long left = deadline - System.nanoTime();
                if (left <= 0) return false;
                changed.awaitNanos(left);
            }
            return true;
        } finally {
            lock.unlock();
        }
    }

    void shutdown() throws InterruptedException {
        lock.lock();
        try {
            shutdown = true;
            changed.signalAll();
        } finally {
            lock.unlock();
        }
        for (Thread w : workers) w.join();
    }

    // ---------- demo ----------
    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) throws InterruptedException {
        List<String> ran = Collections.synchronizedList(new ArrayList<>());
        AtomicInteger flakyTries = new AtomicInteger();
        RetryPolicy backoff = new RetryPolicy(4, 30, 200);
        System.out.println("backoff delays: " + List.of(backoff.delayFor(1), backoff.delayFor(2),
                backoff.delayFor(3), backoff.delayFor(4), backoff.delayFor(5)));

        TaskScheduler s = new TaskScheduler();
        s.subscribe((id, st, note) -> {
            if (st == State.FAILED || st == State.CANCELLED) System.out.println("  [event] " + id + " " + st
                    + (note.isEmpty() ? "" : ": " + note));
        });
        List<String> order = s.submitAll(List.of(
                Spec.of("report", 5, () -> ran.add("report"), "index", "thumbs"),
                Spec.of("index", 5, () -> ran.add("index"), "parse"),
                Spec.of("parse", 5, () -> ran.add("parse"), "fetch"),
                Spec.of("thumbs", 1, () -> ran.add("thumbs"), "fetch"),
                Spec.of("fetch", 5, () -> ran.add("fetch")),
                Spec.of("email", 9, () -> ran.add("email")),
                Spec.of("cleanup", 10, () -> ran.add("cleanup")).delayed(150),
                Spec.of("flaky", 3, () -> {
                    int n = flakyTries.incrementAndGet();
                    ran.add("flaky#" + n);
                    if (n < 3) throw new IllegalStateException("timeout");
                }).retrying(backoff),
                Spec.of("doomed", 3, () -> {
                    ran.add("doomed");
                    throw new IllegalStateException("disk full");
                }).retrying(new RetryPolicy(2, 30, 200)),
                Spec.of("publish", 4, () -> ran.add("publish"), "doomed"),
                Spec.of("archive", 8, () -> ran.add("archive")),
                Spec.of("backup", 7, () -> ran.add("backup"))));
        System.out.println("topological order: " + order);
        check(order.indexOf("fetch") < order.indexOf("parse")
                && order.indexOf("index") < order.indexOf("report"),
                "topological order");
        s.suspend("archive");
        s.cancel("backup");

        s.start(1); // one worker: the run order is easy to read
        check(s.awaitQuiet(5000), "quiet");
        System.out.println("ran: " + ran);
        System.out.println("archive is " + s.state("archive") + ", publish is " + s.state("publish"));
        s.resume("archive");
        check(s.awaitQuiet(5000), "quiet again");
        s.shutdown();
        System.out.println("after resume: archive is " + s.state("archive"));

        check(ran.indexOf("fetch") < ran.indexOf("parse") && ran.indexOf("parse") < ran.indexOf("index"),
                "chain");
        check(ran.indexOf("report") > ran.indexOf("index") && ran.indexOf("report") > ran.indexOf("thumbs"),
                "report waits for both");
        check(ran.get(0).equals("email"), "highest ready priority first");
        check(flakyTries.get() == 3 && s.state("flaky") == State.SUCCEEDED, "retried until success");
        check(s.state("doomed") == State.FAILED && s.state("publish") == State.CANCELLED, "failure cascades");
        check(!ran.contains("backup") && !ran.contains("publish"), "cancelled tasks never run");
        check(ran.get(ran.size() - 1).equals("archive"), "archive runs only after resume");

        // A cycle is rejected before anything is registered.
        TaskScheduler s2 = new TaskScheduler();
        try {
            s2.submitAll(List.of(Spec.of("a", 1, () -> { }, "c"), Spec.of("b", 1, () -> { }, "a"),
                    Spec.of("c", 1, () -> { }, "b")));
            throw new AssertionError("cycle accepted");
        } catch (IllegalArgumentException e) {
            System.out.println("rejected: " + e.getMessage());
        }

        // Four workers, 200 independent tasks and one merge that depends on all of them.
        TaskScheduler pool = new TaskScheduler();
        AtomicInteger done = new AtomicInteger(), active = new AtomicInteger(), peak = new AtomicInteger();
        List<Spec> load = new ArrayList<>();
        List<String> all = new ArrayList<>();
        for (int i = 0; i < 200; i++) {
            all.add("job-" + i);
            load.add(Spec.of("job-" + i, i % 3, () -> {
                peak.accumulateAndGet(active.incrementAndGet(), Math::max);
                Thread.sleep(1);
                active.decrementAndGet();
                done.incrementAndGet();
            }));
        }
        int[] seenByMerge = new int[1];
        load.add(Spec.of("merge", 0, () -> seenByMerge[0] = done.get(), all.toArray(new String[0])));
        pool.submitAll(load);
        pool.start(4);
        check(pool.awaitQuiet(10000), "load finished");
        pool.shutdown();
        System.out.println("4 workers: 200 jobs done, merge saw " + seenByMerge[0] + ", peak parallel "
                + peak.get());
        check(seenByMerge[0] == 200 && peak.get() <= 4 && pool.state("merge") == State.SUCCEEDED, "pool");
        System.out.println("all checks passed");
    }
}

Notes

Requirements

Fix the scope. Tasks carry a priority, and higher priority runs first among tasks that are ready. A task may depend on others and runs only after they all succeed, and a submission with a cycle is rejected. A fixed number of worker threads run tasks. A failed task retries with growing delays. A task can be delayed, cancelled, which also cancels whatever depends on it, or suspended and resumed later.

Clarify the rules that shape the code. If a dependency fails after all its retries, its dependents can never run, so they are cancelled. Equal priorities run in submission order. A running task cannot be killed safely in Java, so cancel marks it and it ends as cancelled when it returns. Retries are set per task. And dependencies must be in the same batch or already known, which is what lets us check for cycles up front.

Requirements
  • submit tasks with a priority
  • task runs after its deps
  • succeed; reject cycles
  • N worker threads
  • retry on failure, with backoff
  • delay: run no sooner than T
  • cancel a task, and its
  • dependents with it
  • suspend and resume
  • see each task's state
Clarify first
  • a dependency fails for good?
  • cancel its dependents
  • same priority?
  • first submitted runs first
  • cancel a running task?
  • cooperative: mark it
  • retry how many times?
  • per task, e.g. 4 attempts
  • deps submitted later?
  • no: in the batch or known

Entities

The entities. A spec is what the caller submits: an id, a priority, dependency ids, a delay, a retry policy and the job itself. The scheduler turns each spec into a task, which holds the changing state: where it is in its lifecycle, how many attempts so far, and the earliest time it may run. Tasks wait in a ready heap or a delay heap, and worker threads take from the ready heap.

Class diagram

Turn them into types. The job is a one-method interface that may throw, so failures come back as exceptions. The retry policy and the spec are records, immutable and easy to build with small helper methods for delay and retry. The task is the one mutable class: its state, the count of dependencies still unfinished, attempts, the not-before time, the list of tasks waiting on it, and a cancel flag. All of it is guarded by the scheduler's lock.

Types
interface Job {
  void run() throws Exception; }
record RetryPolicy(int maxAttempts,
    long baseDelayMs, long maxDelayMs)
record Spec(id, priority, dependsOn,
    delayMs, retry, job)
final class Task {
  State state; int unmetDeps;
  int attempts; long notBefore;
  List<Task> dependents;
  boolean cancelRequested; }

State machine

Draw the lifecycle first; it is the spec for the rest. A task waits until its dependencies succeed, then becomes ready. A worker moves it to running. Success is final. A failure with attempts left sends it back to ready, but through the delay heap. A failure with none left is final, and so is cancelled. Waiting or ready tasks can be suspended and resumed. And any final state other than success cancels every task that depends on it.

Task lifecycle
WAITING   --deps done-->  READY
READY     --worker-->     RUNNING
RUNNING   --ok-->         SUCCEEDED
RUNNING   --fail, tries-->  READY
                 (delay heap)
RUNNING   --fail, none-->  FAILED
WAITING/READY --suspend-->
          SUSPENDED --resume--> back
any pending --cancel--> CANCELLED
FAILED or CANCELLED: cancel
          every dependent

DAG: topological sort

Dependencies form a directed graph that must have no cycles. Submit validates a whole batch with Kahn's algorithm: count each task's dependencies inside the batch, start with the tasks that have none, and repeatedly take one, add it to the order, and decrement its dependents. If the order ends shorter than the batch, the leftovers are in a cycle, so the whole batch is rejected with their names. Otherwise tasks are registered in that topological order.

submitAll: Kahn's algorithm
indegree[t] = deps inside the batch
dep not in batch and unknown: reject
queue = tasks with indegree 0
while queue not empty:
  id = poll; order.add(id)
  for n in next[id]:
    if (--indegree[n] == 0) add n
order shorter than batch:
  the rest form a cycle: reject
register tasks in this order

DAG at run time

At run time we never search the graph. Each task keeps a counter of unfinished dependencies, and each dependency keeps a list of the tasks waiting on it. When fetch succeeds, the scheduler walks fetch's dependents and decrements their counters; parse and thumbnails hit zero and become ready. That is the same idea as Kahn's algorithm, run incrementally as tasks finish, and each success costs only the number of its direct dependents.

Counters, not searches
register(t):
  for each dep not yet succeeded:
    t.unmetDeps++
    dep.dependents.add(t)
  unmetDeps == 0: enqueue(t)

on success of t:
  for d in t.dependents:
    if (--d.unmetDeps == 0
        && d is WAITING) enqueue(d)

Two heaps

Ready tasks sit in a priority heap ordered by priority, highest first, then by a sequence number so equal priorities stay first in, first out. Tasks that are not due yet, a delayed task or a retry waiting out its backoff, sit in a second heap ordered by their not-before time. Before taking work, a worker moves every task that is now due from the delay heap into the ready heap. Each step is log n.

Heaps and order
ready: PriorityQueue<Task>
  by -priority, then seq
  equal priority: FIFO
delayed: PriorityQueue<Task>
  by notBefore, then seq

enqueue(t):
  notBefore > now ? delayed : ready
worker: move due tasks from
  delayed to ready, then poll

Flow: worker loop

Each worker runs one loop. Under the lock, move due tasks into the ready heap and take the best one. If there is none, wait on a condition: forever if the delay heap is empty, or until the next delayed task is due. Mark the task running, then release the lock while the job runs, because user code can be slow or block. Take the lock back to record the result, which may wake dependents. The workers are plain threads pulling from our own heap.

workLoop()
lock
while (!shutdown):
  move due delayed tasks to ready
  t = ready.poll()
  none: await signal, or until
        the next delayed task is due
  RUNNING, attempts++
  unlock; t.job.run(); lock
  afterRun(t, error)
unlock

Retries with backoff

Retries. When a job throws and attempts remain, the retry policy gives the wait: the base delay doubled for each earlier failure, capped at a maximum, so thirty, sixty, a hundred and twenty, then two hundred milliseconds. The task's not-before time moves forward and it goes into the delay heap, so a worker is never blocked sleeping on it. In production add random jitter so many failed tasks do not retry in lockstep.

afterRun on failure
long delayFor(int failed) {
  return min(maxDelayMs,
      baseDelayMs << (failed - 1));
}
attempts < max:
  notBefore = now + delayFor(attempts)
  enqueue: goes to the delay heap
else: FAILED, cancel dependents

base 30, max 200: 30 60 120 200 200

Cancel and suspend

Cancel removes a pending task from whichever heap holds it, marks it cancelled, and walks its dependents to cancel them too, all the way down. A running task only gets a flag, and it ends as cancelled when its job returns. Suspend parks a waiting or ready task outside both heaps. Resume puts it back in the ready heap if its dependencies are done, or back to waiting if not. A dependency finishing never wakes a suspended task.

cancel, suspend, resume
cancel(id):
  RUNNING: cancelRequested = true
  pending: remove from heaps,
    CANCELLED, cascade to dependents
suspend(id): READY or WAITING
  remove from heaps, SUSPENDED
resume(id):
  unmetDeps == 0 ? enqueue : WAITING

a dependency finishing leaves a
  suspended task suspended

Concurrency

Concurrency. All scheduler state, the heaps, the task map, counters and states, sits behind one reentrant lock, because one change, like a success, touches several of them together. One condition wakes workers whenever work appears, a task finishes or we shut down. Waits for delayed tasks use a timed await, so nothing spins. Jobs run with the lock released. In the demo four workers run two hundred jobs, never more than four at once, and the final merge sees all two hundred.

Thread safety
  • one ReentrantLock guards heaps,
  • tasks, counters, states
  • one Condition: signalAll on
  • enqueue, finish, shutdown
  • jobs run with the lock released
  • awaitNanos until the next
  • delayed task: no busy wait
  • listeners: CopyOnWriteArrayList
  • test: 200 jobs, 4 workers,
  • peak parallel 4, merge saw 200

Extensibility

Extensions. Repeating tasks resubmit themselves with a delay after each success. Timeouts mean running jobs through an executor and cancelling the future, which interrupts the thread. Starvation of low priority tasks is fixed by aging: raise a task's priority the longer it waits. Limits per kind of task are a semaphore per type. And to survive a crash, write each state change to a store and rebuild the heaps on startup.

Extension points
  • cron tasks: on success, submit
  • the next run with a delay
  • timeouts: run jobs in a pool
  • and cancel the Future
  • priority aging: raise priority
  • of tasks waiting too long
  • per-queue limits: a semaphore
  • per task type
  • persist: write state changes
  • to a store, replay on start

Testing

The full code is below the player. With a single worker the order is easy to read: email has the highest ready priority, then the fetch, parse, index chain, the flaky task failing twice before succeeding, the doomed task failing for good and cancelling publish, and the delayed cleanup last. The suspended archive runs only after resume, and the cycle is rejected. Then four workers run two hundred jobs. Every rule is asserted.

Run it
backoff delays: [30, 60, 120, 200, 200]
ran: email, fetch, parse, index,
  flaky#1, doomed, thumbs, report,
  flaky#2, doomed, flaky#3, cleanup
[event] doomed FAILED: disk full
[event] publish CANCELLED:
  dependency doomed did not succeed
archive SUSPENDED, then SUCCEEDED
rejected: cycle among [a, b, c]
merge saw 200, peak parallel 4
all checks passed

Follow-ups

Expect follow-ups. Why not just an executor service? It runs tasks in arrival order and knows nothing about dependencies, priorities or suspension, so we keep our own heaps and use threads only to execute. Why a delay heap? So no thread sleeps per delayed task. Starvation? Aging. And across many machines the heap becomes a shared queue where workers take leases, which means tasks can run more than once and must be idempotent.

Follow-ups to expect
  • why not ExecutorService alone?
  • it has no deps, no priority
  • change, no suspend
  • why a DelayQueue-like heap?
  • no thread sleeps per task
  • low priority starves?
  • aging
  • many machines?
  • a shared queue with leases
  • and at-least-once runs

Say it like this

The short version. Batches are validated with Kahn's topological sort, so cycles are rejected. At run time each task counts its unmet dependencies and becomes ready at zero. Ready tasks sit in a priority heap and delayed ones in a heap by time. Workers take a task under one lock and run it without the lock. Failures retry with capped exponential backoff, and a final failure or a cancel cascades to every dependent.

In the interview
  • "Batches are checked with
  • Kahn's sort; at run time each
  • task counts unmet deps. Ready
  • tasks are in a priority heap,
  • delayed ones in a time heap.
  • Workers take under one lock and
  • run without it. Failures retry
  • with capped backoff; failure
  • or cancel cascades down."

Interview questions

How do you detect a cycle in task dependencies?

Run Kahn's algorithm on the batch: compute each task's in-degree, repeatedly remove tasks with in-degree zero and decrement their dependents. If fewer tasks come out than went in, the remaining ones are on a cycle, so reject the batch.

How does a task know when its dependencies are done?

Each task keeps a counter of unfinished dependencies and each dependency keeps a list of dependents. When a task succeeds, decrement each dependent's counter and enqueue any that reach zero. No graph search is needed at run time.

How do you handle priorities and delayed tasks together?

Use two heaps: ready tasks ordered by priority then submission sequence, and not-yet-due tasks ordered by their not-before time. Workers move due tasks from the delay heap to the ready heap before polling, and wait on a condition until the next due time when idle.

Why release the lock while a task runs?

User jobs can be slow or block on I/O. Holding the scheduler lock would stop every other worker from taking tasks and stop callers from submitting or cancelling. Take the task under the lock, run it unlocked, then lock again to record the result.

How do retries with exponential backoff work?

On failure with attempts left, compute a delay of base times 2 to the power of earlier failures, capped at a maximum, set the task's not-before time and put it in the delay heap. Add jitter in production so many tasks do not retry at the same moment.

What happens to dependents when a task fails or is cancelled?

They can never run, so they are cancelled too, recursively down the graph. A pending task is removed from the heaps; a running task is only flagged, because Java cannot safely stop a thread, and ends as cancelled when its job returns.

How do suspend and resume work?

Suspend removes a waiting or ready task from both heaps and marks it suspended; dependency completions still decrement its counter but do not enqueue it. Resume enqueues it if its counter is zero, or returns it to waiting otherwise.

Why not just use a ThreadPoolExecutor?

An executor runs tasks in arrival order and has no notion of dependencies, changing priorities, suspension or cascading cancel. The scheduler keeps its own heaps and dependency counters and uses threads only to execute jobs.