Directed Acyclic Graph (DAG)

The edges in a DAG have a direction, representing a one-way dependency or data flow from one node (task) to another. This directionality is fundamental to defining the order of execution.

• An edge from Node A to Node B means A must complete before B can start.
• This creates a partial order among tasks, where some tasks must precede others, but independent tasks can be unordered relative to each other.

A DAG contains no cycles—it is impossible to start at a node and follow a sequence of directed edges that returns to the same node. This property is critical for preventing infinite loops in workflow execution.

• Ensures tasks have a clear beginning and end.
• Guarantees that a topological ordering of nodes exists, which is the sequence used for execution.
• In orchestration, a cycle would represent a logical paradox (e.g., Task A depends on Task B, which depends on Task A).

In workflow orchestration, each node in the DAG represents a discrete, executable unit of work or an activity. Nodes encapsulate the logic to be performed.

• Examples include: running a script, querying a database, calling an API, or training a machine learning model.
• Nodes can have properties like execution timeouts, retry policies, and resource requirements.
• The granularity of a node is defined by the workflow designer.

The edges define the dependencies and data flow between tasks. They enforce execution order and can optionally pass data or context from upstream to downstream tasks.

• A downstream task cannot execute until all of its upstream dependencies are satisfied (e.g., completed successfully).
• This dependency graph allows the orchestrator to automatically schedule tasks as soon as their prerequisites are met.
• Edges enable the modeling of complex, fan-in/fan-out dependency patterns.

A topological sort is a linear ordering of a DAG's nodes where for every directed edge from node A to node B, A appears before B in the ordering. This ordering is the blueprint for sequential execution.

• Workflow engines perform a topological sort to determine a valid execution sequence.
• Multiple valid orderings may exist for the same DAG, but all respect the dependency constraints.
• This is the algorithmic foundation that makes DAGs executable.

Because a DAG only specifies partial order, tasks that are not directly or indirectly dependent on each other can be executed in parallel. This is a key advantage for performance optimization.

• The orchestrator identifies independent branches of the graph and can schedule their nodes concurrently.
• This maximizes resource utilization and reduces end-to-end workflow runtime.
• The degree of parallelism is constrained only by the dependency structure, not by the definition language.

A workflow engine is the core software component that executes predefined sequences of tasks. It manages the runtime state, routes data between tasks, and invokes activities according to a defined model (like a DAG). Key responsibilities include:

• State Persistence: Durable storage of execution state.
• Task Scheduling: Determining when and where to run tasks.
• Failure Handling: Managing retries and errors. Examples include Apache Airflow, Temporal, and AWS Step Functions.

A task orchestrator is a system responsible for coordinating the execution, scheduling, and dependency management of individual tasks within a larger workflow. While a workflow engine manages the overall model, the orchestrator focuses on the real-time logistics:

• Dependency Resolution: Ensuring tasks run only when their prerequisites are met.
• Resource Allocation: Assigning tasks to available workers or compute resources.
• Lifecycle Management: Starting, monitoring, and terminating task executions. This component is essential for translating a static DAG definition into a dynamic, running process.

An execution plan is a runtime blueprint generated by the workflow engine from a static workflow definition (like a DAG). It specifies the precise, concrete steps for a single run:

• Order of Operations: The exact sequence of tasks to execute.
• Resource Bindings: Specific compute targets or queues for each task.
• Conditional Paths: Resolved logic branches based on initial input data. While the DAG defines possible paths, the execution plan is the deterministic roadmap for a specific instance. It is often optimized for performance before execution begins.

A Workflow Definition Language is a domain-specific language (DSL) or data format used to declaratively specify the structure of an executable workflow. It encodes the DAG's tasks, dependencies, and control flow. Common examples include:

• Apache Airflow: DAGs defined in Python.
• AWS Step Functions: JSON-based Amazon States Language (ASL).
• CWL (Common Workflow Language): YAML/JSON-based standard for portable workflows. These languages allow developers to version, share, and reproduce complex workflows as code.

A process instance is a single, specific execution of a workflow definition. Each time a DAG is triggered, a new instance is created. Key characteristics:

• Isolated State: Maintains its own variables, execution history, and logs.
• Independent Lifecycle: Can be started, paused, resumed, or canceled without affecting other instances.
• Audit Trail: Records all events and state changes for that specific run. In a DAG-based system, each instance tracks which nodes (tasks) have been completed for that particular execution.

An activity is a discrete, executable unit of work within a workflow, represented as a node in a DAG. It is the atomic operation the engine invokes. Activities can be:

• Service Calls: Invoking an external API or microservice.
• Function Execution: Running a piece of business logic or a data transformation.
• Human Tasks: Requiring manual input or approval. The workflow engine manages the scheduling, input/output passing, and retry logic for each activity, while the activity itself contains the business logic.