Import Write Ordering

A static-repo import writes a source's nodes through the one canonical upsert verb. The order it writes them in is part of the contract, because the create pipeline refuses a node whose NodeType names nothing the mesh knows:

System.InvalidOperationException: Upsert of
  'MeshWeaver/samples/Graph/Data/FutuRe/EuropeRe/TransactionMapping/EUR-COMM_FIRE-PROP'
  failed: NodeType 'FutuRe/TransactionMapping' is not registered

The rule

A NodeType node is written before every instance that names it, and a type's Source//Test/ nodes are written before the type. A node whose type this pass cannot put in place first is a blocked create — named, reported, and NOT counted as a failure.

The incident (issue #2556)

The importer wrote nodes in whatever order the source enumerated them, five at a time. A repo shipping an instance of a type it introduces therefore had its instance refused whenever enumeration happened to put it first.

What made that permanent rather than transient is the interaction with the last-sync baseline guard. GitHubSyncService.MayAdvanceBaseline holds the baseline whenever a node failed to land — added by #2229 item C, precisely so a later pass would retry the refused instance once its type node existed. It works exactly as designed. But the retry re-ran the same pass with the same ordering, so the same instance was refused again, the baseline was held again, and the cycle repeated. #2229 item C converted a permanent silent miss into a permanent loud loop — strictly better, and still not landing the content.

Measured on memex-cloud:

Forty attempts, one node, zero progress: non-convergent, not merely slow. The write order was the defect, so more retries, a longer backoff, or a watchdog could not have helped — each would only have made the loop cheaper to ignore.

Ordering is sufficient — the refusal is not about a TypeRegistry

This is the question to settle first, because if registration lagged the write, a topological sort would only postpone the failure instead of removing it.

It does not. Despite the wording, the check in MeshExtensions' create path (step 3) is:

// 3. NodeType existence check.
if (string.IsNullOrEmpty(node.NodeType))            typeExistsObs = Observable.Return(true);
else if (hub.ServiceProvider.FindStaticNode(node.NodeType) is not null)
                                                    typeExistsObs = Observable.Return(true);
else if (persistence != null)                       typeExistsObs = persistence.Exists(node.NodeType);
else                                                typeExistsObs = Observable.Return(false);

IStaticNodeProvider ∪ IStorageAdapter.Exists(typePath) — a node at the type's path, not a compiled assembly, not a hub type registration. And the write that puts it there is commit-then-publish: WriteAndPublishCreated emits only after the storage write commits, and CreateNodeResponse.Ok is posted after that. So a completed type write is already visible to the very next node's probe. There is no registration lag left for ordering to merely delay.

🚨 The two things this deliberately does not conflate:

• the type NODE existing — synchronous with the write, and all an instance needs;
• the type being COMPILED into a live assembly — asynchronous, minutes later, and something instances never wait on.

Only the first is on the import's critical path. (A payload that degrades to an untyped JsonElement because the reading hub never loaded the assembly is a different defect with the same log line — see Node Type Compilation and ObjectAsExtensions. Ordering does not address it, and a count of is not registered lines mixes the two.)

The two edges

ImportWriteOrder.Plan builds a dependency graph over paths only — nothing casts Content, because a node read back from storage carries its content as an untyped JsonElement:

The second edge is the rule PackageInstaller.InstallNodeRepo has applied to node-repo plugin installs since #815, and it carries that path's hard-won caveat: it is Source/ and Test/ only, never "any descendant". Widening it drags a typed instance nested under a leaf-shaped type (ClaimsDeepfield/Cedent/NSV under type ClaimsDeepfield/Cedent) ahead of the very type it needs — the fix becoming the bug it fixes. ImportWriteOrderTest.ANestedInstanceIsADependentOfItsType_NotACompileInput pins that.

The graph is then peeled by NodeTypeDependencyGraph.TopologicalOrder — the same primitive that orders NodeType compiles for the pre-warmer, so import order and compile order cannot disagree — and turned into stages: everything inside a stage is written concurrently at the unchanged BatchSize fan-out, and a stage begins only after the previous one has completed. A well-formed source is two or three stages, so this costs two barriers rather than N serial round-trips.

Within a stage the source's own enumeration order is preserved. The ordering moves only what the dependency graph actually constrains — a partition whose nodes have no type relationships is written exactly as it always was.

Only the core is condensed

Reusing that peel has one trap worth naming. NodeTypeDependencyGraph condenses strongly-connected components by computing a reachability closure per vertex and then grouping — O(V²), which is right for the few hundred dynamic NodeTypes it was written for and wrong for a graph with one vertex per imported node. Measured on the shape a real import actually has (thousands of instances of one type):

So the peel runs over the core — the paths something else depends on — and not over the whole set. This is exact, not an approximation, on two properties: the core is closed under dependencies (if p is depended upon and p depends on q, then p depends on q, so q is depended upon), and a path with no dependents can never be part of a cycle — so every cycle is inside the core and the reported set stays complete. Everything else is a leaf: nothing waits on it, its own dependencies are all core and therefore already staged, so its stage follows directly. In practice the core is the type nodes plus their compile inputs — a handful — whatever the node count.

ImportWriteOrderScaleTest pins this as a complexity class, not a performance target: its bound sits two orders of magnitude above the post-fix time and below the pre-fix time, so only an algorithmic regression can trip it.

Decision 1 — the cycle policy

A typed by B while B is typed by A is a defect in the source, not a state of the mesh, and no write order can satisfy it. The policy:

1. The plan stays total. The peel runs over the graph's strongly-connected components; the condensation of a directed graph is acyclic, so it can never stall and every input node is emitted exactly once. A node the ordering dropped would be a node nobody ever imports — strictly worse than one written late.
2. A cycle is not demoted to last. Its members are emitted at the position their component becomes ready, in path order. This is #1347's lesson, inherited: demoting cycles put the Store/paywall chain — the most user-visible types on the portal — at the very end of an 85-type sweep. Nothing about a cycle says "do this late"; it only says "these cannot be ordered relative to each other".
3. It is deterministic. Members are ordered by path, so which member gets refused is reproducible rather than a race between five concurrent writes.
4. It is reported, and it does not fail the import. The members are named in one warning line and in the import activity. Failing the whole import instead was rejected: the content-addressed marker and its short-circuit read a partial import's verdict, and one malformed pair would take every other node in the partition down with it.
5. A member the type check then refuses is a blocked create, not a per-file failure — see decision 2, which is the same rule.

A node typed by itself is not a cycle: a self-edge is no ordering constraint, and reporting it would name a one-member "cycle" on an ordinary self-typed root.

Decision 2 — a type from another partition or repo

Topological order within one import cannot help when the type arrives from another source entirely — satellite content typed by an upstream package, or a partition whose type lives in a plugin that is not installed yet. That case is settled explicitly rather than left to the retry loop.

Before the write stages, the import probes — once per distinct type, and only for the types the plan does not already order strictly ahead of every node that needs them — using the same rule the create path applies (FindStaticNode, else IStorageAdapter.Exists). For a well-formed source that at-risk set is empty and nothing is probed at all.

A node whose type this pass cannot put in place, and which does not exist in the mesh, and which the mesh has no node at yet, is then recorded as a blocked create:

• No write is attempted, so the refusal — and its log line — is never produced. This is what removes the 6,902 lines rather than merely reordering them.
• The path and the missing type are named on the server log and as a 🚫 line in the import activity.
• The import outcome is ImportedWithBlockedCreates and the marker is stamped Warning, so the next boot re-attempts. The moment the source that defines the type is installed, the node lands — self-healing, with no watchdog.
• 🚨 It is not counted in Failed, so it does not hold the caller's sync baseline.

That last point is the substance of the decision. Holding the baseline means "retry this same commit", which is right for a node that might land next time and catastrophic for one that cannot: a single node whose type lives elsewhere froze every later commit of the same repo, because the diff base could never advance past it. Nothing is lost by letting it move — the git-diff scope deliberately never skips a node that is absent from the database, so a blocked node is re-evaluated on every pass regardless of what the diff says.

The same classification covers a cycle member, for the identical reason: its type is carried, just not ahead of it, and retrying cannot change that.

This is not a bounded-retry or a deferral timer. There is one attempt per import pass, it is named, and it costs no write.

One boundary this deliberately does not cross — the partition root

The partition root is written by EnsureRoot, one step before the node loop, and is not part of the plan. That is on purpose: root-first is what makes the partition routable, listable and landable, and every static-repo source's root is a Space — a statically-registered type — so the ordering has nothing to decide. A root whose own type is a dynamic type defined by one of its children (the Store shape: root nodeType: Store/Catalog, defined by Store/Catalog) would still be refused here. PackageInstaller.InstallNodeRepo solves that with a Space placeholder root that is retyped once the types land; the static-repo importer has never needed it, and adding it speculatively would disturb the root-first ordering for no measured case. If a source ever ships such a root, that placeholder — not a wider plan — is the fix.

What did NOT change (and why that mattered)

StaticRepoImporter.Run's ordering encodes four production incidents. The staging is inserted inside the per-node upsert phase only; every one of these is upstream or downstream of it and is untouched:

Also unchanged: root-first (EnsureRoot before any child), the claimed-node and claimed-root skips, the git-diff scope, the per-node manifest's incremental skip, two-way conflict preservation, the prune phase and its five guards, the phase-batched activity log (per-item appends are O(n²)), and the BatchSize concurrency bound — the barrier is between stages, never inside one.

Where the code is

Related

• Static Repo Import — the import itself, end to end
• Node Type Compilation — what happens after a type node lands
• CQRS and Content Access — why the type probe reads storage, not the query index
• Data Access Patterns