Repository: cockroachdb/pebble (go)

Issue:
internal/metamorphic: cross version testing
The metamorphic tests are great at exercising edge cases by producing a wide breadth of logically equivalent database states. Currently they're limited to exercising database states that may be constructed by the same version of Pebble as the one being tested. This limitation leaves upgrade paths untested.

This limitation was raised in the context of #1470. Pebble no longer splits sstables within a user key, but previous versions did. Pebble needs to appropriately handle these 'atomic compaction units' until [`FormatMarkedCompacted`](https://github.com/cockroachdb/pebble/blob/8e8ff2be5a2fbb57fb79e6eb92305b9809b26a73/format_major_version.go#L80-L87) is the minimum supported format major version (CockroachDB 23.1). The current metamorphic tests don't provide coverage of atomic compaction units, since they're never constructed. Performing metamorphic tests across mixed Pebble versions would add coverage here.

Another alternative would have been to preserve the old behavior, gated behind an internal flag that may be enabled as a metamorphic option. This option would be similar to Pebble's internal support for writing range-del-v1 blocks. This alternative would require a) preserving complicated compaction logic within Pebble until the 23.1 release cycle, and b) leaves open the possibility that the adapted Pebble code doesn't exactly match the behavior of earlier Pebble versions. For these reasons, we're exploring mixed version testing.

Mixed version metamorphic testing needs to be able to handle:
* New metamorphic operations and test coverage introduced in later Pebble versions (eg, iterator `WithLimit` methods, range keys, etc.)
* Continuity of state across version upgrades: The operations applied to a database opened with a later Pebble version must draw from the same set of user keys used to construct the database.

----

One implementation idea:

Add a `--preceding-test` command-line flag that takes the path to a previous metamorphic test's directory. The directory is expected to contain data directories of each run's state, produced by the existing `--keep` flag. When generating the operations for the new test, the `--preceding-test` flag causes the generator to be initialized with keys and prefixes extracted from parsing the preceding run's `ops` file.

When the `--preceding-test` flag is provided, the metamorphic test produces a run for the Cartesian product of the preceding test's configurations and the current test's configurations. All of the |A| × |B| runs are expected to be equivalent.

This would probably be best suited for another nightly roachtest, rather than modifying the existing one.

Pull request description:
internal/metamorphic/crossversion: add TestMetaCrossVersion
Add a new metamorphic variant that runs metamorphic tests across multiple
Pebble SHAs. The test takes an arbitrary number of Pebble versions and paths to
prebuilt metamorphic package test binaries. It runs the metamorphic tests once
on the first version. It then takes a random sampling of `--factor` database
directories produced by that version, and uses them as initial database states
for the next version, and so on.

Resolve #1612.

Patch:
diff --git a/internal/metamorphic/history.go b/internal/metamorphic/history.go
index 64c6aaa1..9b6696af 100644
--- a/internal/metamorphic/history.go
+++ b/internal/metamorphic/history.go
@@ -7,12 +7,16 @@ package metamorphic
 import (
 	"fmt"
 	"io"
+	"io/ioutil"
 	"log"
 	"regexp"
 	"strings"
 	"sync/atomic"
+	"testing"
 
 	"github.com/cockroachdb/errors"
+	"github.com/pmezard/go-difflib/difflib"
+	"github.com/stretchr/testify/require"
 )
 
 // history records the results of running a series of operations.
@@ -89,3 +93,41 @@ func (h *history) Fatalf(format string, args ...interface{}) {
 	_ = h.log.Output(2, h.format("// FATAL: ", format, args...))
 	h.err.Store(errors.Errorf(format, args...))
 }
+
+// CompareHistories takes a slice of file paths containing history files. It
+// performs a diff comparing the first path to all other paths. CompareHistories
+// returns the index and diff for the first history that differs. If all the
+// histories are identical, CompareHistories returns a zero index and an empty
+// string.
+func CompareHistories(t *testing.T, paths []string) (i int, diff string) {
+	base := readHistory(t, paths[0])
+	for i := 1; i < len(paths); i++ {
+		lines := readHistory(t, paths[i])
+		diff := difflib.UnifiedDiff{
+			A:       base,
+			B:       lines,
+			Context: 5,
+		}
+		text, err := difflib.GetUnifiedDiffString(diff)
+		require.NoError(t, err)
+		if text != "" {
+			return i, text
+		}
+	}
+	return 0, ""
+}
+
+// Read a history file, stripping out lines that begin with a comment.
+func readHistory(t *testing.T, historyPath string) []string {
+	data, err := ioutil.ReadFile(historyPath)
+	require.NoError(t, err)
+	lines := difflib.SplitLines(string(data))
+	newLines := make([]string, 0, len(lines))
+	for _, line := range lines {
+		if strings.HasPrefix(line, "// ") {
+			continue
+		}
+		newLines = append(newLines, line)
+	}
+	return newLines
+}


Test patch:
diff --git a/internal/metamorphic/crossversion/crossversion_test.go b/internal/metamorphic/crossversion/crossversion_test.go
new file mode 100644
index 00000000..9581bf5c
--- /dev/null
+++ b/internal/metamorphic/crossversion/crossversion_test.go
@@ -0,0 +1,292 @@
+// Copyright 2022 The LevelDB-Go and Pebble Authors. All rights reserved. Use
+// of this source code is governed by a BSD-style license that can be found in
+// the LICENSE file.
+
+// Package crossversion builds on the metamorphic testing implemented in
+// internal/metamorphic, performing metamorphic testing across versions of
+// Pebble. This improves test coverage of upgrade and migration code paths.
+package crossversion
+
+import (
+	"bytes"
+	"context"
+	"flag"
+	"fmt"
+	"io"
+	"math/rand"
+	"os"
+	"os/exec"
+	"path/filepath"
+	"strconv"
+	"strings"
+	"testing"
+	"time"
+	"unicode"
+
+	"github.com/cockroachdb/errors"
+	"github.com/cockroachdb/pebble/internal/metamorphic"
+	"github.com/stretchr/testify/require"
+)
+
+var (
+	factor   int
+	seed     int64
+	versions pebbleVersions
+)
+
+func init() {
+	// NB: If you add new command-line flags, you should update the
+	// reproductionCommand function.
+	flag.Int64Var(&seed, "seed", 0,
+		`a pseudorandom number generator seed`)
+	flag.IntVar(&factor, "factor", 10,
+		`the number of data directories to carry forward
+from one version's run to the subsequent version's runs.`)
+	flag.Var(&versions, "version",
+		`a comma-separated 3-tuple defining a Pebble version to test.
+The expected format is <label>,<SHA>,<test-binary-path>.
+The label should be a human-readable label describing the
+version, for example, 'CRDB 22.1'. The SHA indicates the
+exact commit sha of the version, and may be abbreviated.
+The test binary path must point to a test binary of the
+internal/metamorphic package built on the indicated SHA.
+A test binary may be built with 'go test -c'.
+
+This flag should be provided multiple times to indicate
+the set of versions to test. The order of the versions
+is significant and database states generated from earlier
+versions will be used to initialize runs of subsequent
+versions.`)
+}
+
+func reproductionCommand() string {
+	return fmt.Sprintf("go test -v -run 'TestMetaCrossVersion' --seed %d --factor %d %s\n",
+		seed, factor, versions.String())
+}
+
+// TestMetaCrossVersion performs cross-version metamorphic testing.
+func TestMetaCrossVersion(t *testing.T) {
+	if seed == 0 {
+		seed = time.Now().UnixNano()
+	}
+	t.Logf("Test directory: %s\n", t.TempDir())
+	t.Logf("Reproduction:\n  %s\n", reproductionCommand())
+
+	// Print all the versions supplied and ensure all the test binaries
+	// actually exist before proceeding.
+	for i, v := range versions {
+		if len(v.SHA) > 8 {
+			// Use shortened SHAs for readability.
+			versions[i].SHA = versions[i].SHA[:8]
+		}
+		if _, err := os.Stat(v.TestBinaryPath); err != nil {
+			t.Fatal(err)
+		}
+		t.Logf("%d: %s", i, v.String())
+	}
+
+	// All randomness should be derived from `seed`. This makes reproducing a
+	// failure locally easier.
+	ctx := context.Background()
+	require.NoError(t, runCrossVersion(ctx, t, versions, seed, factor))
+}
+
+type pebbleVersion struct {
+	Label          string
+	SHA            string
+	TestBinaryPath string
+}
+
+type initialState struct {
+	desc string
+	path string
+}
+
+func (s initialState) String() string {
+	if s.desc == "" {
+		return "<empty>"
+	}
+	return s.desc
+}
+
+func runCrossVersion(
+	ctx context.Context, t *testing.T, versions pebbleVersions, seed int64, factor int,
+) error {
+	prng := rand.New(rand.NewSource(seed))
+	// Use prng to derive deterministic seeds to provide to the child
+	// metamorphic runs. The same seed is used for all runs on a particular
+	// Pebble version.
+	versionSeeds := make([]uint64, len(versions))
+	for i := range versions {
+		versionSeeds[i] = prng.Uint64()
+	}
+
+	rootDir := filepath.Join(t.TempDir(), strconv.FormatInt(seed, 10))
+	if err := os.MkdirAll(rootDir, os.ModePerm); err != nil {
+		return err
+	}
+
+	// The outer for loop executes once per version being tested. It takes a
+	// list of initial states, populated by the previous version. The inner loop
+	// executes once per initial state, running the metamorphic test against the
+	// initial state.
+	//
+	// The number of states that are carried forward from one version to the
+	// next is fixed by `factor`.
+	var buf bytes.Buffer
+	initialStates := []initialState{{}}
+	for i := range versions {
+		t.Logf("Running tests with version %s with %d initial state(s).", versions[i].SHA, len(initialStates))
+		var nextInitialStates []initialState
+		var histories []string
+		for j, s := range initialStates {
+			runID := fmt.Sprintf("%s_%d_%03d", versions[i].SHA, seed, j)
+
+			t.Logf("  Running test with version %s with initial state %s.", versions[i].SHA, s)
+			r := metamorphicTestRun{
+				seed:           versionSeeds[i],
+				dir:            filepath.Join(rootDir, runID),
+				vers:           versions[i],
+				initialState:   s,
+				testBinaryName: filepath.Base(versions[i].TestBinaryPath),
+			}
+			if err := os.MkdirAll(r.dir, os.ModePerm); err != nil {
+				return err
+			}
+			if err := os.Link(versions[i].TestBinaryPath, filepath.Join(r.dir, r.testBinaryName)); err != nil {
+				return err
+			}
+			err := r.run(ctx, &buf)
+			if err != nil {
+				t.Fatalf("Metamorphic test failed: %s\nOutput:%s\n", err, buf.String())
+			}
+
+			// dir is a directory containing the ops file and subdirectories for
+			// each run with a particular set of OPTIONS. For example:
+			//
+			// dir/
+			//   ops
+			//   random-000/
+			//   random-001/
+			//   ...
+			//   standard-000/
+			//   standard-001/
+			//   ...
+			dir := getRunDir(t, r.dir)
+			// subrunDirs contains the names of all dir's subdirectories.
+			subrunDirs := getDirs(t, dir)
+			for _, subrunDir := range subrunDirs {
+				// Record the subrun as an initial state for the next version.
+				nextInitialStates = append(nextInitialStates, initialState{
+					path: filepath.Join(dir, subrunDir),
+					desc: fmt.Sprintf("sha=%s-seed=%d-opts=%s(%s)", versions[i].SHA, versionSeeds[i], subrunDir, s.String()),
+				})
+				histories = append(histories, filepath.Join(dir, subrunDir, "history"))
+			}
+
+			buf.Reset()
+		}
+
+		// All the initial states described the same state and all of this
+		// version's metamorphic runs used the same seed, so all of the
+		// resulting histories should be identical.
+		if h, diff := metamorphic.CompareHistories(t, histories); h > 0 {
+			t.Fatalf("Metamorphic test divergence between %q and %q:\nDiff:\n%s",
+				nextInitialStates[0].desc, nextInitialStates[h].desc, diff)
+		}
+
+		// Prune the set of initial states we collected for this version, using
+		// the deterministic randomness of prng to pick which states we keep.
+		if len(nextInitialStates) > factor {
+			prng.Shuffle(len(nextInitialStates), func(i, j int) {
+				nextInitialStates[i], nextInitialStates[j] = nextInitialStates[j], nextInitialStates[i]
+			})
+			// Delete the states that we're not going to use.
+			for _, s := range nextInitialStates[factor:] {
+				require.NoError(t, os.RemoveAll(s.path))
+			}
+			nextInitialStates = nextInitialStates[:factor]
+		}
+		initialStates = nextInitialStates
+	}
+	return nil
+}
+
+type metamorphicTestRun struct {
+	seed           uint64
+	dir            string
+	vers           pebbleVersion
+	initialState   initialState
+	testBinaryName string
+}
+
+func (r *metamorphicTestRun) run(ctx context.Context, output io.Writer) error {
+	args := []string{
+		"-test.run", "TestMeta$",
+		"-seed", strconv.FormatUint(r.seed, 10),
+		"-keep",
+	}
+	if r.initialState.path != "" {
+		args = append(args,
+			"--initial-state", r.initialState.path,
+			"--initial-state-desc", r.initialState.desc)
+	}
+	cmd := exec.CommandContext(ctx, filepath.Join(r.dir, r.testBinaryName), args...)
+	cmd.Dir = r.dir
+	cmd.Stderr = output
+	cmd.Stdout = output
+	return cmd.Run()
+}
+
+func (v pebbleVersion) String() string {
+	return fmt.Sprintf("%s,%s,%s", v.Label, v.SHA, v.TestBinaryPath)
+}
+
+type pebbleVersions []pebbleVersion
+
+func (f *pebbleVersions) String() string {
+	var buf bytes.Buffer
+	for i, v := range *f {
+		if i > 0 {
+			fmt.Fprint(&buf, " ")
+		}
+		fmt.Fprintf(&buf, "--version %s", v.String())
+	}
+	return buf.String()
+}
+
+func (f *pebbleVersions) Set(value string) error {
+	// Expected format is `<label>,<sha>,<path>`.
+	fields := strings.FieldsFunc(value, func(r rune) bool { return r == ',' || unicode.IsSpace(r) })
+	if len(fields) != 3 {
+		return errors.Newf("unable to parse version %q", value)
+	}
+	*f = append(*f, pebbleVersion{
+		Label:          fields[0],
+		SHA:            fields[1],
+		TestBinaryPath: fields[2],
+	})
+	return nil
+}
+
+func getDirs(t testing.TB, dir string) (names []string) {
+	dirents, err := os.ReadDir(dir)
+	if err != nil {
+		t.Fatal(err)
+	}
+	for _, dirent := range dirents {
+		if dirent.IsDir() {
+			names = append(names, dirent.Name())
+		}
+	}
+	return names
+}
+
+func getRunDir(t testing.TB, dir string) string {
+	metaDir := filepath.Join(dir, "_meta")
+	dirs := getDirs(t, metaDir)
+	if len(dirs) != 1 {
+		t.Fatalf("expected 1 directory, found %d", len(dirs))
+	}
+	return filepath.Join(metaDir, dirs[0])
+}
diff --git a/internal/metamorphic/meta_test.go b/internal/metamorphic/meta_test.go
index 57a16c9a..7eb694ad 100644
--- a/internal/metamorphic/meta_test.go
+++ b/internal/metamorphic/meta_test.go
@@ -114,24 +114,14 @@ func testCompareRun(t *testing.T, compare string) {
 		return
 	}
 
-	base := readHistory(t, historyPaths[0])
-	for i := 1; i < len(historyPaths); i++ {
-		lines := readHistory(t, historyPaths[i])
-		diff := difflib.UnifiedDiff{
-			A:       base,
-			B:       lines,
-			Context: 5,
-		}
-		text, err := difflib.GetUnifiedDiffString(diff)
-		require.NoError(t, err)
-		if text != "" {
-			fmt.Printf(`
+	i, diff := CompareHistories(t, historyPaths)
+	if i != 0 {
+		fmt.Printf(`
 ===== DIFF =====
 %s/{%s,%s}
 %s
-`, *dir, runDirs[0], runDirs[i], text)
-			os.Exit(1)
-		}
+`, *dir, runDirs[0], runDirs[i], diff)
+		os.Exit(1)
 	}
 }
 
@@ -219,21 +209,6 @@ func testMetaRun(t *testing.T, runDir string, seed uint64, historyPath string) {
 	}
 }
 
-// Read a history file, stripping out lines that begin with a comment.
-func readHistory(t *testing.T, historyPath string) []string {
-	data, err := ioutil.ReadFile(historyPath)
-	require.NoError(t, err)
-	lines := difflib.SplitLines(string(data))
-	newLines := make([]string, 0, len(lines))
-	for _, line := range lines {
-		if strings.HasPrefix(line, "// ") {
-			continue
-		}
-		newLines = append(newLines, line)
-	}
-	return newLines
-}
-
 // TestMeta generates a random set of operations to run, then runs the test
 // with different options. See standardOptions() for the set of options that
 // are always run, and randomOptions() for the randomly generated options. The