Per-upload cost grows with bucket size (forest write amplification): 1.0s/file at n=0 to 3.8s/file at n=135

[ehsan6sha]

Context

Found during FxFiles web P0 cache-plan baselining (FxFiles commit f3e4ed0, plan doc FxFiles/docs/web-listing-prefetch-cache-plan.md section 11). Not blocking that work - filing so it can be picked up independently.

Observation

Seeding a fresh documents-v8 bucket with 150 sequential uploadObject calls (4 KB each, distinct keys under /e2e/perf/, fula_client 0.6.7 wasm via FRB, single client, no concurrency) showed the cumulative average upload time rising steadily as the bucket filled:

files uploaded	avg ms/file (cumulative)
25	1040
50	1786
75	2352
100	3041
125	3818

A rising cumulative average means the marginal cost per upload grows roughly linearly with object count - i.e. bulk-uploading N files costs O(N^2) total. Payload size is constant (4 KB), so the growth is in the per-put metadata work, not data transfer.

Hypothesis (unverified)

Each put rewrites/re-uploads forest index state whose size scales with the bucket's object count (forest pages / root chain), rather than an incremental page touch. Likely places to look:

• crates/fula-flutter/src/api/forest.rs (put path takes the outer write().await lock; what does it serialize/upload per put?)
• forest page layout: does a put rewrite one leaf page + root, or re-serialize a larger structure?
• whether small sequential puts could batch/amortize forest commits (e.g. dirty-page flush, or an explicit batch-put API for N files)

Repro

1. FxFiles repo at f3e4ed0: flutter build web --release -t lib/main_web.dart --dart-define=E2E=true --dart-define=PERF=true --pwa-strategy=none
2. Serve build/web, open http://localhost:<port>/?e2e=perf-seed&n=150&seed=<test vault seed> in headless Chrome with --enable-logging=stderr
3. Watch the [e2e] seeded k/150 (...ms/file) console lines.

Same trend should reproduce with any S3-compatible client of fula-api writing N small objects sequentially to one bucket; the FxFiles harness is just a convenient driver.

Why it matters

• Bulk flows (camera-roll sync, folder upload, collaboration receiver-upload) degrade quadratically with bucket size.
• It also inflates read-side forest size/cost (FxFiles web measured cold listing at ~6.5 ms/file - forest download + first enumeration - which is the other half of the same scaling story).

Suggested acceptance

• Instrument the put path to attribute time (forest read-modify-write vs PUT vs lock wait).
• Decide: incremental page write, batched commit API, or documented expected cost.
• A 150-small-file sequential upload should show flat (or near-flat) marginal cost.

🤖 Generated with Claude Code

[ehsan6sha]

Verified: real finding — root cause identified, with unit-test proof

TL;DR. The O(N²) growth is real and client-side, in the SDK's forest flush. Every put_object_flat re-uploads the entire ever-touched portion of the hot shard's HAMT — not just the changed path — because nodes mutated in memory are never marked clean after being persisted. Per-upload index traffic grows by ~1.1 KB per object already in the bucket, on top of a PUT-count curve that grows 1 → ~17 sequential round trips per upload. Proof tests are committed on phase-2.5-multimaster @ 74ec299 (cargo test -p fula-crypto issue_34 -- --nocapture).

Root cause — three facts that compose

1. Copy-on-write insert marks the whole path dirty. Node::set_value replaces every node on the mutated root→leaf path with Pointer::Link(ChildPtr::InMemory(_)) (crates/fula-crypto/src/wnfs_hamt/node.rs:336 and :436). Untouched siblings stay ChildPtr::Stored(key) — so far so good, that's the incremental design.

2. Flush persists InMemory nodes but can never mark them clean. Node::store(&self) recursively PUTs every InMemory child (pointer.rs to_wire, InMemory arm → one network PUT per node, awaited sequentially in node.rs::store's pointer loop). But store takes &self — it cannot downgrade InMemory → Stored after the PUT succeeds, and nothing else does: the only constructor of ChildPtr::Stored/StoredV2 in production code is Pointer::from_wire, i.e. the load path. The InMemory set therefore grows monotonically for the life of the session, and every flush re-PUTs all of it.

3. One directory = one hot shard, and put_object_flat flushes per file. Dir-local routing sends every file of a directory to the same shard (sharded_hamt_forest.rs::upsert_file, routing invariant debug_assert), and put_object_flat = deferred upsert + flush_forest_locked on every call (fula-client/src/encryption.rs::put_object_flat). So N sequential uploads into /e2e/perf/ run N flushes, each re-uploading the whole accumulated tree of that one shard.

Aggravators:

• put_node encrypts with a fresh nonce on every call (v7_store.rs::put_node), so even byte-identical plaintext nodes upload new ciphertext each flush — no dedup is possible at any layer (client cache, proxy, or server).
• Each forest entry carries the ~1 KB x-fula-encryption JSON in user_metadata (stashed by put_object_flat for offline/cold-start reads), so per-node payloads are ~1 KB × entries-in-node.
• Fixed per-put pipeline on top of the amplified node PUTs: 1 manifest-page PUT + 1 dir-index-shard PUT + 1 root-manifest PUT + the object PUT itself — all sequential awaits; on wasm each is a browser fetch (plus CORS preflight when applicable).

The issue's hypothesis said "forest pages / root chain" — close but not quite: pages and root are 1 PUT each per flush and roughly constant-size. The quadratic driver is the HAMT node re-upload.

Unit-test proof

Three current-behaviour pins added in 74ec299 (they pass on today's code and quantify the bug; invert them into regression guards when fixing):

1. Node layer — the engine. wnfs_hamt::node::round_trip_tests::issue_34_store_reputs_entire_unchanged_in_memory_tree: two consecutive store() calls with no mutation in between PUT the same node count (same content address, byte-identical tree). An incremental design would PUT 0 the second time.

2. Forest layer — the growth curve. sharded_hamt_forest::tests::issue_34_per_flush_put_cost_grows_with_bucket_size: 150 × (upsert_file + flush_dirty) into one directory with production-weight entries, against a counting backend:

upload #	HAMT-node PUTs in that flush	bytes in that flush
1	3	1,225
10	1	10,773
25	3	26,958
50	8	54,017
75	13	81,085
100	16	108,052
125	16	134,836
150	17	161,679

Totals: 1,630 node PUTs and 12.2 MB of index uploads to store 150 × 4 KB files (600 KB of payload) — ~20× write amplification at N=150, and the per-flush bytes grow linearly at ~1.08 KB × bucket-size. Extrapolating: at n=1000 every single small upload re-uploads ~1.1 MB of index across ~20 sequential PUTs, and a 1000-file bulk session uploads ~0.5 GB of index.

3. The falsifier — it's session state, not tree size. sharded_hamt_forest::tests::issue_34_fresh_session_flush_is_incremental_long_session_is_not: marginal flush after 150 uploads, same bucket, same persisted data:

• long-lived session: 17 node PUTs
• fresh forest loaded from the same manifest (production load path; pointers deserialize as Stored): 3 node PUTs

Same write, same data — 17 vs 3. The difference is exactly the never-downgraded InMemory set. "The index is just big, the cost is unavoidable" is therefore false.

Why this matches the measured curve

Marginal cost(n) ≈ fixed pipeline (object + page + dir-index + root PUTs) + nodePUTs(n) × RTT + nodeBytes(n) ÷ uplink. PUT count grows 1 → ~17 and saturates around n≈100 (HAMT fanout 16: root + all 16 children resident), but bytes keep growing O(n) — which is why the measured marginal kept rising 5.1 → 6.9 s/file past n=100 instead of plateauing. At browser-to-master RTTs (~150–300 ms per sequential PUT), n≈125 → ~20 round trips ≈ 4–6 s + transfer; the n≈0 baseline of ~1 s is the fixed ~5-PUT pipeline. The read-side number in the report (cold listing ~6.5 ms/file) is the same O(N) forest size but is not amplified by this bug — reads resolve nodes lazily.

Remediation options, ranked

1. Write-back downgrade (the fix). After a successful store(), convert persisted InMemory children to StoredV2 { storage_key, cid } (or Stored). Needs a &mut-capable store pass — e.g. a store_mut using Arc::make_mut, or a post-store fixup walk inside flush_dirty (which would then need the shard's write() guard instead of today's read()). Marginal flush becomes O(depth) ≈ 2–3 PUTs regardless of bucket size. Node PUTs still complete before the ETag-gated root/manifest commit, so the crash-consistency story is unchanged.
2. Parallelize sibling node PUTs. Node::store awaits its pointer loop sequentially; reads already fan out (flat_map uses buffered concurrency 16). Bounded fan-out (~6 on browsers) cuts the latency multiplier even before (1) lands.
3. Session-scoped persisted-key set. Skip put_node when that exact content-address was already PUT this session. Same effect as (1) for unchanged nodes; Plan B if the &mut plumbing is painful. Caveat: skipping a PUT the server actually lost leaves a dangling reference — keep it session-scoped and clear it on any flush error.
4. Bulk callers: use the API that already exists. put_object_flat_deferred + one flush_forest does ONE tree store at the end — O(N) total instead of O(N²). FxFiles' bulk flows (camera-roll seed, folder upload, receiver-upload) can adopt this today. It does not fix the one-file-at-a-time sync pattern, which needs (1).

Acceptance mapping (from the issue)

• "Instrument the put path" — done at unit level; the three tests above are the instrumentation and flip into flat-marginal-cost regression guards once fixed.
• "A 150-small-file sequential upload should show flat (or near-flat) marginal cost" — with (1), node PUTs/flush become O(depth) and per-flush bytes stop scaling with bucket size; the remaining per-put fixed pipeline is constant. With (2) on top, the constant shrinks further.

🤖 Generated with Claude Code

[ehsan6sha]

Fixed in 0.6.8 — merged via #35 (acb3fea)

The fix: flushes now write back a Sealed state into the in-memory HAMT after each successful node PUT (ChildPtr::Sealed { storage_key, cid, node } + Node::store_sealing). A sealed subtree stays memory-resident for zero-I/O reads but is emitted as a reference on subsequent stores — so a flush uploads the shard root plus the path(s) mutated since the previous flush, bounded by tree depth, never by bucket size.

Acceptance check (the issue's own criterion — flat marginal cost on a 150-file sequential upload), measured by the regression guards:

metric	pre-fix (pinned at 2ed7fe0)	post-fix
node PUTs at flush #150	17, growing with N	3, flat
bytes at flush #150	161.7 KB (≈1.08 KB × bucket size)	23 KB, bounded
long-lived vs fresh session marginal flush	17 vs 3	3 vs 3
totals, 150 × 4 KB files	1,630 PUTs / 12.2 MB	384 PUTs / 3.5 MB

No-corruption guarantees (tested):

• Zero wire-format change: a sealing writer produces byte-identical persisted state to the legacy writer (same inserts → identical content-addressed root; issue_34_sealing_and_legacy_store_produce_identical_roots). Existing buckets and older SDKs interoperate unchanged.
• 150-file cold-reload integrity, deletion over a sealed tree, and failure-mid-seal retry convergence are all pinned by tests.

Multi-client safety (two clients alternating writes — the follow-up concern): new integration test two_clients_alternating_writes_compose_without_loss runs client A (sealed forest) → client B (advances ETags) → client A again from its stale sealed forest, asserts the 412 → evict → reload → WAL-replay → retry reconcile actually fires (flush_backoff_count), that A sees B's writes post-reconcile, and that a third fresh client reads all 7 files byte-exactly. Sealing adds no staleness window: conflict arbitration stays manifest-ETag-gated, every reconcile path discards the in-memory forest (sealed state included) wholesale, and sealed pointers reference immutable content-addressed objects.

Platforms: the change is entirely in the shared fula-crypto core; PR CI verified Android (aarch64/armv7/x86_64), iOS (aarch64/x86_64), wasm (test-wasm), bindings generation, and the full Rust workspace suite (449 fula-crypto + 208 fula-client lib tests + integration suites).

Remaining (non-blocking) observations:

• Each put_object_flat still pays a fixed ~5-PUT pipeline (object + page + dir-index shard + root) — that's the flat ~1 s baseline FxFiles measured at n≈0 on a browser. Bulk flows should keep preferring put_object_flat_deferred + one flush_forest (already in the SDK) to amortize it; parallelizing sibling node PUTs inside store_sealing could shave the first-flush-after-bulk case further if it ever matters.
• The FxFiles cold-listing figure (~6.5 ms/file) is plain O(N) forest size on the read side, not affected by (or related to) this write-path bug.

Version bumped 0.6.7 → 0.6.8 (workspace + fula-js/fula-flutter crates + fula_client pubspec/podspec/changelog).

🤖 Generated with Claude Code