depgraph

package module
v0.0.0-...-15d82a0 Latest Latest
Warning

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

 Go to latest Published: Mar 2, 2023 License: Apache-2.0 Imports: 4 Imported by: 5

README

Dependency Graph (depgraph)

Use-case

This package implements a dependency graph. The main use-case is to represent configuration items (network interfaces, routes, volumes, etc.) or any managed stateful objects (incl. processes, containers, files, etc.) as graph nodes, here called items, and their dependencies as directed graph edges.

For example, if there are items A and B with edge (dependency) A->B, it means that B should be created before A. Conversely, the removal of these two items should proceed in the opposite order, i.e. A should be removed first (think of the dependency as "A cannot exist without B"). Edges of this dependency graph slightly diverge from the standard definition as it is allowed for an edge to point to an item which is not present in the graph, representing a scenario of a missing dependency.

The graph can be for example used to model the intended or the current state of a managed system. Note that depgraph alone only provides a data structure to store the modeled state. However, in combination with the Reconciler, it can help to solve the challenge of state reconciliation. A management agent will typically maintain two graphs, one for the intended state, updated based on the input from a user/controller, and the other for the current state. The agent will use APIs of the managed system to learn the actual state and will update the graph accordingly. The reconciler will take both of these graphs as an input and will perform all state transitions needed to reach the intended state, updating the graph representing the current state in the process. For more information on the topic of state reconciliation, please refer to the readme file of the Reconciler.

Subgraphs

Apart from items and edges, the graph also supports a notion of subgraphs. A subgraph is a subset of graph items, including all edges that originate or point from/to any of these items (again, a slight deviation from the standard definition). Subgraph is given a name and optionally also a description (just like the top-level graph). The main use-case is to group related items and allow to select and edit them together.

Here is a visual depiction of an example graph with some subgraphs:

Subgraphs

For example, all components of a virtualized network (bridge, routes, dns server, etc.) can be grouped into one subgraph with the logical name of the network:

virtNetwork := depgraph.New(
    depgraph.InitArgs{
        Name:  virtNetworkName,
        Items: []depgraph.Item{bridge, route1, route2, dnsServer}
    })

Then, to add or replace all the components of the network in the graph, only one function call is needed:

fullStateGraph.PutSubGraph(virtNetwork)

Also, the entire content of the subgraph can be removed with just:

fullStateGraph.DelSubGraph(virtNetworkName)

Subgraphs can be also nested and thus compose a hierarchical tree structure. This is very similar to directory structure of a filesystem if you think of subgraphs as directories and items as files. Currently, subgraphs are not related to and does not affect dependencies.

Note that in terms of API, subgraph is also a graph - it implements the Graph interface. Single item can also be viewed as a subgraph - Graph.ItemAsSubGraph(item) returns a (read-only) graph handle.

API & Usage

Configuration items modeled as graph nodes (in API simply called items) should implement the Item interface. This means that for every distinct item type, there needs to be a structure with methods as required by the interface. For example, it is required to provide a name for every item instance (based on the item configuration) through the method Name() string. Two distinct items of the same type should have different names. Distinct here means that the manifestation of these items are two separate objects in the managed system. A graph-wide unique item identifier/reference is therefore a combination of the type (returned by Type() string) and the name. This is captured by the ItemRef structure. To obtain a reference for an item (which is needed for several graph methods), call Reference(Item). Another notable method defined by the Item interface is Dependencies(). It lists all the dependencies of an item and therefore determines the outgoing edges of the item.

Here is a simplified example for Items representing Linux interfaces and routes. Only Name(), Type() and Dependencies() methods are shown here. For other required methods, please see the Item interface definition.

import "github.com/lf-edge/eve/libs/depgraph"

type LinuxInterface struct {
    name string
}

func (intf LinuxInterface) Name() string {
    return intf.name
}

func (intf LinuxInterface) Type() string {
    return "Linux interface"
}

func (intf LinuxInterface) Dependencies() []depgraph.Dependency {
    // no dependencies
    return nil
}

// Other Item methods for LinuxInterface are omitted.

type LinuxRoute struct {
    via    string
    dst    string
    metric int
}

func (route LinuxRoute) Name() string {
    // Both dst and via should be included to uniquely identify the route
    // among all the routes.
    return route.dst + " via " + route.via
}

func (route LinuxRoute) Type() string {
    return "Linux route"
}

func (route LinuxRoute) Dependencies() []depgraph.Dependency {
    return []depgraph.Dependency{
        {
            Item: depgraph.RequiredItem{
                Type: "Linux interface", // can also use LinuxInterface{}.Type()
                Name: route.via, // can also use LinuxInterface{name: route.via}.Name()
            },
            Description: "Route requires outgoing interface to be configured first",
        },
    }
}

// Other Item methods for LinuxRoute are omitted.

With each item instance the graph also allows to store some state data, implementing the ItemState interface. This can be for example used to store information about the last state transition performed for the item and any errors that resulted from it. Think of Item as the configuration and ItemState as a run-time state. State data are mostly transparent to the graph with only few methods defined to help to enhance the visualization of the graph. Item state data are completely optional and can be passed as nil. They are typically omitted when the graph is used to model the intended state and provided when the currently running state is modeled.

Once all needed Item (and possibly ItemState) implementations are available, you are ready to build a dependency graph to model some kind of system state. Graph with some initial content is created using New():

import "github.com/lf-edge/eve/libs/depgraph"

// using LinuxRoute and LinuxInterface defined above

g := depgraph.New(depgraph.InitArgs{
    Name:           "MyGraph",
    Description:    "This is my example graph",
    ItemsWithState: []ItemWithState{
        {Item: LinuxInterface{name: "eth0"}, State: LinuxInterfaceState{lastOpErr: nil}},
    },
    // For items without state data you can use Items, avoiding to pass ItemState as nil
    // and therefore making the code shorter and easier to read.
    // But do not put the same Item into both Items and ItemsWithState.
    Items: []Item{
        LinuxRoute{via: "eth0", dst: "10.10.0.0/16", metric: 10},
        LinuxRoute{via: "eth0", dst: "192.168.16.0/24", metric: 10},
    }
})

Graph will automatically build edges for all items based on their dependencies. In the example above, there will be one edge from each route pointing to the eth0 interface. InitArgs can also contain the initial content of subgraphs.

A single item is manipulated using Item(), PutItem() and DelItem() methods:

import (
    "fmt"
    "github.com/lf-edge/eve/libs/depgraph"
)

// Add new Linux route (nil ItemState).
item := LinuxRoute{via: "eth0", dst: "10.20.0.0/16", metric: 100}
g.PutItem(item, nil)

// Update the item.
item.routeMetric = 50
g.PutItem(item, nil)

// Delete the item.
itemRef := Reference(item)
g.DelItem(itemRef)

// Read single graph item.
item, found := g.Item(itemRef)
if found {
    fmt.Printf("Linux interface %+v\n", item)
}

To iterate all items in the graph:

inclSubGraphs := true
iter := g.Items(inclSubGraphs)
for iter.Next() {
    item, state := iter.Item()
    fmt.Printf("Item: %+v, with state: %+v\n", item, state)
}

To iterate all edges originating from an item:

iter := g.OutgoingEdges(itemRef)
for iter.Next() {
    e := iter.Edge()
    fmt.Printf("Edge from %s to %s for dep: %+v\n",
        e.FromItem, e.ToItem, e.Dependency)
}

Lastly, sub-graphs are manipulated using SubGraph(), PutSubGraph(), DelSubGraph() and EditSubGraph() methods:

item1 := LinuxInterface{name: "eth0.1"}
item2 := LinuxInterface{name: "eth0.2"}
subG := depgraph.New(depgraph.InitArgs{
    Name:        "MySubGraph",
    Description: "This is my example sub-graph",
    Items:       []Items{item1, item2},
})

// Add new subgraph
g.PutSubGraph(subG)

// Can use the same handle to edit the subgraph...
subG.DelItem(Reference(item1))

// ... or a read-write handle can be retrieved:
readSubG := g.SubGraph("MySubGraph") // can only read nodes, edges, etc.
subG = g.EditSubGraph(readSubG) // elevate to read-write
subG.Putitem(item1, nil)

// Remove the subgraph:
g.DelSubGraph("MySubGraph")

Visualization

The graph content can be exported into DOT using DotExporter and then visualized for example using Graphviz. Subgraphs are drawn as clusters, i.e. items they contain are plotted near each other and contained within a rectangle.

Example usage (incl. Graphviz with a wrapper for Go):

// import "github.com/goccy/go-graphviz"

// Initialize DOT exporter
exporter := &DotExporter{CheckDeps: true}

// Render DOT representation of the dependency graph.
dot, err := exporter.Export(graph)
if err != nil {
    log.Fatalf("depgraph DOT rendering failed: %v", err)
}

// Use go-graphviz - a Graphviz wrapper for Go.
gvizGraph, err := graphviz.ParseBytes([]byte(dot))
if err != nil {
    log.Fatalf("failed to parse DOT: %v", err)
}
gviz := graphviz.New()
err = gviz.RenderFilename(gvizGraph, graphviz.PNG, "/path/to/graph.png")
if err != nil {
    log.Fatal(err)
}

Example of a rendered depgraph:

graph visualization example

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func DelItemFrom 

func DelItemFrom(graph Graph, item ItemRef, path SubGraphPath) bool

DelItemFrom is a helper which allows to remove item from the selected subgraph. Returns true if the path refers to an existing subgraph and the item existed and was successfully removed, false otherwise.

func PutItemInto 

func PutItemInto(graph Graph, item Item, state ItemState, path SubGraphPath) bool

PutItemInto is a helper which allows to add or move (and update) item into the selected subgraph. Returns true if the path refers to an existing subgraph and the item was successfully put, false otherwise.

Types

type Dependency 

type Dependency struct {
	// RequiredItem references item which must be already created.
	RequiredItem ItemRef
	// MustSatisfy : used if the required item must not only exist but also satisfy
	// a certain condition. For example, a network route may depend on a specific network
	// interface to exist and also to have a specific IP address assigned. MustSatisfy can
	// check for the presence of the IP address.
	// This function may get called quite often (by Reconciler) so keep it lightweight.
	MustSatisfy func(Item) bool
	// Description : optional description of the dependency.
	Description string
	// Attributes : some additional attributes that may be helpful in special cases
	// to further describe a dependency.
	Attributes DependencyAttributes
}

Dependency which is considered satisfied if RequiredItem is already created and MustSatisfy returns true for that item or is nil.

type DependencyAttributes 

type DependencyAttributes struct {
	// RecreateWhenModified : items that have this dependency should be recreated whenever
	// the required item changes (through Modify).
	RecreateWhenModified bool
	// AutoDeletedByExternal : items that have this dependency are automatically/externally
	// deleted (by other agents or by the managed system itself) whenever the required
	// *external* item is deleted. If the required item is not external (Item.External()
	// returns false), this dependency attribute should be ignored.
	AutoDeletedByExternal bool
}

DependencyAttributes : some additional attributes that may be helpful in special cases to further describe a dependency.

type DotExporter 

type DotExporter struct {
	// CheckDeps : enable this option to have the dependencies checked
	// and edges colored accordingly (black vs. red).
	CheckDeps bool
	// contains filtered or unexported fields
}

DotExporter exports dependency graph into DOT 1. It provides two methods:

  • Export(graph GraphR): export a single graph into DOT
  • ExportTransition(src, dst GraphR): export graph "src" into DOT just like with Export(), but additionally also describe what is out-of-sync and will need a state transition to match the graph "dst". For example, all items present in "dst" but missing in "src" are also included, but with a lowered saturation for node fillcolor and with a grey border.

func (*DotExporter) Export 

func (e *DotExporter) Export(graph GraphR) (dot string, err error)

Export returns DOT description of the graph content. This can be visualized with Graphviz and used for troubleshooting/presentation purposes.

func (*DotExporter) ExportTransition 

func (e *DotExporter) ExportTransition(src, dst GraphR) (dot string, err error)

ExportTransition exports graph "src" into DOT just like with Export(), but additionally also describes what is out-of-sync and will need a state transition to match the graph "dst".

type Edge 

type Edge struct {
	FromItem ItemRef
	ToItem   ItemRef
	// Dependency represented by this edge.
	Dependency Dependency
}

Edge represents a directed edge of a dependency graph.

type EdgeIterator 

type EdgeIterator interface {
	Iterator

	// Edge returns the current Edge from the iterator.
	Edge() Edge
}

EdgeIterator iterates outgoing or incoming edges of an item. The order of edges is undefined.

type Graph 

type Graph interface {
	GraphR

	// SetDescription updates description assigned to the (sub)graph.
	SetDescription(string)

	// PutItem adds or moves (and updates) item into this (sub)graph.
	// Function also adds or updates ItemState stored alongside the item.
	PutItem(item Item, state ItemState)
	// DelItem deletes an existing item from this (sub)graph.
	// Returns true if the item existed and was actually deleted.
	DelItem(ItemRef) bool

	// PutSubGraph adds a new subgraph into this graph or updates an existing
	// subgraph. This refers to a direct child of this graph, cannot add/update
	// a nested subgraphs.
	PutSubGraph(Graph)
	// DelSubGraph deletes existing subgraph. This refers to a direct child of this
	// graph, cannot delete a nested subgraph.
	// Returns true if the subgraph existed and was actually deleted.
	// It is an error to try to use a subgraph after it was deleted (can't be used
	// even as a separate graph anymore).
	DelSubGraph(name string) bool
	// EditSubGraph elevates read-only subgraph handle to read-write access.
	// Panics if the given graph is not actually a subgraph (direct or nested)
	// of this graph.
	EditSubGraph(GraphR) Graph
	// EditParentGraph returns read-write handle to a (direct) parent graph
	// of this subgraph.
	// Return nil if the graph is not a subgraph.
	EditParentGraph() Graph

	// PutPrivateData allows the user to store any data with the graph.
	// Graph does not do anything with these data.
	// Retrieve with GraphR.PrivateData().
	PutPrivateData(interface{})
}

Graph is a dependency graph. The main use-case is to represent configuration items (network interfaces, routes, volumes, etc.) or any managed stateful objects (incl. processes, containers, files, etc.) as graph nodes (here called items instead) and their dependencies as directed graph edges. For more information please see README.md.

func GetGraphRoot 

func GetGraphRoot(graph Graph) Graph

GetGraphRoot is a simple helper which returns the top-most parent graph for a given (sub)graph.

func GetSubGraph 

func GetSubGraph(graph Graph, path SubGraphPath) Graph

GetSubGraph is a simple helper which allows to obtain subgraph by a relative path (which is for example returned by GraphR.Item()).

func New 

func New(args InitArgs) Graph

New creates a new instance of the dependency graph.

type GraphIterator 

type GraphIterator interface {
	Iterator

	// SubGraph returns the current subgraph from the iterator.
	SubGraph() GraphR
}

GraphIterator iterates subgraphs of a graph. The order of subgraphs is undefined.

type GraphR 

type GraphR interface {
	// Name assigned to the (sub)graph.
	Name() string
	// Description assigned to the (sub)graph.
	Description() string

	// Item returns an item from the graph, incl. state data stored alongside it.
	// The function will look for the item also inside all the subgraphs
	// (both direct and nested). If found, it will also return a path leading
	// to the subgraph with the item.
	// To obtain reference to the subgraph, use GetSubGraph().
	Item(ItemRef) (item Item, state ItemState, path SubGraphPath, found bool)
	// Items returns an iterator for items inside this graph.
	// If inclSubGraphs is set to true, the iteration will include items
	// from subgraphs (both direct and nested).
	Items(inclSubGraphs bool) ItemIterator
	// DiffItems returns references to items that differ between this and the other
	// graph. Two respective item instances are considered different if Item.Equal(other)
	// returns false, or if their location wrt. subgraphs is different.
	// Item state data are not compared.
	// A returned reference may refer to an item present in this graph but not present
	// in the other graph and vice versa.
	// otherGraph is allowed to be nil - in that case references to all items in this
	// graph will be returned.
	// Complexity is O(V).
	DiffItems(otherGraph GraphR) []ItemRef

	// SubGraph returns a read-only handle to a (direct, not nested) subgraph.
	// Returns nil if subgraph with such name is not present.
	SubGraph(name string) GraphR
	// SubGraphs returns an iterator for (direct) subgraphs of this graph.
	SubGraphs() GraphIterator
	// SubGraph returns a read-only handle to the (direct) parent graph.
	// Return nil if the graph is not a subgraph.
	ParentGraph() GraphR
	// ItemAsSubGraph allows to view an item (that may or may not exist)
	// as a single-item subgraph.
	// This is useful if you need a common interface for a subgraph and an item.
	ItemAsSubGraph(ItemRef) GraphR

	// OutgoingEdges returns iterator for all outgoing edges of the given item,
	// as determined by item dependencies.
	// Item can be also from a subgraph (direct or nested).
	OutgoingEdges(ItemRef) EdgeIterator
	// OutgoingEdges returns iterator for all incoming edges of the given item,
	// as determined by dependencies of other items.
	// Item can be also from a subgraph (direct or nested).
	IncomingEdges(ItemRef) EdgeIterator
	// DetectCycle checks if the graph contains a cycle (which it should not,
	// dependency graph is supposed to be DAG) and the first one found is returned
	// as a list of references to items inside the cycle (with the order of the cycle).
	// Complexity is O(V+E).
	DetectCycle() []ItemRef

	// PrivateData returns whatever custom data has the user stored with the graph.
	PrivateData() interface{}
}

GraphR : Read-only access to a dependency graph.

func GetGraphRootR 

func GetGraphRootR(graph GraphR) GraphR

GetGraphRootR is a read-only variant for GetGraphRoot.

func GetSubGraphR 

func GetSubGraphR(graph GraphR, path SubGraphPath) GraphR

GetSubGraphR is a read-only variant for GetSubGraph.

type InitArgs 

type InitArgs struct {
	// Name of the graph.
	Name string
	// Description for the graph.
	Description string
	// ItemsWithState : items inside the graph with state data attached.
	ItemsWithState []ItemWithState
	// Items : items inside the graph without state data attached.
	// Use this instead of ItemsWithState to avoid passing ItemState as nil.
	// This makes the code shorter and easier to read.
	// But do not put the same Item into both Items and ItemsWithState.
	Items []Item
	// List of subgraphs directly under this graph.
	Subgraphs []InitArgs
	// PrivateData for the user of the graph to store anything.
	PrivateData interface{}
}

InitArgs : input arguments to use with the (sub)graph constructor New().

type Item 

type Item interface {
	// Name should return a unique string identifier for the item instance.
	// It is required for the name to be unique only within item instances of the
	// same type (see Type()). A globally unique item identifier is therefore
	// a combination of the item type and the item name.
	Name() string
	// Label is an optional alternative name that does not have to be unique.
	// It is only used in the graph visualization as the label for the graph node
	// that represents the item. If empty string is returned, Item.Name() is used
	// for labeling instead.
	Label() string
	// Type should return the name of the item type.
	// This is something like reflect.TypeOf(item).Name(), but potentially much more
	// human-readable.
	// For example, type could be "Linux bridge".
	Type() string
	// Equal compares this and the other item instance (of the same type and name)
	// for equivalency. For the purposes of state reconciliation (see libs/reconciler),
	// Equal determines if the current and the new intended state of an item is equal,
	// or if a state transition is needed.
	// Note that if two items are equal, their dependencies should be the same!
	Equal(Item) bool
	// External should return true for items which are not managed (created/modified/deleted)
	// by the caller/owner. This could be used for items created by other management agents
	// or to represent system notifications (e.g. interface link is up).
	// For reconciliation, the presence of external items in the graph is used only for
	// dependency purposes (e.g. create A only after another microservice created B).
	External() bool
	// String should return a human-readable description of the item instance.
	// (e.g. a network interface configuration)
	String() string
	// Dependencies returns a list of all dependencies that have to be satisfied before
	// the item can be created (i.e. dependencies in the returned list are AND-ed).
	// Should be empty for external item (see Item.External()).
	Dependencies() []Dependency
}

Item is something that can be created, modified and deleted, essentially a stateful object. This could be for example a network interface, volume instance, configuration file, etc. In this dependency graph, each item instance makes one graph node. Beware that items are stored inside the graph and their content should not change in any other way than through the Graph APIs. It is recommended to implement the Item interface with *value* receivers (or alternatively pass *copied* item values to the graph).

type ItemIterator 

type ItemIterator interface {
	Iterator

	// Item returns the current Item from the iterator.
	Item() (Item, ItemState)
}

ItemIterator iterates items of a graph. Items are ordered lexicographically first by subgraphs (in DFS order) and secondly by item references.

type ItemRef 

type ItemRef struct {
	ItemType string
	ItemName string
}

ItemRef is used to uniquely reference item inside the graph.

func Reference 

func Reference(item Item) ItemRef

Reference is a simple helper to make a reference to an item.

func (ItemRef) Compare 

func (ref ItemRef) Compare(ref2 ItemRef) int

Compare returns an integer comparing two Item references. The result will be 0 if ref==ref2, -1 if ref < ref2, and +1 if ref > ref2. This allows you to have an ordering for a list of items.

func (ItemRef) String 

func (ref ItemRef) String() string

String returns string representation of an item reference.

type ItemState 

type ItemState interface {
	// String should return a human-readable description of the item state.
	String() string
	// IsCreated should return true if the item is actually created.
	// Return false to model a scenario such as item not being created due to
	// a missing dependency, or failing to get created, etc.
	IsCreated() bool
	// WithError should return non-nil error if the last state transition
	// for this item failed. The error should describe why the item is in a failed
	// state.
	WithError() error
	// InTransition should return true if an item state transition is in progress.
	InTransition() bool
}

ItemState should store state information for an item instance. This can be used for state reconciliation purposes for example. It is used by the Reconciler (see libs/reconciler). Beware that items are stored inside the graph and their content should not change in any other way than through the Graph APIs. It is recommended to implement the ItemState interface with *value* receivers (or alternatively pass *copied* values to the graph).

type ItemWithState 

type ItemWithState struct {
	Item  Item
	State ItemState
}

ItemWithState just wraps item with its state data together under one struct. Only used with InitArgs.

type Iterator 

type Iterator interface {
	// Next advances the iterator and returns whether the next call
	// to the Item()/Edge()/... method will return a non-nil value.
	// Next should be called prior to any call to the iterator's
	// item retrieval method after the iterator has been obtained or reset.
	Next() bool

	// Len returns the number of items remaining in the iterator.
	Len() int

	// Reset returns the iterator to its start position.
	Reset()
}

Iterator : a common iterator interface. Note that it is undefined what happens if the iterated set is changed during iteration! Do not add/remove item during iteration.

type SubGraphPath 

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

SubGraphPath is a relative path from a graph to one of its subgraphs (direct or a nested one).

func NewSubGraphPath 

func NewSubGraphPath(subGraphNames ...string) SubGraphPath

NewSubGraphPath is a constructor for SubGraphPath. The path is built by listing the names of subgraphs, each being a child of the previous one, leading to a destination subgraph (the last entry).

func (SubGraphPath) Append 

func (p SubGraphPath) Append(elems ...string) SubGraphPath

Append creates a *new* path with added elements at the end.

func (SubGraphPath) Compare 

func (p SubGraphPath) Compare(p2 SubGraphPath) int

Compare returns an integer comparing two paths lexicographically. The result will be 0 if p==p2, -1 if p < p2, and +1 if p > p2. This allows you to have an ordering for a list of subgraph paths.

func (SubGraphPath) Concatenate 

func (p SubGraphPath) Concatenate(p2 SubGraphPath) SubGraphPath

Concatenate creates a *new* path by concatenating this path with another path.

func (SubGraphPath) IsPrefixOf 

func (p SubGraphPath) IsPrefixOf(p2 SubGraphPath) bool

IsPrefixOf returns true if this path is prefix of the other path.

func (SubGraphPath) Len 

func (p SubGraphPath) Len() int

Len returns the path length (the number of nested subgraphs along the way).

func (SubGraphPath) TrimPrefix 

func (p SubGraphPath) TrimPrefix(prefix SubGraphPath) SubGraphPath

TrimPrefix returns a *new* SubGraphPath which has the given prefix removed from this path.

Source Files

View all Source files

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.