Service Dependency Resolver (Go)
Topics: graphs, topological sort, orchestration
Problem
A service mesh boots services in dependency order: a service may start only once everything it
depends on is already running. Given the dependency graph, compute a valid startup order — or
report a dependency cycle if no order exists.
func Resolve(deps map[string][]string) ([]string, error)
type CycleError struct { Nodes []string }
deps maps each service to the services it depends on. A dependency that isn't itself a key is a
leaf (no dependencies) and still appears in the output.- Every service must appear after all of its dependencies.
- The order is deterministic: when several services are ready (all their deps already emitted),
emit them in lexicographic order.
- If the graph has a cycle (including a self-dependency), return a
*CycleError whose Nodes are
the services that couldn't be ordered, sorted.
{web:[api], api:[db], db:[]} → [db, api, web]
{app:[auth,cache], auth:[db], cache:[db]} → [db, auth, cache, app]
{a:[b], b:[a]} → *CycleError{Nodes: [a, b]}
This is a topological sort; Kahn's algorithm (repeatedly emit a node with no remaining
dependencies) makes the deterministic-order and cycle-detection requirements natural.
Run
go test -v ./challenges/dependency-resolver/go/
Sign in to submit your solution.