Sequencing a Cutover Against a Dependency Graph

A dependency graph tells which components talk to which. A cutover plan needs something the graph does not directly contain: an ordering of moves such that no move leaves a caller unable to reach its callee, and no move creates a window in which two components disagree about state they share. Finding that ordering is a constrained scheduling problem, and the constraints come from three separate sources that are easy to conflate.

The three edge types that constrain order

Not every edge imposes the same constraint, and treating them uniformly produces a plan that is either impossible or needlessly serial.

A call edge from A to B says A sends requests to B. If B moves first, A must be able to reach B at its new location for the duration of the move, which requires either that B’s address be stable across the move or that A tolerate a change. If A moves first, A must reach B at B’s old location, which requires that A’s new environment can route to the old one. The direction that is cheaper depends on whether the two environments are connected during the migration, which is a property of the network, not of the graph.

A state edge from A to B says A and B share durable state. This is the strongest constraint. Both must be on the same side of the move at every instant when either is writing, or a coordination protocol must exist. There is no ordering that avoids this; the only options are to move them together or to introduce the protocol.

An identity edge from A to B says A presents credentials issued by B or validates credentials issued by A. A move that changes either side’s issuer breaks every dependent unless the trust is established on both sides first. Identity edges are unusual in that the safe order is almost always “establish the new trust, then move, then remove the old”, which is not an ordering of components at all but an overlap in time.

The graph that matters is the union of the three, with edges typed so that the plan can apply different rules. A graph that merges them loses the information needed to choose.

A valid sequence and how to compute one

Ignoring the identity edges, which are handled by a parallel trust period, the ordering constraint is: for each call edge A to B, either A moves after B or the link between the environments is available during the interval. If the link is available, the edge imposes no order at all, which is the common case when a migration uses a transit gateway or a VPN between source and destination.

Where the link is not available, the constraint reduces to a topological order of the call graph: callees before callers. Computing one is standard, and the interesting part is what the algorithm does with a cycle. A cycle in the call graph means A calls B and B calls A, which is common in real systems and impossible to order. The resolution is always one of three:

Move the cycle as a unit. The boundary becomes the strongly connected component, not the individual node. This is the correct answer when the cycle is tight, meaning the calls are frequent and stateful. It is the expensive answer, because the unit is large.

Break the cycle by introducing indirection. One of the two calls is redirected through a name or a queue that can point at either side. This converts a hard ordering constraint into a soft one and costs a new component that must itself be operated. The indirection is often a load balancer for synchronous calls and a queue for asynchronous ones.

Accept a transient window. Both sides run, the calls that fail during the window are retried, and the retries are correct because the operations are idempotent. This is the cheapest answer and the one most likely to be wrong, because idempotence is usually assumed rather than established.

Strongly connected components are computable in time linear in the number of edges, using either Tarjan’s algorithm or Kosaraju’s, and the condensation of the graph into its components is acyclic by construction. The plan should therefore be expressed over components, not over individual services, whenever the graph has cycles. A plan expressed over individual services in a cyclic graph is not a plan; it is a list of moves with an implicit assumption that the cycle will not bite.

Why the longest chain sets the schedule

A topological order gives a valid sequence, not a fast one. The duration of the whole migration is the length of the longest path through the graph, weighted by the duration of each move, because moves on independent branches can run concurrently while moves on a chain cannot.

This is the critical path, and it is worth computing because it changes what to optimise. Shortening a move that is not on the critical path does not shorten the migration. Shortening a move on the critical path does, in proportion. Plans that allocate effort evenly across components systematically fail to shorten the critical path, because most components are not on it.

The weighted critical path is computed by a single pass over the topological order: for each node, the earliest start is the maximum over its predecessors of (earliest start plus duration), and the migration’s duration is the maximum earliest start plus duration over all nodes. The pass requires the graph to be acyclic, which is why the condensation matters.

Two properties of the weights are easy to get wrong. A move’s duration includes the verification and the observation window, not just the copy. A move whose copy takes ten minutes and whose verification takes four hours has a duration of four hours and ten minutes, and treating verification as overhead outside the schedule produces a plan that is wrong by an order of magnitude. The second property is that a move that must be reverted and retried has an expected duration that includes the retry, which is a probabilistic quantity and belongs in the plan as a range rather than a point.

Batch size, parallelism, and the coordination limit

The schedule has a second constraint that the graph does not express: the number of moves that can be in flight simultaneously is bounded by the people and systems that can attend to them. Every move in flight needs an owner who can make the decision to proceed or revert, and every move that shares a dependency needs its outcome before the next one starts.

Two regimes follow. Below the coordination limit, moves run in parallel and the migration is bounded by the critical path. Above it, moves queue and the migration is bounded by the limit, and the schedule becomes the number of moves divided by the limit, times the average duration. The transition between the two regimes is where plans go wrong, because a plan computed on the critical path and executed above the limit slips by exactly the amount the model ignores.

Batching is the lever. Moving a batch of independent components as one unit reduces the number of coordination events and increases the blast radius of each. The trade is the same one that governs the boundary decision, applied at the level of the schedule rather than the level of consistency.

Ordering by reversibility rather than by dependency

A second ordering heuristic often conflicts with the topological one and is sometimes better. Move the components with the cheapest rollback first, regardless of their position in the graph, so that early failures cost little and the team learns the mechanics on low-stakes moves.

The two heuristics agree when the low-stakes components are leaves. They disagree when a leaf is a critical system with an expensive rollback, or when an internal component has a trivial rollback because it holds no state. The resolution is to use reversibility as a tiebreaker within a topological level: among the components that are ready to move at a given point, move the most reversible first.

This produces a schedule that is valid by construction and progressively lowers risk, because each move exercises the same machinery on a component whose failure is cheaper than the next one’s. It also front-loads the discovery of mechanical problems, such as a broken credential path or an unrehearsed restore, which are exactly the problems that should be found before the expensive move rather than during it.

The heuristic has a limit: a component that is ready but whose rollback is expensive should be deferred even if it is a leaf, unless deferring it blocks a large subtree. When it does block a subtree, the choice is between paying the risk now and paying it later with less schedule slack, and that is a judgement the graph cannot make.

Where the sequence must be interrupted

No ordering makes a migration safe if the intermediate states are not themselves operable. The plan must therefore check, for each prefix of the sequence, that the resulting mixed state can run. This is a stronger requirement than each individual move being valid, and it is where most sequencing errors hide.

The check is mechanical: for each step, take the set of components already moved, the set not yet moved, and enumerate the call edges that cross between the two sets. Each crossing edge must be supported by the link between the environments, and the link’s capacity must be sufficient for the traffic on all crossing edges at once. A plan that crosses many edges at one step needs a link sized for the aggregate, which is a different requirement than the sum of the individual moves’ needs, because the aggregate is concurrent.

A mixed state also has to be observable. If monitoring is being migrated as one of the components, then for the interval before it moves, the destination is running with the source’s monitoring, and for the interval after, the source is running with the destination’s. Either arrangement can leave a component unobserved at exactly the moment it is most likely to fail. Moving observability first, and keeping it able to see both sides until the last component has moved, is a sequencing constraint that does not appear in the call graph at all.

The final consideration is that the sequence must have a stopping point for each stage that is stable enough to pause. A migration paused overnight in a mixed state will be resumed by different people, and the state they find must be describable in a few sentences. A sequence whose intermediate states require a paragraph of explanation is a sequence that will be resumed incorrectly, and the cost of that is paid in the reconciliation that follows.