Repository: cockroachdb/pebble
Pull request #3921 (2024-09-05 21:08:40)

sstable: refactor sstable layout facilities, add decodeLayout
This commit refactors some of the code surrounding the parsing and construction of a sstable.Layout. It also adds a new decodeLayout helper that parses an in-memory sstable's Layout without opening a Reader. Future work will use decodeLayout to describe the binary layout of a sstable with columnar blocks in tests.

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/3921)
<!-- Reviewable:end -->


Patch:
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/block/block.go b/sstable/block/block.go
index e23f38d5..b18a6a6b 100644
--- a/sstable/block/block.go
+++ b/sstable/block/block.go
@@ -175,6 +175,8 @@ type DataBlockIterator interface {
 // iterators over index blocks. It's currently satisifed by the
 // *rowblk.IndexIter type.
 type IndexBlockIterator interface {
+	// Init initializes the block iterator from the provided block.
+	Init(base.Compare, base.Split, []byte, IterTransforms) error
 	// InitHandle initializes an iterator from the provided block handle.
 	InitHandle(base.Compare, base.Split, BufferHandle, IterTransforms) error
 	// Valid returns true if the iterator is currently positioned at a valid
diff --git a/sstable/colblk/index_block.go b/sstable/colblk/index_block.go
index 83b312c3..3f815d4c 100644
--- a/sstable/colblk/index_block.go
+++ b/sstable/colblk/index_block.go
@@ -163,9 +163,19 @@ type IndexIter struct {
 // Assert that IndexIter satisfies the block.IndexBlockIterator interface.
 var _ block.IndexBlockIterator = (*IndexIter)(nil)
 
-// Init initializes an index iterator from the provided reader.
-func (i *IndexIter) Init(r *IndexReader) {
-	*i = IndexIter{r: r, n: int(r.br.header.Rows)}
+// InitReader initializes an index iterator from the provided reader.
+func (i *IndexIter) InitReader(r *IndexReader) {
+	*i = IndexIter{r: r, n: int(r.br.header.Rows), allocReader: i.allocReader}
+}
+
+// Init initializes an iterator from the provided block data slice.
+func (i *IndexIter) Init(
+	cmp base.Compare, split base.Split, blk []byte, transforms block.IterTransforms,
+) error {
+	// TODO(jackson): Handle the transforms.
+	i.allocReader.Init(blk)
+	i.InitReader(&i.allocReader)
+	return nil
 }
 
 // InitHandle initializes an iterator from the provided block handle.
@@ -181,9 +191,7 @@ func (i *IndexIter) InitHandle(
 	// overhead can be material.)
 	i.h.Release()
 	i.h = block
-	i.allocReader.Init(i.h.Get())
-	i.r = &i.allocReader
-	return nil
+	return i.Init(cmp, split, i.h.Get(), transforms)
 }
 
 // RowIndex returns the index of the block entry at the iterator's current
diff --git a/sstable/layout.go b/sstable/layout.go
index a7356f6e..0be0593f 100644
--- a/sstable/layout.go
+++ b/sstable/layout.go
@@ -14,11 +14,13 @@ import (
 	"slices"
 	"unsafe"
 
+	"github.com/cockroachdb/errors"
 	"github.com/cockroachdb/pebble/internal/base"
 	"github.com/cockroachdb/pebble/internal/bytealloc"
 	"github.com/cockroachdb/pebble/internal/sstableinternal"
 	"github.com/cockroachdb/pebble/objstorage"
 	"github.com/cockroachdb/pebble/sstable/block"
+	"github.com/cockroachdb/pebble/sstable/colblk"
 	"github.com/cockroachdb/pebble/sstable/rowblk"
 )
 
@@ -31,7 +33,7 @@ type Layout struct {
 	Data       []block.HandleWithProperties
 	Index      []block.Handle
 	TopIndex   block.Handle
-	Filter     block.Handle
+	Filter     []NamedBlockHandle
 	RangeDel   block.Handle
 	RangeKey   block.Handle
 	ValueBlock []block.Handle
@@ -42,59 +44,75 @@ type Layout struct {
 	Format     TableFormat
 }
 
-// Describe returns a description of the layout. If the verbose parameter is
-// true, details of the structure of each block are returned as well.
-func (l *Layout) Describe(
-	w io.Writer, verbose bool, r *Reader, fmtRecord func(key *base.InternalKey, value []byte),
-) {
-	ctx := context.TODO()
-	type namedBlockHandle struct {
-		block.Handle
-		name string
+// NamedBlockHandle holds a block.Handle and corresponding name.
+type NamedBlockHandle struct {
+	block.Handle
+	Name string
+}
+
+// FilterByName retrieves the block handle of the named filter, if it exists.
+// The provided the name should be the name as it appears in the metaindex
+// block.
+func (l *Layout) FilterByName(name string) (block.Handle, bool) {
+	for i := range l.Filter {
+		if l.Filter[i].Name == name {
+			return l.Filter[i].Handle, true
+		}
 	}
-	var blocks []namedBlockHandle
+	return block.Handle{}, false
+}
 
+func (l *Layout) orderedBlocks() []NamedBlockHandle {
+	var blocks []NamedBlockHandle
 	for i := range l.Data {
-		blocks = append(blocks, namedBlockHandle{l.Data[i].Handle, "data"})
+		blocks = append(blocks, NamedBlockHandle{l.Data[i].Handle, "data"})
 	}
 	for i := range l.Index {
-		blocks = append(blocks, namedBlockHandle{l.Index[i], "index"})
+		blocks = append(blocks, NamedBlockHandle{l.Index[i], "index"})
 	}
 	if l.TopIndex.Length != 0 {
-		blocks = append(blocks, namedBlockHandle{l.TopIndex, "top-index"})
-	}
-	if l.Filter.Length != 0 {
-		blocks = append(blocks, namedBlockHandle{l.Filter, "filter"})
+		blocks = append(blocks, NamedBlockHandle{l.TopIndex, "top-index"})
 	}
+	blocks = append(blocks, l.Filter...)
 	if l.RangeDel.Length != 0 {
-		blocks = append(blocks, namedBlockHandle{l.RangeDel, "range-del"})
+		blocks = append(blocks, NamedBlockHandle{l.RangeDel, "range-del"})
 	}
 	if l.RangeKey.Length != 0 {
-		blocks = append(blocks, namedBlockHandle{l.RangeKey, "range-key"})
+		blocks = append(blocks, NamedBlockHandle{l.RangeKey, "range-key"})
 	}
 	for i := range l.ValueBlock {
-		blocks = append(blocks, namedBlockHandle{l.ValueBlock[i], "value-block"})
+		blocks = append(blocks, NamedBlockHandle{l.ValueBlock[i], "value-block"})
 	}
 	if l.ValueIndex.Length != 0 {
-		blocks = append(blocks, namedBlockHandle{l.ValueIndex, "value-index"})
+		blocks = append(blocks, NamedBlockHandle{l.ValueIndex, "value-index"})
 	}
 	if l.Properties.Length != 0 {
-		blocks = append(blocks, namedBlockHandle{l.Properties, "properties"})
+		blocks = append(blocks, NamedBlockHandle{l.Properties, "properties"})
 	}
 	if l.MetaIndex.Length != 0 {
-		blocks = append(blocks, namedBlockHandle{l.MetaIndex, "meta-index"})
+		blocks = append(blocks, NamedBlockHandle{l.MetaIndex, "meta-index"})
 	}
 	if l.Footer.Length != 0 {
 		if l.Footer.Length == levelDBFooterLen {
-			blocks = append(blocks, namedBlockHandle{l.Footer, "leveldb-footer"})
+			blocks = append(blocks, NamedBlockHandle{l.Footer, "leveldb-footer"})
 		} else {
-			blocks = append(blocks, namedBlockHandle{l.Footer, "footer"})
+			blocks = append(blocks, NamedBlockHandle{l.Footer, "footer"})
 		}
 	}
-
-	slices.SortFunc(blocks, func(a, b namedBlockHandle) int {
+	slices.SortFunc(blocks, func(a, b NamedBlockHandle) int {
 		return cmp.Compare(a.Offset, b.Offset)
 	})
+	return blocks
+}
+
+// Describe returns a description of the layout. If the verbose parameter is
+// true, details of the structure of each block are returned as well.
+func (l *Layout) Describe(
+	w io.Writer, verbose bool, r *Reader, fmtRecord func(key *base.InternalKey, value []byte),
+) {
+	ctx := context.TODO()
+
+	blocks := l.orderedBlocks()
 	// TODO(jackson): This function formats offsets within blocks by adding the
 	// block's offset. A block's offset is an offset in the physical, compressed
 	// file whereas KV pairs offsets are within the uncompressed block. This is
@@ -103,20 +121,20 @@ func (l *Layout) Describe(
 
 	for i := range blocks {
 		b := &blocks[i]
-		fmt.Fprintf(w, "%10d  %s (%d)\n", b.Offset, b.name, b.Length)
+		fmt.Fprintf(w, "%10d  %s (%d)\n", b.Offset, b.Name, b.Length)
 
 		if !verbose {
 			continue
 		}
-		if b.name == "filter" {
+		if b.Name == "filter" {
 			continue
 		}
 
-		if b.name == "footer" || b.name == "leveldb-footer" {
+		if b.Name == "footer" || b.Name == "leveldb-footer" {
 			trailer, offset := make([]byte, b.Length), b.Offset
 			_ = r.readable.ReadAt(ctx, trailer, int64(offset))
 
-			if b.name == "footer" {
+			if b.Name == "footer" {
 				checksumType := block.ChecksumType(trailer[0])
 				fmt.Fprintf(w, "%10d    checksum type: %s\n", offset, checksumType)
 				trailer, offset = trailer[1:], offset+1
@@ -135,14 +153,14 @@ func (l *Layout) Describe(
 			fmt.Fprintf(w, "%10d    [padding]\n", offset)
 
 			trailing := 12
-			if b.name == "leveldb-footer" {
+			if b.Name == "leveldb-footer" {
 				trailing = 8
 			}
 
 			offset += uint64(len(trailer) - trailing)
 			trailer = trailer[len(trailer)-trailing:]
 
-			if b.name == "footer" {
+			if b.Name == "footer" {
 				version := trailer[:4]
 				fmt.Fprintf(w, "%10d    version: %d\n", offset, binary.LittleEndian.Uint32(version))
 				trailer, offset = trailer[4:], offset+4
@@ -171,7 +189,7 @@ func (l *Layout) Describe(
 		}
 
 		var lastKey InternalKey
-		switch b.name {
+		switch b.Name {
 		case "data", "range-del", "range-key":
 			iter, _ := rowblk.NewIter(r.Compare, r.Split, h.Get(), NoTransforms)
 			iter.Describe(w, b.Offset, func(w io.Writer, key *base.InternalKey, value []byte, enc rowblk.KVEncoding) {
@@ -210,7 +228,7 @@ func (l *Layout) Describe(
 					}
 				}
 
-				if b.name == "data" {
+				if b.Name == "data" {
 					if base.InternalCompare(r.Compare, lastKey, *key) >= 0 {
 						fmt.Fprintf(w, "              WARNING: OUT OF ORDER KEYS!\n")
 					}
@@ -286,6 +304,198 @@ func (l *Layout) Describe(
 	fmt.Fprintf(w, "%10d  EOF\n", last.Offset+last.Length)
 }
 
+func decodeLayout(comparer *base.Comparer, data []byte) (Layout, error) {
+	foot, err := parseFooter(data, 0, int64(len(data)))
+	if err != nil {
+		return Layout{}, err
+	}
+	decompressedMeta, err := decompressInMemory(data, foot.metaindexBH)
+	if err != nil {
+		return Layout{}, errors.Wrap(err, "decompressing metaindex")
+	}
+	meta, vbih, err := decodeMetaindex(decompressedMeta)
+	if err != nil {
+		return Layout{}, err
+	}
+	layout := Layout{
+		MetaIndex:  foot.metaindexBH,
+		Properties: meta[metaPropertiesName],
+		RangeDel:   meta[metaRangeDelV2Name],
+		RangeKey:   meta[metaRangeKeyName],
+		ValueIndex: vbih.h,
+		Footer:     foot.footerBH,
+		Format:     foot.format,
+	}
+	var props Properties
+	decompressedProps, err := decompressInMemory(data, layout.Properties)
+	if err != nil {
+		return Layout{}, errors.Wrap(err, "decompressing properties")
+	}
+	if err := props.load(decompressedProps, map[string]struct{}{}); err != nil {
+		return Layout{}, err
+	}
+
+	if props.IndexType == twoLevelIndex {
+		decompressed, err := decompressInMemory(data, foot.indexBH)
+		if err != nil {
+			return Layout{}, errors.Wrap(err, "decompressing two-level index")
+		}
+		layout.TopIndex = foot.indexBH
+		topLevelIter, err := newIndexIter(foot.format, comparer, decompressed)
+		if err != nil {
+			return Layout{}, err
+		}
+		err = forEachIndexEntry(topLevelIter, func(bhp block.HandleWithProperties) {
+			layout.Index = append(layout.Index, bhp.Handle)
+		})
+		if err != nil {
+			return Layout{}, err
+		}
+	} else {
+		layout.Index = append(layout.Index, foot.indexBH)
+	}
+	for _, indexBH := range layout.Index {
+		decompressed, err := decompressInMemory(data, indexBH)
+		if err != nil {
+			return Layout{}, errors.Wrap(err, "decompressing index block")
+		}
+		indexIter, err := newIndexIter(foot.format, comparer, decompressed)
+		if err != nil {
+			return Layout{}, err
+		}
+		err = forEachIndexEntry(indexIter, func(bhp block.HandleWithProperties) {
+			layout.Data = append(layout.Data, bhp)
+		})
+		if err != nil {
+			return Layout{}, err
+		}
+	}
+
+	if layout.ValueIndex.Length > 0 {
+		vbiBlock, err := decompressInMemory(data, layout.ValueIndex)
+		if err != nil {
+			return Layout{}, errors.Wrap(err, "decompressing value index")
+		}
+		layout.ValueBlock, err = decodeValueBlockIndex(vbiBlock, vbih)
+		if err != nil {
+			return Layout{}, err
+		}
+	}
+
+	return layout, nil
+}
+
+func decompressInMemory(data []byte, bh block.Handle) ([]byte, error) {
+	typ := block.CompressionIndicator(data[bh.Offset+bh.Length])
+	var decompressed []byte
+	if typ == block.NoCompressionIndicator {
+		return data[bh.Offset : bh.Offset+bh.Length], nil
+	}
+	// Decode the length of the decompressed value.
+	decodedLen, prefixLen, err := block.DecompressedLen(typ, data[bh.Offset:bh.Offset+bh.Length])
+	if err != nil {
+		return nil, err
+	}
+	decompressed = make([]byte, decodedLen)
+	if err := block.DecompressInto(typ, data[int(bh.Offset)+prefixLen:bh.Offset+bh.Length], decompressed); err != nil {
+		return nil, err
+	}
+	return decompressed, nil
+}
+
+func newIndexIter(
+	tableFormat TableFormat, comparer *base.Comparer, data []byte,
+) (block.IndexBlockIterator, error) {
+	var iter block.IndexBlockIterator
+	var err error
+	if tableFormat <= TableFormatPebblev4 {
+		iter = new(rowblk.IndexIter)
+		err = iter.Init(comparer.Compare, comparer.Split, data, block.NoTransforms)
+	} else {
+		iter = new(colblk.IndexIter)
+		err = iter.Init(comparer.Compare, comparer.Split, data, block.NoTransforms)
+	}
+	if err != nil {
+		return nil, err
+	}
+	return iter, nil
+}
+
+func forEachIndexEntry(
+	indexIter block.IndexBlockIterator, fn func(block.HandleWithProperties),
+) error {
+	for v := indexIter.First(); v; v = indexIter.Next() {
+		bhp, err := indexIter.BlockHandleWithProperties()
+		if err != nil {
+			return err
+		}
+		fn(bhp)
+	}
+	return indexIter.Close()
+}
+
+func decodeMetaindex(
+	data []byte,
+) (meta map[string]block.Handle, vbih valueBlocksIndexHandle, err error) {
+	i, err := rowblk.NewRawIter(bytes.Compare, data)
+	if err != nil {
+		return nil, valueBlocksIndexHandle{}, err
+	}
+	defer func() { err = firstError(err, i.Close()) }()
+
+	meta = map[string]block.Handle{}
+	for valid := i.First(); valid; valid = i.Next() {
+		value := i.Value()
+		if bytes.Equal(i.Key().UserKey, []byte(metaValueIndexName)) {
+			var n int
+			vbih, n, err = decodeValueBlocksIndexHandle(i.Value())
+			if err != nil {
+				return nil, vbih, err
+			}
+			if n == 0 || n != len(value) {
+				return nil, vbih, base.CorruptionErrorf("pebble/table: invalid table (bad value blocks index handle)")
+			}
+		} else {
+			bh, n := block.DecodeHandle(value)
+			if n == 0 || n != len(value) {
+				return nil, vbih, base.CorruptionErrorf("pebble/table: invalid table (bad block handle)")
+			}
+			meta[string(i.Key().UserKey)] = bh
+		}
+	}
+	return meta, vbih, nil
+}
+
+func decodeValueBlockIndex(data []byte, vbih valueBlocksIndexHandle) ([]block.Handle, error) {
+	var valueBlocks []block.Handle
+	indexEntryLen := int(vbih.blockNumByteLength + vbih.blockOffsetByteLength +
+		vbih.blockLengthByteLength)
+	i := 0
+	for len(data) != 0 {
+		if len(data) < indexEntryLen {
+			return nil, errors.Errorf(
+				"remaining value index block %d does not contain a full entry of length %d",
+				len(data), indexEntryLen)
+		}
+		n := int(vbih.blockNumByteLength)
+		bn := int(littleEndianGet(data, n))
+		if bn != i {
+			return nil, errors.Errorf("unexpected block num %d, expected %d",
+				bn, i)
+		}
+		i++
+		data = data[n:]
+		n = int(vbih.blockOffsetByteLength)
+		blockOffset := littleEndianGet(data, n)
+		data = data[n:]
+		n = int(vbih.blockLengthByteLength)
+		blockLen := littleEndianGet(data, n)
+		data = data[n:]
+		valueBlocks = append(valueBlocks, block.Handle{Offset: blockOffset, Length: blockLen})
+	}
+	return valueBlocks, nil
+}
+
 // layoutWriter writes the structure of an sstable to durable storage. It
 // accepts serialized blocks, writes them to storage and returns a block handle
 // describing the offset and length of the block.
diff --git a/sstable/reader.go b/sstable/reader.go
index c9b8e383..58c6e102 100644
--- a/sstable/reader.go
+++ b/sstable/reader.go
@@ -5,7 +5,6 @@
 package sstable
 
 import (
-	"bytes"
 	"cmp"
 	"context"
 	"encoding/binary"
@@ -497,35 +496,12 @@ func (r *Reader) readMetaindex(
 			errors.Safe(len(data)), errors.Safe(metaindexBH.Length))
 	}
 
-	i, err := rowblk.NewRawIter(bytes.Compare, data)
+	var meta map[string]block.Handle
+	meta, r.valueBIH, err = decodeMetaindex(data)
 	if err != nil {
 		return err
 	}
 
-	meta := map[string]block.Handle{}
-	for valid := i.First(); valid; valid = i.Next() {
-		value := i.Value()
-		if bytes.Equal(i.Key().UserKey, []byte(metaValueIndexName)) {
-			vbih, n, err := decodeValueBlocksIndexHandle(i.Value())
-			if err != nil {
-				return err
-			}
-			if n == 0 || n != len(value) {
-				return base.CorruptionErrorf("pebble/table: invalid table (bad value blocks index handle)")
-			}
-			r.valueBIH = vbih
-		} else {
-			bh, n := block.DecodeHandle(value)
-			if n == 0 || n != len(value) {
-				return base.CorruptionErrorf("pebble/table: invalid table (bad block handle)")
-			}
-			meta[string(i.Key().UserKey)] = bh
-		}
-	}
-	if err := i.Close(); err != nil {
-		return err
-	}
-
 	if bh, ok := meta[metaPropertiesName]; ok {
 		b, err = r.readBlock(
 			ctx, bh, nil /* transform */, readHandle, nil, /* stats */
@@ -576,7 +552,6 @@ func (r *Reader) Layout() (*Layout, error) {
 
 	l := &Layout{
 		Data:       make([]block.HandleWithProperties, 0, r.Properties.NumDataBlocks),
-		Filter:     r.filterBH,
 		RangeDel:   r.rangeDelBH,
 		RangeKey:   r.rangeKeyBH,
 		ValueIndex: r.valueBIH.h,
@@ -585,6 +560,9 @@ func (r *Reader) Layout() (*Layout, error) {
 		Footer:     r.footerBH,
 		Format:     r.tableFormat,
 	}
+	if r.filterBH.Length > 0 {
+		l.Filter = []NamedBlockHandle{{Name: "fullfilter." + r.tableFilter.policy.Name(), Handle: r.filterBH}}
+	}
 
 	indexH, err := r.readIndex(context.Background(), nil, nil, nil)
 	if err != nil {
@@ -647,31 +625,9 @@ func (r *Reader) Layout() (*Layout, error) {
 			return nil, err
 		}
 		defer vbiH.Release()
-		vbiBlock := vbiH.Get()
-		indexEntryLen := int(r.valueBIH.blockNumByteLength + r.valueBIH.blockOffsetByteLength +
-			r.valueBIH.blockLengthByteLength)
-		i := 0
-		for len(vbiBlock) != 0 {
-			if len(vbiBlock) < indexEntryLen {
-				return nil, errors.Errorf(
-					"remaining value index block %d does not contain a full entry of length %d",
-					len(vbiBlock), indexEntryLen)
-			}
-			n := int(r.valueBIH.blockNumByteLength)
-			bn := int(littleEndianGet(vbiBlock, n))
-			if bn != i {
-				return nil, errors.Errorf("unexpected block num %d, expected %d",
-					bn, i)
-			}
-			i++
-			vbiBlock = vbiBlock[n:]
-			n = int(r.valueBIH.blockOffsetByteLength)
-			blockOffset := littleEndianGet(vbiBlock, n)
-			vbiBlock = vbiBlock[n:]
-			n = int(r.valueBIH.blockLengthByteLength)
-			blockLen := littleEndianGet(vbiBlock, n)
-			vbiBlock = vbiBlock[n:]
-			l.ValueBlock = append(l.ValueBlock, block.Handle{Offset: blockOffset, Length: blockLen})
+		l.ValueBlock, err = decodeValueBlockIndex(vbiH.Get(), r.valueBIH)
+		if err != nil {
+			return nil, err
 		}
 	}
 
@@ -693,7 +649,11 @@ func (r *Reader) ValidateBlockChecksums() error {
 		blocks[i] = l.Data[i].Handle
 	}
 	blocks = append(blocks, l.Index...)
-	blocks = append(blocks, l.TopIndex, l.Filter, l.RangeDel, l.RangeKey, l.Properties, l.MetaIndex)
+	blocks = append(blocks, l.TopIndex)
+	for _, bh := range l.Filter {
+		blocks = append(blocks, bh.Handle)
+	}
+	blocks = append(blocks, l.RangeDel, l.RangeKey, l.Properties, l.MetaIndex)
 
 	// Sorting by offset ensures we are performing a sequential scan of the
 	// file.
diff --git a/sstable/rowblk/rowblk_index_iter.go b/sstable/rowblk/rowblk_index_iter.go
index 0ea91153..170faa92 100644
--- a/sstable/rowblk/rowblk_index_iter.go
+++ b/sstable/rowblk/rowblk_index_iter.go
@@ -18,6 +18,13 @@ type IndexIter struct {
 // Assert that IndexIter satisfies the block.IndexBlockIterator interface.
 var _ block.IndexBlockIterator = (*IndexIter)(nil)
 
+// Init initializes an iterator from the provided block data slice.
+func (i *IndexIter) Init(
+	cmp base.Compare, split base.Split, blk []byte, transforms block.IterTransforms,
+) error {
+	return i.iter.Init(cmp, split, blk, transforms)
+}
+
 // InitHandle initializes an iterator from the provided block handle.
 func (i *IndexIter) InitHandle(
 	cmp base.Compare, split base.Split, block block.BufferHandle, transforms block.IterTransforms,
diff --git a/sstable/suffix_rewriter.go b/sstable/suffix_rewriter.go
index 8abf3b7e..190d017f 100644
--- a/sstable/suffix_rewriter.go
+++ b/sstable/suffix_rewriter.go
@@ -127,13 +127,15 @@ func rewriteKeySuffixesInBlocks(
 
 	// Copy over the filter block if it exists (rewriteDataBlocksToWriter will
 	// already have ensured this is valid if it exists).
-	if w.filter != nil && l.Filter.Length > 0 {
-		filterBlock, _, err := readBlockBuf(r, l.Filter, nil)
-		if err != nil {
-			return nil, TableFormatUnspecified, errors.Wrap(err, "reading filter")
-		}
-		w.filter = copyFilterWriter{
-			origPolicyName: w.filter.policyName(), origMetaName: w.filter.metaName(), data: filterBlock,
+	if w.filter != nil {
+		if filterBlockBH, ok := l.FilterByName(w.filter.metaName()); ok {
+			filterBlock, _, err := readBlockBuf(r, filterBlockBH, nil)
+			if err != nil {
+				return nil, TableFormatUnspecified, errors.Wrap(err, "reading filter")
+			}
+			w.filter = copyFilterWriter{
+				origPolicyName: w.filter.policyName(), origMetaName: w.filter.metaName(), data: filterBlock,
+			}
 		}
 	}
 


Test patch:
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/sstable/colblk/index_block_test.go b/sstable/colblk/index_block_test.go
index fc47f5ee..18838c2b 100644
--- a/sstable/colblk/index_block_test.go
+++ b/sstable/colblk/index_block_test.go
@@ -46,7 +46,7 @@ func TestIndexBlock(t *testing.T) {
 			return buf.String()
 		case "iter":
 			var it IndexIter
-			it.Init(&r)
+			it.InitReader(&r)
 			for _, line := range strings.Split(d.Input, "\n") {
 				fields := strings.Fields(line)
 				var valid bool
diff --git a/sstable/data_test.go b/sstable/data_test.go
index e81f782d..25b5e6a9 100644
--- a/sstable/data_test.go
+++ b/sstable/data_test.go
@@ -66,15 +66,15 @@ func optsFromArgs(td *datadriven.TestData, writerOpts *WriterOptions) error {
 	return nil
 }
 
-func runBuildCmd(
-	td *datadriven.TestData, writerOpts *WriterOptions, cacheSize int,
-) (*WriterMetadata, *Reader, error) {
-	f0 := &objstorage.MemObj{}
+func runBuildMemObjCmd(
+	td *datadriven.TestData, writerOpts *WriterOptions,
+) (*WriterMetadata, *objstorage.MemObj, error) {
+	obj := &objstorage.MemObj{}
 	if err := optsFromArgs(td, writerOpts); err != nil {
 		return nil, nil, err
 	}
 
-	w := NewRawWriter(f0, *writerOpts)
+	w := NewRawWriter(obj, *writerOpts)
 	defer func() {
 		if w != nil {
 			_ = w.Close()
@@ -122,7 +122,10 @@ func runBuildCmd(
 	if err != nil {
 		return nil, nil, err
 	}
+	return meta, obj, nil
+}
 
+func openReader(obj *objstorage.MemObj, writerOpts *WriterOptions, cacheSize int) (*Reader, error) {
 	readerOpts := ReaderOptions{Comparer: writerOpts.Comparer}
 	if writerOpts.FilterPolicy != nil {
 		readerOpts.Filters = map[string]FilterPolicy{
@@ -138,7 +141,17 @@ func runBuildCmd(
 			},
 		})
 	}
-	r, err := NewMemReader(f0.Data(), readerOpts)
+	return NewMemReader(obj.Data(), readerOpts)
+}
+
+func runBuildCmd(
+	td *datadriven.TestData, writerOpts *WriterOptions, cacheSize int,
+) (*WriterMetadata, *Reader, error) {
+	meta, obj, err := runBuildMemObjCmd(td, writerOpts)
+	if err != nil {
+		return nil, nil, err
+	}
+	r, err := openReader(obj, writerOpts, cacheSize)
 	if err != nil {
 		return nil, nil, err
 	}
diff --git a/sstable/reader_test.go b/sstable/reader_test.go
index 6b2e0610..9d642c97 100644
--- a/sstable/reader_test.go
+++ b/sstable/reader_test.go
@@ -1695,7 +1695,7 @@ func TestValidateBlockChecksums(t *testing.T) {
 			case corruptionLocationTopIndex:
 				bh = layout.TopIndex
 			case corruptionLocationFilter:
-				bh = layout.Filter
+				bh = layout.Filter[0].Handle
 			case corruptionLocationRangeDel:
 				bh = layout.RangeDel
 			case corruptionLocationProperties:
diff --git a/sstable/testdata/rewriter b/sstable/testdata/rewriter
index 22374d2a..4f97ebb3 100644
--- a/sstable/testdata/rewriter
+++ b/sstable/testdata/rewriter
@@ -43,7 +43,7 @@ layout
          0  data (25)
         30  data (25)
         60  data (25)
-        90  filter (69)
+        90  fullfilter.rocksdb.BuiltinBloomFilter (69)
        164  index (22)
        191  index (22)
        218  index (22)
@@ -78,7 +78,7 @@ layout
          0  data (25)
         30  data (25)
         60  data (25)
-        90  filter (69)
+        90  fullfilter.rocksdb.BuiltinBloomFilter (69)
        164  index (22)
        191  index (22)
        218  index (22)
@@ -113,7 +113,7 @@ layout
          0  data (25)
         30  data (25)
         60  data (25)
-        90  filter (69)
+        90  fullfilter.rocksdb.BuiltinBloomFilter (69)
        164  index (22)
        191  index (22)
        218  index (22)
@@ -148,7 +148,7 @@ layout
          0  data (25)
         30  data (25)
         60  data (25)
-        90  filter (69)
+        90  fullfilter.rocksdb.BuiltinBloomFilter (69)
        164  index (22)
        191  index (22)
        218  index (22)
@@ -184,7 +184,7 @@ layout
          0  data (25)
         30  data (25)
         60  data (25)
-        90  filter (69)
+        90  fullfilter.rocksdb.BuiltinBloomFilter (69)
        164  index (22)
        191  index (22)
        218  index (22)
diff --git a/sstable/testdata/rewriter_v3 b/sstable/testdata/rewriter_v3
index 3c1dfbbb..a00027e7 100644
--- a/sstable/testdata/rewriter_v3
+++ b/sstable/testdata/rewriter_v3
@@ -43,7 +43,7 @@ layout
          0  data (26)
         31  data (26)
         62  data (26)
-        93  filter (69)
+        93  fullfilter.rocksdb.BuiltinBloomFilter (69)
        167  index (22)
        194  index (22)
        221  index (22)
@@ -78,7 +78,7 @@ layout
          0  data (26)
         31  data (26)
         62  data (26)
-        93  filter (69)
+        93  fullfilter.rocksdb.BuiltinBloomFilter (69)
        167  index (22)
        194  index (22)
        221  index (22)
@@ -113,7 +113,7 @@ layout
          0  data (26)
         31  data (26)
         62  data (26)
-        93  filter (69)
+        93  fullfilter.rocksdb.BuiltinBloomFilter (69)
        167  index (22)
        194  index (22)
        221  index (22)
@@ -148,7 +148,7 @@ layout
          0  data (26)
         31  data (26)
         62  data (26)
-        93  filter (69)
+        93  fullfilter.rocksdb.BuiltinBloomFilter (69)
        167  index (22)
        194  index (22)
        221  index (22)
@@ -184,7 +184,7 @@ layout
          0  data (26)
         31  data (26)
         62  data (26)
-        93  filter (69)
+        93  fullfilter.rocksdb.BuiltinBloomFilter (69)
        167  index (22)
        194  index (22)
        221  index (22)
diff --git a/sstable/testdata/writer_v3 b/sstable/testdata/writer_v3
index 48cd1920..ed445059 100644
--- a/sstable/testdata/writer_v3
+++ b/sstable/testdata/writer_v3
@@ -218,6 +218,22 @@ layout
        714  footer (53)
        767  EOF
 
+# Exercise the non-Reader layout-decoding codepath.
+
+decode-layout
+----
+         0  data (22)
+        27  data (22)
+        54  data (22)
+        81  index (22)
+       108  index (22)
+       135  index (22)
+       162  top-index (51)
+       218  properties (453)
+       676  meta-index (33)
+       714  footer (53)
+       767  EOF
+
 scan
 ----
 a#1,SET:a
diff --git a/sstable/writer_test.go b/sstable/writer_test.go
index d203da76..9f19899a 100644
--- a/sstable/writer_test.go
+++ b/sstable/writer_test.go
@@ -109,6 +109,7 @@ func formatWriterMetadata(td *datadriven.TestData, m *WriterMetadata) string {
 
 func runDataDriven(t *testing.T, file string, tableFormat TableFormat, parallelism bool) {
 	var r *Reader
+	var obj *objstorage.MemObj
 	defer func() {
 		if r != nil {
 			require.NoError(t, r.Close())
@@ -124,10 +125,15 @@ func runDataDriven(t *testing.T, file string, tableFormat TableFormat, paralleli
 			}
 			var meta *WriterMetadata
 			var err error
-			meta, r, err = runBuildCmd(td, &WriterOptions{
+			wopts := &WriterOptions{
 				TableFormat: tableFormat,
 				Parallelism: parallelism,
-			}, 0)
+			}
+			meta, obj, err = runBuildMemObjCmd(td, wopts)
+			if err != nil {
+				return err.Error()
+			}
+			r, err = openReader(obj, wopts, 0)
 			if err != nil {
 				return err.Error()
 			}
@@ -231,6 +237,23 @@ func runDataDriven(t *testing.T, file string, tableFormat TableFormat, paralleli
 			l.Describe(&buf, verbose, r, nil)
 			return buf.String()
 
+		case "decode-layout":
+			l, err := decodeLayout(testkeys.Comparer, obj.Data())
+			if err != nil {
+				return err.Error()
+			}
+			verbose := false
+			if len(td.CmdArgs) > 0 {
+				if td.CmdArgs[0].Key == "verbose" {
+					verbose = true
+				} else {
+					return "unknown arg"
+				}
+			}
+			var buf bytes.Buffer
+			l.Describe(&buf, verbose, r, nil)
+			return buf.String()
+
 		case "rewrite":
 			var meta *WriterMetadata
 			var err error
@@ -657,7 +680,9 @@ func TestWriterClearCache(t *testing.T) {
 			f(bh)
 		}
 		f(layout.TopIndex)
-		f(layout.Filter)
+		for _, nbh := range layout.Filter {
+			f(nbh.Handle)
+		}
 		f(layout.RangeDel)
 		for _, bh := range layout.ValueBlock {
 			f(bh)
diff --git a/tool/testdata/sstable_layout b/tool/testdata/sstable_layout
index 7f6d274c..680dcd62 100644
--- a/tool/testdata/sstable_layout
+++ b/tool/testdata/sstable_layout
@@ -45,7 +45,7 @@ h.table-bloom.no-compression.sst
      22464  data (2035)
      24504  data (2036)
      26545  data (249)
-     26799  filter (2245)
+     26799  fullfilter.rocksdb.BuiltinBloomFilter (2245)
      29049  index (325)
      29379  range-del (421)
      29805  properties (453)