Feature idea: infer VM/service boot order from a dependency graph via Datalog

[justinjoy]

Summary

It would be great to have a first-class capability (example + small helper) for inferring the startup/boot order of a set of VMs (or services) from a declared dependency graph, using wirelog's Datalog engine as the reasoning core.

Motivation

Hypervisors in the KVM/libvirt world have no native notion of inter-VM startup ordering. libvirt's autostart is a per-domain boolean; on host boot the autostart domains are launched with no guaranteed or configurable order, and there is no XML/API primitive for "domain A depends on domain B." Management UIs like Cockpit only surface that same per-VM autostart toggle, so they can't express ordering either. The standard workaround is hand-written systemd units or shell scripts with hard-coded virsh start sequences and sleep delays — brittle, and re-derived by hand every time the topology changes.

This is fundamentally a dependency-resolution / topological-ordering problem over a graph, which is exactly wirelog's wheelhouse. The transitive-closure pattern from the README and examples/02-graph-reachability is 90% of the way there; adding stratified negation (to find roots) and max(...) aggregation (to assign levels) yields boot levels directly.

Sketch

Facts are extracted from the environment (a gateway/router that others route through, shared disks, explicit service dependencies), each becoming a depends_on/2 edge:

.decl depends_on(vm: symbol, dep: symbol)     -- vm needs dep up first
.decl needs(vm: symbol, dep: symbol)           -- transitive
.decl has_dep(vm: symbol)
.decl root(vm: symbol)
.decl level(vm: symbol, n: int64)

-- transitive closure of dependencies (README's path/edge pattern)
needs(V, D)  :- depends_on(V, D).
needs(V, D2) :- needs(V, D1), depends_on(D1, D2).

-- roots start first (stratified negation)
has_dep(V)   :- depends_on(V, _).
root(V)      :- vm(V), !has_dep(V).

-- boot level = 1 + max level of anything it depends on (aggregation in head)
level(V, 0)  :- root(V).
level(V, max(N + 1)) :- depends_on(V, D), level(D, N).

level(vm, n) then partitions the VMs into ordered start groups (level 0 first, then 1, …); a cycle shows up as VMs that never receive a finite level — i.e. the reasoner also detects impossible/circular dependency configurations for free.

Why wirelog specifically

• Incremental / delta evaluation + retraction (examples/08-delta-queries, 09-retraction-basics, 10-recursive-under-update): add or remove a VM, or change one dependency edge, and the boot ordering is recomputed incrementally rather than from scratch — a natural fit for a live orchestrator reacting to topology changes.
• Cycle / conflict surfacing: circular dependencies fall out of the same evaluation instead of needing a separate check.
• Embeddable, no-runtime C11: the wirelog_easy facade makes it realistic to embed this directly inside an orchestration daemon or a systemd-generator that emits ordered units.

What could live in the repo

• A worked examples/NN-boot-order/ (facts CSV + .dl + expected output) generalizing graph-reachability into topological levels — useful well beyond VMs (build targets, service meshes, package install order, job schedulers).
• Optionally, a tiny reference recipe showing the extracted facts → wirelog → ordered start groups pipeline.

I ran into this concretely while orchestrating a libvirt host (a gateway/router VM that a reverse-proxy and an LDAP VM both depend on), and it struck me that wirelog is a much cleaner "brain" for this than bespoke scripts. Curious whether the maintainers see boot/dependency-order inference as a good showcase for the incremental engine.