Just a drive by comment:

I believe that enabling this feature for manual compactions will be tricky. Currently, the key ranges for manual compactions are picked assuming that an Li -> Li+1 compaction will be performed.

In general, manual compactions also have the property that we compact on level at a time.

Reviewable status: 0 of 8 files reviewed, 1 unresolved discussion (waiting on @itsbilal)

In general, manual compactions also have the property that we compact on level at a time.

This property isn't inherent to manual compactions, and just the way we do things, so this can certainly be changed if beneficial.

Reviewable status: 0 of 8 files reviewed, 1 unresolved discussion (waiting on @itsbilal)

It would be nice to have an experimental evaluation of the prototype code first, so that we can consider the performance benefits of this versus the extra complexity. Or maybe I missed some discussion that has already happened.

Reviewable status: 0 of 8 files reviewed, 1 unresolved discussion (waiting on @itsbilal)

Manual compactions are only really used to compact an entire level into the level below it. I'll have to take a more careful look at the code in this pr, but I doubt multi input level compactions will benefit manual compactions.

Reviewable status: 0 of 8 files reviewed, 1 unresolved discussion (waiting on @itsbilal)

Clarifying a bit regarding manual compactions.

We currently start with L0, and compact every single file in L0 into Lbase. Then we take the new Lbase, and compact each file into Lbase +1, and so on, until only L6 remains. It's mostly used as mitigation once lsms become inverted, or have some other odd shape.

They can also be used to compact a smaller key range, but I don't think we actually use it that way, currently. Cockroach has a CompactRange function, which uses manual compactions to compact some key range, but I don't believe it's actually used.

Reviewable status: 0 of 8 files reviewed, 1 unresolved discussion (waiting on @itsbilal)

Doing manual compactions a level at a time is wasteful. We're writing data in a level != L6, only to subsequently read it and delete it. We'd be better off compacting all of the levels at once in order to minimize write amplification. The only additional challenge is to get sufficient compaction concurrency. This might require compaction L0->Lbase, and then compacting Lbase...L6 with several concurrent compactions.

I had a plan to try and create a level iter over each level + sublevel and write that directly into L6. Worth trying something like that.

Reviewable status: 0 of 8 files reviewed, 1 unresolved discussion (waiting on @itsbilal)

Reviewable status: 0 of 8 files reviewed, 1 unresolved discussion (waiting on @itsbilal and @msbutler)

compaction.go, line 429 at r1 (raw file):

I believe c.kind was introduced later.

Doing a drive-by review while this is still being benchmarked. Exciting stuff; looking forward to seeing how the experiments turn out!

Reviewed 6 of 8 files at r1, 1 of 2 files at r2, all commit messages.
Reviewable status: 7 of 8 files reviewed, 6 unresolved discussions (waiting on @msbutler)

compaction.go, line 429 at r1 (raw file):

Yep, and kind was always meant to be a log thing, not really something we gate actual compaction logic on, though I'm not sure if that is still true.

compaction.go, line 461 at r2 (raw file):

	c.startLevel = &c.inputs[0]
	c.outputLevel = &c.inputs[1]

This could be c.inputs[len(c.inputs)-1] and that works for the extralevels case too (and also for future cases where we have more than one extra level).

compaction.go, line 965 at r2 (raw file):

	if len(c.extraLevels) > 0 {
		if len(c.extraLevels) > 1 {
			return nil, errors.New("n>2 multi input level compaction not implemented yet")

nit: this could just be a panic

compaction_picker.go, line 228 at r2 (raw file):

// compactions: during the second call to setupInputs, the picked compaction's
// smallest and largest keys should not decrease the key span.
func (pc *pickedCompaction) maybeExpandKeySpace(smallest InternalKey, largest InternalKey) {

nit: maybeExpandBounds is better I think

compaction_picker.go, line 405 at r2 (raw file):

	}
	if pc.outputLevel.level < numLevels-1 && (uint64(levelMaxBytes[pc.outputLevel.
		level]) < predOutputLevelSize) {

This makes a lot of sense, but I wonder if we can add another heuristic to catch cases where this won't trigger right now. I'm thinking of cases where, say, L0 is huge but we're doing an L4 -> L5 compaction here (let's say L4 is Lbase) that ends up spanning most of L4/L5. levelMaxBytes is likely influenced by the huge size contribution of L0 and all the levels combined, but we are already compacting into a majority of L5 so we may as well make it a multi-level compaction into L6. A simpler additional heuristic here could just be "what proportion of the old output level is participating in this compaction? If it's more than 50% or 75%, do a multilevel compaction". Thoughts?

compaction_picker.go, line 435 at r2 (raw file):

	defer func() {
		// Move the original startLevel to its original field in pc struct
		pc.startLevel = origStartLevel

This feels pretty hacky and we could benefit by just passing in startLevel as an argument to setupInputs.

Reviewable status: 1 of 13 files reviewed, 4 unresolved discussions (waiting on @bananabrick, @itsbilal, and @msbutler)

compaction.go line 429 at r1 (raw file):

Cool. I'l remove my comment and keep the code as is.

compaction.go line 461 at r2 (raw file):

Done.

compaction_picker.go line 228 at r2 (raw file):

Done

compaction_picker.go line 405 at r2 (raw file):

I like the idea! In other words: when the original compaction becomes really wide for the output level (e.g. 50% of current output data), do a multi input level compaction to avoid rewriting all of that ouptut level data to same level.

compaction_picker.go line 435 at r2 (raw file):

Good Idea. Done.

Reviewable status: 1 of 16 files reviewed, 4 unresolved discussions (waiting on @bananabrick, @itsbilal, and @msbutler)

compaction_picker.go line 405 at r2 (raw file):

when multiInput compactions are also initialized when over 50% of the original output level is involved, write amp is reduced by about the same percentage as w/o the additional trigger. Workload A did not record a multiInput compaction.

Those benchmark numbers look solid! I imagine write-heavy workloads are where we'll see the biggest improvement here. Unfortunate that ycsb/A nets no benefit, but maybe that doesn't quite get us many instances of small/out-of-shape output levels in compactions. Did you try changing value size in this workload? Maybe smaller value sizes (eg. 64) might be interesting.

Also code is looking like it's in great shape. @sumeerbhola what do you think about the threshold for merging this? It's behind an experimental flag anyway that defaults to false, and there are some clear wins here. Michael can probably keep benchmarking and/or prototyping heuristics to trigger multi-input compactions. Just wondering if we'd be cool with merging it soon or if we want to build a better understanding of when to trigger multi-input compactions first.

Reviewed 10 of 10 files at r3, 11 of 11 files at r4, all commit messages.
Reviewable status: all files reviewed, 4 unresolved discussions (waiting on @bananabrick and @msbutler)

-- commits line 19 at r4:
You're going to squash this before the merge, right?

compaction_picker.go line 405 at r2 (raw file):

Looks good!

compaction_picker.go line 172 at r3 (raw file):

	lcf *manifest.L0CompactionFiles

	// L0 sublevel info is used for compactions out of L0. It is nil for all

nit: paragraph should start with l0SublevelInfo

options.go line 489 at r4 (raw file):

		// MultiLevelCompaction allows the compaction of SSTs from more than two
		// levels iff a conventional two level compaction will quickly trigger a
		// compaction in the output level

Nit: period at the end, also you can mention the other heuristic that you just added.

once the function with the compaction picking heuristic in initMultiLevelCompaction has been separated out into its own PR.

Reviewable status: all files reviewed, 9 unresolved discussions (waiting on @bananabrick and @msbutler)

compaction.go line 659 at r4 (raw file):

	if len(c.extraLevels) == 0 {
		return false
	} else if c.extraLevels[0].files.Empty() {

Was this ever happening in practice? Maybe we could throw in a panic here to confirm it's not. If we're adding an extra level it should not be empty. That way we can also get rid of this function and replace it with just the length check.

compaction_picker.go line 264 at r4 (raw file):

// maybeExpandedBounds is a helper function for setupInputs which ensures the
// pickedcompaction's smallest and largest internal keys are updated iff

Nit: pickedCompaction

compaction_picker.go line 442 at r4 (raw file):

//    immediately (i.e. the predicted output level size exceeds the level's max bytes)
// 2. Over 50% of the original output level is included in the compaction.
func (pc *pickedCompaction) initMultiInputLevelCompaction(

nit: initMultiLevelCompaction, matches the option name and is also easier to search..

compaction_picker.go line 451 at r4 (raw file):

	// which would prevent files with del ranges from hitting this.
	// however this doesn't apply much to use cases (inverted LSM, manual compaction).
	predOutputFileSize := uint64(math.Max(float64(pc.startLevel.files.SizeSum()),

Since the heuristic is mostly in this method, it'd be best to just have this return false for now, and create a new PR with just this code. We can continue the benchmarking/iteration there.

metrics.go line 390 at r4 (raw file):

		redact.Safe(m.Compact.NumInProgress),
		redact.SafeString(""))
	w.Printf("  ctype %9d %7d %7d %7d %7d %7d %7d  (default, delete, elision, move, read, rewrite, multiInput)\n",

nit: multi-input is more consistent with the convention around here

Reviewable status: all files reviewed, 3 unresolved discussions (waiting on @itsbilal)

-- commits line 19 at r4:

Done.

compaction.go line 659 at r4 (raw file):

This is a valid case! see the comment I added:

// a multi level compaction without data in the intermediate input level;
// e.g. for a multi level compaction with levels 4,5, and 6, this could
// occur if there is no files to compact in 5, or in 5 and 6 (i.e. a move).

compaction_picker.go line 172 at r3 (raw file):

Done.

compaction_picker.go line 264 at r4 (raw file):

Done.

compaction_picker.go line 442 at r4 (raw file):

Done.

compaction_picker.go line 451 at r4 (raw file):

Done

options.go line 489 at r4 (raw file):

Done.

Yep, based on offline discussion we agreed to move tests / heuristic code to #1746.

Reviewed 16 of 16 files at r5, all commit messages.
Reviewable status: all files reviewed, 2 unresolved discussions (waiting on @msbutler)

compaction.go line 659 at r4 (raw file):

Interesting, so this seems like a "skip this middle level when compacting" compaction to me. Pretty good idea.

This actually reminds me of another instance where we could schedule multi-level compactions and see a benefit; compactions where we're merging into very few files/bytes in the original output level (but possibly still nonzero bytes) compared to the input level. It probably means we can make those output level files the middle level and compact into one level further down. Worth benchmarking in #1746.

metrics.go line 390 at r5 (raw file):

		redact.Safe(m.Compact.NumInProgress),
		redact.SafeString(""))
	w.Printf("  ctype %9d %7d %7d %7d %7d %7d %7d  (default, delete, elision, move, read, rewrite, multiLevel)\n",

nit: multi-level

testdata/event_listener line 193 at r5 (raw file):

  flush         3
compact         1   2.3 K     0 B       0          (size == estimated-debt, score = in-progress-bytes, in = num-in-progress)
  ctype         1       0       0       0       0       0       0  (default, delete, elision, move, read, rewrite, multiLevel)

nit: multi-level