Repository: cockroachdb/pebble
Pull request #3918 (2024-09-04 21:09:31)

update crlib and use crstrings.Lines in a few tests
Use `Lines` where it helps us remove an extra check for empty lines.

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


Patch:
diff --git a/compaction.go b/compaction.go
index fe6024bc..2456af1e 100644
--- a/compaction.go
+++ b/compaction.go
@@ -2740,7 +2740,11 @@ func (d *DB) newCompactionOutput(
 		d.opts.Experimental.MaxWriterConcurrency > 0 &&
 			(cpuWorkHandle.Permitted() || d.opts.Experimental.ForceWriterParallelism)
 
-	tw := sstable.NewRawWriter(writable, writerOpts)
+	// TODO(jackson): Make the compaction body generic over the RawWriter type,
+	// so that we don't need to pay the cost of dynamic dispatch. For now, we
+	// type assert into the only concrete RawWriter type we see (until colblk is
+	// integrated).
+	tw := sstable.NewRawWriter(writable, writerOpts).(*sstable.RawRowWriter)
 	return objMeta, tw, cpuWorkHandle, nil
 }
 
diff --git a/db.go b/db.go
index 0fca0798..d61fac6f 100644
--- a/db.go
+++ b/db.go
@@ -16,6 +16,7 @@ import (
 	"github.com/cockroachdb/errors"
 	"github.com/cockroachdb/pebble/internal/arenaskl"
 	"github.com/cockroachdb/pebble/internal/base"
+	"github.com/cockroachdb/pebble/internal/cache"
 	"github.com/cockroachdb/pebble/internal/invalidating"
 	"github.com/cockroachdb/pebble/internal/invariants"
 	"github.com/cockroachdb/pebble/internal/keyspan"
@@ -278,7 +279,7 @@ type DB struct {
 	// The number of bytes available on disk.
 	diskAvailBytes atomic.Uint64
 
-	cacheID        uint64
+	cacheID        cache.ID
 	dirname        string
 	opts           *Options
 	cmp            Compare
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/ingest.go b/ingest.go
index 7332aac6..f43c1a8e 100644
--- a/ingest.go
+++ b/ingest.go
@@ -13,6 +13,7 @@ import (
 
 	"github.com/cockroachdb/errors"
 	"github.com/cockroachdb/pebble/internal/base"
+	"github.com/cockroachdb/pebble/internal/cache"
 	"github.com/cockroachdb/pebble/internal/invariants"
 	"github.com/cockroachdb/pebble/internal/manifest"
 	"github.com/cockroachdb/pebble/internal/overlap"
@@ -246,7 +247,7 @@ func ingestLoad1(
 	opts *Options,
 	fmv FormatMajorVersion,
 	readable objstorage.Readable,
-	cacheID uint64,
+	cacheID cache.ID,
 	fileNum base.FileNum,
 ) (*fileMetadata, error) {
 	o := opts.MakeReaderOptions()
@@ -429,7 +430,7 @@ func ingestLoad(
 	paths []string,
 	shared []SharedSSTMeta,
 	external []ExternalFile,
-	cacheID uint64,
+	cacheID cache.ID,
 	pending []base.FileNum,
 ) (ingestLoadResult, error) {
 	localFileNums := pending[:len(paths)]
diff --git a/internal/cache/block_map.go b/internal/cache/block_map.go
index 40e2bc95..0018e2a5 100644
--- a/internal/cache/block_map.go
+++ b/internal/cache/block_map.go
@@ -17,7 +17,7 @@ import (
 func fibonacciHash(k *key, seed uintptr) uintptr {
 	const m = 11400714819323198485
 	h := uint64(seed)
-	h ^= k.id * m
+	h ^= uint64(k.id) * m
 	h ^= uint64(k.fileNum) * m
 	h ^= k.offset * m
 	return uintptr(h)
diff --git a/internal/cache/clockpro.go b/internal/cache/clockpro.go
index 89715b3a..a6792bbb 100644
--- a/internal/cache/clockpro.go
+++ b/internal/cache/clockpro.go
@@ -32,7 +32,7 @@ import (
 
 type fileKey struct {
 	// id is the namespace for fileNums.
-	id      uint64
+	id      ID
 	fileNum base.DiskFileNum
 }
 
@@ -111,7 +111,7 @@ type shard struct {
 	countTest int64
 }
 
-func (c *shard) Get(id uint64, fileNum base.DiskFileNum, offset uint64) Handle {
+func (c *shard) Get(id ID, fileNum base.DiskFileNum, offset uint64) Handle {
 	c.mu.RLock()
 	var value *Value
 	if e, _ := c.blocks.Get(key{fileKey{id, fileNum}, offset}); e != nil {
@@ -129,7 +129,7 @@ func (c *shard) Get(id uint64, fileNum base.DiskFileNum, offset uint64) Handle {
 	return Handle{value: value}
 }
 
-func (c *shard) Set(id uint64, fileNum base.DiskFileNum, offset uint64, value *Value) Handle {
+func (c *shard) Set(id ID, fileNum base.DiskFileNum, offset uint64, value *Value) Handle {
 	if n := value.refs(); n != 1 {
 		panic(fmt.Sprintf("pebble: Value has already been added to the cache: refs=%d", n))
 	}
@@ -220,7 +220,7 @@ func (c *shard) checkConsistency() {
 }
 
 // Delete deletes the cached value for the specified file and offset.
-func (c *shard) Delete(id uint64, fileNum base.DiskFileNum, offset uint64) {
+func (c *shard) Delete(id ID, fileNum base.DiskFileNum, offset uint64) {
 	// The common case is there is nothing to delete, so do a quick check with
 	// shared lock.
 	k := key{fileKey{id, fileNum}, offset}
@@ -249,7 +249,7 @@ func (c *shard) Delete(id uint64, fileNum base.DiskFileNum, offset uint64) {
 }
 
 // EvictFile evicts all of the cache values for the specified file.
-func (c *shard) EvictFile(id uint64, fileNum base.DiskFileNum) {
+func (c *shard) EvictFile(id ID, fileNum base.DiskFileNum) {
 	fkey := key{fileKey{id, fileNum}, 0}
 	for c.evictFileRun(fkey) {
 		// Sched switch to give another goroutine an opportunity to acquire the
@@ -678,6 +678,9 @@ type Cache struct {
 	}
 }
 
+// TODO
+type ID uint64
+
 // New creates a new cache of the specified size. Memory for the cache is
 // allocated on demand, not during initialization. The cache is created with a
 // reference count of 1. Each DB it is associated with adds a reference, so the
@@ -755,7 +758,7 @@ func newShards(size int64, shards int) *Cache {
 	return c
 }
 
-func (c *Cache) getShard(id uint64, fileNum base.DiskFileNum, offset uint64) *shard {
+func (c *Cache) getShard(id ID, fileNum base.DiskFileNum, offset uint64) *shard {
 	if id == 0 {
 		panic("pebble: 0 cache ID is invalid")
 	}
@@ -811,7 +814,7 @@ func (c *Cache) Unref() {
 
 // Get retrieves the cache value for the specified file and offset, returning
 // nil if no value is present.
-func (c *Cache) Get(id uint64, fileNum base.DiskFileNum, offset uint64) Handle {
+func (c *Cache) Get(id ID, fileNum base.DiskFileNum, offset uint64) Handle {
 	return c.getShard(id, fileNum, offset).Get(id, fileNum, offset)
 }
 
@@ -819,17 +822,17 @@ func (c *Cache) Get(id uint64, fileNum base.DiskFileNum, offset uint64) Handle {
 // existing value if present. A Handle is returned which provides faster
 // retrieval of the cached value than Get (lock-free and avoidance of the map
 // lookup). The value must have been allocated by Cache.Alloc.
-func (c *Cache) Set(id uint64, fileNum base.DiskFileNum, offset uint64, value *Value) Handle {
+func (c *Cache) Set(id ID, fileNum base.DiskFileNum, offset uint64, value *Value) Handle {
 	return c.getShard(id, fileNum, offset).Set(id, fileNum, offset, value)
 }
 
 // Delete deletes the cached value for the specified file and offset.
-func (c *Cache) Delete(id uint64, fileNum base.DiskFileNum, offset uint64) {
+func (c *Cache) Delete(id ID, fileNum base.DiskFileNum, offset uint64) {
 	c.getShard(id, fileNum, offset).Delete(id, fileNum, offset)
 }
 
 // EvictFile evicts all of the cache values for the specified file.
-func (c *Cache) EvictFile(id uint64, fileNum base.DiskFileNum) {
+func (c *Cache) EvictFile(id ID, fileNum base.DiskFileNum) {
 	if id == 0 {
 		panic("pebble: 0 cache ID is invalid")
 	}
@@ -909,6 +912,6 @@ func (c *Cache) Metrics() Metrics {
 
 // NewID returns a new ID to be used as a namespace for cached file
 // blocks.
-func (c *Cache) NewID() uint64 {
-	return c.idAlloc.Add(1)
+func (c *Cache) NewID() ID {
+	return ID(c.idAlloc.Add(1))
 }
diff --git a/internal/cache/entry.go b/internal/cache/entry.go
index dac6fae6..81f011a4 100644
--- a/internal/cache/entry.go
+++ b/internal/cache/entry.go
@@ -59,9 +59,6 @@ type entry struct {
 	// referenced is atomically set to indicate that this entry has been accessed
 	// since the last time one of the clock hands swept it.
 	referenced atomic.Bool
-	// Reference count for the entry. The entry is freed when the reference count
-	// drops to zero.
-	ref refcnt
 }
 
 func newEntry(key key, size int64) *entry {
@@ -75,13 +72,11 @@ func newEntry(key key, size int64) *entry {
 	e.blockLink.prev = e
 	e.fileLink.next = e
 	e.fileLink.prev = e
-	e.ref.init(1)
 	return e
 }
 
 func (e *entry) free() {
 	e.setValue(nil)
-	*e = entry{}
 	entryAllocFree(e)
 }
 
diff --git a/internal/cache/entry_invariants.go b/internal/cache/entry_invariants.go
index 31c54e4c..bd326ed7 100644
--- a/internal/cache/entry_invariants.go
+++ b/internal/cache/entry_invariants.go
@@ -25,9 +25,8 @@ func entryAllocNew() *entry {
 	// enabled.
 	invariants.SetFinalizer(e, func(obj interface{}) {
 		e := obj.(*entry)
-		if v := e.ref.refs(); v != 0 {
-			fmt.Fprintf(os.Stderr, "%p: cache entry has non-zero reference count: %d\n%s",
-				e, v, e.ref.traces())
+		if *e != (entry{}) {
+			fmt.Fprintf(os.Stderr, "%p: entry was not freed", e)
 			os.Exit(1)
 		}
 	})
@@ -35,4 +34,5 @@ func entryAllocNew() *entry {
 }
 
 func entryAllocFree(e *entry) {
+	*e = entry{}
 }
diff --git a/internal/cache/entry_normal.go b/internal/cache/entry_normal.go
index 92afb044..893d0e92 100644
--- a/internal/cache/entry_normal.go
+++ b/internal/cache/entry_normal.go
@@ -44,6 +44,7 @@ func entryAllocNew() *entry {
 
 func entryAllocFree(e *entry) {
 	a := entryAllocPool.Get().(*entryAllocCache)
+	*e = entry{}
 	a.free(e)
 	entryAllocPool.Put(a)
 }
diff --git a/internal/compact/spans.go b/internal/compact/spans.go
index 41206e19..03385bb5 100644
--- a/internal/compact/spans.go
+++ b/internal/compact/spans.go
@@ -182,7 +182,7 @@ func (c *RangeKeySpanCompactor) elideInLastStripe(
 //
 // The span can contain either only RANGEDEL keys or only range keys.
 func SplitAndEncodeSpan(
-	cmp base.Compare, span *keyspan.Span, upToKey []byte, tw *sstable.RawRowWriter,
+	cmp base.Compare, span *keyspan.Span, upToKey []byte, tw sstable.RawWriter,
 ) error {
 	if span.Empty() {
 		return nil
diff --git a/internal/sstableinternal/options.go b/internal/sstableinternal/options.go
index 4c0cdca0..3dccebdb 100644
--- a/internal/sstableinternal/options.go
+++ b/internal/sstableinternal/options.go
@@ -15,7 +15,7 @@ type CacheOptions struct {
 	// Cache can be nil, in which case no cache is used. When non-nil, the other
 	// fields must be set accordingly.
 	Cache   *cache.Cache
-	CacheID uint64
+	CacheID cache.ID
 	FileNum base.DiskFileNum
 }
 
diff --git a/internal/treesteps/data.go b/internal/treesteps/data.go
new file mode 100644
index 00000000..b6a0ac9b
--- /dev/null
+++ b/internal/treesteps/data.go
@@ -0,0 +1,119 @@
+// Copyright 2024 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 treesteps
+
+import (
+	"bytes"
+	"compress/zlib"
+	"encoding/base64"
+	"encoding/json"
+	"fmt"
+	"net/url"
+	"strings"
+
+	"github.com/cockroachdb/pebble/internal/treeprinter"
+)
+
+// Steps contains the result of a recording: the full details of the hierarchy
+// for each step.
+type Steps struct {
+	Name  string
+	Steps []Step `json:"steps"`
+}
+
+// Step contains the tree for a single step in a recording.
+type Step struct {
+	Name string   `json:"name"`
+	Root TreeNode `json:"tree"`
+}
+
+// TreeNode is a node in the tree for a step in a recording.
+type TreeNode struct {
+	Name       string      `json:"name"`
+	Properties [][2]string `json:"props"`
+	Ops        []string    `json:"ops"`
+	Children   []TreeNode  `json:"children"`
+}
+
+// String returns the steps as a string (using treeprinter).
+func (s Steps) String() string {
+	var buf strings.Builder
+	for step := range s.Steps {
+		if len(s.Steps) > 1 {
+			fmt.Fprintf(&buf, "step %d/%d:\n", step+1, len(s.Steps))
+		}
+		out := s.Steps[step].Root.String()
+		if len(s.Steps) > 1 {
+			for _, l := range strings.Split(strings.TrimSpace(out), "\n") {
+				fmt.Fprintf(&buf, "  %s\n", l)
+			}
+		} else {
+			buf.WriteString(out)
+		}
+	}
+	return buf.String()
+}
+
+func (t *TreeNode) String() string {
+	tp := treeprinter.New()
+	t.print(tp)
+	return tp.String()
+}
+
+func (t *TreeNode) print(parent treeprinter.Node) {
+	name := t.Name
+	for i := range t.Ops {
+		name += fmt.Sprintf("  ← %s", t.Ops[i])
+	}
+	n := parent.Child(name)
+	for _, p := range t.Properties {
+		n.Childf("%s: %s", p[0], p[1])
+	}
+	for i := range t.Children {
+		t.Children[i].print(n)
+	}
+}
+
+// URL for a visualization of the steps. The URL contains the encoded and
+// compressed data as the URL fragment.
+func (s Steps) URL() url.URL {
+	// TODO(radu): ideally we would encode Steps and have a graphical
+	// visualization. For now, we generate and encode the ASCII trees.
+	var output struct {
+		Name      string
+		StepNames []string
+		Steps     []string
+	}
+	output.Name = s.Name
+	output.StepNames = make([]string, len(s.Steps))
+	output.Steps = make([]string, len(s.Steps))
+	for i := range s.Steps {
+		output.StepNames[i] = s.Steps[i].Name
+		output.Steps[i] = s.Steps[i].Root.String()
+	}
+
+	var jsonBuf bytes.Buffer
+	if err := json.NewEncoder(&jsonBuf).Encode(&output); err != nil {
+		panic(err)
+	}
+	var compressed bytes.Buffer
+	encoder := base64.NewEncoder(base64.URLEncoding, &compressed)
+	compressor := zlib.NewWriter(encoder)
+	if _, err := jsonBuf.WriteTo(compressor); err != nil {
+		panic(err)
+	}
+	if err := compressor.Close(); err != nil {
+		panic(err)
+	}
+	if err := encoder.Close(); err != nil {
+		panic(err)
+	}
+	return url.URL{
+		Scheme:   "https",
+		Host:     "raduberinde.github.io",
+		Path:     "treesteps/decode.html",
+		Fragment: compressed.String(),
+	}
+}
diff --git a/internal/treesteps/node_state.go b/internal/treesteps/node_state.go
new file mode 100644
index 00000000..60f6f8ef
--- /dev/null
+++ b/internal/treesteps/node_state.go
@@ -0,0 +1,60 @@
+// Copyright 2024 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 treesteps
+
+import (
+	"fmt"
+	"sync"
+	"sync/atomic"
+)
+
+type nodeState struct {
+	recording *Recording
+	node      Node
+	name      string
+
+	// ops currently running for this node.
+	ops []*Op
+}
+
+var mu struct {
+	sync.Mutex
+
+	recordingInProgress atomic.Bool
+	nodeMap             map[Node]*nodeState
+}
+
+func buildTree(n *nodeState) TreeNode {
+	var t TreeNode
+	info := n.node.TreeStepsNode()
+	n.name = info.name
+	t.Name = info.name
+	t.Properties = info.properties
+	if len(n.ops) > 0 {
+		t.Ops = make([]string, len(n.ops))
+		for i := range t.Ops {
+			t.Ops[i] = n.ops[i].details
+			if n.ops[i].state != "" {
+				t.Ops[i] += " " + n.ops[i].state
+			}
+		}
+	}
+	for i := range info.children {
+		c := nodeStateLocked(n.recording, info.children[i])
+		t.Children = append(t.Children, buildTree(c))
+	}
+	return t
+}
+
+func nodeStateLocked(w *Recording, n Node) *nodeState {
+	ns, ok := mu.nodeMap[n]
+	if !ok {
+		ns = &nodeState{recording: w, node: n}
+		mu.nodeMap[n] = ns
+	} else if w != ns.recording {
+		panic(fmt.Sprintf("node %v part of multiple recordings", n))
+	}
+	return ns
+}
diff --git a/internal/treesteps/tree_steps.go b/internal/treesteps/tree_steps.go
new file mode 100644
index 00000000..8bc037a5
--- /dev/null
+++ b/internal/treesteps/tree_steps.go
@@ -0,0 +1,231 @@
+// Copyright 2024 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 treesteps
+
+import (
+	"fmt"
+	"reflect"
+	"slices"
+	"strings"
+	"unicode"
+
+	"github.com/cockroachdb/pebble/internal/treeprinter"
+)
+
+// StartRecording starts a new recording that captures step-by-step propagation
+// of operations and changes in a hierarchical structure.
+//
+// Each node in the structure must implement the TreeStepsNode method, which
+// returns information about the current state of the node and a list of its
+// children. For every operation or sub-operation on a node, StartOpf and
+// FinishOpf must be called. Calling Finish() on the Recording will return all
+// the collected information (which can be presented as text or as a link to a
+// visualization).
+//
+// It is not legal to start a recording that involves the same node as another
+// 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 {
+	mu.Lock()
+	defer mu.Unlock()
+	mu.recordingInProgress.Store(true)
+	w := &Recording{name: name}
+
+	if mu.nodeMap == nil {
+		mu.nodeMap = make(map[Node]*nodeState)
+	}
+	w.root = nodeStateLocked(w, root)
+	w.stepLockedf("initial")
+	return w
+}
+
+// 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
+// description.
+func NodeUpdated(n Node, reason string) {
+	if !mu.recordingInProgress.Load() {
+		return
+	}
+	mu.Lock()
+	defer mu.Unlock()
+	if ns, ok := mu.nodeMap[n]; ok {
+		if reason == "" {
+			reason = " updated"
+		} else {
+			reason = ": " + reason
+		}
+		ns.recording.stepLockedf("node %s%s", firstWord(ns.name), reason)
+	}
+}
+
+// Node must be implemnented by every node in the hierarchy.
+type Node interface {
+	TreeStepsNode() NodeInfo
+}
+
+// NodeInfo contains the information that we present for each node.
+type NodeInfo struct {
+	name       string
+	properties [][2]string
+	children   []Node
+}
+
+// NodeInfof returns a NodeInfo with the name initialized with a formatted
+// string.
+func NodeInfof(format string, args ...any) NodeInfo {
+	return NodeInfo{name: fmt.Sprintf(format, args...)}
+}
+
+// AddPropf adds a property to the NodeInfo.
+func (ni *NodeInfo) AddPropf(key string, format string, args ...any) {
+	ni.properties = append(ni.properties, [2]string{key, fmt.Sprintf(format, args...)})
+}
+
+// AddChildren adds one or more children to the NodeInfo.
+//
+// Any nil children are ignored (this includes nil pointers of any type).
+func (ni *NodeInfo) AddChildren(nodes ...Node) {
+	for _, n := range nodes {
+		if n == nil {
+			continue
+		}
+		if val := reflect.ValueOf(n); val.Kind() == reflect.Ptr && val.IsNil() {
+			continue
+		}
+		ni.children = append(ni.children, n)
+	}
+}
+
+// Recording captures the step-by-step propagation of operations. See
+// StartRecording.
+type Recording struct {
+	name  string
+	root  *nodeState
+	steps []Step
+}
+
+// Finish completes the recording and returns the recorded steps.
+func (r *Recording) Finish() Steps {
+	mu.Lock()
+	defer mu.Unlock()
+	for n, ns := range mu.nodeMap {
+		if ns.recording == r {
+			delete(mu.nodeMap, n)
+		}
+	}
+	if len(mu.nodeMap) == 0 {
+		mu.recordingInProgress.Store(false)
+	}
+	r.root = nil
+	return Steps{Name: r.name, Steps: r.steps}
+}
+
+// stpLockedf updates the tree (calling TreeStepsNode on all the nodes) and
+// saves it as a step. The formatted string is the name/description of the step.
+func (r *Recording) stepLockedf(format string, args ...any) {
+	r.steps = append(r.steps, Step{
+		Name: fmt.Sprintf(format, args...),
+		Root: buildTree(r.root),
+	})
+}
+
+// IsRecording indicates whether a recording involving a given node is currently
+// in progress. Can be used as a fast check before calling StartOpf.
+func IsRecording(n Node) bool {
+	if !mu.recordingInProgress.Load() {
+		return false
+	}
+	mu.Lock()
+	defer mu.Unlock()
+	_, ok := mu.nodeMap[n]
+	return ok
+}
+
+// Op represents an operation that is associated with a node.
+type Op struct {
+	details   string
+	state     string
+	nodeState *nodeState
+}
+
+// StartOpf registers the start of a new operation on a node and emits a step.
+// The operation will be displayed for the given node until FinishOpf is called.
+//
+// If a recording involving the node is not currently in progress, does nothing
+// and returns nil. Other methods can be called (and do nothing) when Op is nil.
+//
+// Note: it is recommended that IsRecording() is checked first to avoid any
+// allocations (e.g. due to boxing of args) in the normal, non-recording path.
+func StartOpf(node Node, format string, args ...any) *Op {
+	mu.Lock()
+	defer mu.Unlock()
+	ns, ok := mu.nodeMap[node]
+	if !ok {
+		return nil
+	}
+	op := &Op{
+		details:   fmt.Sprintf(format, args...),
+		nodeState: ns,
+	}
+	ns.ops = append(ns.ops, op)
+	ns.recording.stepLockedf("%s on %s started", firstWord(op.details), firstWord(op.nodeState.name))
+	return op
+}
+
+// Updatef changes the state of the operation and emits a step. The state of the
+// // operation shows up after the details that were provided in StartOpf.
+func (op *Op) Updatef(format string, args ...any) {
+	if op == nil {
+		return
+	}
+	mu.Lock()
+	defer mu.Unlock()
+	op.state = fmt.Sprintf(format, args...)
+	op.nodeState.recording.stepLockedf("%s on %s updated", firstWord(op.details), firstWord(op.nodeState.name))
+}
+
+// Finishf changes the state of the operation, emits a step, and cleans up the
+// operation.The state of the operation shows up after the details that were
+// provided in StartOpf.
+func (op *Op) Finishf(format string, args ...any) {
+	if op == nil {
+		return
+	}
+	mu.Lock()
+	defer mu.Unlock()
+	op.state = fmt.Sprintf(format, args...)
+	op.nodeState.recording.stepLockedf("%s on %s finished", firstWord(op.details), firstWord(op.nodeState.name))
+	op.nodeState.ops = slices.DeleteFunc(op.nodeState.ops, func(o *Op) bool { return o == op })
+}
+
+func firstWord(str string) string {
+	for i, r := range str {
+		if unicode.IsSpace(r) || strings.ContainsRune("()[]{}:", r) {
+			return str[:i]
+		}
+	}
+	return str
+}
+
+// TreeToString returns a string representation of the current state of a Node
+// tree.
+func TreeToString(n Node) string {
+	tp := treeprinter.New()
+	treePrint(n, tp)
+	return tp.String()
+}
+
+func treePrint(n Node, tp treeprinter.Node) {
+	ni := n.TreeStepsNode()
+	tpNode := tp.Child(ni.name)
+	for _, prop := range ni.properties {
+		tpNode.Childf("%s: %s", prop[0], prop[1])
+	}
+	for _, child := range ni.children {
+		treePrint(child, tpNode)
+	}
+}
diff --git a/sstable/block/buffer_pool.go b/sstable/block/buffer_pool.go
index 6a12b2b5..96012a0b 100644
--- a/sstable/block/buffer_pool.go
+++ b/sstable/block/buffer_pool.go
@@ -40,7 +40,7 @@ func (b Value) Get() []byte {
 // backed by a buffer pool, MakeHandle inserts the value into the block cache,
 // returning a handle to the now resident value.
 func (b Value) MakeHandle(
-	c *cache.Cache, cacheID uint64, fileNum base.DiskFileNum, offset uint64,
+	c *cache.Cache, cacheID cache.ID, fileNum base.DiskFileNum, offset uint64,
 ) BufferHandle {
 	if b.buf.Valid() {
 		return BufferHandle{b: b.buf}
diff --git a/sstable/copier.go b/sstable/copier.go
index 805eb68c..011656ee 100644
--- a/sstable/copier.go
+++ b/sstable/copier.go
@@ -61,7 +61,7 @@ func CopySpan(
 		o.FilterPolicy = nil
 	}
 	o.TableFormat = r.tableFormat
-	w := NewRawWriter(output, o)
+	w := newRowWriter(output, o)
 
 	// We don't want the writer to attempt to write out block property data in
 	// index blocks. This data won't be valid since we're not passing the actual
diff --git a/sstable/rowblk_writer.go b/sstable/rowblk_writer.go
index e06e81e3..830bd78c 100644
--- a/sstable/rowblk_writer.go
+++ b/sstable/rowblk_writer.go
@@ -109,7 +109,6 @@ type RawRowWriter struct {
 	indexSepAlloc bytealloc.A
 
 	rangeKeyEncoder rangekey.Encoder
-	rangeKeySpan    keyspan.Span
 	// dataBlockBuf consists of the state which is currently owned by and used by
 	// the Writer client goroutine. This state can be handed off to other goroutines.
 	dataBlockBuf *dataBlockBuf
@@ -578,13 +577,13 @@ type indexBlockAndBlockProperties struct {
 	block []byte
 }
 
-// Add adds a key/value pair to the table being written. For a given Writer,
-// the keys passed to Add must be in increasing order. The exception to this
+// add adds a key/value pair to the table being written. For a given Writer,
+// the keys passed to add must be in increasing order. The exception to this
 // rule is range deletion tombstones. Range deletion tombstones need to be
 // added ordered by their start key, but they can be added out of order from
 // point entries. Additionally, range deletion tombstones must be fragmented
 // (i.e. by keyspan.Fragmenter).
-func (w *RawRowWriter) Add(key InternalKey, value []byte) error {
+func (w *RawRowWriter) add(key InternalKey, value []byte) error {
 	if w.isStrictObsolete {
 		return errors.Errorf("use AddWithForceObsolete")
 	}
@@ -961,24 +960,6 @@ func (w *RawRowWriter) addTombstone(key InternalKey, value []byte) error {
 	return nil
 }
 
-func (w *RawRowWriter) encodeFragmentedRangeKeySpan(span keyspan.Span) {
-	// This method is the emit function of the Fragmenter.
-	//
-	// NB: The span should only contain range keys and be internally consistent
-	// (eg, no duplicate suffixes, no additional keys after a RANGEKEYDEL).
-	//
-	// We use w.rangeKeySpan to avoid allocations.
-
-	// Sort the keys by suffix. Iteration doesn't *currently* depend on it, but
-	// we may want to in the future.
-	w.rangeKeySpan = span
-	keyspan.SortKeysBySuffix(w.suffixCmp, w.rangeKeySpan.Keys)
-
-	if w.err == nil {
-		w.err = w.EncodeSpan(w.rangeKeySpan)
-	}
-}
-
 // addRangeKey adds a range key set, unset, or delete key/value pair to the
 // table being written.
 //
@@ -1600,7 +1581,7 @@ func (w *RawRowWriter) EncodeSpan(span keyspan.Span) error {
 		return nil
 	}
 	if span.Keys[0].Kind() == base.InternalKeyKindRangeDelete {
-		return rangedel.Encode(span, w.Add)
+		return rangedel.Encode(span, w.add)
 	}
 	for i := range w.blockPropCollectors {
 		if err := w.blockPropCollectors[i].AddRangeKeys(span); err != nil {
@@ -1836,7 +1817,11 @@ func (w *RawRowWriter) Metadata() (*WriterMetadata, error) {
 
 // NewRawWriter returns a new table writer for the file. Closing the writer will
 // close the file.
-func NewRawWriter(writable objstorage.Writable, o WriterOptions) *RawRowWriter {
+func NewRawWriter(writable objstorage.Writable, o WriterOptions) RawWriter {
+	return newRowWriter(writable, o)
+}
+
+func newRowWriter(writable objstorage.Writable, o WriterOptions) *RawRowWriter {
 	o = o.ensureDefaults()
 	w := &RawRowWriter{
 		layout: makeLayoutWriter(writable, o),
diff --git a/sstable/suffix_rewriter.go b/sstable/suffix_rewriter.go
index 8a5a18cf..8abf3b7e 100644
--- a/sstable/suffix_rewriter.go
+++ b/sstable/suffix_rewriter.go
@@ -97,7 +97,7 @@ func rewriteKeySuffixesInBlocks(
 
 	tableFormat := r.tableFormat
 	o.TableFormat = tableFormat
-	w := NewRawWriter(out, o)
+	w := newRowWriter(out, o)
 	defer func() {
 		if w != nil {
 			w.Close()
@@ -388,7 +388,7 @@ func RewriteKeySuffixesViaWriter(
 	}
 
 	o.IsStrictObsolete = false
-	w := NewRawWriter(out, o)
+	w := newRowWriter(out, o)
 	defer func() {
 		if w != nil {
 			w.Close()
diff --git a/sstable/writer.go b/sstable/writer.go
index 2ff142d2..a2f35436 100644
--- a/sstable/writer.go
+++ b/sstable/writer.go
@@ -13,7 +13,8 @@ import (
 
 // Writer is a table writer.
 type Writer struct {
-	rw RawWriter
+	rw  RawWriter
+	err error
 	// To allow potentially overlapping (i.e. un-fragmented) range keys spans to
 	// be added to the Writer, a keyspan.Fragmenter is used to retain the keys
 	// and values, emitting fragmented, coalesced spans as appropriate. Range
@@ -32,15 +33,37 @@ type Writer struct {
 func NewWriter(writable objstorage.Writable, o WriterOptions) *Writer {
 	o = o.ensureDefaults()
 	rw := NewRawWriter(writable, o)
-	return &Writer{
+	w := &Writer{}
+	*w = Writer{
 		rw: rw,
 		fragmenter: keyspan.Fragmenter{
 			Cmp:    o.Comparer.Compare,
 			Format: o.Comparer.FormatKey,
-			Emit:   rw.encodeFragmentedRangeKeySpan,
+			Emit:   w.encodeFragmentedRangeKeySpan,
 		},
 		comparer: o.Comparer,
 	}
+	return w
+}
+
+func (w *Writer) encodeFragmentedRangeKeySpan(s keyspan.Span) {
+	// This method is the emit function of the Fragmenter.
+	//
+	// NB: The span should only contain range keys and be internally consistent
+	// (eg, no duplicate suffixes, no additional keys after a RANGEKEYDEL).
+	//
+	// Sort the keys by suffix. Iteration doesn't *currently* depend on it, but
+	// we may want to in the future.
+	keyspan.SortKeysBySuffix(w.comparer.CompareSuffixes, s.Keys)
+
+	if w.Error() == nil {
+		w.rw.EncodeSpan(s)
+	}
+}
+
+// Error returns the current accumulated error if any.
+func (w *Writer) Error() error {
+	return errors.CombineErrors(w.rw.Error(), w.err)
 }
 
 // Raw returns the underlying RawWriter.
@@ -53,7 +76,7 @@ func (w *Writer) Raw() RawWriter { return w.rw }
 //
 // TODO(peter): untested
 func (w *Writer) Set(key, value []byte) error {
-	if err := w.rw.Error(); err != nil {
+	if err := w.Error(); err != nil {
 		return err
 	}
 	if w.rw.IsStrictObsolete() {
@@ -70,7 +93,7 @@ func (w *Writer) Set(key, value []byte) error {
 //
 // TODO(peter): untested
 func (w *Writer) Delete(key []byte) error {
-	if err := w.rw.Error(); err != nil {
+	if err := w.Error(); err != nil {
 		return err
 	}
 	if w.rw.IsStrictObsolete() {
@@ -91,7 +114,7 @@ func (w *Writer) Delete(key []byte) error {
 //
 // TODO(peter): untested
 func (w *Writer) DeleteRange(start, end []byte) error {
-	if err := w.rw.Error(); err != nil {
+	if err := w.Error(); err != nil {
 		return err
 	}
 	return w.rw.EncodeSpan(keyspan.Span{
@@ -110,7 +133,7 @@ func (w *Writer) DeleteRange(start, end []byte) error {
 //
 // TODO(peter): untested
 func (w *Writer) Merge(key, value []byte) error {
-	if err := w.rw.Error(); err != nil {
+	if err := w.Error(); err != nil {
 		return err
 	}
 	if w.rw.IsStrictObsolete() {
@@ -195,7 +218,7 @@ func (w *Writer) addRangeKeySpanToFragmenter(span keyspan.Span) error {
 	}
 	// Add this span to the fragmenter.
 	w.fragmenter.Add(span)
-	return w.rw.Error()
+	return w.Error()
 }
 
 // tempRangeKeyBuf returns a slice of length n from the Writer's rkBuf byte
@@ -227,15 +250,21 @@ func (w *Writer) tempRangeKeyCopy(k []byte) []byte {
 	return buf
 }
 
+// Metadata returns the metadata for the finished sstable. Only valid to call
+// after the sstable has been finished.
+func (w *Writer) Metadata() (*WriterMetadata, error) {
+	return w.rw.Metadata()
+}
+
 // Close finishes writing the table and closes the underlying file that the
 // table was written to.
 func (w *Writer) Close() (err error) {
-	if w.rw.Error() == nil {
+	if w.Error() == nil {
 		// Write the range-key block, flushing any remaining spans from the
 		// fragmenter first.
 		w.fragmenter.Finish()
 	}
-	return w.rw.Close()
+	return errors.CombineErrors(w.rw.Close(), w.err)
 }
 
 // RawWriter defines an interface for sstable writers. Implementations may vary
@@ -268,6 +297,9 @@ type RawWriter interface {
 	// This is a low-level API that bypasses the fragmenter. The spans passed to
 	// this function must be fragmented and ordered.
 	EncodeSpan(span keyspan.Span) error
+	// EstimatedSize returns the estimated size of the sstable being written if
+	// a call to Close() was made without adding additional keys.
+	EstimatedSize() uint64
 	// Close finishes writing the table and closes the underlying file that the
 	// table was written to.
 	Close() error
diff --git a/table_cache.go b/table_cache.go
index 67bba2e4..7444fc43 100644
--- a/table_cache.go
+++ b/table_cache.go
@@ -101,7 +101,7 @@ type tableCacheOpts struct {
 
 	loggerAndTracer   LoggerAndTracer
 	cache             *cache.Cache
-	cacheID           uint64
+	cacheID           cache.ID
 	objProvider       objstorage.Provider
 	readerOpts        sstable.ReaderOptions
 	sstStatsCollector *sstable.CategoryStatsCollector
@@ -121,7 +121,7 @@ type tableCacheContainer struct {
 // doesn't match Options.Cache.
 func newTableCacheContainer(
 	tc *TableCache,
-	cacheID uint64,
+	cacheID cache.ID,
 	objProvider objstorage.Provider,
 	opts *Options,
 	size int,
@@ -348,7 +348,7 @@ func (c *TableCache) getShard(fileNum base.DiskFileNum) *tableCacheShard {
 }
 
 type tableCacheKey struct {
-	cacheID uint64
+	cacheID cache.ID
 	fileNum base.DiskFileNum
 }
 
@@ -1193,7 +1193,7 @@ type tableCacheNode struct {
 
 	// Storing the cache id associated with the DB instance here
 	// avoids the need to thread the dbOpts struct through many functions.
-	cacheID uint64
+	cacheID cache.ID
 }
 
 func (n *tableCacheNode) next() *tableCacheNode {


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/event_listener_test.go b/event_listener_test.go
index 87249935..f467262a 100644
--- a/event_listener_test.go
+++ b/event_listener_test.go
@@ -139,10 +139,10 @@ func TestEventListener(t *testing.T) {
 			if err != nil {
 				return err.Error()
 			}
-			w := sstable.NewRawWriter(objstorageprovider.NewFileWritable(f), sstable.WriterOptions{
+			w := sstable.NewWriter(objstorageprovider.NewFileWritable(f), sstable.WriterOptions{
 				TableFormat: d.FormatMajorVersion().MaxTableFormat(),
 			})
-			if err := w.Add(base.MakeInternalKey([]byte("a"), 0, InternalKeyKindSet), nil); err != nil {
+			if err := w.Set([]byte("a"), nil); err != nil {
 				return err.Error()
 			}
 			if err := w.Close(); err != nil {
@@ -173,10 +173,10 @@ func TestEventListener(t *testing.T) {
 				if err != nil {
 					return err
 				}
-				w := sstable.NewRawWriter(objstorageprovider.NewFileWritable(f), sstable.WriterOptions{
+				w := sstable.NewWriter(objstorageprovider.NewFileWritable(f), sstable.WriterOptions{
 					TableFormat: d.FormatMajorVersion().MaxTableFormat(),
 				})
-				if err := w.Add(base.MakeInternalKey([]byte{key}, 0, InternalKeyKindSet), nil); err != nil {
+				if err := w.Set([]byte{key}, nil); err != nil {
 					return err
 				}
 				if err := w.Close(); err != nil {
diff --git a/ingest_test.go b/ingest_test.go
index 8752a04a..de392717 100644
--- a/ingest_test.go
+++ b/ingest_test.go
@@ -117,7 +117,7 @@ func TestIngestLoad(t *testing.T) {
 				}
 				key := base.ParseInternalKey(data[:j])
 				value := []byte(data[j+1:])
-				if err := w.Add(key, value); err != nil {
+				if err := w.AddWithForceObsolete(key, value, false /* forceObsolete */); err != nil {
 					return err.Error()
 				}
 			}
@@ -202,7 +202,7 @@ func TestIngestLoadRand(t *testing.T) {
 					// Duplicate key, ignore.
 					continue
 				}
-				w.Add(keys[i], nil)
+				require.NoError(t, w.AddWithForceObsolete(keys[i], nil, false /* forceObsolete */))
 				count++
 			}
 			expected[i].Stats.NumEntries = count
@@ -1098,7 +1098,7 @@ func testIngestSharedImpl(
 				func(key *InternalKey, value LazyValue, _ IteratorLevel) error {
 					val, _, err := value.Value(nil)
 					require.NoError(t, err)
-					require.NoError(t, w.Add(base.MakeInternalKey(key.UserKey, 0, key.Kind()), val))
+					require.NoError(t, w.AddWithForceObsolete(base.MakeInternalKey(key.UserKey, 0, key.Kind()), val, false /* forceObsolete */))
 					return nil
 				},
 				func(start, end []byte, seqNum base.SeqNum) error {
@@ -1599,7 +1599,7 @@ func TestConcurrentExcise(t *testing.T) {
 				func(key *InternalKey, value LazyValue, _ IteratorLevel) error {
 					val, _, err := value.Value(nil)
 					require.NoError(t, err)
-					require.NoError(t, w.Add(base.MakeInternalKey(key.UserKey, 0, key.Kind()), val))
+					require.NoError(t, w.AddWithForceObsolete(base.MakeInternalKey(key.UserKey, 0, key.Kind()), val, false /* forceObsolete */))
 					return nil
 				},
 				func(start, end []byte, seqNum base.SeqNum) error {
@@ -2035,7 +2035,7 @@ func TestIngestExternal(t *testing.T) {
 				func(key *InternalKey, value LazyValue, _ IteratorLevel) error {
 					val, _, err := value.Value(nil)
 					require.NoError(t, err)
-					require.NoError(t, w.Add(base.MakeInternalKey(key.UserKey, 0, key.Kind()), val))
+					require.NoError(t, w.AddWithForceObsolete(base.MakeInternalKey(key.UserKey, 0, key.Kind()), val, false /* forceObsolete */))
 					return nil
 				},
 				func(start, end []byte, seqNum base.SeqNum) error {
@@ -2586,7 +2586,7 @@ func TestIngestCompact(t *testing.T) {
 
 	w := sstable.NewRawWriter(objstorageprovider.NewFileWritable(f), sstable.WriterOptions{})
 	key := []byte("a")
-	require.NoError(t, w.Add(base.MakeInternalKey(key, 0, InternalKeyKindSet), nil))
+	require.NoError(t, w.AddWithForceObsolete(base.MakeInternalKey(key, 0, InternalKeyKindSet), nil, false /* forceObsolete */))
 	require.NoError(t, w.Close())
 
 	// Make N copies of the sstable.
@@ -3222,7 +3222,7 @@ func TestIngestFileNumReuseCrash(t *testing.T) {
 func TestIngest_UpdateSequenceNumber(t *testing.T) {
 	mem := vfs.NewMem()
 	cmp := base.DefaultComparer.Compare
-	parse := func(input string) (*sstable.RawRowWriter, error) {
+	parse := func(input string) (sstable.RawWriter, error) {
 		f, err := mem.Create("ext", vfs.WriteCategoryUnspecified)
 		if err != nil {
 			return nil, err
@@ -3245,7 +3245,7 @@ func TestIngest_UpdateSequenceNumber(t *testing.T) {
 			}
 			key := base.ParseInternalKey(data[:j])
 			value := []byte(data[j+1:])
-			if err := w.Add(key, value); err != nil {
+			if err := w.AddWithForceObsolete(key, value, false /* forceObsolete */); err != nil {
 				return nil, err
 			}
 		}
diff --git a/internal/cache/clockpro_test.go b/internal/cache/clockpro_test.go
index 944b1ec7..066d2a9f 100644
--- a/internal/cache/clockpro_test.go
+++ b/internal/cache/clockpro_test.go
@@ -259,7 +259,7 @@ func TestReserveColdTarget(t *testing.T) {
 	defer cache.Unref()
 
 	for i := 0; i < 50; i++ {
-		cache.Set(uint64(i+1), base.DiskFileNum(0), 0, testValue(cache, "a", 1)).Release()
+		cache.Set(ID(i+1), base.DiskFileNum(0), 0, testValue(cache, "a", 1)).Release()
 	}
 
 	if cache.Size() != 50 {
diff --git a/internal/treesteps/testdata/segment_tree b/internal/treesteps/testdata/segment_tree
new file mode 100644
index 00000000..f5848286
--- /dev/null
+++ b/internal/treesteps/testdata/segment_tree
@@ -0,0 +1,738 @@
+init range=4
+----
+n0
+ ├── range: [1, 4]
+ ├── sum: 0
+ ├── n1
+ │    ├── range: [1, 2]
+ │    ├── sum: 0
+ │    ├── n3
+ │    │    ├── range: [1, 1]
+ │    │    └── sum: 0
+ │    └── n4
+ │         ├── range: [2, 2]
+ │         └── sum: 0
+ └── n2
+      ├── range: [3, 4]
+      ├── sum: 0
+      ├── n5
+      │    ├── range: [3, 3]
+      │    └── sum: 0
+      └── n6
+           ├── range: [4, 4]
+           └── sum: 0
+
+add x=3 delta=1
+----
+step 1/10:
+  n0
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 0
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 2/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 0
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 3/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 0
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 4/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5  ← add(3, 1)
+        │    ├── range: [3, 3]
+        │    └── sum: 0
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 5/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5  ← add(3, 1)
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 6/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 0
+        ├── n5  ← add(3, 1) done
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 7/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1)
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 8/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 0
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2  ← add(3, 1) done
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 9/10:
+  n0  ← add(3, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 10/10:
+  n0  ← add(3, 1) done
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+
+add x=2 delta=1
+----
+step 1/10:
+  n0
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 2/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 3/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 4/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4  ← add(2, 1)
+   │         ├── range: [2, 2]
+   │         └── sum: 0
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 5/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4  ← add(2, 1)
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 6/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 0
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4  ← add(2, 1) done
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 7/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1)
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 8/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 1
+   ├── n1  ← add(2, 1) done
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 9/10:
+  n0  ← add(2, 1)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 10/10:
+  n0  ← add(2, 1) done
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+
+sum x1=1 x2=3
+----
+step 1/9:
+  n0
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 2/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 3/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1  ← sum(1, 3)
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 4/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1  ← sum(1, 3) = 1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 5/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2  ← sum(1, 3)
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 6/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2  ← sum(1, 3)
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5  ← sum(1, 3)
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 7/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2  ← sum(1, 3)
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5  ← sum(1, 3) = 1
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 8/9:
+  n0  ← sum(1, 3)
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2  ← sum(1, 3) = 1
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+step 9/9:
+  n0  ← sum(1, 3) = 2
+   ├── range: [1, 4]
+   ├── sum: 2
+   ├── n1
+   │    ├── range: [1, 2]
+   │    ├── sum: 1
+   │    ├── n3
+   │    │    ├── range: [1, 1]
+   │    │    └── sum: 0
+   │    └── n4
+   │         ├── range: [2, 2]
+   │         └── sum: 1
+   └── n2
+        ├── range: [3, 4]
+        ├── sum: 1
+        ├── n5
+        │    ├── range: [3, 3]
+        │    └── sum: 1
+        └── n6
+             ├── range: [4, 4]
+             └── sum: 0
+
+add x=3 delta=10 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzsmLFOwzAYhHee4uQJpAyO0zLkIVjK1nqwZFMikb9Vk04IqWJgZsjI0-VJUFpK3cRGCIEo6B97vp7u__U5inIvrkzpRC4mbl46qnG9cg7GWpGISe2W3Wkl8qkoqKgLcycSYazFgkASVW1WtbOepgLa2NNoYR1onKNal1gvrelbbwoqqlvPq2JeNfTKmFcevHo313YmkjNC27y0zaZtNlgZmrsc0zTBSB-dVOsyhzqSKN3-fAQQjlA6ZNgmBf9Kma_Gc1Md8DV-vPQN-xMaHVSEw9VxaQSid83fM7uVRMKytyUiMn9Pp_FBi8yeJcj0wDWo16tNl3stUnTkFw3NLGfUESaB9um5uxrnWYJUXjA7zA6z8zvsBPbJLDFLp8ZSPJrZYrZOkC2Gi-EKwQW7IMeEMWFfIuzn3rOYpj9MU--hwkh9jFTKTH3bR4R_gs_-BjFDzNBnGNIPZ68BAAD__6rCZP4=
+
+sum x1=1 x2=3 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzslrFKxEAQhnufYphKYYvdJGcR8BVszu5ui4DrGTCjZJNKhMPC2iKlT5cnkVy8S2Jm4YoDhZsy30x-ZocPdl_xNiscprh0m8JRBXelc-DrAhUuK_fSVT2mK8wpr_LsCRX6uoBnAtLgq6ys3P2IGZY95JT7xwmMmMYFy9ifGagHaPvZd3OTXhO0zVfbbNtmC2VGG5fCyihI7KTi6yIFE00Ymd3nOwDwGZHlGvoorkLxmIZzjWX6mnG8HjfsK5QMFPjwaDo0MNH95IfMbiWBsPhni8Cd38wLtBhY4PCxgtjOuppQ8mHK6z0LjJqMR-VOrdeECkkDtB-fHbo0CuIrsUfs-SN7uCyRSWQ6hUxww1shQolQcrcda898nyKTyPT_ZApGi1vi1mnd6h4WRgQ7c8F-WXCG12G3gUi0kuf5kQrZt4vvAAAA___3jnU-
+
+init range=8
+----
+n0
+ ├── range: [1, 8]
+ ├── sum: 0
+ ├── n1
+ │    ├── range: [1, 4]
+ │    ├── sum: 0
+ │    ├── n3
+ │    │    ├── range: [1, 2]
+ │    │    ├── sum: 0
+ │    │    ├── n7
+ │    │    │    ├── range: [1, 1]
+ │    │    │    └── sum: 0
+ │    │    └── n8
+ │    │         ├── range: [2, 2]
+ │    │         └── sum: 0
+ │    └── n4
+ │         ├── range: [3, 4]
+ │         ├── sum: 0
+ │         ├── n9
+ │         │    ├── range: [3, 3]
+ │         │    └── sum: 0
+ │         └── n10
+ │              ├── range: [4, 4]
+ │              └── sum: 0
+ └── n2
+      ├── range: [5, 8]
+      ├── sum: 0
+      ├── n5
+      │    ├── range: [5, 6]
+      │    ├── sum: 0
+      │    ├── n11
+      │    │    ├── range: [5, 5]
+      │    │    └── sum: 0
+      │    └── n12
+      │         ├── range: [6, 6]
+      │         └── sum: 0
+      └── n6
+           ├── range: [7, 8]
+           ├── sum: 0
+           ├── n13
+           │    ├── range: [7, 7]
+           │    └── sum: 0
+           └── n14
+                ├── range: [8, 8]
+                └── sum: 0
+
+add x=6 delta=10 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzs2rFu2zAQBuC9T3Hg1AIaRMmyXT1El3RLNAggmwqozoElT0WBoEPnDhr7dHqSQmkcSyRPatEWSZx_Msw73IFH6rMGf1bvytqqXF3Y69pyS-_31lJpjIrURWtvhmij8ktVcdVW5ScVqdIY2jFxTE1b7ltrRmtJYC0LrOlxIu-MHZZyag41HW5M6SV_qLhqPo6yMyk583PFwoG6sZQbn3KLX6O5GwvHV0x996PvbvvulvYlX9ucLnVE22ISaQ51TtNk1ndfvxJRuMSqCCWMKjkRTserct2kmMnzy7tdNoGg3EyHmt1_dEs9jwm89YIU7pgEt0dL_R4arU6rQod0ejA0Pz4nzG-9kDC6NKLUb7MwOGefrN2YsKdVYE_yzB7KJ1csVczunwBpPO5cstOaMJAsonUhZrmF3UurtReT-2R-H2nw4XNhnTgxYUzrwKakwbuHuz6uCbU34yOYPQf3MHTqRIRRbSLauB1mB-Xdz9UkImxk621EGNHAeEzUf_s-_IS9Xkek4zcAGkADaAANoH9jUN79BNAAeu7OA-i_AzrwMAgdADbABtgAG2CfK9hyaQAOwAE4AAfgAPwRAV_YnzBGgA7QAbp85wE6QD9L0DVEh-gQHaJD9EcTncyOLVgH62AdrIP1P2FdPyXXQTgIB-Eg_OUQHnpzheNwHI7DcTj-JBzX_-1_hzAbZsNsmA2zZbOdF2TA7Z4H4H6WcGvIDbnPSm4gDaSfAdLHFwpIDakhNaSG1AuXNHSt_rnUxZdXPwMAAP__EYeKAA==
+
+add x=3 delta=1 url
+----
+https://raduberinde.github.io/treesteps/decode.html#eJzs2r1u2zAQB_C9T3Hg1AIaREv-0kN0SbdYgwCyqYD6HFjyVBQIOnTu4LFP5ycp7Ca2TN5JQ2PUiP9TEN7hLjwyPwuGvpmP1dKbwtz5h6Xnlj6tvafKOZOYu9Y_7qONKe5NzXVbV19NYirnaMXEKTVttW6966xZYS0X1uadNV45TzwvqNksafPoqjD1c81186WTm2u5eZxrtVwb56ZabnrKLf_O5TATThdMu-3v3fZpt32idcUPvqB7m9CsPIs0m2VB9jyb7eHXH0Qk18hLKeFQKpUinHVX9bqjsicvLh92mQpBvZmVmj3_2A71fEngWRQkueNI3B4N9Ts2yk-rSofs_GCof3xBmOdRSBldllAWtxkYXLBPtmFM2VMu7Emf2bH8aMFaxfHzv4A0nsNfFQ5mfFpTJjJOaFKqWVHl8NpaG8X0RuO4kTZ6-WTYjoKYMqiJsCtp9N2tHZtMXtaU4tPuKWg3VQqyzYKIMqtpQtOwQ--koiuan0WUjcyijUgzShe8pzwl2v38tf8Me58lZD_AaBgNo2E0jB6-pNK1unqjpVogG2SDbJA9cF1BNsgG2SLZ6hEpDSE4BIfgEByC36jgQ-0AOkAH6MGtA-gA_WZBtwAdoMvFATpAB-iXBZ3cij1Uh-pQHapD9WtWPTb1kt-cQ3AIrhSH4BD85gSXH5TBOBgH42D8XxkX3zEH41fy1iHIBtkg-02SHTzWwW24Dbf7JwK3o_OF26_utg3chtEwGkbDaBgd3rpXNfr0PAyoATWgBtSA-v9DXX5_9ycAAP__KvaJtg==
+
+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
diff --git a/internal/treesteps/tree_steps_test.go b/internal/treesteps/tree_steps_test.go
new file mode 100644
index 00000000..16b65d68
--- /dev/null
+++ b/internal/treesteps/tree_steps_test.go
@@ -0,0 +1,170 @@
+// Copyright 2024 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 treesteps
+
+import (
+	"math/bits"
+	"testing"
+
+	"github.com/cockroachdb/datadriven"
+)
+
+// SegmentTree implements a segment tree:
+// https://en.wikipedia.org/wiki/Segment_tree
+//
+// It stores values for points in the range [1, Range]. It can efficiently Add
+// to the value of a single point, and query the Sum of any range.
+type SegmentTree struct {
+	Range int
+	Nodes []SegmentNode
+}
+
+// SegmentNode is a node in a segment tree.
+type SegmentNode struct {
+	// Note: in a normal segment tree implementation, we would only need the sum
+	// (the other information is implicitly available as we go down the tree). But
+	// we store the other fields for the benefit of displaying them.
+	Start, End int
+	// Index of the node in Tree.Nodes.
+	Index int
+	// Sum of the values for the range [Start, End].
+	Sum  int
+	Tree *SegmentTree
+}
+
+// NewSegmentTree creates a SegmentTree with the given range.
+func NewSegmentTree(xRange int) *SegmentTree {
+	size := 1 << (bits.Len32(uint32(xRange-1)) + 1)
+	t := &SegmentTree{
+		Range: xRange,
+		Nodes: make([]SegmentNode, size),
+	}
+	t.Nodes[0] = SegmentNode{
+		Start: 1,
+		End:   xRange,
+		Tree:  t,
+		Index: 0,
+	}
+	for i := range t.Nodes {
+		if n := &t.Nodes[i]; n.End > n.Start {
+			t.Nodes[2*i+1] = SegmentNode{
+				Start: n.Start,
+				End:   (n.Start + n.End) / 2,
+				Tree:  t,
+				Index: 2*i + 1,
+			}
+			t.Nodes[2*i+2] = SegmentNode{
+				Start: (n.Start+n.End)/2 + 1,
+				End:   n.End,
+				Tree:  t,
+				Index: 2*i + 2,
+			}
+		}
+	}
+	return t
+}
+
+var _ Node = (*SegmentNode)(nil)
+
+// TreeStepsNode implements the Node interface.
+func (n *SegmentNode) TreeStepsNode() NodeInfo {
+	info := NodeInfof("n%d", n.Index)
+	info.AddPropf("range", "[%d, %d]", n.Start, n.End)
+	info.AddPropf("sum", "%d", n.Sum)
+	if n.Start < n.End {
+		info.AddChildren(
+			&n.Tree.Nodes[2*n.Index+1],
+			&n.Tree.Nodes[2*n.Index+2],
+		)
+	}
+	return info
+}
+
+// Root returns the root node of the segment tree.
+func (t *SegmentTree) Root() *SegmentNode {
+	return &t.Nodes[0]
+}
+
+// Add delta to the value for x.
+func (t *SegmentTree) Add(x int, delta int) {
+	t.add(0, x, delta)
+}
+
+func (t *SegmentTree) add(nodeIdx int, x int, delta int) {
+	n := &t.Nodes[nodeIdx]
+	if x < n.Start || n.End < x {
+		return
+	}
+	op := StartOpf(n, "add(%d, %d)", x, delta)
+	if n.Start < n.End {
+		t.add(2*nodeIdx+1, x, delta)
+		t.add(2*nodeIdx+2, x, delta)
+	}
+	n.Sum += delta
+	NodeUpdated(n, "sum updated")
+	op.Finishf("done")
+}
+
+// Sum returns the sum of the values for x1 through x2.
+func (t *SegmentTree) Sum(x1, x2 int) int {
+	return t.sum(0, x1, x2)
+}
+
+func (t *SegmentTree) sum(nodeIdx int, x1, x2 int) (result int) {
+	n := &t.Nodes[nodeIdx]
+	if x2 < n.Start || n.End < x1 {
+		return
+	}
+	if IsRecording(n) {
+		op := StartOpf(n, "sum(%d, %d)", x1, x2)
+		defer func() {
+			op.Finishf("= %d", result)
+		}()
+	}
+	if x1 <= n.Start && n.End <= x2 {
+		return n.Sum
+	}
+	return t.sum(2*nodeIdx+1, x1, x2) + t.sum(2*nodeIdx+2, x1, x2)
+}
+
+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
+		switch td.Cmd {
+		case "init":
+			var xRange int
+			td.ScanArgs(t, "range", &xRange)
+			tree = NewSegmentTree(xRange)
+			return TreeToString(tree.Root())
+
+		case "add":
+			var x, delta int
+			td.ScanArgs(t, "x", &x)
+			td.ScanArgs(t, "delta", &delta)
+			r = StartRecording(tree.Root(), "Segment Tree add")
+			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")
+			tree.Sum(x1, x2)
+
+		default:
+			td.Fatalf(t, "unknown command %q", td.Cmd)
+		}
+		if r != nil {
+			steps := r.Finish()
+			if td.HasArg("url") {
+				url := steps.URL()
+				return url.String()
+			}
+			return steps.String()
+		}
+		return ""
+	})
+}
diff --git a/level_checker_test.go b/level_checker_test.go
index 00a80c25..da26e4b9 100644
--- a/level_checker_test.go
+++ b/level_checker_test.go
@@ -201,12 +201,12 @@ func TestCheckLevelsCornerCases(t *testing.T) {
 					switch ikey.Kind() {
 					case InternalKeyKindRangeDelete:
 						if writeUnfragmented {
-							err = w.Add(ikey, value)
+							err = w.AddWithForceObsolete(ikey, value, false /* forceObsolete */)
 							break
 						}
 						frag.Add(rangedel.Decode(ikey, value, nil))
 					default:
-						err = w.Add(ikey, value)
+						err = w.AddWithForceObsolete(ikey, value, false /* forceObsolete */)
 					}
 					if err != nil {
 						return err.Error()
@@ -214,7 +214,7 @@ func TestCheckLevelsCornerCases(t *testing.T) {
 				}
 				frag.Finish()
 				for _, v := range tombstones {
-					if err := rangedel.Encode(v, w.Add); err != nil {
+					if err := w.EncodeSpan(v); err != nil {
 						return err.Error()
 					}
 				}
diff --git a/level_iter_test.go b/level_iter_test.go
index 471e8c42..28152640 100644
--- a/level_iter_test.go
+++ b/level_iter_test.go
@@ -250,14 +250,14 @@ func (lt *levelIterTest) runBuild(d *datadriven.TestData) string {
 				return err.Error()
 			}
 		default:
-			if err := w.Add(ikey, value); err != nil {
+			if err := w.AddWithForceObsolete(ikey, value, false /* forceObsolete */); err != nil {
 				return err.Error()
 			}
 		}
 	}
 	f.Finish()
 	for _, v := range tombstones {
-		if err := rangedel.Encode(v, w.Add); err != nil {
+		if err := w.EncodeSpan(v); err != nil {
 			return err.Error()
 		}
 	}
@@ -508,7 +508,7 @@ func buildLevelIterTables(
 		files[i] = f
 	}
 
-	writers := make([]*sstable.RawRowWriter, len(files))
+	writers := make([]sstable.RawWriter, len(files))
 	for i := range files {
 		writers[i] = sstable.NewRawWriter(objstorageprovider.NewFileWritable(files[i]), sstable.WriterOptions{
 			BlockRestartInterval: restartInterval,
@@ -525,7 +525,7 @@ func buildLevelIterTables(
 			key := []byte(fmt.Sprintf("%08d", i))
 			keys = append(keys, key)
 			ikey := base.MakeInternalKey(key, 0, InternalKeyKindSet)
-			w.Add(ikey, nil)
+			require.NoError(b, w.AddWithForceObsolete(ikey, nil, false /* forceObsolete */))
 		}
 		if err := w.Close(); err != nil {
 			b.Fatal(err)
diff --git a/merging_iter_test.go b/merging_iter_test.go
index 2e2ed5de..91e0a397 100644
--- a/merging_iter_test.go
+++ b/merging_iter_test.go
@@ -20,7 +20,6 @@ import (
 	"github.com/cockroachdb/pebble/internal/itertest"
 	"github.com/cockroachdb/pebble/internal/keyspan"
 	"github.com/cockroachdb/pebble/internal/manifest"
-	"github.com/cockroachdb/pebble/internal/rangedel"
 	"github.com/cockroachdb/pebble/internal/sstableinternal"
 	"github.com/cockroachdb/pebble/internal/testkeys"
 	"github.com/cockroachdb/pebble/objstorage/objstorageprovider"
@@ -240,14 +239,14 @@ func TestMergingIterCornerCases(t *testing.T) {
 					case InternalKeyKindRangeDelete:
 						frag.Add(keyspan.Span{Start: ikey.UserKey, End: value, Keys: []keyspan.Key{{Trailer: ikey.Trailer}}})
 					default:
-						if err := w.Add(ikey, value); err != nil {
+						if err := w.AddWithForceObsolete(ikey, value, false /* forceObsolete */); err != nil {
 							return err.Error()
 						}
 					}
 				}
 				frag.Finish()
 				for _, v := range tombstones {
-					if err := rangedel.Encode(v, w.Add); err != nil {
+					if err := w.EncodeSpan(v); err != nil {
 						return err.Error()
 					}
 				}
@@ -340,7 +339,7 @@ func buildMergingIterTables(
 		files[i] = f
 	}
 
-	writers := make([]*sstable.RawRowWriter, len(files))
+	writers := make([]sstable.RawWriter, len(files))
 	for i := range files {
 		writers[i] = sstable.NewRawWriter(objstorageprovider.NewFileWritable(files[i]), sstable.WriterOptions{
 			BlockRestartInterval: restartInterval,
@@ -366,7 +365,7 @@ func buildMergingIterTables(
 		ikey.UserKey = key
 		j := rand.Intn(len(writers))
 		w := writers[j]
-		w.Add(ikey, nil)
+		w.AddWithForceObsolete(ikey, nil, false /* forceObsolete */)
 	}
 
 	for _, w := range writers {
@@ -543,7 +542,7 @@ func buildLevelsForMergingIterSeqSeek(
 	}
 
 	const targetL6FirstFileSize = 2 << 20
-	writers := make([][]*sstable.RawRowWriter, levelCount)
+	writers := make([][]sstable.RawWriter, levelCount)
 	// A policy unlikely to have false positives.
 	filterPolicy := bloom.FilterPolicy(100)
 	for i := range files {
@@ -583,23 +582,28 @@ func buildLevelsForMergingIterSeqSeek(
 		key := []byte(fmt.Sprintf("%08d", i))
 		keys = append(keys, key)
 		ikey := base.MakeInternalKey(key, 0, InternalKeyKindSet)
-		w.Add(ikey, nil)
+		require.NoError(b, w.AddWithForceObsolete(ikey, nil, false /* forceObsolete */))
 	}
 	if writeRangeTombstoneToLowestLevel {
-		tombstoneKey := base.MakeInternalKey(keys[0], 1, InternalKeyKindRangeDelete)
-		w.Add(tombstoneKey, []byte(fmt.Sprintf("%08d", i)))
+		require.NoError(b, w.EncodeSpan(keyspan.Span{
+			Start: keys[0],
+			End:   []byte(fmt.Sprintf("%08d", i)),
+			Keys: []keyspan.Key{{
+				Trailer: base.MakeTrailer(1, InternalKeyKindRangeDelete),
+			}},
+		}))
 	}
 	for j := 1; j < len(files); j++ {
 		for _, k := range []int{0, len(keys) - 1} {
 			ikey := base.MakeInternalKey(keys[k], base.SeqNum(j), InternalKeyKindSet)
-			writers[j][0].Add(ikey, nil)
+			require.NoError(b, writers[j][0].AddWithForceObsolete(ikey, nil, false /* forceObsolete */))
 		}
 	}
 	lastKey := []byte(fmt.Sprintf("%08d", i))
 	keys = append(keys, lastKey)
 	for j := 0; j < len(files); j++ {
 		lastIKey := base.MakeInternalKey(lastKey, base.SeqNum(j), InternalKeyKindSet)
-		writers[j][1].Add(lastIKey, nil)
+		require.NoError(b, writers[j][1].AddWithForceObsolete(lastIKey, nil, false /* forceObsolete */))
 	}
 	for _, levelWriters := range writers {
 		for j, w := range levelWriters {
diff --git a/range_del_test.go b/range_del_test.go
index 7a051f56..6e90fee9 100644
--- a/range_del_test.go
+++ b/range_del_test.go
@@ -603,7 +603,7 @@ func benchmarkRangeDelIterate(b *testing.B, entries, deleted int, snapshotCompac
 	})
 	for i := 0; i < entries; i++ {
 		key := base.MakeInternalKey(makeKey(i), 0, InternalKeyKindSet)
-		if err := w.Add(key, nil); err != nil {
+		if err := w.AddWithForceObsolete(key, nil, false /* forceObsolete */); err != nil {
 			b.Fatal(err)
 		}
 	}
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 {
diff --git a/sstable/random_test.go b/sstable/random_test.go
index abbe438a..ebf7055c 100644
--- a/sstable/random_test.go
+++ b/sstable/random_test.go
@@ -391,7 +391,7 @@ func buildRandomSSTable(f vfs.File, cfg randomTableConfig) (*WriterMetadata, err
 			value = valueBuf[:cfg.rng.Intn(cfg.maxValLen+1)]
 			cfg.rng.Read(value)
 		}
-		if err := w.Add(keys[i], value); err != nil {
+		if err := w.AddWithForceObsolete(keys[i], value, false /* forceObsolete */); err != nil {
 			return nil, err
 		}
 	}
diff --git a/sstable/reader_test.go b/sstable/reader_test.go
index 16400ccf..6b2e0610 100644
--- a/sstable/reader_test.go
+++ b/sstable/reader_test.go
@@ -1804,7 +1804,7 @@ func buildTestTableWithProvider(
 		value := make([]byte, i%100)
 		key = binary.BigEndian.AppendUint64(key, i)
 		ikey.UserKey = key
-		w.Add(ikey, value)
+		require.NoError(t, w.AddWithForceObsolete(ikey, value, false /* forceObsolete */))
 	}
 
 	require.NoError(t, w.Close())
@@ -1844,7 +1844,7 @@ func buildBenchmarkTable(
 		binary.BigEndian.PutUint64(key, i+uint64(offset))
 		keys = append(keys, key)
 		ikey.UserKey = key
-		w.Add(ikey, nil)
+		require.NoError(b, w.AddWithForceObsolete(ikey, nil, false /* forceObsolete */))
 	}
 
 	if err := w.Close(); err != nil {
diff --git a/sstable/table_test.go b/sstable/table_test.go
index fb564965..4b9a42fe 100644
--- a/sstable/table_test.go
+++ b/sstable/table_test.go
@@ -465,7 +465,7 @@ func TestFinalBlockIsWritten(t *testing.T) {
 						IndexBlockSize: indexBlockSize,
 					})
 					for _, k := range keys[:nk] {
-						if err := w.Add(InternalKey{UserKey: []byte(k)}, xxx[:vLen]); err != nil {
+						if err := w.AddWithForceObsolete(InternalKey{UserKey: []byte(k)}, xxx[:vLen], false /* forceObsolete */); err != nil {
 							t.Errorf("nk=%d, vLen=%d: set: %v", nk, vLen, err)
 							continue loop
 						}
diff --git a/sstable/writer_test.go b/sstable/writer_test.go
index 0662cf61..d203da76 100644
--- a/sstable/writer_test.go
+++ b/sstable/writer_test.go
@@ -864,7 +864,7 @@ func TestWriterBlockPropertiesErrors(t *testing.T) {
 				}
 			}()
 
-			err = w.Add(k1, v1)
+			err = w.AddWithForceObsolete(k1, v1, false /* forceObsolete */)
 			switch tc {
 			case errSiteAdd:
 				require.Error(t, err)
@@ -873,18 +873,18 @@ func TestWriterBlockPropertiesErrors(t *testing.T) {
 			case errSiteFinishBlock:
 				require.NoError(t, err)
 				// Addition of a second key completes the first block.
-				err = w.Add(k2, v2)
+				err = w.AddWithForceObsolete(k2, v2, false /* forceObsolete */)
 				require.Error(t, err)
 				require.Equal(t, blockPropErr, err)
 				return
 			case errSiteFinishIndex:
 				require.NoError(t, err)
 				// Addition of a second key completes the first block.
-				err = w.Add(k2, v2)
+				err = w.AddWithForceObsolete(k2, v2, false /* forceObsolete */)
 				require.NoError(t, err)
 				// The index entry for the first block is added after the completion of
 				// the second block, which is triggered by adding a third key.
-				err = w.Add(k3, v3)
+				err = w.AddWithForceObsolete(k3, v3, false /* forceObsolete */)
 				require.Error(t, err)
 				require.Equal(t, blockPropErr, err)
 				return
@@ -990,12 +990,10 @@ func TestWriterRace(t *testing.T) {
 			}
 			defer wg.Done()
 			f := &objstorage.MemObj{}
-			w := NewRawWriter(f, opts)
+			w := newRowWriter(f, opts)
 			for ki := 0; ki < len(keys); ki++ {
-				require.NoError(
-					t,
-					w.Add(base.MakeInternalKey(keys[ki], base.SeqNum(ki), InternalKeyKindSet), val),
-				)
+				require.NoError(t, w.AddWithForceObsolete(
+					base.MakeInternalKey(keys[ki], base.SeqNum(ki), InternalKeyKindSet), val, false /* forceObsolete */))
 				require.Equal(
 					t, w.dataBlockBuf.dataBlock.CurKey().UserKey, keys[ki],
 				)
diff --git a/table_stats_test.go b/table_stats_test.go
index f2cb0d2c..3293f559 100644
--- a/table_stats_test.go
+++ b/table_stats_test.go
@@ -215,7 +215,7 @@ func TestTableRangeDeletionIter(t *testing.T) {
 						rKeySpan.Keys = append(rKeySpan.Keys, k)
 					} else {
 						k := base.InternalKey{UserKey: s.Start, Trailer: k.Trailer}
-						if err = w.Add(k, s.End); err != nil {
+						if err = w.AddWithForceObsolete(k, s.End, false /* forceObsolete */); err != nil {
 							return err.Error()
 						}
 					}
diff --git a/version_set_test.go b/version_set_test.go
index e76d5cad..38a3f49c 100644
--- a/version_set_test.go
+++ b/version_set_test.go
@@ -32,7 +32,7 @@ func writeAndIngest(t *testing.T, mem vfs.FS, d *DB, k InternalKey, v []byte, fi
 	f, err := mem.Create(path, vfs.WriteCategoryUnspecified)
 	require.NoError(t, err)
 	w := sstable.NewRawWriter(objstorageprovider.NewFileWritable(f), sstable.WriterOptions{})
-	require.NoError(t, w.Add(k, v))
+	require.NoError(t, w.AddWithForceObsolete(k, v, false /* forceObsolete */))
 	require.NoError(t, w.Close())
 	require.NoError(t, d.Ingest(context.Background(), []string{path}))
 }