Repository: cockroachdb/pebble
Pull request #3919 (2024-09-05 15:34:01)

treesteps: add depth limits
In many cases we want to focus on what operations do at the top few
levels of the hierarchy. For example, we may want to look at the
`mergingIter`/`levelIter` interaction but don't care about the
mechanics of what happens under the `singleLevelIterator`.

This commit introduces two options for `StartRecording`:
 - `MaxOpDepth` limits the maximum op depth; any operations or node
   updates for nodes below that depth are ignored.
 - `MaxTreeDepth` limits how many levels of the trees are shown;
   subtrees that are below that depth are replaced with a "..." node.
   `MaxTreeDepth` must be at least `MaxOpDepth`.

cockroach-teamcity: 

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


Patch:
diff --git a/go.mod b/go.mod
index 49e15189..9582f4d3 100644
--- a/go.mod
+++ b/go.mod
@@ -4,7 +4,7 @@ require (
 	github.com/DataDog/zstd v1.5.6-0.20230824185856-869dae002e5e
 	github.com/HdrHistogram/hdrhistogram-go v1.1.2
 	github.com/cespare/xxhash/v2 v2.2.0
-	github.com/cockroachdb/crlib v0.0.0-20240816115810-1c502cdb7c1d
+	github.com/cockroachdb/crlib v0.0.0-20240904210011-3474b320e3bf
 	github.com/cockroachdb/datadriven v1.0.3-0.20240530155848-7682d40af056
 	github.com/cockroachdb/errors v1.11.3
 	github.com/cockroachdb/fifo v0.0.0-20240606204812-0bbfbd93a7ce
diff --git a/go.sum b/go.sum
index 38a1155e..e5ac84d1 100644
--- a/go.sum
+++ b/go.sum
@@ -71,8 +71,8 @@ github.com/chzyer/readline v0.0.0-20180603132655-2972be24d48e/go.mod h1:nSuG5e5P
 github.com/chzyer/test v0.0.0-20180213035817-a1ea475d72b1/go.mod h1:Q3SI9o4m/ZMnBNeIyt5eFwwo7qiLfzFZmjNmxjkiQlU=
 github.com/client9/misspell v0.3.4/go.mod h1:qj6jICC3Q7zFZvVWo7KLAzC3yx5G7kyvSDkc90ppPyw=
 github.com/cncf/udpa/go v0.0.0-20191209042840-269d4d468f6f/go.mod h1:M8M6+tZqaGXZJjfX53e64911xZQV5JYwmTeXPW+k8Sc=
-github.com/cockroachdb/crlib v0.0.0-20240816115810-1c502cdb7c1d h1:IgQRpDBWe+tThngFMwhWpRJ/oEe5ZUJHq5nBNqeiIeI=
-github.com/cockroachdb/crlib v0.0.0-20240816115810-1c502cdb7c1d/go.mod h1:Gq51ZeKaFCXk6QwuGM0w1dnaOqc/F5zKT2zA9D6Xeac=
+github.com/cockroachdb/crlib v0.0.0-20240904210011-3474b320e3bf h1:alUhMh1MUl/WTVq56zeAGOiCR3YyIVblOp+mnNDzWIQ=
+github.com/cockroachdb/crlib v0.0.0-20240904210011-3474b320e3bf/go.mod h1:Gq51ZeKaFCXk6QwuGM0w1dnaOqc/F5zKT2zA9D6Xeac=
 github.com/cockroachdb/datadriven v1.0.3-0.20240530155848-7682d40af056 h1:slXychO2uDM6hYRu4c0pD0udNI8uObfeKN6UInWViS8=
 github.com/cockroachdb/datadriven v1.0.3-0.20240530155848-7682d40af056/go.mod h1:a9RdTaap04u637JoCzcUoIcDmvwSUtcUFtT/C3kJlTU=
 github.com/cockroachdb/errors v1.11.3 h1:5bA+k2Y6r+oz/6Z/RFlNeVCesGARKuC6YymtcDrbC/I=
diff --git a/internal/treesteps/node_state.go b/internal/treesteps/node_state.go
index 60f6f8ef..5cb04ef7 100644
--- a/internal/treesteps/node_state.go
+++ b/internal/treesteps/node_state.go
@@ -12,6 +12,7 @@ import (
 
 type nodeState struct {
 	recording *Recording
+	depth     int
 	node      Node
 	name      string
 
@@ -41,9 +42,16 @@ func buildTree(n *nodeState) TreeNode {
 			}
 		}
 	}
-	for i := range info.children {
-		c := nodeStateLocked(n.recording, info.children[i])
-		t.Children = append(t.Children, buildTree(c))
+	if n.depth < n.recording.maxTreeDepth {
+		for i := range info.children {
+			c := nodeStateLocked(n.recording, info.children[i])
+			c.depth = n.depth + 1
+			t.Children = append(t.Children, buildTree(c))
+		}
+	} else {
+		for range info.children {
+			t.Children = append(t.Children, TreeNode{Name: "..."})
+		}
 	}
 	return t
 }
diff --git a/internal/treesteps/tree_steps.go b/internal/treesteps/tree_steps.go
index 8bc037a5..f428f2e4 100644
--- a/internal/treesteps/tree_steps.go
+++ b/internal/treesteps/tree_steps.go
@@ -28,11 +28,18 @@ import (
 // in-progress recording (this applies to all nodes in the hierarchy).
 //
 // See SegmentTree in tree_steps_test.go for an example.
-func StartRecording(root Node, name string) *Recording {
+func StartRecording(root Node, name string, opts ...RecordingOption) *Recording {
 	mu.Lock()
 	defer mu.Unlock()
 	mu.recordingInProgress.Store(true)
-	w := &Recording{name: name}
+	w := &Recording{
+		name:         name,
+		maxTreeDepth: 20,
+		maxOpDepth:   10,
+	}
+	for _, o := range opts {
+		o(w)
+	}
 
 	if mu.nodeMap == nil {
 		mu.nodeMap = make(map[Node]*nodeState)
@@ -42,6 +49,31 @@ func StartRecording(root Node, name string) *Recording {
 	return w
 }
 
+// RecordingOption is an optional argument to StartRecording.
+type RecordingOption func(*Recording)
+
+// MaxTreeDepth configures a recording to only show trees up to a certain depth.
+// Operations and node updates below that level are ignored.
+func MaxTreeDepth(maxTreeDepth int) RecordingOption {
+	return func(r *Recording) {
+		r.maxTreeDepth = maxTreeDepth
+		if r.maxOpDepth > r.maxTreeDepth {
+			r.maxOpDepth = r.maxTreeDepth
+		}
+	}
+}
+
+// MaxOpDepth configures a recording to only show operations for nodes up to a
+// certain depth. Operations and node updates below that level are ignored.
+func MaxOpDepth(maxOpDepth int) RecordingOption {
+	return func(r *Recording) {
+		r.maxOpDepth = maxOpDepth
+		if r.maxTreeDepth < r.maxOpDepth {
+			r.maxTreeDepth = r.maxOpDepth
+		}
+	}
+}
+
 // NodeUpdated can be used to trigger a new step in any recording that involves
 // the given node. It can be used when the state of the node changed in a
 // significant way. The reason is optional and will show up in the step
@@ -53,6 +85,12 @@ func NodeUpdated(n Node, reason string) {
 	mu.Lock()
 	defer mu.Unlock()
 	if ns, ok := mu.nodeMap[n]; ok {
+		if ns.depth > ns.recording.maxOpDepth {
+			// Ignore node updates below the op depth (if we are not stepping through
+			// operations on these nodes, we should not step through their updates
+			// either).
+			return
+		}
 		if reason == "" {
 			reason = " updated"
 		} else {
@@ -103,9 +141,11 @@ func (ni *NodeInfo) AddChildren(nodes ...Node) {
 // Recording captures the step-by-step propagation of operations. See
 // StartRecording.
 type Recording struct {
-	name  string
-	root  *nodeState
-	steps []Step
+	name         string
+	maxTreeDepth int
+	maxOpDepth   int
+	root         *nodeState
+	steps        []Step
 }
 
 // Finish completes the recording and returns the recorded steps.
@@ -167,6 +207,10 @@ func StartOpf(node Node, format string, args ...any) *Op {
 	if !ok {
 		return nil
 	}
+	if ns.depth > ns.recording.maxOpDepth {
+		// Ignore any ops for nodes below maxOpDepth.
+		return nil
+	}
 	op := &Op{
 		details:   fmt.Sprintf(format, args...),
 		nodeState: ns,
diff --git a/sstable/reader.go b/sstable/reader.go
index 344e9ea7..c9b8e383 100644
--- a/sstable/reader.go
+++ b/sstable/reader.go
@@ -559,29 +559,9 @@ func (r *Reader) readMetaindex(
 	}
 
 	for name, fp := range filters {
-		types := []struct {
-			ftype  FilterType
-			prefix string
-		}{
-			{TableFilter, "fullfilter."},
-		}
-		var done bool
-		for _, t := range types {
-			if bh, ok := meta[t.prefix+name]; ok {
-				r.filterBH = bh
-
-				switch t.ftype {
-				case TableFilter:
-					r.tableFilter = newTableFilterReader(fp, r.filterMetricsTracker)
-				default:
-					return base.CorruptionErrorf("unknown filter type: %v", errors.Safe(t.ftype))
-				}
-
-				done = true
-				break
-			}
-		}
-		if done {
+		if bh, ok := meta["fullfilter."+name]; ok {
+			r.filterBH = bh
+			r.tableFilter = newTableFilterReader(fp, r.filterMetricsTracker)
 			break
 		}
 	}


Test patch:
diff --git a/compaction_picker_test.go b/compaction_picker_test.go
index 481f4a6c..148a2785 100644
--- a/compaction_picker_test.go
+++ b/compaction_picker_test.go
@@ -15,6 +15,7 @@ import (
 	"testing"
 	"time"
 
+	"github.com/cockroachdb/crlib/crstrings"
 	"github.com/cockroachdb/datadriven"
 	"github.com/cockroachdb/errors"
 	"github.com/cockroachdb/pebble/internal/base"
@@ -864,10 +865,7 @@ func TestCompactionPickerPickReadTriggered(t *testing.T) {
 			return buf.String()
 
 		case "add-read-compaction":
-			for _, line := range strings.Split(td.Input, "\n") {
-				if line == "" {
-					continue
-				}
+			for _, line := range crstrings.Lines(td.Input) {
 				parts := strings.Split(line, " ")
 				if len(parts) != 3 {
 					return "error: malformed data for add-read-compaction. usage: <level>: <start>-<end> <filenum>"
diff --git a/compaction_test.go b/compaction_test.go
index edd6283c..5fd5f186 100644
--- a/compaction_test.go
+++ b/compaction_test.go
@@ -20,6 +20,7 @@ import (
 	"testing"
 	"time"
 
+	"github.com/cockroachdb/crlib/crstrings"
 	"github.com/cockroachdb/datadriven"
 	"github.com/cockroachdb/errors"
 	"github.com/cockroachdb/errors/oserror"
@@ -1705,10 +1706,7 @@ func TestCompactionReadTriggeredQueue(t *testing.T) {
 				queue = &readCompactionQueue{}
 				return "(success)"
 			case "add-compaction":
-				for _, line := range strings.Split(td.Input, "\n") {
-					if line == "" {
-						continue
-					}
+				for _, line := range crstrings.Lines(td.Input) {
 					parts := strings.Split(line, " ")
 
 					if len(parts) != 3 {
@@ -1824,10 +1822,7 @@ func TestCompactionReadTriggered(t *testing.T) {
 			case "add-read-compaction":
 				d.mu.Lock()
 				td.MaybeScanArgs(t, "flushing", &d.mu.compact.flushing)
-				for _, line := range strings.Split(td.Input, "\n") {
-					if line == "" {
-						continue
-					}
+				for _, line := range crstrings.Lines(td.Input) {
 					parts := strings.Split(line, " ")
 					if len(parts) != 3 {
 						return "error: malformed data for add-read-compaction. usage: <level>: <start>-<end> <filenum>"
@@ -1947,11 +1942,8 @@ func TestCompactionAllowZeroSeqNum(t *testing.T) {
 				d.mu.Unlock()
 
 				var buf bytes.Buffer
-				for _, line := range strings.Split(td.Input, "\n") {
+				for _, line := range crstrings.Lines(td.Input) {
 					parts := strings.Fields(line)
-					if len(parts) == 0 {
-						continue
-					}
 					c.flushing = nil
 					c.startLevel.level = -1
 
diff --git a/internal/treesteps/testdata/segment_tree b/internal/treesteps/testdata/segment_tree
index f5848286..bd6ff477 100644
--- a/internal/treesteps/testdata/segment_tree
+++ b/internal/treesteps/testdata/segment_tree
@@ -736,3 +736,11 @@ https://raduberinde.github.io/treesteps/decode.html#eJzs2r1u2zAQB_C9T3Hg1AIaREv-
 sum x1=2 x2=7 url
 ----
 https://raduberinde.github.io/treesteps/decode.html#eJzs2ztu20wQwPH-O8WA1ReABZ-SIsBXSON0NgsBYRwB0SYQpSoIYKRInUJlTqeTBHpYj-XMMkgQgJL-leGZ5Y52Z_grLPhL9GYyq6NxdF8_zWq3kLfzupZmOYvi6H5Rf95km2j8EE3ddDGdfIziqFnO5JMTl0izmMwX9buTWKrEciU2UmPvp27afPAeVoKF8nShLUy1YKY8Xaox5eGBdmjthKn6yQf6B1KCyTFY7VqxbYNLHp2sVz_Xq-f16lnmE_dUj-UhjWVUnWWa5WwsaXoWc7tfv4mIvkdRaQt2W2kZl59G7X2zKrBuu30SWOCGStIulmrF9j9WXTVfFrhRKyl6xUw9nnTVOxQqjlGjQn7eGAl3x0u7162UcXV5LHm7jHZx7WqH06SJlzPOVChnsu_ssH326Kwdy_0roF5P0k648hgzbqSMZVCZq1o7-2O7ffvkd6a2jKVsF7JmVu-MSzMvZ1zUQDmVdvWnRzsUGbzEjM2Hp13QWpEYSZfmXsa4q2EsQ79C8KZaI1qcZYyDjFoH0e4oeXRRHLlEZP39xyb0fxbL8BVGYzRGYzRGh4f0Yo3W9oJsyIZsyO4YV8i-TrID-yM4giM4giM4gksPBO86qNF5QAd0fYoBXbkwQAf0rmL_BnS5U9Yb3Qd1UNcnGdSVCwP1nqGuWnc1sKM4iqO4318Uv3jFIfuvyTZbZBREcARHcARH8J4KLncBgFEcxVH81hU_JwLJ-yI5bIffC9iG7VtiG6Mx-qKNbr8MRgHIhmzIhmzIvmKyza0RXJsBBEdwBEfw_goudyGAYRzGYRzGYbxvjEP2H5Bt9MOoheAIjuDq5CM4gvuduDLBw5UAHdABHdAB_VJB3_-7oHTPNaiDOqiDurklqIdRV6jlby0ojuIoHlDc-2YSyv128C1nX9zejGoK3uB9u3gDNVD3DOrq63-_AgAA__9MOM8F
+
+sum x1=2 x2=7 url max-tree-depth=2
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzs2c9q6kAUBvD9fYrDrO6FIElM4iXgK9yNd6dZBDq1gea0mLgqBemi6y6y7NPlSUr8UxM9MyjUVuVb9pvJyZzJ_GCoT-pfmmsVq5Ge5ppL-j_Tmop5rhw1KvVjM1qoeKwyzsosvVeOKuY5PTCxS0WZzkp908o8IeuL2W3GWXHXCQNhYiBN9KTQF54OxUx4OBImRvJbhNDdhslq25Zbxu6Eqa7e62pRVwuapTzVMY09h_4mnZFinsfkeZ2MV3--EJFcI0ikCatS0gj326m5rp9Y5i3Lu5YJvV5PGK3k0U3MwTYleWH9bsNk75osiyJ5SZ9r8SdsWkS4_nLi2939AQ63mWHDQ4eixDhrr7K422TZ651uOdpkhhYH7RalPl3DYOt10g4rR7FLVL--NWV--w4N_kAHdEDHSXRItYAFWIDlB7BY6sMO7MDO4XZoaD328AM_8HMhFzVj67ADO7BzjB0aWo4-_MDPIX66h-j6DQEMwOB_zpegY_8bAguwAMt3YzGWhh3YgZ1j7DSXbfPRByAAAqBzv6kZmoUd2IGd4-ysf9eDH_j5Kj87N6xrRHRGYprd9sDmAtmAyCmIJM-_PgIAAP__yqMz1A==
+
+sum x1=2 x2=7 url max-op-depth=1
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzsl7uu00AQhnueYrQVSFvs-hIHS7wCTegSF5ZYgiU8oNipEFJEQU3hkqfzkyDn4tjeGeeUjs5UR2f-0fyey35SfqqPeelUqjZuXzqs4dPBOaiOpdJqU7sfnVqpdKsKLOoi_6a0qo4lfEdAA1WdH2r3eRCzZOxLgUX1dRQMiMSASjT3YHb5pPPnoNkhtM2_tjm1zQkOOe5dClurYZ2NlOpYpmDtKIaXf38DAF0jyqiESylKwXAY5esG2UzeubyZScCEEHkzS5ld_zSPPG8JuPZEoB0Dsj145NcbRfco4xCOFwPz25nI-N6TmNGFGkLfhhqc79Z3Y81EY3qKiJ74mfXlgx1yFePrEyDHY3wB43uMmUisYZWxWV7l6dmeXx-85GpjDbFvxN0svRm0wURjBrUiuqJGP2ytN1ndYkzxZLgFahWGEdGGE4WZVaIhmTrMTso70WikMI2svUaoGZkdKq3QALR__naht4GG5J0wWhgtjBZGC6Pnj_RpGU3VEmQLsgXZguwH5yrIXgSy4QPNXsG2YFuwLdgWbC8D28JoYfRTM9p_DIyBIFuQLcgWZAuyF4bs7qciwV_htnB7adzuTtUKvAXerxfeAmoB9cJAnf168z8AAP__JXpIKQ==
diff --git a/internal/treesteps/tree_steps_test.go b/internal/treesteps/tree_steps_test.go
index 16b65d68..e072b1ce 100644
--- a/internal/treesteps/tree_steps_test.go
+++ b/internal/treesteps/tree_steps_test.go
@@ -133,6 +133,13 @@ func TestSegmentTree(t *testing.T) {
 	var tree *SegmentTree
 	datadriven.RunTest(t, "testdata/segment_tree", func(t *testing.T, td *datadriven.TestData) string {
 		var r *Recording
+		var opts []RecordingOption
+		if val := 0; td.MaybeScanArgs(t, "max-tree-depth", &val) {
+			opts = append(opts, MaxTreeDepth(val))
+		}
+		if val := 0; td.MaybeScanArgs(t, "max-op-depth", &val) {
+			opts = append(opts, MaxOpDepth(val))
+		}
 		switch td.Cmd {
 		case "init":
 			var xRange int
@@ -144,14 +151,14 @@ func TestSegmentTree(t *testing.T) {
 			var x, delta int
 			td.ScanArgs(t, "x", &x)
 			td.ScanArgs(t, "delta", &delta)
-			r = StartRecording(tree.Root(), "Segment Tree add")
+			r = StartRecording(tree.Root(), "Segment Tree add", opts...)
 			tree.Add(x, delta)
 
 		case "sum":
 			var x1, x2 int
 			td.ScanArgs(t, "x1", &x1)
 			td.ScanArgs(t, "x2", &x2)
-			r = StartRecording(tree.Root(), "Segment Tree sum")
+			r = StartRecording(tree.Root(), "Segment Tree sum", opts...)
 			tree.Sum(x1, x2)
 
 		default:
diff --git a/replay/workload_capture_test.go b/replay/workload_capture_test.go
index 30ce9392..b5f8c6e6 100644
--- a/replay/workload_capture_test.go
+++ b/replay/workload_capture_test.go
@@ -11,6 +11,7 @@ import (
 	"time"
 	"unicode"
 
+	"github.com/cockroachdb/crlib/crstrings"
 	"github.com/cockroachdb/datadriven"
 	"github.com/cockroachdb/pebble"
 	"github.com/cockroachdb/pebble/internal/base"
@@ -109,11 +110,7 @@ func TestWorkloadCollector(t *testing.T) {
 				return buf.String()
 			case "ingest":
 				ingestInfo := pebble.TableIngestInfo{}
-				for _, line := range strings.Split(td.Input, "\n") {
-					if line == "" {
-						continue
-					}
-
+				for _, line := range crstrings.Lines(td.Input) {
 					parts := strings.FieldsFunc(line, func(r rune) bool { return unicode.IsSpace(r) || r == ':' })
 					tableInfo := pebble.TableInfo{Size: 10 << 10}
 					fileNum, err := strconv.ParseUint(parts[0], 10, 64)
diff --git a/snapshot_test.go b/snapshot_test.go
index cb3b56a7..8e03140d 100644
--- a/snapshot_test.go
+++ b/snapshot_test.go
@@ -15,6 +15,7 @@ import (
 	"testing"
 	"time"
 
+	"github.com/cockroachdb/crlib/crstrings"
 	"github.com/cockroachdb/datadriven"
 	"github.com/cockroachdb/errors"
 	"github.com/cockroachdb/pebble/internal/base"
@@ -88,11 +89,8 @@ func testSnapshotImpl(t *testing.T, newSnapshot func(d *DB) Reader) {
 			}
 			snapshots = make(map[string]Reader)
 
-			for _, line := range strings.Split(td.Input, "\n") {
+			for _, line := range crstrings.Lines(td.Input) {
 				parts := strings.Fields(line)
-				if len(parts) == 0 {
-					continue
-				}
 				var err error
 				switch parts[0] {
 				case "set":
@@ -160,11 +158,8 @@ func testSnapshotImpl(t *testing.T, newSnapshot func(d *DB) Reader) {
 			defer iter.Close()
 
 			var b bytes.Buffer
-			for _, line := range strings.Split(td.Input, "\n") {
+			for _, line := range crstrings.Lines(td.Input) {
 				parts := strings.Fields(line)
-				if len(parts) == 0 {
-					continue
-				}
 				switch parts[0] {
 				case "first":
 					iter.First()
diff --git a/sstable/data_test.go b/sstable/data_test.go
index 864751ea..e81f782d 100644
--- a/sstable/data_test.go
+++ b/sstable/data_test.go
@@ -12,6 +12,7 @@ import (
 	"strconv"
 	"strings"
 
+	"github.com/cockroachdb/crlib/crstrings"
 	"github.com/cockroachdb/datadriven"
 	"github.com/cockroachdb/errors"
 	"github.com/cockroachdb/pebble/bloom"
@@ -254,11 +255,8 @@ func runIterCmd(
 			}
 		}
 	}
-	for _, line := range strings.Split(td.Input, "\n") {
+	for _, line := range crstrings.Lines(td.Input) {
 		parts := strings.Fields(line)
-		if len(parts) == 0 {
-			continue
-		}
 		switch parts[0] {
 		case "seek-ge":
 			if len(parts) < 2 || len(parts) > 3 {