Parallel Dataflow Engine

Project roadmap

1. 01

   Design the engine

   ~2h

   Write DESIGN.md: a graph has tasks (id, the ids it depends on, the kind of work, a timeout and retry settings); results of dependencies are passed to the tasks that need them; a task's state is pending, running, succeeded, failed, skipped or cancelled; what happens downstream of a failure (skip dependents, keep independent branches, or fail fast as an option); and the global concurrency limit. Done when: DESIGN.md covers states, failure handling and concurrency.

2. 02

   Validate the graph

   ~1.5h

   Model graphs as case classes and validate them: unique ids, every dependency exists, and no cycles (detected with a depth-first search that reports the cycle's path). Compute a topological order for display. Done when: tests show cycles and missing dependencies are reported clearly, and valid graphs are accepted.

3. 03

   Run tasks in parallel

   ~3h

   Write the scheduler with Cats Effect: keep each task's state in a Ref, start every task whose dependencies have succeeded, run them as fibers limited by a Semaphore, and when a task finishes, start the ones it unblocked. Pass dependency results to each task. Apply each task's timeout with IO.timeout. Done when: a diamond-shaped graph runs its middle tasks in parallel, and the final task gets both results.

4. 04

   Handle failures and cancellation

   ~2.5h

   Retry failed tasks with exponential backoff up to their limit. When a task finally fails, mark its dependents skipped while independent branches continue, or cancel all running tasks in fail-fast mode. Cancelling a whole run cancels running fibers and releases resources safely (use Resource and guarantee for cleanup). Done when: tests show skipped dependents, continuing branches, and clean cancellation.

5. 05

   Add the HTTP API

   ~2h

   Add http4s endpoints: POST /runs (submit a graph as JSON, validated with clear errors), GET /runs/{id} (each task's state, attempts, duration and error), GET /runs/{id}/events as a stream of state changes (server-sent events), and DELETE /runs/{id} to cancel. Keep runs in memory with a limit on how many are kept. Done when: a graph can be submitted, watched live and cancelled over HTTP.

6. 06

   Add observability

   ~1h

   Log every state change with the run, task, attempt and duration, and compute per-run statistics: total time, the critical path (the longest chain of dependencies) and how much parallelism was achieved. Done when: finished runs report their critical path and statistics.

7. 07

   Test it

   ~2.5h

   Write tests with munit-cats-effect and TestControl to control time: parallelism within the limit, dependency order, retries with backoff, skipping and fail-fast, timeouts, cancellation mid-run, and a property-based test with random acyclic graphs checking no task ever starts before its dependencies finish. Done when: sbt test passes reliably.

Resources

• DocsCats Effect: concurrency basics (fibers)
• DocsCats Effect: Semaphore
• DocsCats Effect: TestControl
• ArticleTopological sorting (Wikipedia)
• Docshttp4s documentation