Migration Step Ordering with Optional Steps (Go)
Topics: backtracking, topological sort, configuration
Problem
A database migration runbook has a set of steps. Some steps depend on others (and must run
after them); some steps are alternatives — at most one of a few competing strategies should
run, and a strategy may itself pull in extra steps. Produce a valid execution order for the
required steps (plus whatever their dependencies pull in), or prove no valid order exists.
type Step struct {
Name string
DependsOn [][]string
Excludes []string
}
func Plan(steps []Step, required []string) ([]string, bool)
DependsOn is a list of groups. For each group, at least one member must be included
in the plan and scheduled before this step. A single-element group ({"x"}) is a plain "run
after x"; a multi-element group ({"x", "y"}) is a choice — either satisfies it.Excludes is symmetric: if A.Excludes contains B, then A and B can never both be in
the plan, even if B.Excludes doesn't mention A.
Plan returns an order containing every step in required plus everything DependsOn pulls in,
with every dependency scheduled before the step that needs it, and true — or nil, false if no
such order exists.
cutover depends on (strategy-a OR strategy-b)
strategy-a requires cutover (would create a cycle!)
strategy-b (no constraints)
Plan({cutover}) -> [strategy-b, cutover], true
Key concepts
- Two kinds of work items: a "include step X" obligation (check
Excludes, then queue X's
DependsOn groups) and a "satisfy this OR-group, ordered before owner" obligation. Only the
OR-group is a choice point.
- Why backtracking — two ways to hit a dead end:
- Exclusion conflict (as in the Feature Flag solver): a candidate satisfies a
DependsOn
group but its Excludes rules out a step that's also required.
- Cycle: a candidate satisfies a
DependsOn group, but itself (transitively) depends on
the step it's supposed to precede. In the example above, picking strategy-a for cutover's
requirement creates strategy-a → cutover → strategy-a — no valid order exists with
strategy-a included, so the solver must undo it and try strategy-b.
- Topological sort as the success check: once a combination of choices has been made, the
candidate plan is valid only if its dependency edges form a DAG. A cycle isn't discovered until
the whole set of edges is known, so cycle detection becomes the final check that can still
trigger backtracking at an earlier choice point.
The Step struct is provided; you implement Plan.
Run
go test -v ./challenges/migration-ordering/go/
Sign in to submit your solution.