Repository: cockroachdb/pebble (go)

Issue:
internal/metamorphic: enhance by printing a prng seed on failure
When the metamorphic tests fail in CI, it prints the history diff, options and operations for debugging. It seems like we might be able to make it easier to debug and reproduce by printing the prng seed from which the operations and random options were deterministically generated. If we add a `--seed` flag, we could reproduce a CI failure on the same SHA easily.

Pull request description:
internal/metamorphic: generate deterministically from prng seed
Generate tests operations and random options deterministically from a
pseudorandom number generator seed. On failure, print the seed alondside
the test results.

Add a new `--seed` flag for passing a specific seed, allowing
re-executing a full metamorphic test run on the same SHA from just the
seed.

We may want to augment the seed with a small checksum over the
operations and options to ensure that accidental introduction of outside
randomness or use of a seed on a different SHA doesn't confuse us.

Close #785.

Patch:
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/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))