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.
- 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
- 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.
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.
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.
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.
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.
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.
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.
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(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.
- 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.
- 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.
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.
- 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.
- "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."