How do you make a monorepo's topological build order deterministic across machines, and what does it cost?
answer
- the graph allows many valid orders
- who decides when two are ready?
- look at the container iteration order
- tie-break the ready set canonically
- a log factor on pushes and pops
basics
~20 sA dependency graph admits many valid orders, so pin the choice: hold the ready set in a min-heap keyed on a canonical module identifier, and sort adjacency lists. Cost is a log factor on node pushes and pops.
solid answer
~50 sNondeterminism here is not randomness, it is unpinned freedom. Whenever two or more modules are simultaneously ready — all their dependencies built — the algorithm may emit either, and which one it picks falls out of incidental things: the iteration order of whatever set holds the nodes, or the order edges were parsed. Make the choice canonical instead. Replace the plain ready queue with a min-heap keyed on a stable identifier such as the module path, and sort each adjacency list once when the graph is built. The order then depends only on the graph and the key, not on the machine. Cost is an extra O(log V) factor on the V pushes and pops — invisible next to compilation. What you buy is diffable build logs, stable cache keys, and reproducible bisects. What you do not buy is identical artifacts; that requires hermetic, content-addressed tasks.
go deeper
Know that a dependency graph normally has many valid orders, so two runs can legitimately differ. Be able to name the moment the choice happens: when more than one module has all its dependencies already built.
Explain the mechanism of the fix — a ready set ordered by a stable key plus sorted adjacency lists — and state the cost change from O(V + E) to an added log factor on node insertions and removals.
Diagnose the sources of drift in a real pipeline (container iteration, filesystem walk order, worker completion) and argue what determinism buys operationally: diffable logs, stable cache keys, reproducible bisects, and what it does not buy.
Decide whether the build order is a contract or an implementation detail, and make the whole organisation consistent with that call. Weigh pinning the plan against investing in hermetic, content-addressed tasks, which removes the class of order-dependent bugs rather than hiding it.
## Where the nondeterminism comes from A build graph with V modules typically has an enormous number of valid topological orders — every pair of modules with no dependency path between them can appear in either relative position. Any correct algorithm is free to return any of them, and "free" in practice means the answer is decided by details nobody chose deliberately: - **The ready set's removal discipline.** A queue, a stack, or an unordered container will each hand back a different ready node. - **Container iteration order.** If nodes or edges live in a hash-based set, the traversal order can differ between processes, between runs, or between machines depending on capacity and insertion history. - **Input order.** Modules discovered by walking a directory tree arrive in whatever order the filesystem reports. - **Completion order under parallelism.** When workers report back, whichever finishes first releases its dependents first. None of these is a bug on its own. Together they mean two runs on the same commit produce different — equally correct — orders. ## Pinning it The fix has two halves and both are needed: 1. **Canonicalise the ready set.** Keep ready modules in a min-heap ordered by a stable key: the module path, or a content hash if paths can move. When several modules are ready, the smallest key always goes next. 2. **Canonicalise the graph.** Sort each adjacency list, and iterate the node set in key order when seeding. Otherwise you have merely moved the nondeterminism from the ready set into the order edges are relaxed, which can still change which ready nodes exist at the same moment. With both, the emitted sequence is a pure function of (graph, key function). Two machines with the same commit produce byte-identical order. ## The cost, stated precisely The plain version is O(V + E) with a constant-time ready structure. Swapping in a binary heap adds a logarithmic factor to the V insertions and V removals — the edge relaxation work is untouched — so the total becomes O(V log V + E). For a graph of a few thousand modules that is microseconds of ordering work in front of minutes of compilation. Calling this "a log factor slower" is technically true and practically meaningless; the honest framing is that ordering cost is not on the critical path of a build at all. The real cost is elsewhere: a canonical serial order can *conflict with throughput*. If you insist that work start in canonical order while running many workers, you constrain the scheduler for no benefit — the workers should take whatever is ready. The resolution is to keep the canonical order as the **reporting and cache-key** artifact while letting the scheduler dispatch whatever is ready. Determinism of the plan, freedom in the execution. ## What determinism actually buys - **Diffable logs.** Two runs differ only where the build differs, so a log diff is meaningful instead of noise. - **Stable cache and test-sharding keys.** Anything derived from position in the order stops drifting between runs. - **Bisectable failures.** "Passes on rerun" stops being explained away by ordering luck; an order-dependent bug becomes reproducible rather than intermittent. - **Reviewable plans.** A generated plan can be committed and diffed when a dependency graph changes. ## What it does not buy A deterministic order does **not** give you identical output artifacts. If a task embeds a timestamp, a build path, a hostname, or reads ambient state, the artifact varies no matter how fixed the order is. Reproducible artifacts come from hermetic tasks and content-addressed inputs. Conversely, if your tasks *are* hermetic and content-addressed, order-dependence largely stops mattering — which is why a senior answer usually says: fix the order because it makes operations legible, but treat any *behavioural* dependence on order as the actual defect to hunt. ## The interview shape The weak answer is "sort the output" — you cannot sort a topological order alphabetically without destroying it. The strong answer separates three things: the freedom is inherent to the problem, the tie-break is where you remove it, and determinism of the plan is a different property from reproducibility of the artifacts.
- Why not just sort the emitted order by module name at the end?Because sorting destroys the property that made it a build order: alphabetical position has nothing to do with dependencies, so a module would routinely land before something it needs. The tie-break has to happen inside the algorithm, at the moment several modules are simultaneously ready, so that dependency constraints are still enforced while ties are resolved by the key.
- Does a deterministic order guarantee identical build artifacts?No. Artifacts vary when tasks embed timestamps, absolute paths, hostnames, or read ambient environment state — the ordering is irrelevant to all of that. Reproducible artifacts come from hermetic tasks with content-addressed inputs. Determinism of the order buys legible operations: diffable logs, stable cache keys, bisectable failures. Treat them as two separate properties and fix them separately.
- You also run many builders in parallel. Does the canonical order still make sense?Keep it as the plan, not as the dispatch rule. Forcing workers to start strictly in canonical order throttles throughput for no gain. Emit the canonical order for logging, cache keys and review, and let the scheduler hand any ready module to any free worker. If a build breaks only under parallel dispatch, the defect is a missing dependency edge, not the scheduler.
saying these in an interview costs you the question
- Proposes sorting the final order alphabetically
- Calls the varying order a bug in the algorithm
- Ignores adjacency iteration order as a source
- Claims deterministic order implies identical artifacts
- Treats the log factor as a real build cost