Repository: cockroachdb/pebble
Pull request #742 (2020-06-15 06:07:19)

db: use lock free rand for skiplist
Currnely, when write in batch, pebble use a rand with mutex to generate random height for skiplist. This is so much slow where write is heavy. In my benchmark,  [`skiplist.randomheight`](https://github.com/cockroachdb/pebble/blob/master/internal/arenaskl/skl.go#L349-L360) costs about 1/3 of time. By replace it with [`runtime.fastrand`](https://golang.org/pkg/runtime/?m=all#fastrand) provided by go runtime, this costs disappears.

When there is little(or none) deleted keys in db, `isNextEntryDeleted` still takes more the 60% of the cpu times. So add a slice to record sub iters that contains deletes can eliminate this cost.

petermattis: 

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

glorv: @petermattis  I add a benchmark for fastrand and the origin rand implement, the result is as follows:
```
$ go test -cpu 1,2,4,8,16,32 -bench=.
goos: linux
goarch: amd64
pkg: github.com/cockroachdb/pebble/internal/randvar
BenchmarkFastRand          	339266436	         3.46 ns/op
BenchmarkFastRand-2        	642935722	         1.81 ns/op
BenchmarkFastRand-4        	1000000000	         0.973 ns/op
BenchmarkFastRand-8        	1000000000	         0.509 ns/op
BenchmarkFastRand-16       	1000000000	         0.294 ns/op
BenchmarkFastRand-32       	1000000000	         0.217 ns/op
BenchmarkDefaultRand       	64620588	        19.1 ns/op
BenchmarkDefaultRand-2     	27767486	        43.6 ns/op
BenchmarkDefaultRand-4     	 9757675	       138 ns/op
BenchmarkDefaultRand-8     	 6172735	       202 ns/op
BenchmarkDefaultRand-16    	 6602660	       182 ns/op
BenchmarkDefaultRand-32    	 6674312	       183 ns/op
```
so with a higher concurrency, the random impl with mutex does have some impact when the throughput is high.
glorv: > > _[Reviewable](https://reviewable.io/reviews/cockroachdb/pebble/742)_ status: 0 of 3 files reviewed, 3 unresolved discussions (waiting on @glorv)
> 
> _[merging_iter.go, line 262 at r3](https://reviewable.io/reviews/cockroachdb/pebble/742#-M9rvW_2CM6GhHdO5hbM:-M9rvW_2CM6GhHdO5hbN:byplai3) ([raw file](https://github.com/cockroachdb/pebble/blob/724f1277e6da74ba707986adfeed8612e10dfa97/merging_iter.go#L262)):_
> 
> > ```go
> > 	hasDelLevels := make([]int, 0, len(levels))
> > 	for i, l := range levels {
> > 		if l.rangeDelIter != nil || mayHaveDeletion(l.iter) {
> > ```
> 
> I don't think this is sufficient. A level for which `l.iter.(*levelIter)` is true will have a `l.rangeDelIter` that can switch from nil to non-nil as we iterate through the level.

We uses pebble as a temp storage to sort huge numbers of key-values pairs. In some benchmark, the level compaction will make it about 10% slower as we only write and then scan all the key-values once. Thus there are several hundred of level 1 sst files that make the `isNextEntryDeleted ` quite slow. 
BTW, It seems the deletions informations are stored in the meta fields in sst files. And In my test, even if there is no deletion, many of the `levelIter.rangeDelIter`s  are not nil, so the logic to skip deletion check base on this won't help much besides it will change in runtime.



petermattis: > $ go test -cpu 1,2,4,8,16,32 -bench=.

For Go benchmarks, and benchmarks in general, it is usually good to run the benchmarks multiple times and perform some statistical analysis to exclude outliers. With Go, this is usually done by running with `-count=10` or `-count=20` and using [benchstat](https://godoc.org/golang.org/x/perf/cmd/benchstat) to process the output.

> so with a higher concurrency, the random impl with mutex does have some impact when the throughput is high.

I'm not particularly surprised that `fastrand` shows better performance under contention. The question is whether this matters for the `arenaskl` benchmarks. See https://github.com/cockroachdb/pebble/pull/583 and the discussion there for when this previously came up. I'm not against this change on principle, but I would like to see it move the needle on the arenaskl benchmarks. It is possible a new benchmark needs to be added that properly demonstrates contention on this mutex under concurrent insertions.

> We uses pebble as a temp storage to sort huge numbers of key-values pairs. In some benchmark, the level compaction will make it about 10% slower as we only write and then scan all the key-values once. Thus there are several hundred of level 1 sst files that make the isNextEntryDeleted quite slow.

I believe you meant there are several hundred Level 0 sstables. Several hundered Level 1 sstables will not benefit from this change as they will be contiguous and non-overlapping. But I don't think this change will benefit the several hundred Level 0 sstable case either as we now wrap the Level 0 sstables in `levelIter`.

> BTW, It seems the deletions informations are stored in the meta fields in sst files. And In my test, even if there is no deletion, many of the levelIter.rangeDelIters are not nil, so the logic to skip deletion check base on this won't help much besides it will change in runtime.

The deletion information stored in `FileMetadata` is populated lazily and cannot be relied on to be present by `mergingIter`. I'm not currently seeing a good way to accomplish an improvement for your use case in a clean manner, but let me think about it more. 
nvanbenschoten: @petermattis I made the corresponding change to `github.com/andy-kimball/arenaskl` in https://github.com/andy-kimball/arenaskl/pull/10. Here are the results from that library's benchmarks:
```
name                     old time/op    new time/op    delta
ReadWrite/frac_0-16         380ns ± 7%     324ns ± 3%  -14.75%  (p=0.000 n=10+10)
ReadWrite/frac_30-16        314ns ± 8%     273ns ± 6%  -12.92%  (p=0.000 n=10+10)
ReadWrite/frac_10-16        350ns ± 6%     306ns ± 6%  -12.38%  (p=0.000 n=10+10)
ReadWrite/frac_20-16        328ns ± 9%     291ns ± 4%  -11.52%  (p=0.000 n=10+9)
ReadWrite/frac_40-16        289ns ± 4%     256ns ± 4%  -11.26%  (p=0.000 n=9+9)
ReadWrite/frac_60-16        237ns ± 6%     214ns ± 4%   -9.58%  (p=0.000 n=10+9)
ReadWrite/frac_50-16        262ns ± 6%     237ns ± 4%   -9.52%  (p=0.000 n=10+10)
ReadWrite/frac_70-16        213ns ± 2%     194ns ± 2%   -8.87%  (p=0.000 n=9+10)
ReadWrite/frac_80-16        176ns ± 3%     171ns ± 7%   -2.85%  (p=0.009 n=9+9)
ReadWrite/frac_90-16        135ns ± 3%     135ns ± 9%     ~     (p=0.303 n=9+10)
ReadWrite/frac_100-16      7.03ns ±11%    6.99ns ±12%     ~     (p=0.748 n=9+9)
```
glorv: @petermattis  I updated the pr , PTAL again. And thanks @nvanbenschoten for the comments and benchmark

Patch:
diff --git a/checkpoint.go b/checkpoint.go
index 1f14dee1..ded0a321 100644
--- a/checkpoint.go
+++ b/checkpoint.go
@@ -42,11 +42,6 @@ func (d *DB) Checkpoint(destDir string) (err error) {
 	// large, or roll the manifest if the MANIFEST size is too large. Should we
 	// do this too?
 
-	// Lock the manifest before getting the current version. We need the
-	// length of the manifest that we read to match the current version that
-	// we read, otherwise we might copy a versionEdit not reflected in the
-	// sstables we copy/link.
-	d.mu.versions.logLock()
 	// Get the unflushed log files, the current version, and the current manifest
 	// file number.
 	memQueue := d.mu.mem.queue
@@ -55,9 +50,7 @@ func (d *DB) Checkpoint(destDir string) (err error) {
 	manifestSize := d.mu.versions.manifest.Size()
 	optionsFileNum := d.optionsFileNum
 
-	// Release the manifest and DB.mu so we don't block other operations on
-	// the database.
-	d.mu.versions.logUnlock()
+	// Release DB.mu so we don't block other operations on the database.
 	d.mu.Unlock()
 
 	// Wrap the normal filesystem with one which wraps newly created files with
diff --git a/cmd/pebble/ycsb.go b/cmd/pebble/ycsb.go
index 3d0fb110..f6aec35e 100644
--- a/cmd/pebble/ycsb.go
+++ b/cmd/pebble/ycsb.go
@@ -243,18 +243,20 @@ type ycsbBuf struct {
 }
 
 type ycsb struct {
-	writeOpts *pebble.WriteOptions
-	weights   ycsbWeights
-	reg       *histogramRegistry
-	ops       *randvar.Weighted
-	keyDist   randvar.Dynamic
-	batchDist randvar.Static
-	scanDist  randvar.Static
-	valueDist *randvar.BytesFlag
-	keyNum    *ackseq.S
-	numOps    uint64
-	limiter   *rate.Limiter
-	opsMap    map[string]int
+	writeOpts   *pebble.WriteOptions
+	weights     ycsbWeights
+	reg         *histogramRegistry
+	ops         *randvar.Weighted
+	keyDist     randvar.Dynamic
+	batchDist   randvar.Static
+	scanDist    randvar.Static
+	valueDist   *randvar.BytesFlag
+	keyNum      *ackseq.S
+	numOps      uint64
+	numKeys     [ycsbNumOps]uint64
+	prevNumKeys [ycsbNumOps]uint64
+	limiter     *rate.Limiter
+	opsMap      map[string]int
 }
 
 func newYcsb(
@@ -445,6 +447,7 @@ func (y *ycsb) insert(db DB, buf *ycsbBuf) {
 		log.Fatal(err)
 	}
 	_ = b.Close()
+	atomic.AddUint64(&y.numKeys[ycsbInsert], uint64(len(keyNums)))
 
 	for i := range keyNums {
 		delta, err := y.keyNum.Ack(keyNums[i])
@@ -468,6 +471,7 @@ func (y *ycsb) read(db DB, buf *ycsbBuf) {
 	if err := iter.Close(); err != nil {
 		log.Fatal(err)
 	}
+	atomic.AddUint64(&y.numKeys[ycsbRead], 1)
 }
 
 func (y *ycsb) scan(db DB, buf *ycsbBuf, reverse bool) {
@@ -476,6 +480,11 @@ func (y *ycsb) scan(db DB, buf *ycsbBuf, reverse bool) {
 	if err := db.Scan(key, int64(count), reverse); err != nil {
 		log.Fatal(err)
 	}
+	if reverse {
+		atomic.AddUint64(&y.numKeys[ycsbReverseScan], count)
+	} else {
+		atomic.AddUint64(&y.numKeys[ycsbScan], count)
+	}
 }
 
 func (y *ycsb) update(db DB, buf *ycsbBuf) {
@@ -488,36 +497,44 @@ func (y *ycsb) update(db DB, buf *ycsbBuf) {
 		log.Fatal(err)
 	}
 	_ = b.Close()
+	atomic.AddUint64(&y.numKeys[ycsbUpdate], uint64(count))
 }
 
 func (y *ycsb) tick(elapsed time.Duration, i int) {
 	if i%20 == 0 {
-		fmt.Println("____optype__elapsed__ops/sec(inst)___ops/sec(cum)__p50(ms)__p95(ms)__p99(ms)_pMax(ms)")
+		fmt.Println("____optype__elapsed____ops/sec___keys/sec__p50(ms)__p95(ms)__p99(ms)_pMax(ms)")
 	}
 	y.reg.Tick(func(tick histogramTick) {
+		op := y.opsMap[tick.Name]
+		numKeys := atomic.LoadUint64(&y.numKeys[op])
 		h := tick.Hist
 
-		fmt.Printf("%10s %8s %14.1f %14.1f %8.1f %8.1f %8.1f %8.1f\n",
+		fmt.Printf("%10s %8s %10.1f %10.1f %8.1f %8.1f %8.1f %8.1f\n",
 			tick.Name,
 			time.Duration(elapsed.Seconds()+0.5)*time.Second,
 			float64(h.TotalCount())/tick.Elapsed.Seconds(),
-			float64(tick.Cumulative.TotalCount())/elapsed.Seconds(),
+			float64(numKeys-y.prevNumKeys[op])/tick.Elapsed.Seconds(),
 			time.Duration(h.ValueAtQuantile(50)).Seconds()*1000,
 			time.Duration(h.ValueAtQuantile(95)).Seconds()*1000,
 			time.Duration(h.ValueAtQuantile(99)).Seconds()*1000,
 			time.Duration(h.ValueAtQuantile(100)).Seconds()*1000,
 		)
+
+		y.prevNumKeys[op] = numKeys
 	})
 }
 
 func (y *ycsb) done(elapsed time.Duration) {
-	fmt.Println("\n____optype__elapsed_____ops(total)___ops/sec(cum)__avg(ms)__p50(ms)__p95(ms)__p99(ms)_pMax(ms)")
+	fmt.Println("\n____optype__elapsed_____ops(total)___ops/sec(cum)__keys/sec(cum)__avg(ms)__p50(ms)__p95(ms)__p99(ms)_pMax(ms)")
 	y.reg.Tick(func(tick histogramTick) {
+		op := y.opsMap[tick.Name]
+		numKeys := atomic.LoadUint64(&y.numKeys[op])
 		h := tick.Cumulative
 
-		fmt.Printf("%10s %7.1fs %14d %14.1f %8.1f %8.1f %8.1f %8.1f %8.1f\n",
+		fmt.Printf("%10s %7.1fs %14d %14.1f %14.1f %8.1f %8.1f %8.1f %8.1f %8.1f\n",
 			tick.Name, elapsed.Seconds(), h.TotalCount(),
 			float64(h.TotalCount())/elapsed.Seconds(),
+			float64(numKeys)/elapsed.Seconds(),
 			time.Duration(h.Mean()).Seconds()*1000,
 			time.Duration(h.ValueAtQuantile(50)).Seconds()*1000,
 			time.Duration(h.ValueAtQuantile(95)).Seconds()*1000,
diff --git a/compaction.go b/compaction.go
index 75e7e1a0..e47568b9 100644
--- a/compaction.go
+++ b/compaction.go
@@ -1824,7 +1824,7 @@ func (d *DB) disableFileDeletions() {
 	for d.mu.cleaner.cleaning {
 		d.mu.cleaner.cond.Wait()
 	}
-	d.mu.cleaner.cond.Broadcast()
+	d.mu.cleaner.cond.Signal()
 }
 
 // enableFileDeletions enables previously disabled file deletions. Note that if
@@ -1866,7 +1866,7 @@ func (d *DB) acquireCleaningTurn(waitForOngoing bool) bool {
 // d.mu must be held when calling this.
 func (d *DB) releaseCleaningTurn() {
 	d.mu.cleaner.cleaning = false
-	d.mu.cleaner.cond.Broadcast()
+	d.mu.cleaner.cond.Signal()
 }
 
 // deleteObsoleteFiles deletes those files that are no longer needed.
diff --git a/compaction_picker.go b/compaction_picker.go
index 82010274..1ed79a48 100644
--- a/compaction_picker.go
+++ b/compaction_picker.go
@@ -163,31 +163,7 @@ func (p *compactionPickerByScore) estimatedCompactionDebt(l0ExtraSize uint64) ui
 }
 
 func (p *compactionPickerByScore) initLevelMaxBytes(inProgressCompactions []compactionInfo) {
-	// The levelMaxBytes calculations here differ from RocksDB in two ways:
-	//
-	// 1. The use of bottomLevelSize vs maxLevelSize. RocksDB uses the size of
-	//    the maximum level in L1-L6, rather than the size of the bottommost
-	//    non-empty level. In practice this seems to have little impact.
-	//
-	// 2. Not adjusting the size of base level based on L0. RocksDB computes
-	//    baseBytesMax as the maximum of the configured LBaseMaxBytes and the
-	//    size of L0. This is problematic because baseBytesMax is used to compute
-	//    the max size of lower levels. A very large baseBytesMax will result in
-	//    an overly large value for the size of lower levels which will caused
-	//    those levels not to be compacted even when they should be
-	//    compacted. This often results in "inverted" LSM shapes where Ln is
-	//    larger than Ln+1.
-	//
-	// TODO(peter): An alternative to the current calculation of bottomLevelSize
-	// is to compute the total number of bytes in the LSM and then compute
-	// bottomLevelSize as 90% of that value (presuming a level multiplier of
-	// 10). This computation has the advantage of being stable: it changes at the
-	// rate that data is inserted into the DB, independently of
-	// compactions. Unfortunately, it performed worse experimentally and often
-	// resulted in "inverted" LSM shapes where L5 was significantly larger than
-	// L6. The reason for this inversion was not clear.
-
-	// Determine the first non-empty level and the bottom level size.
+	// Determine the first non-empty level and the maximum size of any level.
 	firstNonEmptyLevel := -1
 	var bottomLevelSize int64
 	for level := 1; level < numLevels; level++ {
@@ -236,9 +212,9 @@ func (p *compactionPickerByScore) initLevelMaxBytes(inProgressCompactions []comp
 	}
 
 	if curLevelSize <= baseBytesMin {
-		// If we make target size of last level to be bottomLevelSize, target size
-		// of the first non-empty level would be smaller than baseBytesMin. We set
-		// it be baseBytesMin.
+		// If we make target size of last level to be bottomLevelSize, target size of
+		// the first non-empty level would be smaller than baseBytesMin. We set it
+		// be baseBytesMin.
 		p.baseLevel = firstNonEmptyLevel
 	} else {
 		// Compute base level (where L0 data is compacted to).
@@ -447,35 +423,7 @@ func (p *compactionPickerByScore) pickFile(level int) int {
 // If a score-based compaction cannot be found, pickAuto falls back to looking
 // for a forced compaction (identified by FileMetadata.MarkedForCompaction).
 func (p *compactionPickerByScore) pickAuto(env compactionEnv) (c *compaction) {
-	// highPriorityThreshold controls compaction concurrency. If there is already
-	// a compaction in progress, highPriorityThreshold is set to the minimum
-	// score needed for a concurrent compaction to be initiated. Since all level
-	// scores are >= 0, a positive value will cause compactions to be
-	// disabled. We set highPriorityThreshold to a value only when a there is at
-	// least one in-progress compaction. Concurrent compactions are useful for
-	// ensuring that compaction doesn't fall far behind, but concurrent
-	// compactions can have an adverse affect on write throughput.
-	//
-	// There are a variety of possibilities for choosing highPriorityThreshold:
-	// - A fixed value: 1.5.
-	// - A value linear in the number of in-progress compactions: 2, 3, 4.
-	// - A value exponential in the number of in-progress compactions: 2, 4, 8.
-	//
-	// A fixed value tends to allow too much compaction concurrency. There was
-	// only a minor difference between the linear and exponential values, making
-	// the choice of exponential below somewhat arbitrary.
-	//
-	// For comparison, RocksDB alternates between only allowing a single
-	// compaction at a time to allowing the configured maximum number of
-	// concurrent compactions depending on whether compaction-debt has gotten too
-	// large or the number of L0 sstables has reached 2x the L0 compaction
-	// threshold. In testing, it is usually the latter condition that triggers
-	// concurrent compactions in RocksDB.
-	var highPriorityThreshold float64
-	if len(env.inProgressCompactions) > 0 {
-		// Exponential high priority threshold: 2, 4, 8, ...
-		highPriorityThreshold = float64(int(1) << len(env.inProgressCompactions))
-	}
+	const highPriorityThreshold = 1.5
 
 	scores := p.calculateScores(env.inProgressCompactions)
 
@@ -484,7 +432,7 @@ func (p *compactionPickerByScore) pickAuto(env compactionEnv) (c *compaction) {
 	// compaction anchored at at that level.
 	for i := range scores {
 		info := &scores[i]
-		if info.score < highPriorityThreshold {
+		if len(env.inProgressCompactions) > 0 && info.score < highPriorityThreshold {
 			// Don't start a low priority compaction if there is already a compaction
 			// running.
 			return nil
@@ -620,7 +568,7 @@ func pickL0(env compactionEnv, opts *Options, vers *version, baseLevel int) (c *
 	// compaction.
 	lcf, err = vers.L0Sublevels.PickIntraL0Compaction(env.earliestUnflushedSeqNum, opts.L0CompactionThreshold)
 	if err != nil {
-		opts.Logger.Infof("error when picking intra-L0 compaction: %s", err)
+		opts.Logger.Infof("error when picking base compaction: %s", err)
 		return
 	}
 	if lcf != nil {
diff --git a/db.go b/db.go
index 8a7e506d..761feeaf 100644
--- a/db.go
+++ b/db.go
@@ -789,11 +789,11 @@ func (d *DB) NewSnapshot() *Snapshot {
 		panic(ErrClosed)
 	}
 
-	d.mu.Lock()
 	s := &Snapshot{
 		db:     d,
 		seqNum: atomic.LoadUint64(&d.mu.versions.visibleSeqNum),
 	}
+	d.mu.Lock()
 	d.mu.snapshots.pushBack(s)
 	d.mu.Unlock()
 	return s
diff --git a/internal/arenaskl/skl.go b/internal/arenaskl/skl.go
index 6b88d2ae..3f294476 100644
--- a/internal/arenaskl/skl.go
+++ b/internal/arenaskl/skl.go
@@ -47,14 +47,12 @@ import (
 	"encoding/binary"
 	"math"
 	"runtime"
-	"sync"
 	"sync/atomic"
-	"time"
 	"unsafe"
 
 	"github.com/cockroachdb/errors"
 	"github.com/cockroachdb/pebble/internal/base"
-	"golang.org/x/exp/rand"
+	"github.com/cockroachdb/pebble/internal/fastrand"
 )
 
 const (
@@ -84,11 +82,6 @@ type Skiplist struct {
 	tail   *node
 	height uint32 // Current height. 1 <= height <= maxHeight. CAS.
 
-	rand struct {
-		sync.Mutex
-		src rand.PCGSource
-	}
-
 	// If set to true by tests, then extra delays are added to make it easier to
 	// detect unusual race conditions.
 	testing bool
@@ -158,7 +151,6 @@ func (s *Skiplist) Reset(arena *Arena, cmp base.Compare) {
 		tail:   tail,
 		height: 1,
 	}
-	s.rand.src.Seed(uint64(time.Now().UnixNano()))
 }
 
 // Height returns the height of the highest tower within any of the nodes that
@@ -347,9 +339,7 @@ func (s *Skiplist) newNode(
 }
 
 func (s *Skiplist) randomHeight() uint32 {
-	s.rand.Lock()
-	rnd := uint32(s.rand.src.Uint64())
-	s.rand.Unlock()
+	rnd := fastrand.Uint32()
 
 	h := uint32(1)
 	for h < maxHeight && rnd <= probabilities[h] {
diff --git a/internal/fastrand/fastrand.go b/internal/fastrand/fastrand.go
new file mode 100644
index 00000000..c9d88f5e
--- /dev/null
+++ b/internal/fastrand/fastrand.go
@@ -0,0 +1,13 @@
+// Copyright 2020 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 fastrand
+
+import (
+	_ "unsafe" // required by go:linkname
+)
+
+// Uint32 returns a lock free uint32 value.
+//go:linkname Uint32 runtime.fastrand
+func Uint32() uint32
diff --git a/internal/manifest/l0_sublevels.go b/internal/manifest/l0_sublevels.go
index 3000dedd..dfbcb052 100644
--- a/internal/manifest/l0_sublevels.go
+++ b/internal/manifest/l0_sublevels.go
@@ -1125,9 +1125,11 @@ func (s *L0Sublevels) PickIntraL0Compaction(
 			return nil, errors.New("no seed file found in sublevel intervals")
 		}
 		if f.Compacting {
-			// This file could be in a concurrent intra-L0 or base compaction.
-			// Try another interval.
-			continue
+			// We chose a compaction seed file that should not be
+			// compacting. Usually means the score is not accurately
+			// accounting for files already compacting, or internal state is
+			// inconsistent.
+			return nil, errors.Errorf("file %d chosen as seed file for compaction should not be compacting", f.FileNum)
 		}
 
 		// We have a seed file. Build a compaction off of that seed.
diff --git a/internal/metamorphic/history.go b/internal/metamorphic/history.go
index 64c6aaa1..3311b3be 100644
--- a/internal/metamorphic/history.go
+++ b/internal/metamorphic/history.go
@@ -10,17 +10,13 @@ import (
 	"log"
 	"regexp"
 	"strings"
-	"sync/atomic"
 
-	"github.com/cockroachdb/errors"
+	"github.com/cockroachdb/pebble"
 )
 
 // history records the results of running a series of operations.
-//
-// history also implements the pebble.Logger interface, outputting to a stdlib
-// logger, prefixing the log messages with "//"-style comments.
 type history struct {
-	err    atomic.Value
+	failed bool
 	failRE *regexp.Regexp
 	log    *log.Logger
 	seq    int
@@ -52,21 +48,29 @@ func (h *history) Recordf(format string, args ...interface{}) {
 	h.log.Print(m)
 
 	if h.failRE != nil && h.failRE.MatchString(m) {
-		err := errors.Errorf("failure regexp %q matched output: %s", h.failRE, m)
-		h.err.Store(err)
+		h.failed = true
 	}
 }
 
-// Error returns an error if the test has failed from log output, either a
-// failure regexp match or a call to Fatalf.
-func (h *history) Error() error {
-	if v := h.err.Load(); v != nil {
-		return v.(error)
-	}
-	return nil
+// Failed returns true if the fail regular expression has matched the results
+// of an operation.
+func (h *history) Failed() bool {
+	return h.failed
+}
+
+// Logger returns a pebble.Logger that will output to history.
+func (h *history) Logger() pebble.Logger {
+	return &historyLogger{log: h.log}
+}
+
+// historyLogger is an implementation of the pebble.Logger interface which
+// outputs to a stdlib logger, prefixing the log messages with "//"-style
+// comments.
+type historyLogger struct {
+	log *log.Logger
 }
 
-func (h *history) format(prefix, format string, args ...interface{}) string {
+func (h *historyLogger) format(prefix, format string, args ...interface{}) string {
 	var buf strings.Builder
 	orig := fmt.Sprintf(format, args...)
 	for _, line := range strings.Split(strings.TrimSpace(orig), "\n") {
@@ -79,13 +83,12 @@ func (h *history) format(prefix, format string, args ...interface{}) string {
 
 // Infof implements the pebble.Logger interface. Note that the output is
 // commented.
-func (h *history) Infof(format string, args ...interface{}) {
+func (h *historyLogger) Infof(format string, args ...interface{}) {
 	_ = h.log.Output(2, h.format("// INFO: ", format, args...))
 }
 
 // Fatalf implements the pebble.Logger interface. Note that the output is
 // commented.
-func (h *history) Fatalf(format string, args ...interface{}) {
+func (h *historyLogger) Fatalf(format string, args ...interface{}) {
 	_ = h.log.Output(2, h.format("// FATAL: ", format, args...))
-	h.err.Store(errors.Errorf(format, args...))
 }
diff --git a/internal/metamorphic/ops.go b/internal/metamorphic/ops.go
index 6532312e..63f213af 100644
--- a/internal/metamorphic/ops.go
+++ b/internal/metamorphic/ops.go
@@ -7,6 +7,7 @@ package metamorphic
 import (
 	"fmt"
 	"io"
+	"os"
 	"strings"
 
 	"github.com/cockroachdb/errors"
@@ -633,7 +634,8 @@ type dbRestartOp struct {
 func (o *dbRestartOp) run(t *test, h *history) {
 	if err := t.restartDB(); err != nil {
 		h.Recordf("%s // %v", o, err)
-		h.err.Store(errors.Wrap(err, "dbRestartOp"))
+		fmt.Fprintf(os.Stderr, "terminating since dbRestartOp returned err %s\n", err)
+		h.failed = true
 	} else {
 		h.Recordf("%s", o)
 	}
diff --git a/internal/record/record.go b/internal/record/record.go
index e223c34e..026285a4 100644
--- a/internal/record/record.go
+++ b/internal/record/record.go
@@ -149,13 +149,6 @@ var (
 	ErrInvalidChunk = errors.New("pebble/record: invalid chunk")
 )
 
-// IsInvalidRecord returns true if the error matches one of the error types
-// returned for invalid records. These are treated in a way similar to io.EOF
-// in recovery code.
-func IsInvalidRecord(err error) bool {
-	return err == ErrZeroedChunk || err == ErrInvalidChunk || err == io.ErrUnexpectedEOF
-}
-
 // Reader reads records from an underlying io.Reader.
 type Reader struct {
 	// r is the underlying reader.
diff --git a/level_iter.go b/level_iter.go
index cb835860..513218d3 100644
--- a/level_iter.go
+++ b/level_iter.go
@@ -335,10 +335,10 @@ func (l *levelIter) verify(key *InternalKey, val []byte) (*InternalKey, []byte)
 		// bounds as such keys are always range tombstones which will be skipped by
 		// the Iterator.
 		if l.lower != nil && key != l.smallestBoundary && l.cmp(key.UserKey, l.lower) < 0 {
-			l.logger.Fatalf("levelIter %s: lower bound violation: %s < %s\n%s", l.level, key, l.lower, debug.Stack())
+			l.logger.Fatalf("levelIter: lower bound violation: %s < %s\n%s", key, l.lower, debug.Stack())
 		}
 		if l.upper != nil && key != l.largestBoundary && l.cmp(key.UserKey, l.upper) > 0 {
-			l.logger.Fatalf("levelIter %s: upper bound violation: %s > %s\n%s", l.level, key, l.upper, debug.Stack())
+			l.logger.Fatalf("levelIter: upper bound violation: %s > %s\n%s", key, l.upper, debug.Stack())
 		}
 	}
 	return key, val
diff --git a/merging_iter.go b/merging_iter.go
index 8f7d3e19..3ff76f7a 100644
--- a/merging_iter.go
+++ b/merging_iter.go
@@ -366,7 +366,7 @@ func (m *mergingIter) switchToMinHeap() {
 		if l == cur {
 			continue
 		}
-		if l.iterKey == nil || l.iterKey.Kind() == base.InternalKeyKindRangeDelete {
+		if l.iterKey == nil {
 			if m.lower != nil {
 				l.iterKey, l.iterValue = l.iter.SeekGE(m.lower)
 			} else {
@@ -415,7 +415,7 @@ func (m *mergingIter) switchToMaxHeap() {
 		if l == cur {
 			continue
 		}
-		if l.iterKey == nil || l.iterKey.Kind() == base.InternalKeyKindRangeDelete {
+		if l.iterKey == nil {
 			if m.upper != nil {
 				l.iterKey, l.iterValue = l.iter.SeekLT(m.upper)
 			} else {
diff --git a/open.go b/open.go
index 7b125550..6f66e0a8 100644
--- a/open.go
+++ b/open.go
@@ -484,7 +484,7 @@ func (d *DB) replayWAL(
 			// preallocation and WAL recycling. We need to distinguish these errors
 			// from EOF in order to recognize that the record was truncated, but want
 			// to otherwise treat them like EOF.
-			if err == io.EOF || record.IsInvalidRecord(err) {
+			if err == io.EOF || err == record.ErrZeroedChunk || err == record.ErrInvalidChunk {
 				break
 			}
 			return 0, errors.Wrap(err, "pebble: error when replaying WAL")
diff --git a/version_set.go b/version_set.go
index 63f6d4be..14364596 100644
--- a/version_set.go
+++ b/version_set.go
@@ -196,7 +196,7 @@ func (vs *versionSet) load(dirname string, opts *Options, mu *sync.Mutex) error
 	rr := record.NewReader(manifest, 0 /* logNum */)
 	for {
 		r, err := rr.Next()
-		if err == io.EOF || record.IsInvalidRecord(err) {
+		if err == io.EOF {
 			break
 		}
 		if err != nil {
@@ -206,11 +206,6 @@ func (vs *versionSet) load(dirname string, opts *Options, mu *sync.Mutex) error
 		var ve versionEdit
 		err = ve.Decode(r)
 		if err != nil {
-			// Break instead of returning an error if the record is corrupted
-			// or invalid.
-			if err == io.EOF || record.IsInvalidRecord(err) {
-				break
-			}
 			return err
 		}
 		if ve.ComparerName != "" {


Test patch:
diff --git a/checkpoint_test.go b/checkpoint_test.go
index e0458cbb..cc51dde4 100644
--- a/checkpoint_test.go
+++ b/checkpoint_test.go
@@ -5,14 +5,11 @@
 package pebble
 
 import (
-	"context"
 	"fmt"
 	"sort"
 	"strings"
-	"sync"
 	"testing"
 
-	"github.com/cockroachdb/pebble/internal/base"
 	"github.com/cockroachdb/pebble/internal/datadriven"
 	"github.com/cockroachdb/pebble/vfs"
 	"github.com/stretchr/testify/require"
@@ -137,81 +134,3 @@ func TestCheckpoint(t *testing.T) {
 		}
 	})
 }
-
-func TestCheckpointCompaction(t *testing.T) {
-	fs := vfs.NewMem()
-	d, err := Open("", &Options{FS: fs})
-	require.NoError(t, err)
-
-	ctx, cancel := context.WithCancel(context.Background())
-
-	var wg sync.WaitGroup
-	wg.Add(4)
-	go func() {
-		defer cancel()
-		defer wg.Done()
-		for i := 0; ctx.Err() == nil; i++ {
-			if err := d.Set([]byte(fmt.Sprintf("key%06d", i)), nil, nil); err != nil {
-				t.Error(err)
-				return
-			}
-		}
-	}()
-	go func() {
-		defer cancel()
-		defer wg.Done()
-		for ctx.Err() == nil {
-			if err := d.Compact([]byte("key"), []byte("key999999")); err != nil {
-				t.Error(err)
-				return
-			}
-		}
-	}()
-	check := make(chan string, 100)
-	go func() {
-		defer cancel()
-		defer close(check)
-		defer wg.Done()
-		for i := 0; ctx.Err() == nil && i < 200; i++ {
-			dir := fmt.Sprintf("checkpoint%6d", i)
-			if err := d.Checkpoint(dir); err != nil {
-				t.Error(err)
-				return
-			}
-			select {
-			case <-ctx.Done():
-				return
-			case check <- dir:
-			}
-		}
-	}()
-	go func() {
-		opts := &Options{FS: fs}
-		defer cancel()
-		defer wg.Done()
-		for dir := range check {
-			d2, err := Open(dir, opts)
-			if err != nil {
-				t.Error(err)
-				return
-			}
-			// Check the checkpoint has all the sstables that the manifest
-			// claims it has.
-			for _, tables := range d2.SSTables() {
-				for _, tbl := range tables {
-					if _, err := fs.Stat(base.MakeFilename(fs, dir, base.FileTypeTable, tbl.FileNum)); err != nil {
-						t.Error(err)
-						return
-					}
-				}
-			}
-			if err := d2.Close(); err != nil {
-				t.Error(err)
-				return
-			}
-		}
-	}()
-	<-ctx.Done()
-	wg.Wait()
-	require.NoError(t, d.Close())
-}
diff --git a/compaction_test.go b/compaction_test.go
index 8ea57dff..815d683c 100644
--- a/compaction_test.go
+++ b/compaction_test.go
@@ -9,11 +9,9 @@ import (
 	"fmt"
 	"math"
 	"regexp"
-	"runtime"
 	"sort"
 	"strconv"
 	"strings"
-	"sync"
 	"testing"
 	"time"
 
@@ -1250,7 +1248,7 @@ func TestCompactionFindL0Limit(t *testing.T) {
 				}
 
 				vers = &version{
-					Files: fileMetas,
+					Files:       fileMetas,
 				}
 				if err := vers.InitL0Sublevels(DefaultComparer.Compare, base.DefaultFormatter, flushSplitBytes); err != nil {
 					t.Fatal(err)
@@ -1268,11 +1266,11 @@ func TestCompactionFindL0Limit(t *testing.T) {
 
 			case "flush":
 				c := &compaction{
-					cmp:         cmp,
-					version:     vers,
-					l0Limits:    vers.L0Sublevels.FlushSplitKeys(),
-					startLevel:  -1,
-					outputLevel: 0,
+					cmp:          cmp,
+					version:      vers,
+					l0Limits:     vers.L0Sublevels.FlushSplitKeys(),
+					startLevel:   -1,
+					outputLevel:  0,
 				}
 
 				var buf bytes.Buffer
@@ -1928,51 +1926,3 @@ func TestCompactFlushQueuedLargeBatch(t *testing.T) {
 	require.NoError(t, d.Compact([]byte("a"), []byte("a")))
 	require.NoError(t, d.Close())
 }
-
-// Regression test for #747. Test a problematic series of "cleaner" operations
-// that could previously lead to DB.disableFileDeletions blocking forever even
-// though no cleaning was in progress.
-func TestCleanerCond(t *testing.T) {
-	d, err := Open("", &Options{
-		FS: vfs.NewMem(),
-	})
-	require.NoError(t, err)
-
-	for i := 0; i < 10; i++ {
-		d.mu.Lock()
-		require.True(t, d.acquireCleaningTurn(true))
-		d.mu.Unlock()
-
-		var wg sync.WaitGroup
-		wg.Add(2)
-
-		go func() {
-			defer wg.Done()
-			d.mu.Lock()
-			if d.acquireCleaningTurn(true) {
-				d.releaseCleaningTurn()
-			}
-			d.mu.Unlock()
-		}()
-
-		runtime.Gosched()
-
-		go func() {
-			defer wg.Done()
-			d.mu.Lock()
-			d.disableFileDeletions()
-			d.enableFileDeletions()
-			d.mu.Unlock()
-		}()
-
-		runtime.Gosched()
-
-		d.mu.Lock()
-		d.releaseCleaningTurn()
-		d.mu.Unlock()
-
-		wg.Wait()
-	}
-
-	require.NoError(t, d.Close())
-}
diff --git a/internal/fastrand/fastrand_test.go b/internal/fastrand/fastrand_test.go
new file mode 100644
index 00000000..16c10514
--- /dev/null
+++ b/internal/fastrand/fastrand_test.go
@@ -0,0 +1,47 @@
+// Copyright 2020 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 fastrand
+
+import (
+	"golang.org/x/exp/rand"
+	"sync"
+	"testing"
+	"time"
+)
+
+type defaultRand struct {
+	mu sync.Mutex
+	src rand.PCGSource
+}
+
+func newDefaultRand() *defaultRand {
+	r := &defaultRand{}
+	r.src.Seed(uint64(time.Now().UnixNano()))
+	return r
+}
+
+func (r *defaultRand) Uint32() uint32 {
+	r.mu.Lock()
+	i := uint32(r.src.Uint64())
+	r.mu.Unlock()
+	return i
+}
+
+func BenchmarkFastRand(b *testing.B) {
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			Uint32()
+		}
+	})
+}
+
+func BenchmarkDefaultRand(b *testing.B) {
+	r := newDefaultRand()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			r.Uint32()
+		}
+	})
+}
diff --git a/internal/manifest/testdata/l0_sublevels b/internal/manifest/testdata/l0_sublevels
index a2d3f8ae..4cd14542 100644
--- a/internal/manifest/testdata/l0_sublevels
+++ b/internal/manifest/testdata/l0_sublevels
@@ -1,4 +1,3 @@
-
 define
 L0
   000009:a.SET.10-b.SET.10
@@ -888,48 +887,3 @@ flush user split keys: c, e
 max-depth-after-ongoing-compactions
 ----
 2
-
-# Ensure that the compaction picker doesn't error out when all seed files are
-# compacting.
-
-define
-L0
-  000004:h.SET.2-j.SET.4    base_compacting
-  000005:f.SET.6-h.SET.9
-  000006:f.SET.4-g.SET.5    base_compacting
-  000007:k.SET.2-l.SET.4    base_compacting
-  000009:f.SET.12-p.SET.12  intra_l0_compacting
-  000010:f.SET.11-g.SET.11
-  000011:n.SET.8-p.SET.10   base_compacting
-L6
-  000012:a.SET.0-f.SET.0
-  000008:g.SET.0-s.SET.0
-----
-file count: 7, sublevels: 4, intervals: 9
-flush split keys(5): [g, h, j, l, p]
-0.3: file count: 1, bytes: 256, width (mean, max): 8.0, 8, interval range: [0, 7]
-	000009:f#12,1-p#12,1
-0.2: file count: 1, bytes: 256, width (mean, max): 1.0, 1, interval range: [0, 0]
-	000010:f#11,1-g#11,1
-0.1: file count: 1, bytes: 256, width (mean, max): 3.0, 3, interval range: [0, 2]
-	000005:f#6,1-h#9,1
-0.0: file count: 4, bytes: 1024, width (mean, max): 1.2, 2, interval range: [0, 7]
-	000006:f#4,1-g#5,1
-	000004:h#2,1-j#4,1
-	000007:k#2,1-l#4,1
-	000011:n#8,1-p#10,1
-compacting file count: 5, base compacting intervals: [0, 0], [2, 3], [5, 5], [7, 8]
-L0.3:                 f^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^p
-L0.2:                 f---g
-L0.1:                 f------h
-L0.0:                 fvvvg hvvvvvvj kvvvl    nvvvvvvp
-L6:    a---------------f g------------------------------------s
-       aa bb cc dd ee ff gg hh ii jj kk ll mm nn oo pp qq rr ss
-
-pick-base-compaction min_depth=2
-----
-no compaction picked
-
-pick-intra-l0-compaction min_depth=2
-----
-no compaction picked
diff --git a/internal/metamorphic/history_test.go b/internal/metamorphic/history_test.go
index b7f34ae7..46771fd9 100644
--- a/internal/metamorphic/history_test.go
+++ b/internal/metamorphic/history_test.go
@@ -14,8 +14,9 @@ import (
 func TestHistoryLogger(t *testing.T) {
 	var buf bytes.Buffer
 	h := newHistory("", &buf)
-	h.Infof("hello\nworld\n")
-	h.Fatalf("hello\n\nworld")
+	l := h.Logger()
+	l.Infof("hello\nworld\n")
+	l.Fatalf("hello\n\nworld")
 
 	expected := `// INFO: hello
 // INFO: world
@@ -32,7 +33,7 @@ func TestHistoryFail(t *testing.T) {
 	var buf bytes.Buffer
 	h := newHistory("foo", &buf)
 	h.Recordf("bar")
-	require.NoError(t, h.Error())
+	require.False(t, h.Failed())
 	h.Recordf("foo bar")
-	require.EqualError(t, h.Error(), `failure regexp "foo" matched output: foo bar #2`)
+	require.True(t, h.Failed())
 }
diff --git a/internal/metamorphic/meta_test.go b/internal/metamorphic/meta_test.go
index a6153798..94ded260 100644
--- a/internal/metamorphic/meta_test.go
+++ b/internal/metamorphic/meta_test.go
@@ -117,8 +117,10 @@ func testMetaRun(t *testing.T, runDir string) {
 	m := newTest(ops)
 	require.NoError(t, m.init(h, opts.FS.PathJoin(runDir, "data"), testOpts))
 	for m.step(h) {
-		if err := h.Error(); err != nil {
-			fmt.Fprintln(os.Stderr, err)
+		if h.Failed() {
+			if len(*failRE) > 0 {
+				fmt.Fprintf(os.Stderr, "failure regex %q matched\n", *failRE)
+			}
 			m.maybeSaveData()
 			os.Exit(1)
 		}
diff --git a/internal/metamorphic/test.go b/internal/metamorphic/test.go
index 8dc17b5a..26d2769b 100644
--- a/internal/metamorphic/test.go
+++ b/internal/metamorphic/test.go
@@ -49,7 +49,7 @@ func (t *test) init(h *history, dir string, testOpts *testOptions) error {
 		t.writeOpts = pebble.Sync
 	}
 	t.opts = testOpts.opts.EnsureDefaults()
-	t.opts.Logger = h
+	t.opts.Logger = h.Logger()
 	t.opts.EventListener = pebble.MakeLoggingEventListener(t.opts.Logger)
 	t.opts.DebugCheck = func(db *pebble.DB) error {
 		// Wrap the ordinary DebugCheckLevels with retrying
@@ -71,7 +71,6 @@ func (t *test) init(h *history, dir string, testOpts *testOptions) error {
 			return
 		}
 		t.maybeSaveData()
-		fmt.Fprintln(os.Stderr, err)
 		os.Exit(1)
 	}
 
diff --git a/snapshot_test.go b/snapshot_test.go
index e0ef78d4..75f60a44 100644
--- a/snapshot_test.go
+++ b/snapshot_test.go
@@ -12,7 +12,6 @@ import (
 	"strings"
 	"sync"
 	"testing"
-	"time"
 
 	"github.com/cockroachdb/pebble/internal/datadriven"
 	"github.com/cockroachdb/pebble/vfs"
@@ -283,67 +282,3 @@ func TestSnapshotRangeDeletionStress(t *testing.T) {
 	wg.Wait()
 	require.NoError(t, d.Close())
 }
-
-// TestNewSnapshotRace tests atomicity of NewSnapshot.
-//
-// It tests for a regression of a previous race condition in which NewSnapshot
-// would retrieve the visible sequence number for a new snapshot before
-// locking the database mutex to add the snapshot. A write and flush that
-// that occurred between the reading of the sequence number and appending the
-// snapshot could drop keys required by the snapshot.
-func TestNewSnapshotRace(t *testing.T) {
-	const runs = 10
-	d, err := Open("", &Options{FS: vfs.NewMem()})
-	require.NoError(t, err)
-
-	v := []byte(`foo`)
-	ch := make(chan string)
-	var wg sync.WaitGroup
-	wg.Add(1)
-
-	go func() {
-		defer wg.Done()
-		for k := range ch {
-			if err := d.Set([]byte(k), v, nil); err != nil {
-				t.Error(err)
-				return
-			}
-			if err := d.Flush(); err != nil {
-				t.Error(err)
-				return
-			}
-		}
-	}()
-	for i := 0; i < runs; i++ {
-		// This main test goroutine sets `k` before creating a new snapshot.
-		// The key `k` should always be present within the snapshot.
-		k := fmt.Sprintf("key%06d", i)
-		require.NoError(t, d.Set([]byte(k), v, nil))
-
-		// Lock d.mu in another goroutine so that our call to NewSnapshot
-		// will need to contend for d.mu.
-		wg.Add(1)
-		locked := make(chan struct{})
-		go func() {
-			defer wg.Done()
-			d.mu.Lock()
-			close(locked)
-			time.Sleep(20 * time.Millisecond)
-			d.mu.Unlock()
-		}()
-		<-locked
-
-		// Tell the other goroutine to overwrite `k` with a later sequence
-		// number. It's indeterminate which key we'll read, but we should
-		// always read one of them.
-		ch <- k
-		s := d.NewSnapshot()
-		_, c, err := s.Get([]byte(k))
-		require.NoError(t, err)
-		require.NoError(t, c.Close())
-		require.NoError(t, s.Close())
-	}
-	close(ch)
-	wg.Wait()
-	require.NoError(t, d.Close())
-}
diff --git a/testdata/compaction_picker_target_level b/testdata/compaction_picker_target_level
index 16276901..7fe4b7aa 100644
--- a/testdata/compaction_picker_target_level
+++ b/testdata/compaction_picker_target_level
@@ -193,6 +193,12 @@ queue
 L4->L5: 10.0
 L4->L5: 9.0
 L4->L5: 8.0
+L4->L5: 7.0
+L4->L5: 6.0
+L4->L5: 5.0
+L4->L5: 4.0
+L4->L5: 3.0
+L4->L5: 2.0
 
 pick ongoing=(5,6)
 ----
@@ -204,7 +210,7 @@ L0->L0: 2.2
 
 pick ongoing=(0,0,0,4)
 ----
-no compaction
+L0->L0: 2.0
 
 init_cp
 ----
@@ -215,7 +221,7 @@ pick ongoing=(0,5)
 L0->L0: 2.2
 
 init 1
-0: 20
+0: 10
 6: 10
 ----
 
@@ -225,36 +231,36 @@ base: 5
 
 queue
 ----
-L0->L5: 5.0
-L0->L0: 4.8
+L0->L5: 2.5
+L0->L0: 2.2
 
 pick
 ----
-L0->L5: 5.0
+L0->L5: 2.5
 
 pick ongoing=(0,5)
 ----
-L0->L0: 4.8
+L0->L0: 2.2
 
 # An intra-L0 compaction is only queued if there is an in-progress
 # L0->Lbase compaction.
 
 pick ongoing=(0,0)
 ----
-L0->L5: 4.8
+L0->L5: 2.2
 
 # Pick another intra-L0 compaction even if there is one already in
 # progress.
 
 pick ongoing=(0,0,0,5)
 ----
-L0->L0: 4.5
+L0->L0: 2.0
 
 # We'll only pick a concurrent compaction if it is "high" priority
-# (i.e. has a score >= highPriorityThreshold).
+# (i.e. has a score >= 1.5).
 
 init 1
-0: 17
+0: 7
 5: 1
 6: 10
 ----
@@ -265,12 +271,12 @@ base: 5
 
 queue
 ----
-L0->L5: 4.2
-L0->L0: 4.0
+L0->L5: 1.8
+L0->L0: 1.5
 
 pick ongoing=(0,5,5,6)
 ----
-L0->L0: 4.0
+L0->L0: 1.5
 
 pick ongoing=(5,6)
 ----
@@ -292,6 +298,7 @@ queue
 ----
 L5->L6: 4.0
 L5->L6: 3.0
+L5->L6: 2.0
 
 pick
 ----
@@ -303,7 +310,7 @@ L5->L6: 3.0
 
 pick ongoing=(5,6,5,6)
 ----
-no compaction
+L5->L6: 2.0
 
 pick ongoing=(5,6,5,6,5,6)
 ----
@@ -325,6 +332,8 @@ base: 5
 queue
 ----
 L5->L6: 2.0
+L5->L6: 1.8
+L5->L6: 1.6
 
 pick_manual level=0 start=0 end=12
 ----
diff --git a/testdata/merging_iter b/testdata/merging_iter
index 8f85bad6..c3576e87 100644
--- a/testdata/merging_iter
+++ b/testdata/merging_iter
@@ -444,61 +444,3 @@ b#0,1:1
 a#0,1:1
 a#2,1:2
 .
-
-# Verify the upper bound is respected when switching directions at a RANGEDEL
-# boundary.
-
-define
-L
-kq.RANGEDEL.100 p.RANGEDEL.72057594037927935
-kq.RANGEDEL.100:p
-L
-b.SET.90 o.SET.65
-b.SET.90:90 cat.SET.70:70 g.SET.80:80 o.SET.65:65
-L
-a.SET.41 z.RANGEDEL.72057594037927935
-a.SET.41:41 koujdlp.MERGE.37:37 ok.SET.46:46 v.SET.43:43 v.RANGEDEL.19:z
-----
-1:
-  000019:[kq#100,RANGEDEL-p#72057594037927935,RANGEDEL]
-2:
-  000020:[b#90,SET-o#65,SET]
-3:
-  000021:[a#41,SET-z#72057594037927935,RANGEDEL]
-
-iter
-set-bounds upper=n
-seek-ge krgywquurww
-prev
-----
-p#72057594037927935,15:
-kq#100,15:
-
-# Verify the lower bound is respected when switching directions at a RANGEDEL
-# boundary.
-
-define
-L
-a.SET.103 jyk.RANGEDEL.72057594037927935
-a.SET.103:103 imd.SET.793:793 iwoeionch.SET.792:792 c.RANGEDEL.101:jyk
-L
-b.SET.90 o.SET.65
-b.SET.90:90 cat.SET.70:70 g.SET.80:80 o.SET.65:65
-L
-all.SET.0 zk.SET.722
-all.SET.0:0 c.SET.0:0 zk.SET.722:722
-----
-1:
-  000022:[a#103,SET-jyk#72057594037927935,RANGEDEL]
-2:
-  000023:[b#90,SET-o#65,SET]
-3:
-  000024:[all#0,SET-zk#722,SET]
-
-iter
-set-bounds lower=cz upper=jd
-seek-lt jd
-next
-----
-iwoeionch#792,1:792
-jyk#72057594037927935,15: