The recovery dependency graph · Backup & DR

Service tiers told you which systems matter most and how long each may be down, and the natural next move is to turn that ranked list into a recovery runbook. It does not convert. A tier is a statement about consequence — what an hour of this being unavailable costs. Recovery order is a statement about possibility — what can be brought to a working state given what is already running. The two lists disagree constantly, and the disagreement is expensive in exactly one direction: a Tier 1 service you attempt first and cannot start consumes the one resource an incident never returns.

Tiers rank consequence, the graph constrains sequence

Picture the disagreement concretely. The payments API is Tier 1, so it is attempted first, and it fails its readiness check because it cannot reach its database. The database will not open its data directory, because the volume is not mounted. The storage client cannot authenticate to the backend, because the certificate it presents came from an internal CA that is not running. Twenty minutes are gone, three services are crash-looping, and nothing has been recovered — not because the team was slow, but because the order came from the wrong list.

The graph converts a priority list into a schedule, and answers two questions a tier list cannot. The first is what must precede what — the difference between a plan that executes and a plan that thrashes. The second is what may proceed at the same time: any two nodes whose prerequisites are already satisfied can be worked by separate people. Once parallelism is allowed, elapsed recovery stops being the sum of the work and becomes the longest chain through it.

Recovery order is therefore not a matter of taste. Two engineers can disagree about which service matters most; they cannot disagree about whether a database opens without its volume. One list is negotiated, the other is architecture, and only the second can be run.

Nodes are things that start, edges are “cannot start without”

A node is anything that must be brought to a working state and can fail on its own. Services are the easy part, and most graphs are wrong because they contain only services. The omissions are the infrastructure primitives: routing and VLANs, DHCP, time synchronisation, the resolvers, the storage backend, the identity provider, the secret manager, the internal CA, the container or package registry, the configuration management controller, and the backup repository along with whatever credential reaches it.

The edges come from one question, asked once per node: if this were the only thing in the estate that were running, would it reach a healthy state, and if not, what is missing? Whatever the answer names is a prerequisite, and the edge points from the prerequisite to the thing that needs it. Three classes of edge are routinely missed.

First, edges that exist only at start-up. A service that reads its database password from the secret manager once at boot and caches it for the life of the process has a total dependency that is invisible in steady state and absolute during recovery.

Second, edges to things nobody in the room owns: time synchronisation, because certificate validation and token expiry are wall-clock sensitive; an upstream resolver; a licence server; the VPN an operator needs to reach a console. Documentation counts too — a wiki that authenticates against the identity provider you are recovering is a node inside your own graph.

Third, human edges: someone must approve the failover, someone must retrieve a sealed envelope, someone must be awake. A step that waits on a person is an edge with a latency, and omitting it is how a ninety-minute plan takes four hours.

Memory is a poor source of edges, and the estate will answer better than a meeting will. Three sources are worth working through in order. The unit files state part of it outright: Requires=, Wants= and After= on a service are its author’s recorded opinion about what that service needs and when. The configuration is the second source — every hostname, URL, socket and path in a service’s configuration that leaves the machine is a candidate edge, and reading a config tree for them turns up dependencies nobody remembers introducing. The third is the decisive one: a cold start on an isolated host, where the node is brought up with nothing else reachable and you read what it tries to open before it gives up. The first two produce a draft. Only the third separates the dependencies a service declares from the ones it actually has, and the gap between those two sets is where recovery plans fail.

Write the result down as pairs rather than prose, because a list of pairs can be sorted, diffed and reviewed:

GRAPH=recovery-graph.txt
cat > "$GRAPH" <<'EOF'
network   identity
network   storage
identity  secrets
secrets   pki
pki       secrets
storage   database
secrets   database
database  application
EOF
tsort "$GRAPH"

Read-only / Safetsort over the edge file — the loop reported, not discovered at 03:00— ILLUSTRATIVE output, not drawn from this course's captured evidence set. Reproduce it by running the block above; the exact wording of the diagnostic varies between coreutils implementations.

$ tsort "$GRAPH"

network
storage
identity
tsort: recovery-graph.txt: input contains a loop:
tsort: pki
tsort: secrets
pki
secrets
database
application

>>> exit code: 1

Illustrative output

Two things in that output matter, and they are easy to get backwards. The ordering on standard output is not a plan: an ordering is still printed when the input is cyclic, so a script that consumes standard output and ignores everything else will cheerfully execute a sequence the graph does not support. The signal is the diagnostic and the non-zero exit, and the pair it names — pki and secrets — is the thing to go and fix. Run this over the checked-in edge file in CI, and a change that closes a loop fails a review instead of surfacing on the night the estate is down.

The canonical layering is a hypothesis, not an answer

Most estates, drawn honestly, come out roughly like this: the network first, because nothing reaches anything without it; then identity, secrets and PKI, because almost everything else authenticates; then storage, because stateful services need their volumes; then databases; then applications; then ingress and the DNS records pointing at it, because publishing an endpoint that is not ready is worse than publishing none; and observability near the end.

Every one of those placements is contingent. An identity provider that keeps its sessions in the applications’ database cluster has moved the database below identity. A storage backend that authenticates clients with internal-CA certificates has moved PKI below storage. A network fabric whose controller runs as a workload on the platform it configures has moved the platform below the network. And observability-last is defensible right up to the moment you notice that observability is how you intend to prove each preceding step succeeded, at which point it belongs earlier and in a form independent of what it watches. The layering is a first guess to argue with; copied unexamined, it documents somebody else’s estate.

flowchart TD
  NET[Network, routing, DHCP, NTP] --> IDP[Identity provider]
  NET --> STO[Storage backend]
  IDP --> SEC[Secret manager]
  SEC --> CA[Internal CA]
  CA --> SEC
  STO --> DB[Primary database]
  SEC --> DB
  DB --> APP[Application tier]
  CA --> ING[Ingress and TLS termination]
  APP --> ING
  ING --> DNS[Public DNS records]
  DB --> MON[Monitoring and alerting]
  classDef cycle fill:#b3261e,stroke:#601410,color:#ffffff,stroke-width:2px
  class SEC,CA cycle
  linkStyle 3 stroke:#b3261e,stroke-width:3px
  linkStyle 4 stroke:#b3261e,stroke-width:3px

Read every arrow as “must be working before”. The diagram sorts cleanly except for the two red nodes, which point at each other.

Topological sort, the critical path, and the edge systemd splits in two

A recovery order is a topological order of a directed graph: a listing in which every node appears after all of its prerequisites. The construction is mechanical. Take every node with no unsatisfied prerequisite, emit it, delete its outgoing edges, repeat. If the graph empties, the order is valid. If nodes remain and none is ready, those nodes contain a cycle — detection falls out of the same pass. GNU coreutils ships tsort, which reads whitespace-separated pairs and writes a total order consistent with the partial order they describe; when the input contains a loop it names the members of that loop on standard error and exits non-zero. That is the value of pairs: a text file of edges is a runnable check that finds a cycle in a second rather than during an outage.

The order is almost never unique, and the alternatives are not equivalent: every node whose prerequisites are satisfied is eligible at the same moment, so the graph is a sequencing document and a parallelism document at once. The floor on elapsed recovery is its longest path — the critical path — and shortening that is architecture, not staffing.

That floor is worth computing rather than sensing, and the arithmetic is small enough to do on paper. Take the graph above with its cycle already broken, and attach durations from a rehearsal — these belong to one estate and one exercise, never to a product: network 10 minutes, identity 15, the secret manager 10, the internal CA 5, storage 20, the database restore 90, the application tier 10, ingress and DNS 15. The work totals 175 minutes. The longest chain is network → identity → secrets → database → application → ingress, at 150, and 150 is therefore the floor no amount of staffing goes below. Notice which branch it runs through. Storage reaches the database in 30 minutes against identity’s 35, so the storage branch carries five minutes of slack and no more: a storage recovery that overruns by six does not merely delay itself, it moves the critical path onto storage and lengthens the whole recovery. Slack is the quantity worth recording next to each branch, because it is where an estimate that was comfortable last quarter quietly stops being comfortable.

“Cannot start without” is also two relations rather than one. systemd.unit(5) keeps them apart: Requires= declares that a unit needs another to be active, After= declares that a unit must be started later than another, and the manual is explicit that the two settings are independent. A unit that requires another without also ordering itself after it starts at the same time as its dependency. Recovery graphs carry the same two edges — “will not function without” and “must not be started before” — and the second is the one people forget, because in a healthy estate it never binds.

Cycles are common, and they are found at 03:00

A cycle is a set of nodes each of which is downstream of the others. No topological order exists — not a difficulty to be overcome by trying harder, but a proof that the plan as written cannot be executed. Three turn up again and again.

The secret manager and the CA. The secret manager serves its API over TLS with a certificate issued by the internal CA, and the CA’s signing key is sealed in the secret manager. Neither can start first, and each one’s start-up log blames the other.

The monitoring and the thing it monitors. “Restore the primary database” is complete only when someone confirms the database is healthy, and that confirmation is a dashboard whose credentials, metric storage or own state sit on the platform being recovered. The gate depends on the node it gates.

The backup repository and the estate it protects. The key that reads the repository lives in the secret manager, and the secret manager is restored from the repository. Or, more quietly: the repository is addressed by a DNS name served from inside the estate, so recovery cannot find its own backups.

These are dangerous because they are invisible in production: every member is already running, and the edges fire only at start-up. They are also created by ordinary good work — moving a hard-coded key into a secret manager, or backing the CA with an HSM that authenticates through the identity provider.

Breaking a cycle needs a bootstrap path, and that path is an artefact

Because a cycle admits no order, breaking it means removing an edge, and an edge is removed by supplying what it demanded from outside the graph. Four shapes do this, and they are not interchangeable.

Out-of-band material. A sealed static credential, unseal shares, an offline copy of the CA root — on media no member of the cycle touches, split across named people, with a written retrieval procedure. It is honest only if the material’s location, custody and expiry are documented as carefully as the procedure that uses it.

A degraded start. The node comes up reduced — a temporary self-signed certificate, or authentication relaxed on a loopback listener — just long enough to issue the real material, then restarts properly. That state must be time-boxed and its removal a numbered step, because a bootstrap certificate still in production a month later has become the architecture.

A pinned local copy. The configuration, images or packages a node needs, cached on its own disk, so it does not need the registry that needs it. It decays silently.

Cutting the edge for good. Keep the CA root offline so it was never in the cycle; hold the repository credential in a different trust domain from the estate it protects. This is the only shape that removes the problem rather than managing it.

A bootstrap path is real only if it is written down, stored where it survives the disaster it is for — not in the wiki inside the cycle — and has actually been performed. The graph deserves the same treatment, reviewed against a question narrow enough to get asked: did this change add an edge, and does it close a loop?

Production discipline

Derive the recovery order from your own graph, never inherit it. The network-identity-storage-database-application layering is a first guess to argue with; the order you execute comes from asking every node what it cannot start without in the estate you run.
Write the graph as pairs of nodes, not as narrative. A file of edges can be topologically sorted, diffed in review and checked in CI. A paragraph describing the order can only be re-read, and it cannot tell you it contains a loop.
Put the invisible nodes in. Time synchronisation, resolvers, the registry, the operator’s access path, the runbook system and every step that waits on a human are nodes with edges; a graph of services alone stalls on the first thing omitted.
Name every cycle and give each one a bootstrap path with an owner. A cycle is not a risk to be noted, it is a proof that the plan cannot run, and the material satisfying the broken edge must live outside the failure domain the recovery is for.
Prove the graph on an exercise and re-derive it on architectural change. The evidence that an order is correct is a recovery performed in that order, bootstrap steps included; the trigger to redraw is any change that could add an edge.

Cross-course references

Secrets, PKI & Certificate Management for Infrastructure Engineers — Part XVIII (Incidents and Recovery) covers recovering a secret management platform and an internal CA, the node pair forming the cycle highlighted above; its unseal and root-key custody material is what a bootstrap path for that cycle is made of.
Kubernetes for Production Sysadmins — Part XCIX (Complete Cluster Loss) is this lesson’s graph instantiated on one platform, where the ordering of etcd, the control plane, the CNI and the image registry must be derived, not assumed.
Observability for Production Sysadmins — Part XCII (Disaster Recovery) sequences the recovery of the monitoring stack itself, the other half of the validation cycle above: if monitoring is how you confirm each step, it cannot sit downstream of the steps it confirms.