timely-util: bound serialized column chunks and merge allocations - #39042

Please add a short function doc comment, it's hard to tell from the implementation what exactly this is doing.

Added a doc comment. This change now lives in #39374, split out below this PR.

Is this right to call itself recursively? Or am I missing something?

Yes, intentional. The first cut is at the average record width, which is exact for uniform rows. With uneven widths a piece can still overflow, and the recursive call cuts it again. Each piece has strictly fewer records than its parent, and the recursion stops at a single record, which may exceed the bound. A piece that still overflows is now halved, so the depth is at most log2 of the record count. The comment now says this, and push_bounded_splits_uneven_widths covers the halving path.

Thanks for the explanation, makes sense!

When the incoming chunk doesn't fit, the carry flushes at whatever size it has. A 1.1 MiB carry followed by a 1.0 MiB chunk commits 1.1 MiB into a 2 MiB slot, and a stream of ~1 MiB chunks commits every chunk at about 50% slot utilization. That trades the old 4 MiB slots for half-empty 2 MiB ones.

Filling the carry up to COMMIT_BYTES with a prefix of rc (extend_from_self(view, 0..k), with k chosen the way push_bounded picks its cut) and pushing the remainder back to input would keep commits near full.

Fixed: when the next chunk is below commit size, the carry now fills toward the bound from a prefix of it, cut at its average width, and the rest returns to the input. A chunk at commit size still commits whole rather than being rewritten to top up the carry. settle_fills_carry_from_next_chunk fails on the old code, where every chunk committed at 1.12 MB.

A shared body gets copied twice here: copy_column makes a full copy, and push_bounded then only borrows it and copies again, piece by piece, via extend_from_self. If push_bounded took a borrowed view, shared bodies could be split directly from &rc, and the unique case would lose nothing.

Fixed: an oversized chunk is now cut directly from the borrow, so a shared body is copied once, into its pieces.

With spill threads on, evictions complete asynchronously, so resident_bytes only drops after a spill finishes. Under sustained load, resident bytes stay at budget + slack and this fallback runs SwapExtent::write on the dataflow worker for every insert. That bounds memory but undoes what the spill threads offload, exactly when they are behind. The description flags this. Could we get a number for direct_extent_inserts_total / inserts_total on a hydration with spill threads on before merging? Waiting briefly for spill progress before falling back might be the better trade.

On the synchronous path it didn't fire: 0 of 728,818 inserts over a 25M-row window of a 192M-row hydration with four spill workers. The async-merge path, which is not in this stack, hit 15%. I'm getting the ratio for the landing-stack hydrations as well. If it's material, I'll add a bounded wait for spill progress before the fallback. The numbers are now in #39374's description.

This shrinks the compressed-resident tier by budget / 8 for every pool with an RSS target, even when no insertion is using the slack. It's a behavior change for existing deployments that the description doesn't mention. Either call it out, or subtract only the slack currently in use (resident_bytes - budget, clamped at zero).

Fixed in #39374: the cap now subtracts only the slack in use, clamped to the eighth, so the compressed tier is unchanged when nothing is using it. unused_insert_slack_leaves_compressed_tier_intact fails on the old cap.

The average is taken over both whole inputs. If one side is narrow and the other wide, the stretch between checks can consume only wide rows and overshoot. Even for uniform rows the margin is thin: the check fires at 1.8 MiB and a stretch adds up to 0.2 MiB, so the worst case is just under 2.0 MiB before framing. The comment says merge-batcher output ships as cut without settle. Can those chunks reach the pool? If so, a test with mixed row widths would help.

No. This merger feeds ColumnMergeBatcher, whose output goes to the column pager, which has no pool size classes. I've corrected the comment: the cadence bounds uniform rows to just under the ship size, it is only a hint for mixed widths, and only ColumnChunk output needs the hard bound, which settle enforces.

nit: the rewrite drops two pieces of rationale that still apply. One is why reserve_for walks each input's as_bytes instead of reserving a record count (variable-length leaves). The other is why the capacity check is amortized (it walks every leaf slice). Worth keeping both.

Restored both.

nit: this allocates up to one full size class on the heap, outside any accounting, and in debug builds writes it twice (zero, then poison). Harmless, but worth noting in the comment. Chunks inserted this way also pay full compression even if they die young, so under pressure writes_elided under-reports.

Noted in the doc comment, in #39374.

nit: shrinking this to 60k rows means no test now settles a single Resident chunk above COMMIT_BYTES at a non-zero depth together with a small neighbor. settle_split_preserves_depth covers the split, but not the coalescing that follows it.

Added settle_split_then_coalesce_keeps_depth: an oversized depth-2 chunk with a small depth-0 neighbor, checking that every committed piece keeps depth 2 and stays within the bound.

This confirms the QA bot's finding. part stays alive while the recursive call materializes its own pieces, so each halving level on the path to an oversized update holds another copy of that update. For one update of W bytes among narrow rows, the top-level cut leaves a few hundred records per piece. Halving that down to a single record takes about log2(records) levels, each holding about W, all outside the pool budget, and this repeats on every settle or extract that sees the update.

Recursing over index ranges of the original view keeps the depth bound and limits peak memory to one piece: compute the piece's byte size from view over start..end, or materialize it only when it fits, and otherwise descend with push_cuts(view, start..end, (end - start).div_ceil(2), …).

Fixed: push_cuts now recurses over index ranges of the original view and drops an oversized piece before descending. Peak transient memory is the input plus one piece, and the depth stays at most log2 of the record count. Thanks to the QA review for the measurements.