Repository: cockroachdb/pebble

Issue:
compact: reduce allocations for lone MERGE keys
Currently both iterators and compactions unconditionally send `MERGE` keys' values through a roundtrip of the user-configured `ValueMerger`, even when there is a single `MERGE` key (so the value should be unchanged). This results in unnecessary allocations, especially in the context of CockroachDB and its allocation-heavy `ValueMerger` implementation.

There are two potential resolutions:
1. We could explicitly defer beginning the merging of values until we observe two internal keys with the same user key.
2. We could adapt the compaction iterator to transform `MERGE` keys into `SET`s if we know a key is the oldest key at that user key (i.e., `allowZeroSeqNum=true` and the key is in the final snapshot stripe).

The code changes for approach (2) are a lot simpler, and changing the key to a SET has other advantages (eg, iteration can stop as soon as it hits the SET, avoiding an additional Next of the internal iterator).

Jira issue: PEBBLE-1139

Discussion:

Solution patch:
diff --git a/compaction.go b/compaction.go
index b607e1d5..7aa42cf3 100644
--- a/compaction.go
+++ b/compaction.go
@@ -964,11 +964,16 @@ func (c *tableCompaction) errorOnUserKeyOverlap(ve *manifest.VersionEdit) error
 	return nil
 }
 
-// allowZeroSeqNum returns true if seqnum's can be zeroed if there are no
-// snapshots requiring them to be kept. It performs this determination by
-// looking at the TombstoneElision values which are set up based on sstables
-// which overlap the bounds of the compaction at a lower level in the LSM.
-func (c *tableCompaction) allowZeroSeqNum() bool {
+// isBottommostDataLayer returns true if the compaction's inputs are known to be
+// the bottommost layer of data for the compaction's key range. If true, this
+// allows the compaction iterator to perform transformations to keys such as
+// setting a key's sequence number to zero.
+//
+// This function performs this determination by looking at the TombstoneElision
+// values which are set up based on sstables which overlap the bounds of the
+// compaction at a lower level in the LSM. This function always returns false
+// for flushes.
+func (c *tableCompaction) isBottommostDataLayer() bool {
 	// TODO(peter): we disable zeroing of seqnums during flushing to match
 	// RocksDB behavior and to avoid generating overlapping sstables during
 	// DB.replayWAL. When replaying WAL files at startup, we flush after each
@@ -3335,12 +3340,12 @@ func (d *DB) compactAndWrite(
 		return compact.Result{Err: err}
 	}
 	cfg := compact.IterConfig{
-		Comparer:         c.comparer,
-		Merge:            d.merge,
-		TombstoneElision: c.delElision,
-		RangeKeyElision:  c.rangeKeyElision,
-		Snapshots:        snapshots,
-		AllowZeroSeqNum:  c.allowZeroSeqNum(),
+		Comparer:              c.comparer,
+		Merge:                 d.merge,
+		TombstoneElision:      c.delElision,
+		RangeKeyElision:       c.rangeKeyElision,
+		Snapshots:             snapshots,
+		IsBottommostDataLayer: c.isBottommostDataLayer(),
 		IneffectualSingleDeleteCallback: func(userKey []byte) {
 			d.opts.EventListener.PossibleAPIMisuse(PossibleAPIMisuseInfo{
 				Kind:    IneffectualSingleDelete,
diff --git a/internal/compact/iterator.go b/internal/compact/iterator.go
index 6efb9ecd..236f604f 100644
--- a/internal/compact/iterator.go
+++ b/internal/compact/iterator.go
@@ -269,11 +269,17 @@ type IterConfig struct {
 	TombstoneElision TombstoneElision
 	RangeKeyElision  TombstoneElision
 
-	// AllowZeroSeqNum allows the sequence number of KVs in the bottom snapshot
-	// stripe to be simplified to 0 (which improves compression and enables an
-	// optimization during forward iteration). This can be enabled if there are no
-	// tables overlapping the output at lower levels (than the output) in the LSM.
-	AllowZeroSeqNum bool
+	// IsBottommostDataLayer indicates that the compaction inputs form the
+	// bottommost layer of data for the compaction's key range. This allows the
+	// sequence number of KVs in the bottom snapshot stripe to be simplified to
+	// 0 (which improves compression and enables an optimization during forward
+	// iteration). This can be enabled if there are no tables overlapping the
+	// output at lower levels (than the output) in the LSM.
+	//
+	// This field may be false even when nothing is overlapping in lower levels.
+	// At the time of writing, flushes always set this to false (because flushes
+	// almost never form the bottommost layer of data).
+	IsBottommostDataLayer bool
 
 	// IneffectualPointDeleteCallback is called if a SINGLEDEL is being elided
 	// without deleting a point set/merge. False positives are rare but possible
@@ -613,8 +619,24 @@ func (i *Iter) Next() *base.InternalKV {
 			}
 			var needDelete bool
 			if i.err == nil {
-				// includesBase is true whenever we've transformed the MERGE record
-				// into a SET.
+				// If this is the oldest version of this key (the bottommost
+				// snapshot stripe), we can transform the sequence number to
+				// zero. This can improve compression and enables an
+				// optimization during forward iteration to skip some key
+				// comparisons. Additionally, we can transform the key kind to
+				// SET so that iteration and future compactions do not need to
+				// invoke the user's Merge operator.
+				if i.isBottommostSnapshotStripe(origSnapshotIdx) {
+					i.kv.K.SetSeqNum(base.SeqNumZero)
+					// During the merge (see mergeNext), we may have already
+					// transformed the key kind to SET or SETWITHDEL, in which case we want to preserve the existing key kind.
+					if i.kv.K.Kind() == base.InternalKeyKindMerge {
+						i.kv.K.SetKind(base.InternalKeyKindSet)
+					}
+				}
+
+				// includesBase is true when we've merged the oldest operand in
+				// the LSM.
 				var includesBase bool
 				switch i.kv.K.Kind() {
 				case base.InternalKeyKindSet, base.InternalKeyKindSetWithDelete:
@@ -633,8 +655,6 @@ func (i *Iter) Next() *base.InternalKV {
 					}
 					continue
 				}
-
-				i.maybeZeroSeqnum(origSnapshotIdx)
 				return &i.kv
 			}
 			if i.err != nil {
@@ -799,7 +819,14 @@ func (i *Iter) setNext() {
 	// Save the current key.
 	i.saveKey()
 	i.kv.V = i.iterKV.V
-	i.maybeZeroSeqnum(i.curSnapshotIdx)
+
+	// If this is the oldest version of this key (the bottommost snapshot
+	// stripe), we can transform the sequence number to zero. This can improve
+	// compression and enables an optimization during forward iteration to skip
+	// some key comparisons.
+	if i.isBottommostSnapshotStripe(i.curSnapshotIdx) {
+		i.kv.K.SetSeqNum(base.SeqNumZero)
+	}
 
 	// If this key is already a SETWITHDEL we can early return and skip the remaining
 	// records in the stripe:
@@ -1415,23 +1442,21 @@ func (i *Iter) lastRangeDelSpanFrontierReached(key []byte) []byte {
 	return nil
 }
 
-// maybeZeroSeqnum attempts to set the seqnum for the current key to 0. Doing
-// so improves compression and enables an optimization during forward iteration
-// to skip some key comparisons. The seqnum for an entry can be zeroed if the
-// entry is on the bottom snapshot stripe and on the bottom level of the LSM.
-func (i *Iter) maybeZeroSeqnum(snapshotIdx int) {
-	if !i.cfg.AllowZeroSeqNum {
-		// TODO(peter): allowZeroSeqNum applies to the entire compaction. We could
-		// make the determination on a key by key basis, similar to what is done
-		// for elideTombstone. Need to add a benchmark for Iter to verify
-		// that isn't too expensive.
-		return
-	}
-	if snapshotIdx > 0 {
-		// This is not the last snapshot
-		return
-	}
-	i.kv.K.SetSeqNum(base.SeqNumZero)
+// isBottommostSnapshotStripe returns true if the compaction's inputs form the
+// bottommost layer of the LSM for the compaction's key range and the provided
+// snapshot stripe is the last stripe.
+//
+// When isBottommostSnapshotStripe returns true, it is guaranteed there does not
+// exist any overlapping keys with lower sequence numbers than the keys in the
+// provided snapshot stripe. However isBottommostSnapshotStripe is permitted to
+// return false even when there is no overlapping data in lower levels (eg,
+// flushes).
+func (i *Iter) isBottommostSnapshotStripe(snapshotIdx int) bool {
+	// TODO(peter): This determination applies to the entire compaction. We
+	// could make the determination on a key by key basis, similar to what is
+	// done for elideTombstone. Need to add a benchmark for Iter to verify that
+	// isn't too expensive.
+	return i.cfg.IsBottommostDataLayer && snapshotIdx == 0
 }
 
 func finishValueMerger(



Test patch:
diff --git a/compaction_test.go b/compaction_test.go
index 9c6ddd6e..62161c93 100644
--- a/compaction_test.go
+++ b/compaction_test.go
@@ -2283,7 +2283,7 @@ func TestCompactionAllowZeroSeqNum(t *testing.T) {
 					c.delElision, c.rangeKeyElision = compact.SetupTombstoneElision(
 						c.comparer.Compare, c.version, d.mu.versions.latest.l0Organizer,
 						c.outputLevel.level, c.bounds)
-					fmt.Fprintf(&buf, "%t\n", c.allowZeroSeqNum())
+					fmt.Fprintf(&buf, "%t\n", c.isBottommostDataLayer())
 				}
 				return buf.String()
 
diff --git a/internal/compact/iterator_test.go b/internal/compact/iterator_test.go
index b0586a1c..1e7e5a9d 100644
--- a/internal/compact/iterator_test.go
+++ b/internal/compact/iterator_test.go
@@ -55,7 +55,7 @@ func TestCompactionIter(t *testing.T) {
 	var rangeDels []keyspan.Span
 	var snapshots Snapshots
 	var elideTombstones bool
-	var allowZeroSeqnum bool
+	var isBottommostDataLayer bool
 	var ineffectualSingleDeleteKeys []string
 	var invariantViolationSingleDeleteKeys []string
 	var missizedDeleteInfo []string
@@ -79,12 +79,12 @@ func TestCompactionIter(t *testing.T) {
 			elision = ElideTombstonesOutsideOf(nil)
 		}
 		cfg := IterConfig{
-			Comparer:         base.DefaultComparer,
-			Merge:            merge,
-			Snapshots:        snapshots,
-			TombstoneElision: elision,
-			RangeKeyElision:  elision,
-			AllowZeroSeqNum:  allowZeroSeqnum,
+			Comparer:              base.DefaultComparer,
+			Merge:                 merge,
+			Snapshots:             snapshots,
+			TombstoneElision:      elision,
+			RangeKeyElision:       elision,
+			IsBottommostDataLayer: isBottommostDataLayer,
 			IneffectualSingleDeleteCallback: func(userKey []byte) {
 				ineffectualSingleDeleteKeys = append(ineffectualSingleDeleteKeys, string(userKey))
 			},
@@ -160,7 +160,7 @@ func TestCompactionIter(t *testing.T) {
 			case "iter":
 				snapshots = snapshots[:0]
 				elideTombstones = false
-				allowZeroSeqnum = false
+				isBottommostDataLayer = false
 				printSnapshotPinned := false
 				printMissizedDels := false
 				printForceObsolete := false
@@ -177,9 +177,9 @@ func TestCompactionIter(t *testing.T) {
 						if err != nil {
 							return err.Error()
 						}
-					case "allow-zero-seqnum":
+					case "is-bottommost-layer":
 						var err error
-						allowZeroSeqnum, err = strconv.ParseBool(arg.Vals[0])
+						isBottommostDataLayer, err = strconv.ParseBool(arg.Vals[0])
 						if err != nil {
 							return err.Error()
 						}
diff --git a/internal/compact/testdata/iter b/internal/compact/testdata/iter
index ca25379d..1d915dc4 100644
--- a/internal/compact/testdata/iter
+++ b/internal/compact/testdata/iter
@@ -947,14 +947,14 @@ a.RANGEDEL.1:b
 a.MERGE.1:v1
 ----
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 next
 next
 ----
 a#inf,RANGEDEL:; Span() = a-b:{(#1,RANGEDEL)}
-a#0,MERGE:v1v2
+a#0,SET:v1v2[base]
 .
 .
 
@@ -973,7 +973,7 @@ next
 a#5,SETWITHDEL:5[base]
 .
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 ----
@@ -1023,13 +1023,13 @@ a#inf,RANGEDEL:; Span() = a-c:{(#3,RANGEDEL)}
 b#5,MERGE:5
 .
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 next
 ----
 a#inf,RANGEDEL:; Span() = a-c:{(#3,RANGEDEL)}
-b#0,MERGE:5
+b#0,SET:5[base]
 .
 
 iter snapshots=2
diff --git a/internal/compact/testdata/iter_delete_sized b/internal/compact/testdata/iter_delete_sized
index 408f2973..6b42bbff 100644
--- a/internal/compact/testdata/iter_delete_sized
+++ b/internal/compact/testdata/iter_delete_sized
@@ -974,13 +974,13 @@ a.RANGEDEL.1:b
 a.MERGE.1:v1
 ----
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 next
 ----
 a#inf,RANGEDEL:; Span() = a-b:{(#1,RANGEDEL)}
-a#0,MERGE:v1v2
+a#0,SET:v1v2[base]
 .
 
 # Verify that we transform merge+del -> set.
@@ -998,7 +998,7 @@ next
 a#5,SETWITHDEL:5[base]
 .
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 ----
@@ -1048,13 +1048,13 @@ a#inf,RANGEDEL:; Span() = a-c:{(#3,RANGEDEL)}
 b#5,MERGE:5
 .
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 next
 ----
 a#inf,RANGEDEL:; Span() = a-c:{(#3,RANGEDEL)}
-b#0,MERGE:5
+b#0,SET:5[base]
 .
 
 iter snapshots=2
@@ -1211,7 +1211,7 @@ a.SET.2:b
 a.DEL.1:
 ----
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 next
@@ -1220,7 +1220,7 @@ a#inf,RANGEDEL:; Span() = a-z:{(#2,RANGEDEL)}
 a#0,SET:c
 .
 
-iter allow-zero-seqnum=true snapshots=3
+iter is-bottommost-layer=true snapshots=3
 first
 next
 next
@@ -1231,7 +1231,7 @@ a#3,SET:c
 a#0,SET:b
 .
 
-iter allow-zero-seqnum=true snapshots=2
+iter is-bottommost-layer=true snapshots=2
 first
 next
 next
@@ -1573,7 +1573,7 @@ next
 
 # Try the same test as above, but with allowing sequence number zeroing as well.
 
-iter elide-tombstones=t allow-zero-seqnum=t
+iter elide-tombstones=t is-bottommost-layer=t
 first
 next
 ----
@@ -1670,7 +1670,7 @@ next
 a#inf,RANGEDEL:; Span() = a-d:{(#5,RANGEDEL)}
 .
 
-iter elide-tombstones=t allow-zero-seqnum=t
+iter elide-tombstones=t is-bottommost-layer=t
 first
 next
 ----
diff --git a/internal/compact/testdata/iter_set_with_del b/internal/compact/testdata/iter_set_with_del
index d0eefbb6..4b2cc662 100644
--- a/internal/compact/testdata/iter_set_with_del
+++ b/internal/compact/testdata/iter_set_with_del
@@ -938,13 +938,13 @@ a.RANGEDEL.1:b
 a.MERGE.1:v1
 ----
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 next
 ----
 a#inf,RANGEDEL:; Span() = a-b:{(#1,RANGEDEL)}
-a#0,MERGE:v1v2
+a#0,SET:v1v2[base]
 .
 
 # Verify that we transform merge+del -> set.
@@ -962,7 +962,7 @@ next
 a#5,SETWITHDEL:5[base]
 .
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 ----
@@ -1012,13 +1012,13 @@ a#inf,RANGEDEL:; Span() = a-c:{(#3,RANGEDEL)}
 b#5,MERGE:5
 .
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 next
 ----
 a#inf,RANGEDEL:; Span() = a-c:{(#3,RANGEDEL)}
-b#0,MERGE:5
+b#0,SET:5[base]
 .
 
 iter snapshots=2
@@ -1172,7 +1172,7 @@ a.SET.2:b
 a.DEL.1:
 ----
 
-iter allow-zero-seqnum=true
+iter is-bottommost-layer=true
 first
 next
 next
@@ -1181,7 +1181,7 @@ a#inf,RANGEDEL:; Span() = a-z:{(#2,RANGEDEL)}
 a#0,SET:c
 .
 
-iter allow-zero-seqnum=true snapshots=3
+iter is-bottommost-layer=true snapshots=3
 first
 next
 next
@@ -1192,7 +1192,7 @@ a#3,SET:c
 a#0,SET:b
 .
 
-iter allow-zero-seqnum=true snapshots=2
+iter is-bottommost-layer=true snapshots=2
 first
 next
 next
diff --git a/testdata/excise b/testdata/excise
index 63200150..25605c81 100644
--- a/testdata/excise
+++ b/testdata/excise
@@ -402,7 +402,7 @@ lsm
 L0.0:
   000009:[bd#17,RANGEKEYSET-f#17,MERGE]
 L6:
-  000008:[a@3#0,SET-z#0,MERGE]
+  000008:[a@3#0,SET-z#0,SET]
 
 build ext3
 set z updated
@@ -417,8 +417,8 @@ L0.0:
   000011(000009):[cc#17,RANGEKEYSET-f#17,MERGE]
   000010:[z#19,SET-z#19,SET]
 L6:
-  000012(000008):[a@3#0,SET-bbsomethinglong@4#0,MERGE]
-  000013(000008):[d@6#0,MERGE-z#0,MERGE]
+  000012(000008):[a@3#0,SET-bbsomethinglong@4#0,SET]
+  000013(000008):[d@6#0,SET-z#0,SET]
 
 iter range-key-masking=@10
 first