db: ingestTargetLevel places external files in L0 when L1..baseLevel-1 are empty

[dt]

Summary

ingestTargetLevel's level-search loop starts at baseLevel, not L1. The function initializes targetLevel = 0 and walks for level := baseLevel; level < numLevels; level++, updating targetLevel to the deepest empty level it visits before returning when it hits data overlap.

When the very first iteration (at baseLevel) sees data overlap, the function returns the un-updated targetLevel = 0 — placing the file in L0 even though L1..baseLevel-1 are physically empty. Per Pebble's own compaction-invariant model those levels are "not opened yet" because the LSM is small, but they're still legal placement targets and would dramatically reduce L0 stacking when the alternative is the fallthrough to L0.

This shows up in the wild when an LSM has substantial data at L6 but little above (so baseLevel is high) and ingests arrive with overlapping bounds — each subsequent overlapping ingest collapses to L0 instead of cascading into the empty intermediate levels. The symptom is documented from the CockroachDB side at cockroachdb/cockroach#170225 (online restore links a chain of overlapping external SSTs and tens of GB pile up in L0).

Standalone reproduction

A small standalone Go program reproduces this in ~2 seconds:

1. Open a pebble DB with RemoteStorage configured (in-memory remote.NewInMem() is enough) and DisableAutomaticCompactions: true so placement decisions are observable.
2. Build three external sstables in the remote store. Disjoint point keys, but each declared with identical user-key bounds [a, m). Set Size: 128 << 20 (realistic backup-style file size) so baseLevel doesn't collapse to L6.
3. Ingest each with a separate IngestExternalFiles call.

Observed placement:

ingest #1 → L6  (empty LSM)
ingest #2 → L5  (overlap at L6, baseLevel is high, cascade reaches L5)
ingest #3 → L0  (overlap at L5 — loop returns initial targetLevel=0)

Expected (and what would happen if the loop started at L1):

ingest #1 → L6
ingest #2 → L5
ingest #3 → L4

After warming the LSM with ~940 MiB of non-overlapping data to push baseLevel down to L4, ingest #3 cascades to L4 as expected. So the trigger is unambiguously "loop starts at baseLevel."

Code reference

ingestTargetLevel in ingest.go. The loop initialization is for level := baseLevel; level < numLevels; level++. Changing the lower bound from baseLevel to 1 (keeping the lsmOverlap[0] fast-path check above the loop) lets the loop consider empty intermediate levels. A branch at https://github.com/dt/pebble/tree/ingest-cascade-from-l1 makes that one-line change with a regression-test fixture; the integration test on the CockroachDB side that previously showed 3.3 GB ingested at L0 dropped to 0 with that fix applied.

Open questions

• Is baseLevel the right floor for the search at all? The current comment block on the function explains the size-ratio reasoning, but that reasoning is about steady-state compaction shape, not about whether a given level is a legal ingest target. If placement above baseLevel is legal (it is — nothing else in pebble seems to assume otherwise), the search should consider those levels and let the compaction picker reconcile the size invariant over time.
• The compaction picker may target a file placed above baseLevel for an aggressive level-compaction (since its target_bytes ≈ 0 above baseLevel), potentially defeating the placement by triggering a materializing merge. Worth thinking about whether a compaction-side change is needed in tandem — or whether the picker's natural behavior (trivial-move-down when destination is empty) is enough.

Workaround

CockroachDB can mitigate symptom on its side, but the placement decision is upstream of any caller and any code path that does many overlapping external ingests into a small LSM would hit this.

Related: cockroachdb/cockroach#170225.

Jira issue: PEBBLE-1445

[RaduBerinde]

This is as designed. Levels between 1 and baseLevel must be empty. Not sure what placing things in those levels instead of L0 sublevels would achieve anyway?

[dt]

Levels between 1 and baseLevel must be empty

Can you expand on this, and the invariant this "must" is upholding? My impression was the geometric level size targets are for bounding write-amp under a steady-state flush-and-compact workload?

instead of L0 sublevels

This is indeed something I'd like to understand a bit better; my impression is we tend to assume L0 files are the result of flushing and have different treatment of L0 vs L1..L6. Specifically, doesn't the compaction picker treat the two cases pretty asymmetrically?

• L0 has its own dedicated scoring function (calculateL0FillFactor) driven by sublevel depth (2 * sublevels / L0CompactionThreshold, default 4) OR file count (files / L0CompactionFileThreshold, default 500), whichever is higher — so even a small number of L0 files makes the level score-eligible for compaction.
• pickCompactionScore at compaction_picker.go:1052 explicitly continues past levels in (0, baseLevel) — files there aren't scored at all.
• L0 compactions, once picked, can't be trivial moves: maybeSwitchToMoveOrCopy wants a single-file source, but pickL0 / PickBaseCompaction / PickIntraL0Compaction take overlapping sublevels — so L0 compactions fundamentally read data and materialize.

[RaduBerinde]

Can you expand on this, and the invariant this "must" is upholding? My impression was the geometric level size targets are for bounding write-amp under a steady-state flush-and-compact workload?

Yes, and we want to bound read amp when store sizes are not large enough to warrant maintaining all the levels.

This is indeed something I'd like to understand a bit better; my impression is we tend to assume L0 files are the result of flushing and have different treatment of L0 vs L1..L6.

Yes, there are specific heuristics for L0. Putting files in e.g. L1 when Lbase is L3 feels like we'd be "hiding" the file from those heuristics (which in general would be a bad thing). If we want special compaction treatment of these ingestions, we need to figure out what we want exactly.

CC @sumeerbhola who has more context on the heuristics we use and the reasoning behind them.

By the way, this is inacurrate:

This shows up in the wild when an LSM has substantial data at L6 but little above (so baseLevel is high)

The baseLevel is calculated from the total size of the store (including L0), regardless how the LSM is currently arranged.

[dt]

Say I have e.g 400GB in a full backup and then 3 x 10gb layers of inc backup diffs on top of it. Each layer of backup consists of 500 to 25000 non-overlapping SSTs (backup has a target file size of 16mb to keep things small enough to retry/pass around in distsql/single raft commands/etc). My expectation is our ideal "restore" of this backup ends up with the 25k full backup ssts in L6, the 600ish ssts of the first inc backup in L5, the next inc in L4 and the final inc in L3, with everything above them, including L0, empty and ready for flushes from the workload.

One thing to note is we work left to right: for a given "span" (~300mb sum size), we ingest all the files, then go to the next span. With the current target level choice that means the fulls end up in l6, but until we've moved far enough into the the restore, we're sticking everything else in L0 because Lbase does not yet reflect the size of the restore. And we're not adding just 600 files per layer either, since for any given span, we can only add the subset of the file in that layer that intersects that span (via a vSST), so the actual "file" count in that span once we have several vSSTs per SST could be much higher -- we can easily end up with hundreds and hundreds of files in L0.

we want to bound read amp when store sizes

I'm not really following: read amp here is fixed isn't it? I have 4 layers -- full and 3 incs -- so read amp is 4 whether that is L6+L5+L4+L3 or L6+L0+L0+L0+L0 -- either way there are 4 layers to merge for a read, the only difference is if 3 are regular levels or L0 sublevels.

[RaduBerinde]

I see. What if we had a configuration option that tells Pebble to configure the LSM as if there are at least X GB in it? This could default to e.g. 10% of the disk capacity, and it could also be set to other values by tests.

From an algorithmic standpoint, the number of levels should grow logarithmically with the size of the store, so it makes sense for Lbase to be adaptive. But practically, it doesn't make much sense to have Lbase be L4 or L5 since stores that tiny are not realistic.

I'm not really following: read amp here is fixed isn't it? I have 4 layers -- full and 3 incs -- so read amp is 4 whether that is L6+L5+L4+L3 or L6+L0+L0+L0+L0 -- either way there are 4 layers to merge for a read, the only difference is if 3 are regular levels or L0 sublevels.

Sure, initially, but if Lbase=L4, eventually we will compact everything to where we only have L4,L5,L6 (read amp = 3). If Lbase=L1, we would allow L1 through L6 (read amp = 6).

[dt]

I'm reluctant to add some sort of "expected" size hint that tries to predict the future: if we actively set it during import or restore, does it expire? What if we abort? Or pause? If it's just based on disk size, restore of the same data behaves differently based on disk size?

I'd argue we should just treat ingest and compaction separately here, and define LBase as only pertinent to the latter.

Ingested files are already written, unlike a picked compaction, so we don't control their write-amp at placement time. Operations that involve ingest tend to be bulk operations where our goal is to do the ingests with minimal cost and preserve capacity for more ingest, not to start compactions that compete with the bulk operation for limited write bandwidth.

In a large bulk operation, we'll end up with a large LSM anyway — LBase will eventually reflect that, and if we'd been using an early/premature LBase value for choosing ingest target levels, we'd find ourselves acutely regretting it: putting hundreds of files in L0 obligates us to compact them, which then competes for the scarce capacity the bulk operation needs to complete. For small ingests our choice matters a lot less: sure, maybe if the restore/import ends up small and we're left with a small LSM, we could have afforded to stick some layers in L0 and eagerly compact toward a shallower LSM with lower read-amp — but if we're talking about an LSM that small, it probably all fits in page cache anyway.

I think it makes sense to just remove LBase from the ingest target level choice, and define LBase strictly as a compaction-picking concern — and then leave LBase alone (no LSM size floor/hint/etc.) for compaction picking.

[RaduBerinde]

I think it makes sense to just remove LBase from the ingest target level choice, and define LBase strictly as a compaction-picking concern — and then leave LBase alone (no LSM size floor/hint/etc.) for compaction picking.

If compactions still target the same LSM shape as before, you would get pretty much the same compactions that try to clear out the levels that are supposed to be empty. Whether the input files are in L0 or L(Base-1) is a technicality.

I feel that we are arguing about a specific mechanism and working backwards from that instead of starting from the functional goal. Can you try to outline in more clear terms the functional change you are hoping for?

Is the hope that once the LSM gets big enough to where Lbase changes, the files that are still on that level can just stay there? I think we'd achieve that in a cleaner way by just planning move compactions from the bottom L0 sublevels. That would probably benefit us more generally.

There is valid intuition behind this discussion - ingestions and flushes can look very differently in term of file sizes and key span width and compaction heuristics should perhaps distinguish. But I don't think the proposed solution addresses that, it feels more like a hack.