feat(storage): stage topology append-only with linear ingest I/O

[DecisionNerd]

Problem

GraphForge's original large-ingest architecture caused both scale-linear RSS and superlinear immutable-generation work. The core architecture has now been repaired:

• feat(storage): publish compact authenticated graph roots #930 publishes compact authenticated graph roots.
• feat(storage): append topology shards with persistent surrogate lookup #931 appends bounded immutable topology shards with persistent surrogate lookup.
• feat(api): stream one-generation graph construction sessions #932 provides the ordinary resumable one-generation GraphConstructionSession used by the Graph500 client.
• fix(storage): remove redundant authenticated construction passes #971 removes redundant whole-payload authentication, CAS installation, and hydration passes while preserving fail-closed integrity and crash recovery.

Attempt 5 on Fly confirmed that construction is disk-bound rather than RAM-bound: S20 ingest including seal/publication recovery completed at about 194.5 MB peak RSS. It also took 1,940.12 seconds and late probes observed roughly 59 GB read and 44 GB written. The remaining close work is therefore not another architecture rewrite or a larger machine. It is to remove harness-created fixed-cost amplification through #979, attribute and reconcile the actual storage work through #951, and prove the integrated post-#971 path against deterministic constant-factor ceilings and provider evidence.

Objective

Close the append-only construction gate by proving that the ordinary public construction path keeps memory bounded by configured work windows and keeps append, seal, authenticated publication, recovery, and retained storage within documented linear constant factors of accepted canonical data.

Completed prerequisites

• feat(storage): publish compact authenticated graph roots #930 / PR feat(storage): publish compact authenticated graph roots #933: compact authenticated graph roots.
• feat(storage): append topology shards with persistent surrogate lookup #931 / PR feat(storage): append bounded topology shards with authenticated UUID lookup #949: append-only topology shards and persistent surrogate lookup.
• feat(api): stream one-generation graph construction sessions #932 / PR feat(api): add resumable bounded graph construction #950: resumable one-generation public construction session and Graph500 client integration.
• fix(storage): remove redundant authenticated construction passes #971 / PR fix(storage): remove redundant authenticated construction passes #972: fused authentication/consumption, inline output capabilities, single-pass CAS adoption, and nonredundant hydration.

These merged outcomes remain part of this issue's close evidence; they are not open implementation scope.

Remaining requirements

• Complete fix(scale): use construction-budget Arrow batches for S20 ingest #979 so the S20 client submits bounded Arrow batches at the authoritative construction-session budget instead of multiplying durable transactions with a hidden 8,192-row subdivision.
• Complete test(scale): attribute physical bytes per node and edge before SCALE26 #951 so logical bytes, allocated physical bytes, retained bytes, and transient lifecycle peak are attributed and reconciled by artifact and phase without double-counting shared/CAS objects.
• Preserve resumable import, idempotency, cancellation, corruption handling, atomic one-generation publication, and ordinary reopen/query/export/verify/clean-import semantics.
• Keep Rust authoritative and bindings thin.
• Record content-free counters for append/merge, seal authentication/consumption, encode writes, CAS installation, hydration, fsync/synchronization, recovery reauthentication, and retained/transient storage.

Acceptance criteria

• fix(scale): use construction-budget Arrow batches for S20 ingest #979 proves one authoritative construction chunk budget, direct bounded Arrow batches, and no hidden smaller durable-transaction boundary.
• Aggregate topology rows decoded/encoded and application bytes read/written during a fresh import are O(N), with deterministic phase-specific constant-factor ceilings asserted by 1x/2x/4x tests.
• Peak resident topology state is bounded by configured batch/shard/index-run limits and does not materially grow with previously imported edge count.
• test(scale): attribute physical bytes per node and edge before SCALE26 #951 reconciles logical and allocated bytes for staging, canonical artifacts, authenticated publication, retained state, portable export, and clean import; physical retained plus transient peak remains within a documented linear factor of canonical output.
• Writer open and endpoint resolution perform zero complete node/edge topology scans per construction batch.
• Immediate execution uses carried authenticated artifact capabilities and fused unavoidable consumers; crash resume reauthenticates exactly where durable capability state is unavailable.
• Interrupted staging resumes without duplicated live rows; abort/failure leave the prior generation authoritative; recovery never publishes corrupt or missing payloads.
• Reopen, count, query, export, verify, and clean import operate on the canonical graph through ordinary product readers without a harness-only fallback.
• A post-merge S20 lower qualification records RSS, configured/submitted chunks, accepted rows, artifact/sync counts, phase bytes/calls, append/seal/recovery elapsed time, and retained/transient disk. S22 runs only after S20 passes and measured headroom admits it.
• Exact-head repository gates pass for each changed surface.

BDD completion scenarios

Linear constant-factor construction

Given a fixed construction budget and equivalent 1x, 2x, and 4x inputs
When construction, seal, publication, and recovery complete
Then peak resident state remains within the configured bounded envelope
And per-phase rows, bytes, artifacts, calls, and synchronizations grow within documented linear constant factors.

Atomic resumable publication

Given an import stops after several durable chunks or at a publication boundary
When the same session resumes and commits
Then each accepted row appears once
And readers observe either the prior project generation or the complete new generation, never a partial mixture.

Ordinary product readers

Given a graph built through the public append-only construction path
When it is reopened, queried, exported, verified, and imported cleanly
Then ordinary Rust-facade results, counts, and fingerprints match without a scale-harness-only fallback.

Observability

Emit aggregate counters only: configured/submitted rows and chunks, prior rows decoded, rows encoded, artifact/object counts, authentication/read/write bytes and calls by phase, fsyncs, elapsed time, current/peak RSS, logical/allocated retained bytes, and transient peak. Exclude graph identities, values, paths, credentials, and provider resource IDs.

Testing

• fix(scale): use construction-budget Arrow batches for S20 ingest #979 chunk-budget and transaction-amplification regressions.
• test(scale): attribute physical bytes per node and edge before SCALE26 #951 artifact classification, reconciliation, deduplication, sparse allocation, and projection regressions.
• Deterministic payload-dominated and end-to-end 1x/2x/4x constant-factor tests.
• Resume, idempotency, cancellation, corruption, atomicity, and crash-boundary tests.
• Public-facade lower-scale lifecycle and post-merge S20 qualification.
• Formatting, Clippy, Cargo/Bazel drift, authoritative exact-head CI, and CI Gate for changed surfaces.

Documentation

Document the public construction budget, append-only/sharded physical model, authenticated phase counters, retained-versus-transient storage, and the interpretation of deterministic versus provider evidence.

Non-goals

Distributed ingest, increasing RAM or timeouts, weakening integrity/durability, treating asymptotic O(N) alone as sufficient throughput evidence, changing Graph500 policy, or running S24/SCALE26 before #951 qualifies storage.

Relationships

• Parent/canonical S20 gate: test(scale): complete the Fly S18-S26 lifecycle ladder #900
• Remaining native sub-issues: fix(scale): use construction-budget Arrow batches for S20 ingest #979 and test(scale): attribute physical bytes per node and edge before SCALE26 #951
• Closed native prerequisites: feat(storage): publish compact authenticated graph roots #930, feat(storage): append topology shards with persistent surrogate lookup #931, feat(api): stream one-generation graph construction sessions #932, fix(storage): remove redundant authenticated construction passes #971
• Final certification: test(scale): certify the Fly S26 billion-edge round trip #745

[DecisionNerd]

The bounded-memory precursor #902 merged through PR #903 (eccb6e06726d05cdef9e5242cad885be80565eee). It streams current rewrite batches and bounded surrogate tails, so accumulated topology no longer drives RSS.

The measured cumulative recopy remains visible and is not waived: S18 emitted 10,358,282 topology output rows for roughly 3.8 million retained edges. This issue remains the append-only/shard-staged linear-I/O and disk-growth close gate.

[DecisionNerd]

Live Fly S20 evidence from merged commit eccb6e06726d05cdef9e5242cad885be80565eee strengthens this issue's root-cause statement.

At 8,388,608 newly ingested rows, the bounded writer had performed zero complete topology reads and held peak RSS near 644 MB, but had encoded 30,408,704 cumulative topology output rows. During the next immutable-generation publication, direct process counters exceeded 100 GB read traffic and 24 GB write traffic while physical volume use rose to roughly 13-16 GB. Multiple complete immutable generations were simultaneously retained under the project generation tree even though the live graph was only a few GB.

Therefore the required root repair is the issue's existing append-only/shard-staged transaction model plus bounded generation retention/reclamation. Increasing RAM, reducing the request window, changing providers, or weakening S20/S22 cannot repair the storage amplification. Acceptance must assert both O(N) logical topology work and a linear bound on physical peak staged-plus-retained bytes, including in-flight publication.

[DecisionNerd]

Code-level root cause found while correlating the live process counters: stream_replay_edges performs two complete passes over every existing relation and, on the write pass, calls ArrowWriter::write once per retained row (writer.rs:470-514, 532-558, specifically batch.slice(row, 1) at line 557). At the S20 midpoint that turns millions of retained edges into millions of one-row Arrow/Parquet writes, matching the observed hundreds of millions of read calls and extreme traffic amplification.

The root solution should not merely tune the batch size. The shard-staged transaction must:

1. carry forward untouched immutable shards by manifest/reference rather than decode/re-encode them;
2. rewrite only shards intersecting replacements/deletions;
3. batch contiguous untouched spans if legacy whole-file replay remains temporarily necessary;
4. append new canonical shards in bounded batches;
5. publish one atomic manifest/generation and reclaim prior unleased generations within the documented retention bound.

Regression evidence should explicitly bound Arrow/Parquet writer calls or encoded batches as well as rows/bytes, so a return to one-row replay cannot satisfy the nominal O(N) row counter while remaining operationally unusable.

[DecisionNerd]

Final S20 rerun completed ingest before an independent query OOM:

• ingest peak RSS stayed bounded at about 688 MB for 15,698,918 live unique edges
• ingest wall time was 2,602.08 s
• cumulative topology rewrite work exceeded 126.8 million output rows before the final publish for roughly 15.7 million retained edges
• live disk accounting exceeded 22.4 GB during the late ingest windows
• a 25 GB first volume reached its physical limit during the later proof; the clean 50 GB rerun had sufficient storage headroom

This confirms #901 remains a root architecture blocker even though ingest no longer OOMs. The measured amplification is caused by complete immutable-generation recopy, retained generations, and per-row replay writes, not by Fly memory or the request window. #904 separately owns the later reopen/query OOM.

[DecisionNerd]

Root-cause refinement from implementation

The append-only shard prototype proves that immutable edge fragments eliminate prior-row decode/re-encode, and hard-link reuse eliminates repeated payload allocation. It also exposes the remaining architectural owner: the v1 graph/files participant is a fully expanded per-generation inventory, so every internal publication still enumerates and re-owns all prior graph objects. Reusing cached digests would make payload bytes linear but would not make aggregate publication work linear.

The root repair therefore needs:

• project-level content-addressed immutable graph objects for topology shards and delta runs;
• a compact generation root that references only its manifest-segment/root digest instead of embedding a fully expanded inventory;
• append-only digest-linked manifest segments for new/replaced/tombstoned paths;
• reopen verification that resolves and verifies the selected root once into an ordinary reader view;
• retention/GC by tracing CURRENT, checkpoint, revert, and live-lease roots;
• GC only after atomic CURRENT publication, with recovery completing interrupted cleanup. Pre-publication work may plan capacity/reachability but must not delete authoritative ancestors.

This preserves the issue's existing acceptance criteria. Hard links, inode caches, or global counters alone are not sufficient evidence and will not be treated as completion.