The Dependency Graph Behind an Apply: Ordering Edges, Cycles, and Partial Failure

A configuration file is written top to bottom and applied in whatever order the dependency graph permits. Those two orders are usually the same for a small tree, which is why the distinction is easy to miss until the tree grows large enough for the tool to reorder it or to apply independent branches concurrently. The rules that decide the order are few, and the failure modes they create are highly predictable once the graph is visible.

Two kinds of edge, and why they are separate

The first edge type expresses ordering: resource B must be applied after resource A. The second expresses notification: if resource A changes, resource B must be told. Both create an edge in the graph, and both are directed, but they carry different meaning and most tools keep them distinguishable.

Ordering exists because some writes require a prior condition: a directory before a file inside it, a package before its configuration, a user before a file owned by that user. In Puppet, a resource that references another with the capitalised form of its type (File['/etc/app']) is implicitly ordered after it, and the metaparameters before, require, notify, and subscribe add explicit edges. Ansible uses task sequence plus notify for handlers. Salt uses require, watch, onchanges, and their inverses.

Notification exists because some work is expensive and must run only when its input changed. Restarting a service after writing its configuration is the canonical case. A notification edge is an ordering edge plus a condition: B runs after A, and only if A reported a change on this run. This makes the apply phase’s behaviour depend on the diff results, not only on the graph, and it produces the ordering rule that surprises people most: if A reports no change, the notify edge does not fire, and B never runs even though it is topologically after A.

Mixing the two produces a subtle asymmetry. A resource that subscribed to a change may be applied before the resource that would change it, if the only edge between them is the subscription and the tool evaluates subscriptions at the end of the phase. Tools differ on whether subscriptions are evaluated immediately or batched, and the difference determines whether a chain of three notification hops reaches the third resource on the same run.

Building and checking the graph

The graph construction is mechanical. Each resource becomes a vertex. Each reference or metaparameter becomes a directed edge. Then the engine checks the resulting graph for cycles before applying anything, because a cycle has no topological order and the apply cannot proceed.

A cycle is reported as a path, which is the useful form. The common accidental cycle has three or four edges and arises from a modelling mistake rather than a genuine circular dependency: a service resource that requires the configuration file, and a file resource that requires the service because it needs the package to have created an owning user. Splitting the user out as its own resource breaks the loop, and the reported path is what identifies that.

Self-dependency is the degenerate cycle: a resource that references itself, often through a templated value that resolves at run time to the same resource name. Tools that resolve references by string comparison detect it; tools that resolve late may fail at apply time instead.

The graph is also where duplicate declaration is detected. Two declarations of the same resource on the same node either merge or conflict depending on the tool, and the merge case is another way to build an accidental cycle: the merged resource now depends on both declarations’ dependencies, so a cycle can exist that neither declaration contains on its own.

What actually gets ordered

Resources with no path between them are unordered, and the engine is free to apply them in any sequence. In practice they are applied in the order they appear in the collected catalogue, or in parallel up to a configured concurrency limit. The important consequence is that the file order of unrelated resources is not a contract. Moving a resource in the source can change its position among its unordered peers without changing any edge.

The graph is also where a template change becomes a service restart, without any declaration saying so: the file resource reports a change because its rendered bytes differ, and the notification edge fires. A template that renders nondeterministically therefore restarts services for no reason, which is the practical cost of an unordered iteration in a template.

Independence also means a resource that reads state written by an unordered peer is a latent bug. The classic instance is a resource that queries the system to discover something a peer creates: it works when the peer happens to run first and fails otherwise. The bug is invisible in a small tree because the collection order is stable, and appears when the tree is refactored or when concurrency is enabled.

Concurrency is the second-order effect. An engine that applies independent resources in parallel will interleave their output, their log lines, and its own process spawns. Concurrency limits bound the number of in-flight resources, which matters when each resource shells out: the process table becomes the bottleneck, and the observed performance gain from raising the limit saturates and then reverses as the scheduler thrashes.

The same graph is what a fleet-level rollout orders its batches by, at a coarser granularity: host-to-host edges that no per-host declaration contains. That extension, and its limits, belongs to fleet-wide plan and apply.

Partial failure and the state it leaves

An apply that fails halfway leaves a graph in which some vertices have been applied, some have not, and some were in the middle of a non-atomic operation. Three behaviours are possible, and tools choose among them.

Fail fast stops at the first failed resource. Everything topologically after it on a path through it is skipped and reported as such. Independent branches may still run. The result is a partially applied graph whose failed frontier is well defined by the dependency structure, which is the property that makes the next run useful: the same apply will retry the failed resource and everything downstream, and skip the resources that already converged.

Continue on error applies everything it can and collects a list of failures. This is useful for auditing a large estate, and dangerous for the same reason: a later resource may be applied against a broken prerequisite, and its own failure will be attributed to it rather than to the upstream one. The error list then contains several entries when the underlying cause is single.

Transactional application applies the graph inside a transaction that can be rolled back. This works on resources the underlying system can transact over, and it does not generalise: a filesystem write and a cloud API call cannot be committed together. Some tools offer transactional mode for a restricted subset, and the constraint is exactly that the providers must support commit and rollback.

The next run’s behaviour is determined by convergence, not by memory of the failure. The tool does not remember that resource A failed; it re-inspects every resource, finds A still out of state, and reapplies. This is why a partially applied graph is a benign condition in a convergent system and a serious one in a scripted system. It is also why failure handling has to preserve the inspection path: a tool that marks a node as “attempted” and skips it on retry has broken convergence.

Notifications during a partial apply

A notification queued by a resource that changed, whose target never ran because a later resource failed, is dropped in most engines. The target will run on the next apply only if its own inputs still differ. If the target’s declaration compares a file that the earlier resource already rewrote, the file is now in the declared state, no diff is reported, and the notification does not fire. The service keeps its old configuration while its file on disk is new and correct. This is the mechanism behind the most confusing class of “configuration applied but service unchanged” outcomes, and it is a direct consequence of the notification being conditional on a diff rather than on a recorded intent.

The available remedy is to make the condition explicit rather than inferred: declare the restart as a resource whose state is comparable (for example, an action keyed on the checksum of the configuration), or accept that the restart will be performed by a separate path that runs after the graph completes. Tools that batch notifications to the end of the phase get partway there, because the batch drains after all resources have been considered; the remaining gap is the failed resource whose notification was never queued at all.

Cycle detection, topological ordering, and the notification-as-edge rule together explain most of the behaviour that looks arbitrary in a large configuration: the order of unrelated resources in the log, the resource that is reported before the one it depends on, the service that does not restart. The graph is the actual program being executed, and the file is one of the ways it is written down.