CONCEPT · 60 minutes

Designing a Workflow Engine

Design a typed-node graph execution engine — grounded in the workflow-engine-rs graph validation and execution model.

Why Workflow Engines Are a Graph Problem

The hardest bug I shipped in workflow-engine-rs was a silent ordering violation. Task B was supposed to run only after task A completed. My first execution loop checked dependencies and thought they were satisfied — but it had a race condition: two workers could both check at the same moment, both see A as "not yet complete," and both skip B. B never ran. The workflow finished successfully but with a missing step.

The fix required rethinking the execution model from scratch. The problem was not the checking logic — it was that I was trying to enforce ordering at runtime. The right approach is to compute the execution order before any task runs, using topological sort, and then execute in that order. A DAG (directed acyclic graph) whose traversal order is computed up front has no race condition: the ordering is determined once, before execution, by graph structure alone.

This is the model I rebuilt around in workflow-engine-rs — and it is the same model under every production workflow engine for the same reason: nothing else gets the ordering right without a runtime race condition. Represent work as a directed graph; validate the graph before execution; execute in topological order, dispatching parallel tasks when their dependencies are satisfied; propagate failures explicitly.

Think of it like a meal preparation plan. You cannot serve the soup before it has simmered; you cannot simmer before it has been chopped; you cannot chop before the vegetables are washed. But you can wash multiple vegetables in parallel. The DAG captures all of this: it enforces ordering where it matters and permits parallelism where it is safe.

The graph abstraction pays for itself in two ways: correctness (cycle detection prevents deadlocks before execution begins) and parallelism (topological sort identifies safe concurrent branches without complex locking). Both of these are much harder to get right at runtime than at graph-construction time.

What This Module Covers

This module walks through the workflow engine as I built it in workflow-engine-rs: the typed-node graph model, graph construction and validation (cycle detection with DFS), topological sort execution with Kahn's algorithm, and failure propagation semantics.

The Typed-Node Graph Model

A workflow is a directed graph where:

Nodes are tasks (units of work with declared inputs and outputs)
Edges are data-flow dependencies (task B's input comes from task A's output)
Types annotate both inputs and outputs — the engine validates that connected nodes have compatible types before execution

One of the things I genuinely love about this model: a whole class of runtime bugs becomes impossible. The typed-node model catches configuration errors before execution. A node that expects a JsonArray input connected to a node that outputs a String is a type mismatch — the engine rejects it at graph construction time rather than failing at runtime when the mismatch causes a crash.

flowchart LR
    A["Node A\nin: Query:String\nout: Results:JsonArray"]
    B["Node B\nin: Results:JsonArray\nout: Summary:String"]
    C["Node C\nin: Results:JsonArray\nout: Stats:JsonObject"]
    D["Node D\nin: Summary:String + Stats:JsonObject\nout: Report:String"]
    A -->|"Results:JsonArray"| B
    A -->|"Results:JsonArray"| C
    B -->|"Summary:String"| D
    C -->|"Stats:JsonObject"| D
    style A fill:#3b82f6,color:#fff
    style D fill:#10b981,color:#fff

In this graph, nodes B and C are parallel branches — they both depend on A but not on each other. Node D depends on both B and C. Topological execution order: A first, then B and C in parallel, then D after both complete.

Graph Construction and Validation

Before any execution, the engine performs two validations:

Cycle detection: a workflow with a cycle is not a DAG — it cannot be executed because task A depends on task B which depends on task A, creating a deadlock. DFS with three-color marking (white = unvisited, gray = in-progress, black = done) detects cycles: a gray → gray edge means a cycle.
Type compatibility: for every edge A → B, check that A's output type is compatible with B's input type. Incompatible types are caught before any task runs.

Cycle Detection — DFS with Three-Color Marking

python

Why reject cycles at construction time: A cycle means two tasks each wait for the other to complete — a deadlock. Without cycle detection at construction time, the engine would start executing, eventually stall with every task in "waiting" state, and give you no indication of why. Detecting cycles at construction time gives you a clear error ("cycle detected between task A and task B") before any work is lost.

Topological Sort Execution

Once the graph is validated (no cycles, types compatible), execution begins using Kahn's algorithm. The key idea: compute in-degree for every node (how many tasks must complete before it can run). Start with all zero-in-degree nodes. As each node completes, decrement the in-degree of its successors. Any successor with in-degree zero is now ready — dispatch it.

Kahn's Algorithm — Topological Execution Order

python

Parallelism: the ready queue can hold multiple tasks simultaneously. In a real engine, each ready task is dispatched to a worker thread or async task — not executed sequentially as the pseudocode above suggests. The in-degree tracking is the correctness mechanism; the parallelism is an implementation detail of how tasks are dispatched from the ready queue.

Failure Propagation Semantics

When a node fails, what happens to its successors? There are three common semantics:

Fail-fast: when any node fails, stop the entire workflow immediately. No new tasks start; in-flight tasks complete (or are cancelled). Best when the workflow represents a single atomic unit of work (a deployment pipeline — if the build step fails, there is no point running tests).

Skip-on-failure: when a node fails, mark its successors as "skipped" rather than running them. Other branches of the graph continue. Best for workflows where branches are independent (a data processing pipeline — one corrupted file should not abort all other files).

Continue-with-error-signal: a failed node emits a typed error output; successors receive this error as their input and can decide how to handle it. Most flexible, but requires every node to handle error inputs. This is the model I use in workflow-engine-rs — each node's output type includes a Result<T, Error> variant, and nodes that cannot handle errors propagate them to their own outputs.

Mid-Module Checkpoint

Before the exercise, verify you can answer these from memory:

What is the three-color marking in cycle detection, and what does a gray → gray edge indicate?
In Kahn's algorithm, what event causes a node to become "ready" for execution?
Name one use case where "fail-fast" is the right failure semantics, and one where "skip-on-failure" is right.

Reflective prompt: In workflow-engine-rs, I validate type compatibility at graph construction time. This catches mismatches before any task runs. What is the cost of this approach? Are there cases where you would prefer to discover a type mismatch at runtime rather than at construction time? Write two sentences before moving to the exercise.

Build It Yourself

Apply the workflow engine design to a concrete problem.

The task: Design a workflow engine for a content moderation pipeline. User-submitted posts go through: text classification (safe/unsafe), image analysis (if the post has images), author reputation check (always), and a final moderation decision (waits for all three). If text classification returns "unsafe," the system should skip image analysis and go directly to the decision step.

<CodeExample title="Design Prompt Starter — Content Moderation Workflow Engine" language="markdown" code={`## Workflow Structure Nodes:

text_classify: in: Post → out: {label: safe|unsafe, score: float}
image_analyze: in: Post → out: {label: safe|unsafe, score: float}
reputation_check: in: author_id → out: {score: float, flags: list}
decision: in: text_result + image_result? + reputation → out: Decision

Dependency questions:

Which nodes can run in parallel?
When should image_analyze be skipped?
What does decision receive when image_analyze is skipped?

Test Your Understanding

Apply workflow engine design principles to realistic scenarios

1. In Kahn's algorithm for topological sort, a node becomes ready for execution when what condition is met?

A)When all nodes in the graph have been visited
B)When the node's in-degree reaches zero — meaning all its dependencies have completed
C)When the node is the first alphabetically among unprocessed nodes
D)When the execution queue is empty

Show Answer

Correct Answer: B

In Kahn's algorithm, each node's in-degree tracks how many of its dependencies are still incomplete. When a dependency completes, the executor decrements the in-degree of each successor. A node with in-degree zero has all dependencies satisfied and is ready to run. Starting with all zero-in-degree nodes and repeating this process produces a valid topological execution order.

2. DFS cycle detection uses three-color marking: white (unvisited), gray (in-progress), black (done). What does finding a gray-to-gray edge indicate?

A)Two nodes are in parallel branches — a normal condition
B)A cycle exists: the current DFS path visits a node that is already in the current path
C)The graph has been fully traversed
D)The edge connects two nodes at the same depth in the graph

Show Answer

Correct Answer: B

A gray node is one that is currently in the DFS call stack — it has been visited but not all its descendants have been processed. Finding an edge to a gray node means the current path is attempting to visit a node that is an ancestor in the current DFS traversal — which is the definition of a back edge, and a back edge means a cycle exists.

3. A workflow engine validates type compatibility at graph construction time. Task A outputs a String, but Task B expects a JsonArray as input. When is this error discovered?

A)When Task B fails at runtime trying to parse the String as JSON
B)Before any task executes — at graph construction/validation time, catching the mismatch before any work is done
C)After Task A completes but before Task B starts
D)Only if Task B explicitly checks its input type

Show Answer

Correct Answer: B

Type validation at construction time checks every edge in the graph before execution begins. The incompatibility between A's String output and B's JsonArray input is caught immediately, with a clear error message naming the nodes and types. This is far better than discovering the mismatch at runtime after A has already run — which wastes the work done by A and any other tasks that completed before B failed.

4. A deployment pipeline has five stages: build, unit-test, integration-test, security-scan, deploy. If the build step fails, what is the correct failure semantics?

A)Skip-on-failure — other stages should continue even if build fails
B)Fail-fast — no subsequent stage has any value if the build fails; stop immediately
C)Continue-with-error-signal — let unit-test run with the build error as input
D)Retry the build three times before propagating failure

Show Answer

Correct Answer: B

Fail-fast is correct here: if the build fails, there is no artifact to test, scan, or deploy. Running subsequent stages is pointless and wasteful. Fail-fast stops the workflow immediately and surfaces the build failure. Skip-on-failure would silently mark later stages as skipped — acceptable in data pipelines but confusing in a deployment context where every stage is a sequential prerequisite.

5. A workflow node fails permanently after three retries. With 'continue-with-error-signal' semantics, what does the executor send to the node's successors?

A)Nothing — successors are skipped automatically
B)A typed error output, so successors can inspect the failure and decide how to handle it — propagate, log, or use a fallback
C)The last partial output produced before the failure
D)A null value, and successors must handle null inputs

Show Answer

Correct Answer: B

Continue-with-error-signal means the failed node emits a typed error value (Result::Err or Option::None) rather than a successful output. Successors receive this error value as their input. Successors that can handle errors gracefully (log and continue) do so; successors that cannot handle errors propagate the error to their own outputs. This gives the workflow designer precise control over error handling per node.

6. In a concurrent workflow executor, two nodes (B and C) both complete at the same time and both decrement the in_degree of node D. What risk does this create and how do you fix it?

A)No risk — in_degree decrement is always atomic in Python and Rust
B)A race condition: both threads could read in_degree=2, both compute 2-1=1, and neither enqueues D even though its in_degree should now be 0. Fix with an atomic decrement or mutex.
C)D will be enqueued twice — once by B's thread and once by C's thread
D)The executor will deadlock waiting for D to complete

Show Answer

Correct Answer: B

Without atomicity, two threads can both read in_degree=2 simultaneously, both compute 1, and both write 1 — so in_degree stays at 1 even though two predecessors have completed. D is never enqueued. The fix: use an atomic decrement (fetch_sub in Rust, threading.Lock in Python) so exactly one thread sees in_degree go to zero and enqueues D. This is one of the subtle concurrency bugs that makes check-then-act patterns dangerous in a multithreaded executor.

You've completed this path

Nice work. Here's what's next.

Back to this path Or book the diagnostic call