Dependency Graph & Sync Order

Relevant source files

The following files were used as context for generating this wiki page:

• infrahub_sync/dependency_graph.py
• tests/test_dependency_graph.py
• dev/knowledge/schema-mapping.md
• infrahub_sync/cli.py
• dev/knowledge/sync-architecture.md
• tasks/bench.py

Infrahub Sync calculates the sequence of operations for infrastructure data by analyzing relationships between data models. It organizes these models into a directed acyclic graph (DAG) where edges represent references. The sync engine uses this graph to determine a safe "write order," ensuring that parent objects or referenced dependencies exist in the destination before child objects or dependent attributes attempt to reference them.

The system supports both manual ordering via configuration and automatic tier-based execution. Automatic tiering allows for parallel processing of independent object groups, while sequential ordering maintains strict legacy compatibility. This mechanism prevents foreign key violations and data integrity errors during the synchronization process.
Sources: dev/knowledge/sync-architecture.md, dev/knowledge/schema-mapping.md

Core Components and Data Structures

The dependency graph relies on the schema_mapping defined in the project's config.yml. This mapping identifies which models reference others through specific fields.

Component	Description
SchemaMappingModel	Defines a destination model, its source mapping, identifiers, and related fields.
SchemaMappingField	Describes a field within a model, potentially including a reference to another model.
build_dependency_graph	Function that generates a dictionary mapping model names to sets of their dependencies.
compute_tiers	Logic that organizes the dependency graph into a list of sets, where each set represents a tier of independent models.

Sources: infrahub_sync/dependency_graph.py, dev/knowledge/schema-mapping.md

Dependency Graph Logic

The build_dependency_graph function parses the schema_mapping to identify reference attributes. When a field in Model A has a reference to Model B, the system adds an edge from Model A to Model B. If the same model name appears multiple times in the mapping, the engine merges their field references into a single dependency set.

Reference Identification Flow

This diagram shows how the system identifies dependencies from a configuration.

Sync Tiers and Parallelism

The engine organizes the dependency graph into discrete "tiers" for execution. Tier 0 contains leaf-like models that have no outgoing references. Each subsequent tier contains models that only reference models in lower tiers.

Tier Calculation Process

1. The engine identifies all models in the graph.
2. It performs a topological sort to group models into independent layers.
3. If an identity-bearing cycle exists (where models in two different identifiers reference each other), the system raises a DependencyCycleExistsError.
4. If a cycle involves an optional reference (not part of the model's identifiers), the engine drops the optional edge to break the cycle and allow the sync to proceed.

Sources: infrahub_sync/dependency_graph.py:35-86, tests/test_dependency_graph.py:37-80

Sync Execution Flow

The following sequence diagram illustrates how the Potenda engine uses calculated tiers during a sync operation.

Configuration and Overrides

Users can influence the sync order through the config.yml file. By default, the order is auto-computed from reference edges.

• Auto-computed Order: The engine uses compute_tiers to determine the write sequence. This is required for --parallel execution.
• Manual Order: Users can explicitly define an order list in the configuration. If this list is provided, the CLI disables parallel execution and follows the specified sequence exactly.

# Example schema mapping demonstrating references
schema_mapping:
  - name: Tag
    identifiers: ["name"]
  - name: Device
    identifiers: ["name"]
    fields:
      - name: tag
        mapping: tags
        reference: Tag

Sources: dev/knowledge/schema-mapping.md, infrahub_sync/cli.py:236-244

Performance Impact of Sync Order

The choice between sequential and parallel ordering impacts synchronization speed. The benchmark suite compares different scenarios to measure wall-clock time.

• Baseline: Explicit order list, serial execution, and sequential loads.
• Topology-only: Automatic order calculation but serial execution.
• Parallel: Automatic order calculation with tier-by-tier parallel sync.

The tasks/bench.py utility measures these scenarios, showing that parallel execution combined with concurrent loads typically yields the highest performance, especially for large datasets where resource extraction and write operations dominate the time.
Sources: tasks/bench.py:30-45, tasks/bench.py:127-160

Conclusion

The Dependency Graph and Sync Order systems provide a robust framework for managing complex infrastructure relationships. By automatically deriving dependencies from declarative schema mappings, the engine ensures data integrity while offering optimization paths through tier-based parallel execution. The ability to automatically break non-identity cycles further ensures that synchronization remains resilient even in the presence of complex, cross-referenced data models.
Sources: infrahub_sync/dependency_graph.py, dev/knowledge/sync-architecture.md