Repository: cockroachdb/pebble

Issue:
virtual table property scaling causes compensated size underflow
We noticed some extremely large level scores in a production environment (v24.1). We eventually reproduced and root caused to the code below:

https://github.com/cockroachdb/pebble/blob/b6630de7f9339ab36cd05c8ff51363e33dd2bbb4/sstable/reader_virtual.go#L84

We are scaling the number of deletions, but the code that uses them assumes that they are still sane with respect to each other, in particular that NumDeletions >= NumRangeDeletions + NumSizedDeletions:

https://github.com/cockroachdb/pebble/blob/47c8e5262bb640d21fcadf09e65bcaa0d88d2bc0/table_stats.go#L773

This issue tracks fixing this and also adding some safeguards to these substractions.

Jira issue: PEBBLE-432

Discussion:

Solution patch:
diff --git a/internal/invariants/off.go b/internal/invariants/off.go
index 01513f27..41c93ad5 100644
--- a/internal/invariants/off.go
+++ b/internal/invariants/off.go
@@ -9,3 +9,17 @@ package invariants
 
 // Enabled is true if we were built with the "invariants" or "race" build tags.
 const Enabled = false
+
+// SafeSub returns a - b. If a < b, it panics in invariant builds and returns 0
+// in non-invariant builds.
+func SafeSub[T Integer](a, b T) T {
+	if a < b {
+		return 0
+	}
+	return a - b
+}
+
+// Integer is a constraint that permits any integer type.
+type Integer interface {
+	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
+}
diff --git a/internal/invariants/on.go b/internal/invariants/on.go
index b4186807..41ada9bc 100644
--- a/internal/invariants/on.go
+++ b/internal/invariants/on.go
@@ -7,5 +7,21 @@
 
 package invariants
 
+import "fmt"
+
 // Enabled is true if we were built with the "invariants" or "race" build tags.
 const Enabled = true
+
+// SafeSub returns a - b. If a < b, it panics in invariant builds and returns 0
+// in non-invariant builds.
+func SafeSub[T Integer](a, b T) T {
+	if a < b {
+		panic(fmt.Sprintf("underflow: %d - %d", a, b))
+	}
+	return a - b
+}
+
+// Integer is a constraint that permits any integer type.
+type Integer interface {
+	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
+}
diff --git a/sstable/properties.go b/sstable/properties.go
index 9e5cfa96..308cc4cd 100644
--- a/sstable/properties.go
+++ b/sstable/properties.go
@@ -14,6 +14,7 @@ import (
 	"unsafe"
 
 	"github.com/cockroachdb/pebble/internal/intern"
+	"github.com/cockroachdb/pebble/internal/invariants"
 )
 
 const propertiesBlockRestartInterval = math.MaxInt32
@@ -117,7 +118,7 @@ func (c *CommonProperties) String() string {
 // NumPointDeletions is the number of point deletions in the sstable. For virtual
 // sstables, this is an estimate.
 func (c *CommonProperties) NumPointDeletions() uint64 {
-	return c.NumDeletions - c.NumRangeDeletions
+	return invariants.SafeSub(c.NumDeletions, c.NumRangeDeletions)
 }
 
 // Properties holds the sstable property values. The properties are
diff --git a/sstable/reader_virtual.go b/sstable/reader_virtual.go
index 6f4e36d6..f3baece7 100644
--- a/sstable/reader_virtual.go
+++ b/sstable/reader_virtual.go
@@ -8,6 +8,7 @@ import (
 	"context"
 
 	"github.com/cockroachdb/pebble/internal/base"
+	"github.com/cockroachdb/pebble/internal/invariants"
 	"github.com/cockroachdb/pebble/internal/keyspan"
 	"github.com/cockroachdb/pebble/internal/rangekey"
 )
@@ -68,22 +69,33 @@ func MakeVirtualReader(reader *Reader, p VirtualReaderParams) VirtualReader {
 	scale := func(a uint64) uint64 {
 		return (a*p.Size + p.BackingSize - 1) / p.BackingSize
 	}
+	// It's important that no non-zero fields (like NumDeletions, NumRangeKeySets)
+	// become zero (or vice-versa).
+	if invariants.Enabled && (scale(1) != 1 || scale(0) != 0) {
+		panic("bad scale()")
+	}
+
+	physical := &reader.Properties
+	virtual := &v.Properties
+
+	virtual.RawKeySize = scale(physical.RawKeySize)
+	virtual.RawValueSize = scale(physical.RawValueSize)
+	virtual.NumEntries = scale(physical.NumEntries)
+
+	virtual.NumRangeDeletions = scale(physical.NumRangeDeletions)
+	virtual.NumSizedDeletions = scale(physical.NumSizedDeletions)
+	// We cannot directly scale NumDeletions, because it is supposed to be the sum
+	// of various types of deletions. See #4670.
+	numOtherDeletions := scale(invariants.SafeSub(physical.NumDeletions, physical.NumRangeDeletions) + physical.NumSizedDeletions)
+	virtual.NumDeletions = numOtherDeletions + virtual.NumRangeDeletions + virtual.NumSizedDeletions
+
+	virtual.NumRangeKeyDels = scale(physical.NumRangeKeyDels)
+	virtual.NumRangeKeySets = scale(physical.NumRangeKeySets)
+
+	virtual.ValueBlocksSize = scale(physical.ValueBlocksSize)
 
-	v.Properties.RawKeySize = scale(reader.Properties.RawKeySize)
-	v.Properties.RawValueSize = scale(reader.Properties.RawValueSize)
-	v.Properties.NumEntries = scale(reader.Properties.NumEntries)
-	v.Properties.NumDeletions = scale(reader.Properties.NumDeletions)
-	v.Properties.NumRangeDeletions = scale(reader.Properties.NumRangeDeletions)
-	v.Properties.NumRangeKeyDels = scale(reader.Properties.NumRangeKeyDels)
-
-	// Note that we rely on NumRangeKeySets for correctness. If the sstable may
-	// contain range keys, then NumRangeKeySets must be > 0. ceilDiv works because
-	// meta.Size will not be 0 for virtual sstables.
-	v.Properties.NumRangeKeySets = scale(reader.Properties.NumRangeKeySets)
-	v.Properties.ValueBlocksSize = scale(reader.Properties.ValueBlocksSize)
-	v.Properties.NumSizedDeletions = scale(reader.Properties.NumSizedDeletions)
-	v.Properties.RawPointTombstoneKeySize = scale(reader.Properties.RawPointTombstoneKeySize)
-	v.Properties.RawPointTombstoneValueSize = scale(reader.Properties.RawPointTombstoneValueSize)
+	virtual.RawPointTombstoneKeySize = scale(physical.RawPointTombstoneKeySize)
+	virtual.RawPointTombstoneValueSize = scale(physical.RawPointTombstoneValueSize)
 
 	return v
 }
diff --git a/table_stats.go b/table_stats.go
index 985ecaf9..276dea9f 100644
--- a/table_stats.go
+++ b/table_stats.go
@@ -649,6 +649,13 @@ func sanityCheckStats(meta *fileMetadata, logger Logger, info string) {
 
 	if meta.Stats.PointDeletionsBytesEstimate > maxDeletionBytesEstimate ||
 		meta.Stats.RangeDeletionsBytesEstimate > maxDeletionBytesEstimate {
+		if invariants.Enabled {
+			panic(fmt.Sprintf("%s: table %s has extreme deletion bytes estimates: point=%d range=%d",
+				info, meta.FileNum,
+				redact.Safe(meta.Stats.PointDeletionsBytesEstimate),
+				redact.Safe(meta.Stats.RangeDeletionsBytesEstimate),
+			))
+		}
 		if v := lastSanityCheckStatsLog.Load(); v == 0 || time.Since(processStartTime)-time.Duration(v) > 30*time.Second {
 			logger.Errorf("%s: table %s has extreme deletion bytes estimates: point=%d range=%d",
 				info, meta.FileNum,
@@ -770,7 +777,7 @@ func pointDeletionsBytesEstimate(
 
 	// 2b. Calculate the contribution of the KV entries shadowed by ordinary DEL
 	// keys.
-	numUnsizedDels := numPointDels - props.NumSizedDeletions
+	numUnsizedDels := invariants.SafeSub(numPointDels, props.NumSizedDeletions)
 	{
 		// The shadowed keys have the same exact user keys as the tombstones
 		// themselves, so we can use the `tombstonesLogicalSize` we computed



Test patch:
diff --git a/sstable/testdata/virtual_reader_props b/sstable/testdata/virtual_reader_props
index c9d76cde..c5647c74 100644
--- a/sstable/testdata/virtual_reader_props
+++ b/sstable/testdata/virtual_reader_props
@@ -143,3 +143,27 @@ props:
   rocksdb.num.entries: 1
   rocksdb.raw.key.size: 10
   rocksdb.raw.value.size: 2
+
+build
+a.DEL.1:
+b.DELSIZED.1:
+c.RANGEDEL.1:d
+----
+point:    [a#1,DEL-b#1,DELSIZED]
+rangedel: [c#1,RANGEDEL-d#72057594037927935,RANGEDEL]
+seqnums:  [1-1]
+
+# Verify that we get 3 deletions instead of 1 (because it has to be the sum of
+# its components).
+virtualize lower=a.DEL.1 upper=a0.SET.1 show-props
+----
+bounds:  [a#1,DEL-a0#1,SET]
+filenum: 000005
+props:
+  rocksdb.num.entries: 1
+  rocksdb.raw.key.size: 2
+  rocksdb.raw.value.size: 1
+  pebble.raw.point-tombstone.key.size: 1
+  pebble.num.deletions.sized: 1
+  rocksdb.deleted.keys: 3
+  rocksdb.num.range-deletions: 1