Dependency Graph: Cycle Detection at Scale (advanced)

Why GantryCD detects cross-stack circular dependencies with an in-process strongly-connected-component (SCC) pass over a Postgres edge table, and not with a graph database or in-database recursion. This is an advanced implementation note: it assumes you know the dependency graph feature and want the theory and the measurements behind the engineering choice.

TL;DR. Cross-stack cycle detection is an SCC problem. SCC is a single O(V+E) pass that finds cycles of any length and is bounded by edges (memory), never by depth. The two alternatives we measured — a graph database’s variable-length closed-walk and a Postgres WITH RECURSIVE closed-walk — both enumerate cycles, which explodes combinatorially on tangled graphs and forces a depth cap that silently misses longer cycles. For our workload (configuration-bounded edges, shallow neighborhood views, 1–2-hop trigger lookups) the dedicated graph engine earned nothing it couldn’t already do in Go over Postgres, at the cost of a whole stateful HA service. So we retired it.

1. The problem

A stack can declare gantrycd:dependency: edges to other stacks/resources. The union of those edges per org is a directed graph. We need to answer three questions over it:

1. Cycles — which sets of stacks form a circular dependency (A → B → C → A)? Surfaced as a warning and in the org-wide Insights view.
2. Neighborhood — the bounded subgraph around one stack, for the Dependencies view (depth ≈ 4).
3. Triggers — 1–2-hop inbound/outbound lookups on the deployment path (who depends on me; what does each dependent wait on).

Only the first is algorithmically interesting. The other two are bounded local traversals that any store does well. Cycle detection is the whole question.

2. Theory: decomposition vs enumeration

There are two families of cycle algorithm, and they have fundamentally different complexity.

Enumeration (closed-walk) — what graph DBs and recursive CTEs do

A closed-walk search asks “starting from node n, walk forward up to D hops; report every path that returns to n.” Cypher’s MATCH p=(n)-[:DEP*1..D]->(n) and a Postgres WITH RECURSIVE that extends paths are both this. It is path enumeration, and the number of paths is combinatorial in the graph’s density: a clique of k nodes has on the order of k! distinct cycles. The work is O(paths), which is exponential in the worst case, so every real implementation must bound it two ways:

• a depth cap D (you cannot afford unbounded paths), and
• a result/time cap (you cannot afford to stream them all).

Both caps are lossy:

• A depth cap D cannot see a cycle longer than D. With D = 25, a 50-stack loop is reported as “no cycle” — a silent false negative.
• On a dense graph the search times out before reaching even small D, so the engine returns a partial or empty answer (the previous FalkorDB implementation backed off 50 → 25 → 12 → 6 → 3 → 1 on timeout, returning whatever depth survived).

The crucial point: this is a property of the algorithm, not the engine. A graph database runs the same enumeration; it just runs it server-side. It does not make the combinatorics go away.

Decomposition (SCC / Tarjan) — what we do

Endpoints are first collapsed onto their owning stack — a cycle is a stack-level fact, and the hop that closes one runs inside a stack where there is no edge to follow. A directed graph then contains a circular dependency exactly where it has a strongly-connected component (SCC) of more than one node; a single stack is never one, since it cannot deadlock against itself. Tarjan’s algorithm finds every SCC in a single O(V+E) depth-first pass, and each component is reported once as the set of stacks it entangles — the right granularity for alerting (“these N stacks form a cycle”), and deliberately not a path, which at stack granularity could omit members that are equally circular. Implementation: pkg/domain/dependency_cycles.go (CyclesFromStackPairs).

Decomposition has the properties enumeration lacks:

• No depth parameter. SCC finds cycles of length 2, 50, or 5000 at the same cost. There is no cap to misconfigure and no length it silently misses.
• Linear, not combinatorial. A dense tangle is the easy case for SCC (it’s one component) and the worst case for enumeration.
• Bounded by edges, not paths. Cost and memory scale with O(V+E) — the size of the graph — independent of how many cycles it contains.

The cost SCC does pay: it needs the whole (org) edge set in memory at once. That is the only axis it scales on, and §5 is about bounding it.

3. Empirics

All numbers below were measured locally with every component capped at 2 GiB / 2 CPU (a modest pod), fresh databases and freshly generated data per run (no cache pollution). Three candidates:

• A — FalkorDB closed-walk (MATCH p=(n)-[:DEPENDS_ON*1..D]->(n)), the old per-stack detector.
• B — Postgres WITH RECURSIVE closed-walk (recursion in the database).
• C — Postgres flat SELECT of edges + Tarjan SCC in Go (CyclesFromStackPairs).

3a. Density: a tangle breaks enumeration; SCC shrugs

One dense cluster (a clique = a single SCC with a combinatorial number of cycles):

A 50-stack tangle — 2 450 edges, trivially small — times out both closed-walk engines, while SCC answers in 0 ms. This is the headline result and it is purely structural: more RAM/CPU does not help enumeration here.

3b. Depth: the closed-walk cap is a correctness hole; SCC has no cap

Same graph, sweeping the closed-walk depth on a tiny 20-stack clique:

Both die between depth 4 and 6 on a tangled graph. And a depth cap is lossy even when it completes: 2 000 independent 50-stack loops, closed-walk capped at depth 25, returns 0 cycles (the loops are length 50) — while SCC finds all 2 000 in 69 ms. Meanwhile SCC is depth-independent: at a fixed ~900 k edges, cycle lengths 9 / 50 / 200 all cost 1.19 / 1.14 / 1.15 s (~700 MB), flat.

3c. Scale matrix (the realistic shape)

N independent loops at a given level (cycle length), all components 2 GiB / 2 CPU. Cycle latency is independent of the resource-index size (search scale) — it tracks edges only:

Two things stand out. At the realistic edge counts (≤ 2 000 — up to a hundred 20-stack cycles) everything is trivial and SCC’s working set is tens of MB. At the pathological 500 k-edge stress (10 000 distinct 50-stack loops — no real org) SCC is the only approach that stays usable: 0.41 s and 241 MB, versus a Postgres recursion timeout and FalkorDB at 3–12 s. No component OOMs at 2 GiB anywhere in the matrix. (The Go SCC working set only reaches ~4.6 GB around ~9 million edges — ~18× past the most extreme cell here and unreachable for declared dependencies.)

3d. The neighborhood view is a non-issue

For the bounded per-stack view, a seeded, index-driven Postgres recursive CTE serves a neighborhood-only query and stays flat at scale: 900 k edges → 7 ms (vs FalkorDB 12 ms); 9 M edges → 3 ms. The implementation does not use a recursive CTE, but it no longer reads the org’s edges either. The per-stack view takes the reduced pair set (OrgStackPairs, §5) — the org’s shape, which is all both the BFS and the cycle SCC consume — and then reads resource-level edges only for the stacks that BFS reached (EdgesAmongStacks). Deriving the neighborhood from a whole-org edge read was what made every stack in an over-budget org render as a lone box.

That second read carries one array predicate, dependent_stack_id = ANY($2), on the primary key’s (org_id, dependent_stack_id) prefix; the dependency endpoint is checked in Go against the same in-memory set. That is a hard requirement, not a preference. An edge is stored under its dependent’s stack, so scanning owners already returns every edge with both endpoints in the set — and adding the second endpoint as a second = ANY on an adjacent index column is a production trap: pgx runs statements through the prepared-statement cache, so after five executions on a pooled connection Postgres switches to the generic plan, which cannot see either array and therefore seeks once per value of the leading array while re-applying the other inside each range. Measured on 1,500,000 edges with a 1,000-stack neighborhood, executions 5→8 on one connection:

At the size a real page asks for — a 17-stack neighborhood in that same org — the custom and generic plans agree and both cost 8,648 buffers / 2-4 ms. Buffers track how many edges the neighborhood’s stacks own, not how long the array is; array length costs planning instead, non-linearly (a 50,000-id array plans in ~102 ms).

3e. What the graph engine actually costs

• No SCC primitive. The deployed FalkorDB (v4.18.8) exposes WCC (weakly- connected components — ignores edge direction, useless for cycles), BFS, pageRank, … but no SCC. To get SCC you pull the edges out and run it in Go regardless — exactly approach C.
• Slowest ingest. Loading 900 k edges took 12.9 s (MERGE-per-edge) vs Postgres COPY at 0.6 s.
• ~1 150 lines of plumbing plus a stateful HA service (Sentinel, persistence, maxmemory, a lazy connector with two upstream-bug workarounds).

4. The decision and the resulting structure

For this workload the dedicated graph engine was worse at the one hard problem (complex cycles — it has no SCC and its closed-walk explodes) and merely tied on the easy ones (neighborhood, 1–2-hop triggers), while costing an extra HA datastore. So:

• Edges live in Postgres — a single dependency_edges table in the gantrycd_explore database (derived, recreatable, off the critical primary; the natural home, since the resource index already lives there). One row per directed edge, owned by the dependent’s stack, org-scoped.
• Cycles → Tarjan SCC in Go (domain.CyclesFromStackPairs) over stack pairs — read reduced (OrgStackPairs) by the per-stack cycle warning / trigger demotion (GetStackCycle) and the topology, and collapsed from the raw edges the Dependencies view and Insights already load (Insights falls back to the pair read only when its edge read is over budget). One algorithm, and rows a stack could not refresh are read like any other — a stale stack fails closed on its own edges, not on everyone who can reach it.
• Neighborhood → an in-memory BFS over the (budget-capped) raw edge read — that view needs the resource edges regardless.
• Triggers → one targeted 1-hop query (InboundCrossStackEdges), indexed on (org_id, dependency_stack_id, dependent_stack_id) and bounded to whole child edge sets (10,000 per child, 50,000 total). Over-budget children become manual rows rather than disappearing or resolving from a prefix.
• No Redis cache. The Postgres reads are fast enough that the old read-through cache (and its invalidation) is deleted — fewer moving parts.

What was removed: the FalkorDB connector + Sentinel probing, the Cypher repository, the depth-backoff machinery, the Redis dependency-graph cache, the GANTRYCD_DEPGRAPH_URL config, the FalkorDB metrics, and the falkordb-go dependency — about 1 150 lines and one stateful service. There is no backwards compatibility or migration: the graph is recreatable from runs, so the rebuild sweep repopulates the new table from scratch.

5. Scale & OOM: bound by edges, never by depth

The one cost SCC pays is loading the org’s edges into the backend. Two facts make this safe, and one rule makes it safe by construction:

1. Declared edges are coupling-bounded; inferred edges are capped. Declared edges come from explicit gantrycd:dependency: comments, deduplicated on ingest, so they track how much cross-stack coupling someone configured — realistically hundreds to low-thousands per org, whatever the fleet size. Inferred edges (see dependency_graph.md) come from a stack’s cross-stack DATA sources: one edge per (data row, owner) match. That follows how many objects a stack reads from elsewhere rather than how many it manages, which is usually the same shape — but it is a product of two inventory-derived numbers, not a count of anything a human wrote, so it is not bounded by construction the way a comment count is. maxInferredEdgesPerStack bounds it per reindex instead, sized so that no realistic number of stacks at the cap can put an org over maxOrgEdges (where cycle and orphan detection stop running entirely). A 100 M-resource org still has a small edge graph, but it is the cap that guarantees it, not the shape of the data.

2. Cycle detection is not a hot search. It runs in the org diagnostics sweep, behind the per-stack warning, in the topology view, and — the one on a real latency path — in trigger demotion on every qualifying deployment. That last one is why it reads the reduced stack-pair projection rather than the full edge set. Resource search is paginated; the dependency views read the org’s edges only up to the budget below.

3. The rule: never load an unbounded graph into a serving pod. Both reads are LIMIT-capped, so the load itself — not just the SCC compute — is bounded:

   • OrgStackPairs (cycle detection and topology, which need exactly the same thing) returns the graph reduced to distinct cross-stack pairs, capped at maxOrgStackPairs.

     Be precise about what that cap does: it bounds backend memory. It is not a ceiling on database work. With the covering index the plan is Limit → GroupAggregate → Index Only Scan, so once the budget is established the scan stops rather than walking the remaining distinct prefixes — but the work to reach that point is data-dependent, since each prefix costs however many raw rows carry it. A duplicate-heavy org under budget scans everything: a million edges reducing to one pair returns one row and reads the million. Measured, that scan is ~144 ms for 1 M edges reducing to 2,000 pairs — and only because the index carries discovered as an INCLUDE payload, without which the provenance aggregate visits the heap per row and the same read costs ~140x the buffers. A normal org against a many-org table stays well under a millisecond, which is why this is accepted rather than engineered around. If a real number ever demands a scan bound, the answer is a stack-pair projection maintained transactionally alongside dependency_edges — a second derived store, and not worth its sync cost until something measures slow.

   • EdgesAmongStacks (the neighborhood view, capped at maxNeighborhoodEdges) and OrgEdges (the diagnostics sweep, capped at maxOrgEdges) still need resource granularity — rows to render, and orphan endpoints to check. Both numbers are 200,000 and they are deliberately separate constants: only the sweep reads the org, while the view asks for the edges among the stacks it draws, so an org many times larger than either still renders each of its pages. EdgesAmongStacks’s budget is spent on the OWNER-SIDE scan, which is the work it does, not on the rows that survive the endpoint check.

   A truncated read degrades gracefully rather than computing from an arbitrary subset: the per-stack graph serves the central stack only, topology serves groups without connections, and the diagnostics sweep drops only the check whose read was refused. Cycles and orphans normally come out of the SAME OrgEdges snapshot; the reduced pair read is the fallback the sweep takes only when that edge read is over budget, so an org past maxOrgEdges loses orphans and keeps cycles, and loses cycles only if it is past maxOrgStackPairs too. The per-stack view is unaffected by the org’s total: it degrades only if the ORG’S SHAPE is past maxOrgStackPairs, or that one neighborhood’s own edges are past maxNeighborhoodEdges. (At realistic and even pathological-but-real sizes neither budget is hit; they exist so a degenerate org cannot take a pod down.)

Contrast the two failure modes: a depth cap (closed-walk) is a correctness limit you cannot raise on tangled graphs and which silently drops long cycles; an edge budget (SCC) is a memory limit you degrade gracefully and which never lies about the cycles it does report. The edge budget is the better thing to operate.

6. When this decision would flip

Keep this design unless one of these becomes true:

• Graph analytics join the roadmap — pageRank / centrality / deep reachability / shortest-path at scale are genuine graph-engine workloads that Postgres + Go would not serve well. (Cycle detection is not one of them.)
• Edges stop being coupling-bounded — identity inference derives one edge per cross-stack data source, which still tracks coupling rather than inventory in practice, and is capped per reindex where it does not. A rule that derived an edge per intra-stack reference at fleet scale would be a different thing entirely — pushing per-org edge counts past ~10 M, and you want the computation off the app tier. Then adopt an engine with a server-side SCC primitive (today’s FalkorDB has none); do not return to a closed-walk.

Neither is on the roadmap, so YAGNI points here.

See also

• Dependency Graph — the feature, the data model, the reconcile flow.
• Datastores & Connection Pooling — the gantrycd_explore database.
• pkg/domain/dependency_cycles.go — the SCC implementation (CyclesFromStackPairs).