Repository: cockroachdb/pebble
Pull request #802 (2020-07-07 18:12:08)

*: Always pick base compactions with minCompactionDepth = 1
This change updates the call to PickBaseCompaction for sublevel
compactions to use a min compaction depth of 1. This allows for
base compactions where we would completely "clear out" L0,
something that was not happening with the previous setup. To
compensate for this change, we account for L0CompactionThreshold
in the L0 score instead, by dividing the existing score with it.

This change also calls p.grow when trying to optionally grow
a compaction. This calls version.Overlaps, which is more
optimistic in picking overlapping L0 files than
extendCandidateToRectangle. This helps in reducing write-amp
in some workloads.

In practice, this seems to work better in read-heavy benchmarks
where sublevel compactions would fail to clear out L0 while
having them disabled would clear out L0 and result in better
read performance:

	name              old ops/sec  new ops/sec  delta
	ycsb/C/values=64   64.6k ± 7%   68.0k ± 5%  +5.18%  (p=0.035 n=6+7)

	name              old read     new read     delta
	ycsb/C/values=64   3.53G ± 5%   3.50G ± 6%    ~     (p=0.445 n=6+7)

	name              old write    new write    delta
	ycsb/C/values=64   5.42G ± 3%   5.38G ± 4%    ~     (p=0.445 n=6+7)

	name              old r-amp    new r-amp    delta
	ycsb/C/values=64    5.75 ± 1%    5.24 ± 2%  -8.92%  (p=0.001 n=6+7)

	name              old w-amp    new w-amp    delta
	ycsb/C/values=64    5.40 ± 3%    5.36 ± 4%    ~     (p=0.421 n=6+7)

petermattis: 

<!-- Reviewable:start -->
This change is [<img src="https://reviewable.io/review_button.png" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/cockroachdb/pebble/802)
<!-- Reviewable:end -->


Patch:
diff --git a/compaction_picker.go b/compaction_picker.go
index 1c1b227c..93e85ffe 100644
--- a/compaction_picker.go
+++ b/compaction_picker.go
@@ -174,15 +174,56 @@ func (pc *pickedCompaction) setupInputs() {
 	if pc.lcf != nil && pc.startLevel.level == 0 && pc.outputLevel.level != 0 {
 		// Call the L0-specific compaction extension method. Similar logic as
 		// pc.grow. Additional L0 files are optionally added to the compaction at
-		// this step.
-		if pc.version.L0Sublevels.ExtendL0ForBaseCompactionTo(pc.smallest, pc.largest, pc.lcf) {
-			pc.startLevel.files = pc.startLevel.files[:0]
+		// this step. Note that the bounds passed in are not the bounds of the
+		// compaction, but rather the smallest and largest internal keys that
+		// the compaction cannot include from L0 without pulling in more Lbase
+		// files. Consider this example:
+		//
+		// L0:        c-d e+f g-h
+		// Lbase: a-b     e+f     i-j
+		//        a b c d e f g h i j
+		//
+		// The e-f files have already been chosen in the compaction. As pulling
+		// in more LBase files is undesirable, the logic below will pass in
+		// smallest = b and largest = i to ExtendL0ForBaseCompactionTo, which
+		// will expand the compaction to include c-d and g-h from L0. The
+		// bounds passed in are exclusive; the compaction cannot be expanded
+		// to include files that "touch" it.
+		smallestBaseKey := base.InvalidInternalKey
+		largestBaseKey := base.InvalidInternalKey
+		baseFiles := pc.version.Levels[pc.outputLevel.level]
+		if len(baseFiles) != 0 {
+			// smallestBaseFileIdx is the index of the smallest
+			// (by key ordering) base file already in the compaction.
+			smallestBaseFileIdx := sort.Search(len(baseFiles), func(i int) bool {
+				return base.InternalCompare(pc.cmp, baseFiles[i].Largest, pc.smallest) >= 0
+			})
+			if smallestBaseFileIdx > 0 {
+				smallestBaseKey = baseFiles[smallestBaseFileIdx-1].Largest
+			}
+			// largestBaseFileIdx is the index that's one higher than the
+			// largest base file included in the compaction.
+			largestBaseFileIdx := sort.Search(len(baseFiles), func(i int) bool {
+				return base.InternalCompare(pc.cmp, baseFiles[i].Smallest, pc.largest) > 0
+			})
+			if largestBaseFileIdx < len(baseFiles) {
+				largestBaseKey = baseFiles[largestBaseFileIdx].Smallest
+			}
+		}
+		oldLcf := *pc.lcf
+		if pc.version.L0Sublevels.ExtendL0ForBaseCompactionTo(smallestBaseKey, largestBaseKey, pc.lcf) {
+			newStartLevelFiles := make([]*fileMetadata, 0, len(pc.startLevel.files))
 			for j := range pc.lcf.FilesIncluded {
 				if pc.lcf.FilesIncluded[j] {
-					pc.startLevel.files = append(pc.startLevel.files, pc.version.Levels[0][j])
+					newStartLevelFiles = append(newStartLevelFiles, pc.version.Levels[0][j])
 				}
 			}
-			pc.smallest, pc.largest = manifest.KeyRange(pc.cmp, pc.startLevel.files, pc.outputLevel.files)
+			if totalSize(newStartLevelFiles)+totalSize(pc.outputLevel.files) < pc.maxExpandedBytes {
+				pc.startLevel.files = newStartLevelFiles
+				pc.smallest, pc.largest = manifest.KeyRange(pc.cmp, pc.startLevel.files, pc.outputLevel.files)
+			} else {
+				*pc.lcf = oldLcf
+			}
 		}
 	} else if pc.grow(pc.smallest, pc.largest) {
 		pc.smallest, pc.largest = manifest.KeyRange(pc.cmp, pc.startLevel.files, pc.outputLevel.files)
@@ -621,7 +662,8 @@ func (p *compactionPickerByScore) calculateL0Score(
 		// If L0Sublevels are present, we use the sublevel count as opposed to
 		// the L0 file count to score this level. The base vs intra-L0
 		// compaction determination happens in pickAuto, not here.
-		info.score = float64(2 * p.vers.L0Sublevels.MaxDepthAfterOngoingCompactions())
+		info.score = float64(2 * p.vers.L0Sublevels.MaxDepthAfterOngoingCompactions()) /
+			float64(p.opts.L0CompactionThreshold)
 		return info
 	}
 
@@ -955,8 +997,10 @@ func pickL0(env compactionEnv, opts *Options, vers *version, baseLevel int) (pc
 	// so it can pick a compaction that does not conflict with an Lbase => Lbase+1
 	// compaction. Without this, we observed reduced concurrency of L0=>Lbase
 	// compactions, and increasing read amplification in L0.
-	lcf, err := vers.L0Sublevels.PickBaseCompaction(
-		opts.L0CompactionThreshold, vers.Levels[baseLevel])
+	//
+	// TODO(bilal) Remove the minCompactionDepth parameter once fixing it at 1
+	// has been shown to not cause a performance regression.
+	lcf, err := vers.L0Sublevels.PickBaseCompaction(1, vers.Levels[baseLevel])
 	if err != nil {
 		opts.Logger.Infof("error when picking base compaction: %s", err)
 		return
@@ -971,7 +1015,9 @@ func pickL0(env compactionEnv, opts *Options, vers *version, baseLevel int) (pc
 	}
 
 	// Couldn't choose a base compaction. Try choosing an intra-L0
-	// compaction.
+	// compaction. Note that we pass in L0CompactionThreshold here as opposed to
+	// 1, since choosing a single sublevel intra-L0 compaction is
+	// counterproductive.
 	lcf, err = vers.L0Sublevels.PickIntraL0Compaction(env.earliestUnflushedSeqNum, opts.L0CompactionThreshold)
 	if err != nil {
 		opts.Logger.Infof("error when picking intra-L0 compaction: %s", err)
diff --git a/internal/manifest/l0_sublevels.go b/internal/manifest/l0_sublevels.go
index ffea985a..e4481506 100644
--- a/internal/manifest/l0_sublevels.go
+++ b/internal/manifest/l0_sublevels.go
@@ -667,7 +667,7 @@ type L0CompactionFiles struct {
 	filesAdded              []*FileMetadata
 }
 
-// Adds the specified file to the LCF.
+// addFile adds the specified file to the LCF.
 func (l *L0CompactionFiles) addFile(f *FileMetadata) {
 	if l.FilesIncluded[f.l0Index] {
 		return
@@ -1238,41 +1238,49 @@ func (s *L0Sublevels) intraL0CompactionUsingSeed(
 }
 
 // ExtendL0ForBaseCompactionTo extends the specified base compaction candidate
-// L0CompactionFiles to cover all L0 files in the specified key interval,
-// by calling extendCandidateToRectangle.
+// L0CompactionFiles to optionally cover more files in L0 without "touching"
+// any of the passed-in keys (i.e. the smallest/largest bounds are exclusive),
+// as including any user keys for those internal keys
+// could require choosing more files in LBase which is undesirable. Unbounded
+// start/end keys are indicated by passing in the InvalidInternalKey.
 func (s *L0Sublevels) ExtendL0ForBaseCompactionTo(
 	smallest, largest InternalKey, candidate *L0CompactionFiles,
 ) bool {
-	firstIntervalIndex := sort.Search(len(s.orderedIntervals), func(i int) bool {
-		// Need to start at >= smallest since if we widen too much we may miss
-		// an Lbase file that overlaps with an L0 file that will get picked in
-		// this widening, which would be bad. This interval will not start with
-		// an immediate successor key.
-		return s.cmp(smallest.UserKey, s.orderedIntervals[i].startKey.key) <= 0
-	})
-	// First interval that starts at or beyond the largest. This interval will not
-	// start with an immediate successor key.
-	var lastIntervalIndex int
-	if largest.Trailer == base.InternalKeyRangeDeleteSentinel {
-		// largest.UserKey is excluded. Do not expand L0 to include it.
+	firstIntervalIndex := 0
+	lastIntervalIndex := len(s.orderedIntervals) - 1
+	if smallest.Kind() != base.InternalKeyKindInvalid {
+		if smallest.Trailer == base.InternalKeyRangeDeleteSentinel {
+			// Starting at smallest.UserKey == interval.startKey is okay.
+			firstIntervalIndex = sort.Search(len(s.orderedIntervals), func(i int) bool {
+				return s.cmp(smallest.UserKey, s.orderedIntervals[i].startKey.key) <= 0
+			})
+		} else {
+			firstIntervalIndex = sort.Search(len(s.orderedIntervals), func(i int) bool {
+				// Need to start at >= smallest since if we widen too much we may miss
+				// an Lbase file that overlaps with an L0 file that will get picked in
+				// this widening, which would be bad. This interval will not start with
+				// an immediate successor key.
+				return s.cmp(smallest.UserKey, s.orderedIntervals[i].startKey.key) < 0
+			})
+		}
+	}
+	if largest.Kind() != base.InternalKeyKindInvalid {
+		// First interval that starts at or beyond the largest. This interval will not
+		// start with an immediate successor key.
 		lastIntervalIndex = sort.Search(len(s.orderedIntervals), func(i int) bool {
 			return s.cmp(largest.UserKey, s.orderedIntervals[i].startKey.key) <= 0
 		})
-	} else {
-		lastIntervalIndex = sort.Search(len(s.orderedIntervals), func(i int) bool {
-			return s.cmp(largest.UserKey, s.orderedIntervals[i].startKey.key) < 0
-		})
-	}
-	// Right now, lastIntervalIndex has a startKey that extends beyond largest.
-	// The previous interval, by definition, has an end key higher than largest.
-	// Iterate back twice to get the last interval that's completely within
-	// [smallest, largest]. Except in the case where we went past the end of the
-	// list; in that case, the last interval to include is the very last
-	// interval in the list.
-	if lastIntervalIndex < len(s.orderedIntervals) {
+		// Right now, lastIntervalIndex has a startKey that extends beyond largest.
+		// The previous interval, by definition, has an end key higher than largest.
+		// Iterate back twice to get the last interval that's completely within
+		// (smallest, largest). Except in the case where we went past the end of the
+		// list; in that case, the last interval to include is the very last
+		// interval in the list.
+		if lastIntervalIndex < len(s.orderedIntervals) {
+			lastIntervalIndex--
+		}
 		lastIntervalIndex--
 	}
-	lastIntervalIndex--
 	if lastIntervalIndex < firstIntervalIndex {
 		return false
 	}
@@ -1302,10 +1310,10 @@ func (s *L0Sublevels) ExtendL0ForBaseCompactionTo(
 // it's in the bounds, then add b-d, then a--d, and so on, to produce this:
 //
 //         _____________
-//    L0.3 |a--d    g-j|      _________
-//    L0.2 |       f--j|      |  r-t  |
-//    L0.1 | b-d  e---j|      |       |
-//    L0.0 |a--d   f--j| l--o |p-----x|
+//    L0.3 |a--d    g-j|
+//    L0.2 |       f--j|         r-t
+//    L0.1 | b-d  e---j|
+//    L0.0 |a--d   f--j| l--o  p-----x
 //
 //    Lbase a-------i     m---------w
 //
diff --git a/internal/metamorphic/generator.go b/internal/metamorphic/generator.go
index 866aa509..26a2967d 100644
--- a/internal/metamorphic/generator.go
+++ b/internal/metamorphic/generator.go
@@ -7,7 +7,6 @@ package metamorphic
 import (
 	"bytes"
 	"fmt"
-	"time"
 
 	"github.com/cockroachdb/pebble/internal/randvar"
 	"golang.org/x/exp/rand"
@@ -58,9 +57,9 @@ type generator struct {
 	snapshots map[objID]objIDSet
 }
 
-func newGenerator() *generator {
+func newGenerator(rng *rand.Rand) *generator {
 	g := &generator{
-		rng:         rand.New(rand.NewSource(uint64(time.Now().UnixNano()))),
+		rng:         rng,
 		init:        &initOp{},
 		liveReaders: objIDSlice{makeObjID(dbTag, 0)},
 		liveWriters: objIDSlice{makeObjID(dbTag, 0)},
@@ -74,8 +73,8 @@ func newGenerator() *generator {
 	return g
 }
 
-func generate(count uint64, cfg config) []op {
-	g := newGenerator()
+func generate(rng *rand.Rand, count uint64, cfg config) []op {
+	g := newGenerator(rng)
 
 	generators := []func(){
 		batchAbort:        g.batchAbort,
@@ -203,7 +202,7 @@ func (g *generator) batchClose(batchID objID) {
 		delete(g.readers, batchID)
 	}
 	g.liveWriters.remove(batchID)
-	for id := range iters {
+	for _, id := range iters.sorted() {
 		g.liveIters.remove(id)
 		delete(g.iters, id)
 		g.add(&closeOp{objID: id})
@@ -477,7 +476,7 @@ func (g *generator) snapshotClose() {
 	g.liveReaders.remove(snapID)
 	delete(g.readers, snapID)
 
-	for id := range iters {
+	for _, id := range iters.sorted() {
 		g.liveIters.remove(id)
 		delete(g.iters, id)
 		g.add(&closeOp{objID: id})
diff --git a/internal/metamorphic/utils.go b/internal/metamorphic/utils.go
index 31434ac7..2233d404 100644
--- a/internal/metamorphic/utils.go
+++ b/internal/metamorphic/utils.go
@@ -6,6 +6,7 @@ package metamorphic
 
 import (
 	"fmt"
+	"sort"
 
 	"golang.org/x/exp/rand"
 )
@@ -55,6 +56,10 @@ func (i objID) String() string {
 // element is required.
 type objIDSlice []objID
 
+func (s objIDSlice) Len() int           { return len(s) }
+func (s objIDSlice) Less(i, j int) bool { return s[i] < s[j] }
+func (s objIDSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
+
 // Remove removes the specified integer from the set.
 //
 // TODO(peter): If this proves slow, we can replace this implementation with a
@@ -78,6 +83,17 @@ func (s *objIDSlice) rand(rng *rand.Rand) objID {
 // objIDSet is an unordered set of object IDs.
 type objIDSet map[objID]struct{}
 
+// sortedKeys returns a sorted slice of the set's keys for deterministc
+// iteration.
+func (s objIDSet) sorted() []objID {
+	keys := make(objIDSlice, 0, len(s))
+	for id := range s {
+		keys = append(keys, id)
+	}
+	sort.Sort(keys)
+	return keys
+}
+
 // firstError returns the first non-nil error of err0 and err1, or nil if both
 // are nil.
 func firstError(err0, err1 error) error {
diff --git a/tool/data/lsm.js b/tool/data/lsm.js
index 07f185ce..4d441c90 100644
--- a/tool/data/lsm.js
+++ b/tool/data/lsm.js
@@ -202,7 +202,10 @@ let version = {
             this.sublevels.push([]);
         }
         for (let file of this.levels[0]) {
-            let sublevel = data.Edits[this.index].Sublevels[file];
+            let sublevel = null;
+            for (let i = index; i >= 0 && (sublevel === null || sublevel === undefined); i--) {
+                sublevel = data.Edits[i].Sublevels[file];
+            }
             this.sublevels[sublevel].push(file);
         }
 
diff --git a/tool/lsm.go b/tool/lsm.go
index 7f58d58e..10195747 100644
--- a/tool/lsm.go
+++ b/tool/lsm.go
@@ -36,7 +36,7 @@ type lsmVersionEdit struct {
 	Added map[int][]base.FileNum `json:",omitempty"`
 	// Map from level to files deleted from the level.
 	Deleted map[int][]base.FileNum `json:",omitempty"`
-	// L0 sublevel structure for all files at this point.
+	// L0 sublevels for any files with changed sublevels so far.
 	Sublevels map[base.FileNum]int `json:",omitempty"`
 }
 
@@ -247,6 +247,12 @@ func (l *lsmT) buildEdits(edits []*manifest.VersionEdit) {
 		edit.Sublevels = make(map[base.FileNum]int)
 		for sublevel, files := range sublevels.Levels {
 			for _, f := range files {
+				if len(l.state.Edits) > 0 {
+					lastEdit := l.state.Edits[len(l.state.Edits) - 1]
+					if sublevel2, ok := lastEdit.Sublevels[f.FileNum]; ok && sublevel == sublevel2 {
+						continue
+					}
+				}
 				edit.Sublevels[f.FileNum] = sublevel
 			}
 		}
diff --git a/tool/lsm_data.go b/tool/lsm_data.go
index 5b7753f4..91e0c2a4 100644
--- a/tool/lsm_data.go
+++ b/tool/lsm_data.go
@@ -310,7 +310,10 @@ let version = {
             this.sublevels.push([]);
         }
         for (let file of this.levels[0]) {
-            let sublevel = data.Edits[this.index].Sublevels[file];
+            let sublevel = null;
+            for (let i = index; i >= 0 && (sublevel === null || sublevel === undefined); i--) {
+                sublevel = data.Edits[i].Sublevels[file];
+            }
             this.sublevels[sublevel].push(file);
         }
 


Test patch:
diff --git a/internal/manifest/l0_sublevels_test.go b/internal/manifest/l0_sublevels_test.go
index ba15c39c..d75d085c 100644
--- a/internal/manifest/l0_sublevels_test.go
+++ b/internal/manifest/l0_sublevels_test.go
@@ -365,9 +365,9 @@ func TestL0Sublevels(t *testing.T) {
 				lcf, err = sublevels.PickBaseCompaction(minCompactionDepth, fileMetas[baseLevel])
 				if err == nil && lcf != nil {
 					// Try to extend the base compaction into a more rectangular
-					// shape, using the smallest/largest keys of overlapping
-					// base files. This mimics the logic the compactor is
-					// expected to implement.
+					// shape, using the smallest/largest keys of the files before
+					// and after overlapping base files. This mimics the logic
+					// the compactor is expected to implement.
 					baseFiles := fileMetas[baseLevel]
 					firstFile := sort.Search(len(baseFiles), func(i int) bool {
 						return sublevels.cmp(baseFiles[i].Largest.UserKey, sublevels.orderedIntervals[lcf.minIntervalIndex].startKey.key) >= 0
@@ -375,10 +375,17 @@ func TestL0Sublevels(t *testing.T) {
 					lastFile := sort.Search(len(baseFiles), func(i int) bool {
 						return sublevels.cmp(baseFiles[i].Smallest.UserKey, sublevels.orderedIntervals[lcf.maxIntervalIndex+1].startKey.key) >= 0
 					})
-					lastFile--
+					startKey := base.InvalidInternalKey
+					endKey := base.InvalidInternalKey
+					if firstFile > 0 {
+						startKey = baseFiles[firstFile-1].Largest
+					}
+					if lastFile < len(baseFiles) {
+						endKey = baseFiles[lastFile].Smallest
+					}
 					sublevels.ExtendL0ForBaseCompactionTo(
-						baseFiles[firstFile].Smallest,
-						baseFiles[lastFile].Largest,
+						startKey,
+						endKey,
 						lcf)
 				}
 			} else {
diff --git a/internal/manifest/testdata/l0_sublevels b/internal/manifest/testdata/l0_sublevels
index 74d6695f..4e47442c 100644
--- a/internal/manifest/testdata/l0_sublevels
+++ b/internal/manifest/testdata/l0_sublevels
@@ -1049,11 +1049,11 @@ L6:    a------------------------------------------o p---------s
 pick-base-compaction min_depth=2
 ----
 compaction picked with stack depth reduction 3
-000006,000005,000004,000010,000007
+000006,000005,000004,000010,000007,000011,000009
 seed interval: f-g
 L0.2:                 f+++g
-L0.1:                 f++++++h                n---o
-L0.0:                 f+++g h++++++j k+++l    n---o
+L0.1:                 f++++++h                n+++o
+L0.0:                 f+++g h++++++j k+++l    n+++o
 L6:    a------------------------------------------o p---------s
        aa bb cc dd ee ff gg hh ii jj kk ll mm nn oo pp qq rr ss
 
diff --git a/internal/metamorphic/generator_test.go b/internal/metamorphic/generator_test.go
index 293e0e06..f39da06d 100644
--- a/internal/metamorphic/generator_test.go
+++ b/internal/metamorphic/generator_test.go
@@ -6,13 +6,17 @@ package metamorphic
 
 import (
 	"testing"
+	"time"
 
 	"github.com/cockroachdb/pebble/internal/randvar"
+	"github.com/pmezard/go-difflib/difflib"
 	"github.com/stretchr/testify/require"
+	"golang.org/x/exp/rand"
 )
 
 func TestGenerator(t *testing.T) {
-	g := newGenerator()
+	rng := randvar.NewRand()
+	g := newGenerator(rng)
 
 	g.newBatch()
 	g.newBatch()
@@ -57,7 +61,7 @@ func TestGenerator(t *testing.T) {
 		t.Logf("\n%s", g)
 	}
 
-	g = newGenerator()
+	g = newGenerator(rng)
 
 	g.newSnapshot()
 	g.newSnapshot()
@@ -90,7 +94,7 @@ func TestGenerator(t *testing.T) {
 		t.Logf("\n%s", g)
 	}
 
-	g = newGenerator()
+	g = newGenerator(rng)
 
 	g.newIndexedBatch()
 	g.newIndexedBatch()
@@ -121,8 +125,29 @@ func TestGenerator(t *testing.T) {
 }
 
 func TestGeneratorRandom(t *testing.T) {
-	ops := generate(ops.Uint64(randvar.NewRand()), defaultConfig)
+	seed := uint64(time.Now().UnixNano())
+	generateFromSeed := func() string {
+		rng := rand.New(rand.NewSource(seed))
+		count := ops.Uint64(rng)
+		return formatOps(generate(rng, count, defaultConfig))
+	}
+
+	// Ensure that generate doesn't use any other source of randomness other
+	// than rng.
+	referenceOps := generateFromSeed()
+	for i := 0; i < 10; i++ {
+		regeneratedOps := generateFromSeed()
+		diff, err := difflib.GetUnifiedDiffString(difflib.UnifiedDiff{
+			A:       difflib.SplitLines(referenceOps),
+			B:       difflib.SplitLines(regeneratedOps),
+			Context: 1,
+		})
+		require.NoError(t, err)
+		if len(diff) > 0 {
+			t.Fatalf("Diff:\n%s", diff)
+		}
+	}
 	if testing.Verbose() {
-		t.Logf("\n%s", formatOps(ops))
+		t.Logf("\nOps:\n%s", referenceOps)
 	}
 }
diff --git a/internal/metamorphic/meta_test.go b/internal/metamorphic/meta_test.go
index a6153798..cabfe818 100644
--- a/internal/metamorphic/meta_test.go
+++ b/internal/metamorphic/meta_test.go
@@ -51,6 +51,8 @@ var (
 		"write an execution trace to `<run-dir>/file`")
 	keep = flag.Bool("keep", false,
 		"keep the DB directory even on successful runs")
+	seed = flag.Uint64("seed", uint64(time.Now().UnixNano()),
+		"a pseudorandom number generator seed")
 	ops    = randvar.NewFlag("uniform:5000-10000")
 	runDir = flag.String("run-dir", "",
 		"the specific configuration to (re-)run (used for post-mortem debugging)")
@@ -118,6 +120,7 @@ func testMetaRun(t *testing.T, runDir string) {
 	require.NoError(t, m.init(h, opts.FS.PathJoin(runDir, "data"), testOpts))
 	for m.step(h) {
 		if err := h.Error(); err != nil {
+			fmt.Fprintf(os.Stderr, "Seed: %d\n", *seed)
 			fmt.Fprintln(os.Stderr, err)
 			m.maybeSaveData()
 			os.Exit(1)
@@ -141,6 +144,17 @@ func testMetaRun(t *testing.T, runDir string) {
 //
 // This will reuse the existing operations present in _meta/ops, rather than
 // generating a new set.
+//
+// The generated operations and options are generated deterministically from a
+// pseudorandom number generator seed. If a failure occurs, the seed is
+// printed, and the full suite of tests may be re-run using the `--seed` flag:
+//
+//   go test -v -run TestMeta --seed 1594395154492165000
+//
+// This will generate a new `_meta/<test>` directory, with the same operations
+// and options. This must be run on the same commit SHA as the original
+// failure, otherwise changes to the metamorphic tests may cause the generated
+// operations and options to differ.
 func TestMeta(t *testing.T) {
 	if *runDir != "" {
 		// The --run-dir flag is specified either in the child process (see
@@ -162,9 +176,12 @@ func TestMeta(t *testing.T) {
 		}
 	}()
 
+	rng := rand.New(rand.NewSource(*seed))
+	opCount := ops.Uint64(rng)
+
 	// Generate a new set of random ops, writing them to <dir>/ops. These will be
 	// read by the child processes when performing a test run.
-	ops := generate(ops.Uint64(randvar.NewRand()), defaultConfig)
+	ops := generate(rng, opCount, defaultConfig)
 	opsPath := filepath.Join(metaDir, "ops")
 	formattedOps := formatOps(ops)
 	require.NoError(t, ioutil.WriteFile(opsPath, []byte(formattedOps), 0644))
@@ -198,6 +215,8 @@ func TestMeta(t *testing.T) {
 		out, err := cmd.CombinedOutput()
 		if err != nil {
 			t.Fatalf(`
+===== SEED =====
+%d
 ===== ERR =====
 %v
 ===== OUT =====
@@ -207,7 +226,7 @@ func TestMeta(t *testing.T) {
 ===== OPS =====
 %s
 ===== HISTORY =====
-%s`, err, out, optionsStr, formattedOps, readHistory(filepath.Join(runDir, "history")))
+%s`, *seed, err, out, optionsStr, formattedOps, readHistory(filepath.Join(runDir, "history")))
 		}
 	}
 
@@ -224,7 +243,6 @@ func TestMeta(t *testing.T) {
 	}
 
 	// Perform runs with random options.
-	rng := rand.New(rand.NewSource(uint64(time.Now().UnixNano())))
 	for i := 0; i < 20; i++ {
 		name := fmt.Sprintf("random-%03d", i)
 		names = append(names, name)
@@ -274,6 +292,8 @@ func TestMeta(t *testing.T) {
 			optionsStrB := optionsToString(options[names[i]])
 
 			fmt.Printf(`
+===== SEED =====
+%d
 ===== DIFF =====
 %s/{%s,%s}
 %s
@@ -283,7 +303,7 @@ func TestMeta(t *testing.T) {
 %s
 ===== OPS =====
 %s
-`, metaDir, names[0], names[i], text, names[0], optionsStrA, names[1], optionsStrB, formattedOps)
+`, *seed, metaDir, names[0], names[i], text, names[0], optionsStrA, names[1], optionsStrB, formattedOps)
 			os.Exit(1)
 		}
 	}
diff --git a/internal/metamorphic/parser_test.go b/internal/metamorphic/parser_test.go
index 8192a13f..2c96b130 100644
--- a/internal/metamorphic/parser_test.go
+++ b/internal/metamorphic/parser_test.go
@@ -10,6 +10,7 @@ import (
 	"testing"
 
 	"github.com/cockroachdb/pebble/internal/datadriven"
+	"github.com/cockroachdb/pebble/internal/randvar"
 	"github.com/kr/pretty"
 )
 
@@ -29,7 +30,7 @@ func TestParser(t *testing.T) {
 }
 
 func TestParserRandom(t *testing.T) {
-	ops := generate(10000, defaultConfig)
+	ops := generate(randvar.NewRand(), 10000, defaultConfig)
 	src := formatOps(ops)
 
 	parsedOps, err := parse([]byte(src))
diff --git a/testdata/compaction_picker_L0 b/testdata/compaction_picker_L0
index 891fb77c..31259071 100644
--- a/testdata/compaction_picker_L0
+++ b/testdata/compaction_picker_L0
@@ -32,6 +32,12 @@ L6: 000200
 
 pick-auto l0_compaction_threshold=2
 ----
+L0 -> L6
+L0: 000100
+L6: 000200
+
+pick-auto l0_compaction_threshold=3
+----
 nil
 
 # 2 L0 files, no overlaps.
@@ -57,6 +63,12 @@ L6: 000200
 
 pick-auto l0_compaction_threshold=2
 ----
+L0 -> L6
+L0: 000100,000110
+L6: 000200
+
+pick-auto l0_compaction_threshold=3
+----
 nil
 
 # 2 L0 files, with ikey overlap.
@@ -149,6 +161,18 @@ L6: 000200
 
 pick-auto l0_compaction_threshold=3
 ----
+L0 -> L6
+L0: 000100,000110,000120
+L6: 000200
+
+pick-auto l0_compaction_threshold=4
+----
+L0 -> L6
+L0: 000100,000110,000120
+L6: 000200
+
+pick-auto l0_compaction_threshold=6
+----
 nil
 
 # 3 L0 files (1 overlap, 1 intra-L0 compacting). Should avoid the compacting