Read OSS
hashicorp/terraform

图引擎：Terraform 如何构建和遍历依赖图

•高级

前置知识

  • ›第一篇：架构与代码库导航
  • ›理解 DAG、拓扑排序与并行执行的基本概念
  • ›Go 并发原语（goroutine、channel、sync.WaitGroup）

图引擎：Terraform 如何构建和遍历依赖图

Terraform 最具代表性的架构决策在于：所有操作——plan、apply、validate、import——都被抽象为对有向无环图的遍历。彼此没有依赖关系的资源并行执行，有依赖关系的资源则按拓扑顺序依次执行。正是这一统一的抽象，让 Terraform 能够在单次运行中安全地管理数千个基础设施资源。

图引擎分布在两个包中：internal/dag/ 提供与 Terraform 业务无关的通用图库，而 internal/terraform/ 则在其上封装了特定领域的顶点类型和一套图 transformer 流水线。理解这两层之间的协作方式，对于排查 plan 行为、理解并行机制以及阅读核心引擎代码至关重要。

DAG 包：通用图库

基础结构是 internal/dag/dag.go#L15-L18 中的 AcyclicGraph：

type AcyclicGraph struct {
    Graph
}

AcyclicGraph 内嵌了基础的 Graph 类型，并在此之上添加了假设（并验证）图中不存在环的方法。顶点类型为 interface{}——DAG 包本身对 Terraform 资源、provider 以及任何领域概念一无所知。边是有方向的，表示依赖关系。

classDiagram
    class Graph {
        +vertices Set
        +edges Set
        +Add(Vertex)
        +Remove(Vertex)
        +Connect(Edge)
        +DownEdges(Vertex) Set
        +UpEdges(Vertex) Set
    }
    class AcyclicGraph {
        +Ancestors(vs) Set
        +TransitiveReduction()
        +Validate() error
        +Walk(cb WalkFunc) Diagnostics
    }
    class Walker {
        +Callback WalkFunc
        +Reverse bool
        +Update(g)
        +Wait() Diagnostics
    }
    Graph <|-- AcyclicGraph
    AcyclicGraph ..> Walker : uses

Terraform 主要依赖以下几个核心操作：

  • Ancestors() — 查找某个顶点的所有传递依赖，用于资源 targeting
  • TransitiveReduction() — 删除冗余边，在不改变执行顺序的前提下简化图结构
  • Validate() — 检测环和自引用边
  • Walk() — 高层入口，负责创建 Walker 并运行

这种刻意的解耦设计意味着 DAG 包可以（也确实）使用简单的字符串顶点独立测试，完全不需要引入任何 Terraform 特定类型。

并行遍历：Goroutine、Channel 与依赖信号

internal/dag/walk.go#L39-L68 中的 Walker 结构体是并行执行引擎的核心：

type Walker struct {
    Callback   WalkFunc
    Reverse    bool
    changeLock sync.Mutex
    vertices   Set
    edges      Set
    vertexMap  map[Vertex]*walkerVertex
    wait       sync.WaitGroup
    diagsMap       map[Vertex]tfdiags.Diagnostics
    upstreamFailed map[Vertex]struct{}
    diagsLock      sync.Mutex
}

Walker 为每个顶点创建一个 walkerVertex（第 88-119 行），其中包含两个关键 channel：

  • DoneCh — 当该顶点执行完成（无论成功或失败）时关闭
  • DepsCh — 当所有上游依赖执行完毕后接收一个布尔值；true 表示全部成功，false 表示至少有一个失败
flowchart TD
    subgraph "Vertex A (no deps)"
        A_exec["Execute callback"] --> A_done["Close DoneCh"]
    end
    subgraph "Vertex B (depends on A)"
        B_wait["Wait on A.DoneCh"] --> B_deps["Receive on DepsCh"]
        B_deps -->|"true: deps OK"| B_exec["Execute callback"]
        B_deps -->|"false: upstream failed"| B_skip["Skip execution"]
        B_exec --> B_done["Close DoneCh"]
        B_skip --> B_done
    end
    A_done -.->|"signals"| B_wait

Walker 为每个顶点启动两个 goroutine：一个等待依赖 channel 并将聚合结果发送到 DepsCh，另一个从 DepsCh 接收信号并执行回调。如注释所述，这会产生总计 V*2 个 goroutine。

当上游顶点失败时，所有下游顶点都会在 DepsCh 上收到 false，并被记录到 upstreamFailed 中。这些顶点的错误会被排除在最终诊断结果之外，因为它们属于级联失败——这一设计避免了错误信息的大量堆积，相当贴心。

提示： Terraform 默认并行度为 10（在 internal/terraform/context.go#L146-L148 的 NewContext 中设置）。这里限制的并不是 goroutine 的数量——所有顶点依然会获得各自的 goroutine——而是通过信号量限制同时执行回调的顶点数量，以防超出 provider 的速率限制。

Terraform 的图封装与遍历分发

internal/terraform/ 包在 internal/terraform/graph.go#L19-L28 中定义了自己的 Graph 类型，对通用 DAG 进行封装：

type Graph struct {
    dag.AcyclicGraph
    Path addrs.ModuleInstance
}

通过内嵌，Graph 继承了所有 DAG 方法，同时增加了模块路径，以及连接到 GraphWalker 接口的关键 Walk() 方法（第 37-39 行）。

walk() 函数（第 41-120+ 行）负责领域特定的分发逻辑。对于 DAG 遍历器访问的每个顶点，它会：

  1. 检查该顶点是否实现了 GraphNodeOverridable（用于测试框架覆盖）
  2. 确定求值上下文的作用域（全局、模块实例或部分展开的模块）
  3. 若顶点实现了 GraphNodeExecutable，则分发到其 Execute() 方法

顶点接口构成了一套丰富的类型系统：

classDiagram
    class GraphNodeExecutable {
        <<interface>>
        +Execute(EvalContext, walkOperation) Diagnostics
    }
    class GraphNodeReferenceable {
        <<interface>>
        +ReferenceableAddrs() []Referenceable
    }
    class GraphNodeReferencer {
        <<interface>>
        +References() []*Reference
    }
    class GraphNodeModuleInstance {
        <<interface>>
        +Path() ModuleInstance
    }
    class GraphNodeConfigResource {
        <<interface>>
        +ResourceAddr() ConfigResource
    }

像 NodePlannableResourceInstance 这样的节点类型可以同时实现上述多个接口。图遍历代码通过 Go 的类型断言来探测每个顶点的能力，从而实现灵活的分发机制，而无需定义一个臃肿的单一节点接口。

BasicGraphBuilder：transformer 流水线

图的构建通过一系列变换操作来完成。internal/terraform/graph_builder.go#L26-L34 中的 BasicGraphBuilder 维护着一组 GraphTransformer 步骤：

type BasicGraphBuilder struct {
    Steps []GraphTransformer
    Name  string
    SkipGraphValidation bool
}

Build() 方法（第 36-90 行）遍历这个切片，依次对每个步骤调用 Transform(g)：

for _, step := range b.Steps {
    if step == nil { continue }
    err := step.Transform(g)
    // ...handle errors...
}
sequenceDiagram
    participant Builder as BasicGraphBuilder
    participant G as Graph
    participant T1 as ConfigTransformer
    participant T2 as ReferenceTransformer
    participant T3 as TransitiveReductionTransformer

    Builder->>T1: Transform(g)
    Note over T1,G: Adds resource vertices from config
    T1-->>G: mutated
    Builder->>T2: Transform(g)
    Note over T2,G: Wires dependency edges from HCL refs
    T2-->>G: mutated
    Builder->>T3: Transform(g)
    Note over T3,G: Removes redundant edges
    T3-->>G: mutated
    Builder->>G: Validate()

每个 transformer 都就地修改图——添加顶点、添加边、移除顶点或修改现有节点。这种变换流水线的模式非常强大，因为 transformer 天然可组合：你可以增减步骤而不影响其他步骤。当然，这也意味着图在任意时刻的结构取决于之前各 transformer 的执行顺序，这正是各图构建器中 Steps() 方法需要精心排序的原因。

所有变换完成后，Build() 会调用 g.Validate() 检测环。若验证失败，Terraform 会记录图的结构信息并返回错误。

PlanGraphBuilder：plan 图的结构解析

internal/terraform/graph_builder_plan.go#L30-L135 中的 PlanGraphBuilder 负责生成用于 planning 的图。其 Steps() 方法（第 148-328 行）返回超过 20 个 transformer。以下是最重要的几个，按执行顺序列出：

flowchart TD
    CT["ConfigTransformer<br/>Add resource vertices from config"] --> RVT["RootVariableTransformer<br/>Add input variable nodes"]
    RVT --> MVT["ModuleVariableTransformer<br/>Add module variable nodes"]
    MVT --> LT["LocalTransformer<br/>Add local value nodes"]
    LT --> OT["OutputTransformer<br/>Add output value nodes"]
    OT --> ORIT["OrphanResourceInstanceTransformer<br/>Add nodes for state resources missing from config"]
    ORIT --> ST["StateTransformer<br/>Add deposed instance nodes"]
    ST --> AST["AttachStateTransformer<br/>Attach state to resource nodes"]
    AST --> ARC["AttachResourceConfigTransformer<br/>Attach config to resource nodes"]
    ARC --> PT["ProviderTransformer<br/>Wire provider dependencies"]
    PT --> SchemaT["AttachSchemaTransformer<br/>Attach schemas to nodes"]
    SchemaT --> MET["ModuleExpansionTransformer<br/>Handle count/for_each"]
    MET --> RT["ReferenceTransformer<br/>Wire dependency edges from HCL refs"]
    RT --> TT["TargetsTransformer<br/>Prune to targeted resources"]
    TT --> CPRT["CloseProviderTransformer<br/>Add provider close nodes"]
    CPRT --> TRT["TransitiveReductionTransformer<br/>Simplify graph"]

internal/terraform/transform_config.go#L33-L73 中的 ConfigTransformer 通常是第一个实质性的 transformer。它遍历配置树，为每个资源声明添加一个顶点。但需要注意：此阶段 count 和 for_each 尚未被求值，因此每个顶点代表的是配置层面的资源，而非具体的实例。实例展开会在后续通过 ModuleExpansionTransformer 以及遍历期间的动态展开来完成。

internal/terraform/transform_reference.go#L19-L43 中的 ReferenceTransformer 负责连接依赖边。它检查每个节点引用了哪些地址（通过 GraphNodeReferencer），以及每个节点提供了哪些地址（通过 GraphNodeReferenceable），然后建立边连接。正是通过这个机制，资源配置中的 var.name 创建了对变量节点的依赖，aws_instance.web.id 创建了对 aws_instance.web 资源节点的依赖。

ApplyGraphBuilder：与 Plan 的区别

internal/terraform/graph_builder_apply.go#L26-L93 中的 ApplyGraphBuilder 接收的输入与 plan 有本质区别：它的输入是 plan 生成的变更集，而不是配置本身。其 Steps() 方法（第 105-200+ 行）引入了 DiffTransformer：

&DiffTransformer{
    Concrete: concreteResourceInstance,
    State:    b.State,
    Changes:  b.Changes,
    Config:   b.Config,
},

ConfigTransformer 从配置中添加顶点，而 DiffTransformer 则从计划变更中添加顶点。这确保了 apply 图只包含真正需要变更的资源——这是一个重要的安全保障。

apply 图还使用了不同的具体节点类型。plan 图使用 NodePlannableResourceInstance，而 apply 图使用 NodeApplyableResourceInstance（第 119-124 行），后者调用的是 provider.ApplyResourceChange() 而非 PlanResourceChange()。

两种构建器共用了许多相同的 transformer——ReferenceTransformer、ProviderTransformer、TransitiveReductionTransformer——因为依赖排序和图简化的基本需求是一致的。

遍历操作：八种图遍历模式

同一套图基础设施支持八种不同的遍历类型，定义在 internal/terraform/graph_walk_operation.go#L9-L21：

const (
    walkInvalid walkOperation = iota
    walkApply
    walkPlan
    walkPlanDestroy
    walkValidate
    walkDestroy
    walkImport
    walkEval
    walkInit
)

PlanGraphBuilder.Steps() 方法根据操作类型进行分支，选择正确的初始化逻辑（第 149-160 行）。对于 walkPlan，调用 initPlan() 为可规划资源设置具体的节点工厂；对于 walkPlanDestroy，则调用 initDestroy() 为销毁顺序配置图结构。

这一设计意味着，同一套 transformer 流水线可以根据操作类型生成截然不同的图，同时共用绝大部分结构逻辑。

下一篇预告

了解了图的构建与遍历机制之后，第三篇文章将跟踪单个资源实例走完完整的 plan-and-apply 生命周期——从 Context.Plan() 创建图，到 NodePlannableResourceInstance.Execute() 调用 provider，再到 Context.Apply() 真正执行基础设施变更。我们还将深入研究 EvalContext 接口，看看它如何在图节点与外部世界之间架起桥梁。