orchestrator_graph

package module
v1.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 23, 2026 License: EUPL-1.2 Imports: 15 Imported by: 0

README

Stellwerk Platform Orchestrator Graph

The core graph algorithms behind the Stellwerk Platform Orchestrator.

☑️ - resource types, classes, and IDs ☑️ - resource params ☑️ - workloads ☑️ - shared resources ☑️ - matching of resources to module definitions using "rules" ☑️ - dependency resources in module definitions ☑️ - co-provisioned resources in module definitions ☑️ - optional "is dependent on current" flag to link co-provisioned resource to current resource ☑️ - optional "copy dependents on current" flag to link co-provisioned resource to ancestors of current resource

This is a shared library with zero or at least few production dependencies. This provides the core types and algorithms for:

  1. The manifest (the thing the customer gives us describing their workloads and resources)
  2. The rules that map requested resources to modules
  3. The algorithm for building a graph from (1) and (2) in a deterministic way
  4. The algorithm for building a new graph and determine drift when compared to an old graph
  5. An algorithm for building a mermaid visualisation of the graph

It does not include:

  1. The schema or shape of a module
  2. The mechanism for converting this to Terraform (since that depends on a complex HCL parser and library)
  3. An implementation for placeholders, resource references, or resource selectors - yet.

This means that this core graph does not change even if we change the way modules are implemented or need to fix or change serialization.

With low dependencies, this package should change very rarely.

API

First, convert the user manifest into a Manifest. The source material may have more fields, like the variable embeddings and everything, but here we just need the core elements that impact the graph.

manifest := Manifest{
    Workloads: map[string]ManifestWorkload{
        "my-workload": {
            Resources: map[string]ManifestResource{
                "some-name": {
                   Type: "postgres",
                   # ...
                }
                # ...
            }    
        }
        # ...
    }
    # ...
}

Then, convert the set of module rules for the current context or environment into an array of ModuleDefinition and then into NewModuleDefinitionIndex. Note that this is generic over the type of module configuration structure, here called ExampleConfiguration.

index := NewModuleDefinitionIndex([]ModuleDefinition[*ExampleConfiguration]{
    {ResourceType: "postgres", Rules: []Rule{{}}, Configuration: &ExampleConfiguration{ /* ... */ }},
    # ...
})

And you can convert the manifest and module index into the final graph with errors and drift calculated. This graph is a Graph instance, and you can inspect the Nodes, Edges, Workloads, SharedResources, DepthFirstIterator() and various variants of these methods to look over the nodes, inspect errors and drift, and look at the module configuration used for each node.

graph, err := SeedAndExpandAll(context.TODO(), manifest, *index, nil)
# ...

Once you have a graph, you can store this and reconstruct it as needed. The last parameter of the SeedAndExpandAll function is the previous graph. This is used to determine "drift" where a module used to provision a resource is changing. This may be critical to know about when the provisioned infrastructure is stateful like databases, object store buckets, and other sensitive things that should not be dropped or lost.

Note that this is just the first line of defence against losing stateful data. The modules themselves can set their own locking or "prevent-destroy" semantics which you should respect at implementation time.

What about parameter and selector evaluation?!

For now, not implemented directly in this package but the tools to support it are here.

  • Graph.Nodes contains all the nodes in the graph including resources and workloads (which are also resources)
  • Graph.Edges contains the map of source node to target node
  • Graph.SharedResources contains the map of alias to target node for shared resources

With these, we can support ${resources.fizz..} and ${shared.buzz...} resource references.

  • A BuildAdjacencyMatrix() function that can be used to build an adjacency and distance matrix that supports functions like FindDescendentsOf and FindAncestorsOf which can be used to navigate up and down.
  • Workloads represented as resources with workload type
  • A AddAnonymousdependency() function that can add an arbitrary anonymous edge to enforce dependency across the graph.

With these, we can support CSS-style parent/child navigating selectors.

Development

  • go tool gotestsum or go test -v ./... to run unit tests.
  • go vet ./... and golangci-lint run to lint the code.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var DefaultAnonymousEdgeAliasFunc = func(from, to ResourceCoordinate) string {
	h := sha256.New()
	_, _ = h.Write([]byte(to.Type))
	_, _ = h.Write([]byte{0})
	_, _ = h.Write([]byte(to.Class))
	_, _ = h.Write([]byte{0})
	_, _ = h.Write([]byte(to.Id))
	return base64.RawStdEncoding.EncodeToString(h.Sum(nil))
}

DefaultAnonymousEdgeAliasFunc is the function used to determine an alias for an anonymous edge added due to placeholder resolution or coprovisioning rules.

View Source 
var DefaultClass = "default"

DefaultClass is the default class to assign resources that haven't requested a class specifically

View Source 
var DefaultSharedResourceIdFunc = func(ctx context.Context, alias string, manifest ManifestResource) string {
	return fmt.Sprintf("shared.%s", alias)
}

DefaultSharedResourceIdFunc is the function that allocates ids to the shared resources anchored by the manifest. The function uses the resource alias by default.

View Source 
var DefaultWorkloadResourceIdFunc = func(ctx context.Context, workload string, alias string, manifest ManifestResource) string {
	return fmt.Sprintf("workloads.%s.%s", workload, alias)
}

DefaultWorkloadResourceIdFunc is the function that allocates ids to the resources anchored by the workloads. The function by default uses the workload id and alias, but you can choose to override this.

View Source 
var DefaultWorkloadResourceType = "workload"

DefaultWorkloadResourceType is the type of the workload resource node that we inject for each workload.

View Source 
var InheritClassOrIdSymbol = "@"

InheritClassOrIdSymbol is the symbol that can be used in place of the class or id to inherit the value from the resource that declares the dependency or co-provisions the resource.

View Source 
var RePlaceholder = regexp.MustCompile(`\${[^{}]+}`)

Functions

func CompareOptionalString 

func CompareOptionalString(a, b OptionalString) int

func CompareResourceCoordinate 

func CompareResourceCoordinate(a, b ResourceCoordinate) int

func IterPlaceholders 

func IterPlaceholders(data interface{}, finalErr *error) iter.Seq2[string, PlaceholderSub]

IterPlaceholders streams over the data type and returns any observed placeholders and a parsed object for them. It will automatically deduplicate placeholders so they only need to be evaluated once.

func Version 

func Version() string

Types

type ContextPlaceholder 

type ContextPlaceholder struct {
	// Key is the context key from the context map
	Key string
}

func (ContextPlaceholder) Type 

func (c ContextPlaceholder) Type() PlaceholderType

type DepthFirstIterateOrder 

type DepthFirstIterateOrder int
const (
	DepthFirstIteratePreOrder DepthFirstIterateOrder = iota
	DepthFirstIteratePostOrder
)

type DistanceMatrix 

type DistanceMatrix map[ResourceCoordinate]map[ResourceCoordinate]int

func (DistanceMatrix) FillDistanceMatrix 

func (d DistanceMatrix) FillDistanceMatrix() DistanceMatrix

FillDistanceMatrix builds a full distance matrix. Looking up any node should produce all the nodes that are dependencies in some way by their minimum depth. Nodes that don't have any dependencies are excluded. This uses the Floyd-Warshall (https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) algorithm.

func (DistanceMatrix) FindAncestorsOf 

func (d DistanceMatrix) FindAncestorsOf(c ResourceCoordinate) iter.Seq2[ResourceCoordinate, int]

FindAncestorsOf returns an iteration over all the resources that depend on c, directly and transitively through. The integer value is the depth.

func (DistanceMatrix) FindDescendentsOf 

func (d DistanceMatrix) FindDescendentsOf(c ResourceCoordinate) iter.Seq2[ResourceCoordinate, int]

FindDescendentsOf returns an iteration over all the resources that the given resource c depends on, directly and transitively through other dependencies. The integer value is the depth. This is more efficient than the DepthFirstIterate function but doesn't return in any particular order.

func (DistanceMatrix) ResolveSelectorPlaceholder 

func (d DistanceMatrix) ResolveSelectorPlaceholder(context ResourceCoordinate, sp *SelectorPlaceholder) error

ResolveSelectorPlaceholder fills the MatchedCoordinates field on the selector placeholder with the correct matched nodes based on the distance matrix.

type DriftResolution 

type DriftResolution string
const (
	// DriftResolutionAcceptModuleChange allows the node to accept module and configuration changes
	DriftResolutionAcceptModuleChange DriftResolution = "accept_module_change"
	// DriftResolutionAcceptConfigChange allows the node to accept configuration changes
	DriftResolutionAcceptConfigChange DriftResolution = "accept_config_change"
)

type DriftType 

type DriftType string
const (
	// DriftNone means the nodes are using exactly the same module configuration
	DriftNone DriftType = ""
	// DriftConfigurationChange means the nodes are using the same module, but they differ in version, params,
	// or configuration. An upgrade is likely to succeed.
	DriftConfigurationChange DriftType = "config_change"
	// DriftModuleChange means the nodes are using different modules entirely and a replacement will likely be needed.
	DriftModuleChange DriftType = "module_change"
	// DriftConfigurationChangeSkipped occurs when a configuration change is skipped due to a drift resolution strategy.
	DriftConfigurationChangeSkipped DriftType = "config_change_skipped"
	// DriftModuleChangeSkipped occurs when a module change is skipped due to a drift resolution strategy.
	DriftModuleChangeSkipped DriftType = "module_change_skipped"
)

func ApplyDriftResolution 

func ApplyDriftResolution(current DriftType, resolution DriftResolution) (DriftType, bool)

type ErrCycle 

type ErrCycle struct{}

func (*ErrCycle) Error 

func (e *ErrCycle) Error() string

type ErrGraph 

type ErrGraph struct {
	ByNode map[ResourceCoordinate]error
}

func (*ErrGraph) Error 

func (e *ErrGraph) Error() string

type ErrInvalidPlaceholder 

type ErrInvalidPlaceholder struct {
	// contains filtered or unexported fields
}

func NewErrInvalidPlaceholder 

func NewErrInvalidPlaceholder(message string) *ErrInvalidPlaceholder

func (*ErrInvalidPlaceholder) Error 

func (e *ErrInvalidPlaceholder) Error() string

type ErrNoRuleMatch 

type ErrNoRuleMatch struct{}

func (*ErrNoRuleMatch) Error 

func (e *ErrNoRuleMatch) Error() string

type ErrParamsMismatch 

type ErrParamsMismatch struct{}

func (*ErrParamsMismatch) Error 

func (e *ErrParamsMismatch) Error() string

type Graph 

type Graph[D ModuleConfiguration] struct {
	// Nodes is the map of node coordinate to node details.
	Nodes map[ResourceCoordinate]ResourceNode[D] `json:"nodes"`
	// Edges is the map of node, to node via a labeled edge. The label is the 'alias' in the dependent resources.
	Edges map[ResourceCoordinate]map[string]ResourceCoordinate `json:"edges"`

	// Workloads are the set of named workloads that have been added from the manifest.
	Workloads map[string]ResourceCoordinate `json:"workloads"`
	// SharedResources are the map of aliased shared resources in the root of the manifest.
	SharedResources map[string]ResourceCoordinate `json:"shared_resources"`
	// LeafResources are leaf resources in the graph that may be workload resources, shared resources, or dependent
	// resources. The common concept is that no nodes depend on them.
	LeafResources map[ResourceCoordinate]bool `json:"leaf_resources"`
	// contains filtered or unexported fields
}

A Graph is the graph state resulted from applying a set of module definitions and rules to a manifest. This is done through the SeedAndExpandAll api OR through a combination of a single call to Seed and 'N' calls to Expand until IsExpanded returns true. The graph holds a set of nodes and edges along with the workloads, shared resources. The generic parameter D is the implementation of the ModuleConfiguration which includes things like the module, version, and dependency declarations. None of which particularly matter for the graph resolution itself. On each node, we also store an error found during expansion or a drift when we have compared the result to a previous graph from a previous deployment.

func Seed 

func Seed[D ModuleConfiguration](ctx context.Context, manifest Manifest) Graph[D]

The Seed function is a constructor that creates the initial graph with leaf nodes and prepares for Expand.

func SeedAndExpandAll 

func SeedAndExpandAll[D ModuleConfiguration](ctx context.Context, manifest Manifest, definitions ModuleDefinitionIndex[D], previousGraph *Graph[D]) (Graph[D], error)

SeedAndExpandAll is the constructor that seeds the graph and expands all iteratively until the end of the graph is reached. It then labels any cycles and identifies if errors were found. THIS IS THE CONSTRUCTOR YOU SHOULD USE.

func (*Graph[D]) AddAnonymousDependency 

func (g *Graph[D]) AddAnonymousDependency(from ResourceCoordinate, to ResourceCoordinate) error

AddAnonymousDependency can be used after the graph is expanded to add additional dependency edges to the graph. You should call LabelCycle after this to check if there is now a dependency cycle. The node is added with an alias that is a base64 encoded hash. The hash algorithm is DefaultAnonymousEdgeHash.

func (*Graph[D]) BuildAdjacencyMatrix 

func (g *Graph[D]) BuildAdjacencyMatrix() DistanceMatrix

BuildAdjacencyMatrix returns a DistanceMatrix which contains only the immediate neighbours set to distance 1.

func (*Graph[D]) DepthFirstIterate 

func (g *Graph[D]) DepthFirstIterate(o DepthFirstIterateOrder) iter.Seq[ResourceCoordinate]

DepthFirstIterate iterates through the entire graph in a depth first way. This is useful to make sure that all dependencies are processed or visited first.

func (*Graph[D]) DepthFirstIterateFrom 

func (g *Graph[D]) DepthFirstIterateFrom(c ResourceCoordinate, o DepthFirstIterateOrder) iter.Seq[ResourceCoordinate]

DepthFirstIterateFrom iterates through the subgraph rooted at the given resource coordinate.

func (*Graph[D]) Expand 

func (g *Graph[D]) Expand(ctx context.Context, definitions ModuleDefinitionIndex[D], previousGraph *Graph[D])

Expand attempts to expand the next unexpanded node. This is only needed if you are using Seed and IsExpanded manually.

func (*Graph[D]) HasErrors 

func (g *Graph[D]) HasErrors() bool

HasErrors returns if any errors were found during expansion.

func (*Graph[D]) IsExpanded 

func (g *Graph[D]) IsExpanded() bool

IsExpanded returns whether the graph is fully expanded. This is only useful if you are using Seed and Expand manually.

func (*Graph[D]) LabelCycle 

func (g *Graph[D]) LabelCycle() map[ResourceCoordinate]bool

LabelCycle will attempt to find a cycle in the graph. This does not find _all_ cycles. This is called automatically within SeedAndExpandAll but can be called again if you have added additional edges to the graph through AddAnonymousDependency.

func (*Graph[D]) ResolveResourcePlaceholder 

func (g *Graph[D]) ResolveResourcePlaceholder(aliasContext ResourceCoordinate, rt *ResourcePlaceholder) error

ResolveResourcePlaceholder fills the Coordinate field on the resource placeholder with the correct node.

type Manifest 

type Manifest struct {
	Workloads       map[string]ManifestWorkload
	SharedResources map[string]ManifestResource
}

type ManifestCoProvision 

type ManifestCoProvision struct {
	ManifestResource
	// If IsDependentOnCurrent is true, then we create an edge from the co provisioned resource to the current resource
	// so that this co provisioned resource "depends" on the current resource and is only provisioned after the
	// current resource is completely provisioned. This may be needed if the co provisioned resource uses selectors
	// to pull values out of the current resource or relies on side effects from it.
	IsDependentOnCurrent bool

	// If CopyDependentsOnCurrent is true, then we also add edges from all resources that depend on the current resource
	// to the co provisioned resource. So that we enforce a sibling relationships between the current resource and the
	// co provisioned one. This ensures that the co provisioned resource is co provisioned before the parents.
	CopyDependentsOnCurrent bool
}

type ManifestResource 

type ManifestResource struct {
	Type   string
	Class  OptionalString
	Id     OptionalString
	Params map[string]interface{}
}

type ManifestWorkload 

type ManifestWorkload struct {
	Resources map[string]ManifestResource
	Outputs   map[string]string
}

type ModuleConfiguration 

type ModuleConfiguration interface {
	CalculateDrift(mc ModuleConfiguration) DriftType
	GetDependencies() map[string]ManifestResource
	GetCoProvisioned() []ManifestCoProvision
}

type ModuleDefinition 

type ModuleDefinition[E ModuleConfiguration] struct {
	// The resource matching bits
	ResourceType string
	Rules        []Rule

	// The actual configuration of the module
	Configuration E
}

type ModuleDefinitionIndex 

type ModuleDefinitionIndex[D ModuleConfiguration] struct {
	// contains filtered or unexported fields
}

func NewModuleDefinitionIndex 

func NewModuleDefinitionIndex[D ModuleConfiguration](defs []ModuleDefinition[D]) *ModuleDefinitionIndex[D]

func (*ModuleDefinitionIndex[D]) FindBest 

func (d *ModuleDefinitionIndex[D]) FindBest(_ context.Context, coordinate ResourceCoordinate) (ModuleDefinition[D], bool)

type OptionalString 

type OptionalString struct {
	// contains filtered or unexported fields
}

OptionalString is a static non-pointer implementation of a nullable string. Use IsSet to check the value, and MustValue to retrieve tha value. Various utility constructors and methods exist for making things easy

func OptionalStringOf 

func OptionalStringOf(s string) OptionalString

OptionalStringOf returns an OptionalString with the value set.

func OptionalStringOfNonEmpty 

func OptionalStringOfNonEmpty(s string) OptionalString

OptionalStringOfNonEmpty is similar to OptionalStringOf but treats an empty string as not set.

func OptionalStringOfRef 

func OptionalStringOfRef(s *string) OptionalString

OptionalStringOfRef returns an OptionalString with the value set if it is not nil.

func (OptionalString) IsSet 

func (o OptionalString) IsSet() bool

func (OptionalString) Map 

func (o OptionalString) Map(f func(s string) string) OptionalString

func (OptionalString) MustValue 

func (o OptionalString) MustValue() string

func (OptionalString) Ref 

func (o OptionalString) Ref() *string

func (OptionalString) String 

func (o OptionalString) String() string

func (OptionalString) ValueOr 

func (o OptionalString) ValueOr(defaultValue string) string

func (OptionalString) ValueOrFunc 

func (o OptionalString) ValueOrFunc(defaultValue func() string) string

type PlaceholderSub 

type PlaceholderSub interface {
	Type() PlaceholderType
}

func ParsePlaceholder 

func ParsePlaceholder(placeholder string) (PlaceholderSub, error)

type PlaceholderType 

type PlaceholderType string
const (
	PlaceholderTypeResource PlaceholderType = "resource"
	PlaceholderTypeContext  PlaceholderType = "context"
	PlaceholderTypeTfVar    PlaceholderType = "var"
	PlaceholderTypeSelector PlaceholderType = "select"
	PlaceholderTypeSelf     PlaceholderType = "self"
)

type ResourceCoordinate 

type ResourceCoordinate struct {
	Type  string
	Class string
	Id    string
}

func (ResourceCoordinate) MarshalText 

func (rc ResourceCoordinate) MarshalText() ([]byte, error)

func (ResourceCoordinate) String 

func (rc ResourceCoordinate) String() string

func (*ResourceCoordinate) UnmarshalText 

func (rc *ResourceCoordinate) UnmarshalText(data []byte) error

type ResourceNode 

type ResourceNode[D ModuleConfiguration] struct {
	// The ModuleConfiguration of this node. This is the _next_ configuration to use, not necessarily what was
	// previously used. This has already had any NextDriftResolution strategy applied.
	ModuleConfiguration D `json:"config"`
	// The Params (parameters) captured from the Manifest or the dependent node.
	Params map[string]interface{} `json:"params"`
	// ParamsDefinedBy is coordinates of the node that defined the Params, which has a direct dependency on this resource and should be used for placeholder context in the params.
	// Empty string, if there's no direct dependency.
	ParamsDefinedBy *ResourceCoordinate `json:"params_defined_by"`
	// CurrentDrift DEPRECATED use DetectedDrift, keeping it for backward compatibility
	CurrentDrift int `json:"current_drift,omitzero"`
	// DetectedDrift is the drift found in the current Expand cycle, caused by the module rules or module configuration
	// changing since the previous graph.
	DetectedDrift DriftType `json:"detected_drift,omitzero"`
	// EffectiveDrift is the final drift after applying the NextDriftResolution strategy to the DetectedDrift.
	EffectiveDrift DriftType `json:"effective_drift,omitzero"`

	// Error is an error encountered during Expand, we don't serialize this since we should not store error'ed graphs.
	Error error `json:"-"`
	// NextDriftResolution is the drift resolution to use in the _next_ graph expansion. This is usually set by the module
	// definition or by an operator/admin. We don't serialize this, since this is only used when expanding a new graph.
	NextDriftResolution DriftResolution `json:"-"`
}

ResourceNode is the state of a node in the graph.

type ResourcePlaceholder 

type ResourcePlaceholder struct {
	// Coordinate is the matched coordinate once we've resolved the placeholder
	Coordinate *ResourceCoordinate
	// Alias is the local alias within the context of the current node
	Alias string
	// IsShared holds whether this is from the shared aliases rather than the dependency aliases
	IsShared bool
	// IsSelf holds whether this is the self placeholder
	IsSelf bool
	// Output captures the output key traversal they want to pull out of the target resource
	Output []string
}

func (ResourcePlaceholder) Type 

func (r ResourcePlaceholder) Type() PlaceholderType

type Rule 

type Rule struct {
	ResourceClass OptionalString
	ResourceId    OptionalString
}

type SelectorFilter 

type SelectorFilter struct {
	Type  string
	Class OptionalString
	Id    OptionalString
}

func ParseSelectorFilter 

func ParseSelectorFilter(raw string) SelectorFilter

func (SelectorFilter) Matches 

func (f SelectorFilter) Matches(rc ResourceCoordinate, context ResourceCoordinate) bool

type SelectorFunction 

type SelectorFunction struct {
	Func string
	Args []interface{}
}

type SelectorPlaceholder 

type SelectorPlaceholder struct {
	// MatchedCoordinates is the set of matches nodes once we've resolved the placeholder
	MatchedCoordinates []ResourceCoordinate
	// Functions is the list of dependency / consumer function calls
	Functions []string
	// Args is the 1:1 map of args to each function call
	Args []string
	// Output is the output key traversal to pull out of the target resources
	Output []string
}

func (SelectorPlaceholder) Type 

func (e SelectorPlaceholder) Type() PlaceholderType

type TfVarPlaceholder 

type TfVarPlaceholder struct {
	Key string
}

func (TfVarPlaceholder) Type 

func (e TfVarPlaceholder) Type() PlaceholderType

Source Files

View all Source files

Directories

Path Synopsis
expressions
expressions/generated/errors
expressions/generated/lexer
expressions/generated/parser
expressions/generated/token
expressions/generated/util
expressions/types

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.