Repository: cockroachdb/pebble
Pull request #4293 (2025-01-27 16:32:29)

cockroachkvs: handle untimestamped keys in IsLowerBound
The untimestamped key is special and sorts before all other keys. Previously the cockroachkv KeySeeker treated it as sorting after all other keys for the purposes of IsLowerBound.

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

RaduBerinde: 




*[`cockroachkvs/cockroachkvs.go` line 774 at r1](https://reviewable.io/reviews/cockroachdb/pebble/4293#-OHccrYT88m1WH5KbYO1:-OHd8EFnDVEUZdqWyg1I:bwmoshc) ([raw file](https://github.com/cockroachdb/pebble/blob/9f49f63fb5f836c62d450881e0404c507ab5d5af/cockroachkvs/cockroachkvs.go#L774)):*
<details><summary><i>Previously, jbowens (Jackson Owens) wrote…</i></summary><blockquote>

I'm surprised those KV test cases work in that case. We're stuck with the ordering that we have, but it seems extremely error prone to break up the suffix keyspace like that. I can adjust this for now, but I think we should ultimately prohibit those cases because it's not likely to do what's intended (eg, seeking will not get you the most recent version of the key)
</blockquote></details>

I'm not sure I understand the concern. When we introduced crdb we conflated a non-existant suffix with a suffix that is a 0 timestamp Which is fine because the latter is not valid.

But a timestamp that has 0 wall time and non-zero logical time is a valid timestamp and sorts just like any other timestamp. That's why the rest of the code in this file checks both the logical and the wall time against 0, e.g. below we have
```
if wallTime == 0 && logicalTime == 0 {
				// This row has an empty suffix. Since the seek suffix is not empty, it comes after.
```

We Just need `&& !(firstRowWall == 0 && ks.mvccLogicalTimes.At(0) == 0)` I think


<!-- Sent from Reviewable.io -->

RaduBerinde: 




*[`cockroachkvs/cockroachkvs.go` line 774 at r1](https://reviewable.io/reviews/cockroachdb/pebble/4293#-OHccrYT88m1WH5KbYO1:-OHdARi-4BvfWKSa3HzU:b-8disuc) ([raw file](https://github.com/cockroachdb/pebble/blob/9f49f63fb5f836c62d450881e0404c507ab5d5af/cockroachkvs/cockroachkvs.go#L774)):*
<details><summary><i>Previously, RaduBerinde wrote…</i></summary><blockquote>

I'm not sure I understand the concern. When we introduced crdb we conflated a non-existant suffix with a suffix that is a 0 timestamp Which is fine because the latter is not valid.

But a timestamp that has 0 wall time and non-zero logical time is a valid timestamp and sorts just like any other timestamp. That's why the rest of the code in this file checks both the logical and the wall time against 0, e.g. below we have
```
if wallTime == 0 && logicalTime == 0 {
				// This row has an empty suffix. Since the seek suffix is not empty, it comes after.
```

We Just need `&& !(firstRowWall == 0 && ks.mvccLogicalTimes.At(0) == 0)` I think
</blockquote></details>

*When we introduced the crdb key schema


<!-- Sent from Reviewable.io -->

RaduBerinde: 




*[`cockroachkvs/cockroachkvs.go` line 774 at r1](https://reviewable.io/reviews/cockroachdb/pebble/4293#-OHccrYT88m1WH5KbYO1:-OHhoII4EvNLP_xwb55k:b-br7fbm) ([raw file](https://github.com/cockroachdb/pebble/blob/9f49f63fb5f836c62d450881e0404c507ab5d5af/cockroachkvs/cockroachkvs.go#L774)):*
<details><summary><i>Previously, jbowens (Jackson Owens) wrote…</i></summary><blockquote>

> But the latter never happens.. We do use `walltime=0,logical=y` reliably as long as y != 0.

It _can_ happen though, because if we serialize an MVCC key with `walltime=0,logical=0`, it _will_ work. Its encoding is just the empty suffix.
</blockquote></details>

Inside crdb a zero timestamp is treated specially and is never serialized (definitely not with the expectation that it will function as a timestamp). It is considered just a marker for "no timestamp".


<!-- Sent from Reviewable.io -->


Patch:
diff --git a/cockroachkvs/cockroachkvs.go b/cockroachkvs/cockroachkvs.go
index b5ffce88..e0518592 100644
--- a/cockroachkvs/cockroachkvs.go
+++ b/cockroachkvs/cockroachkvs.go
@@ -745,34 +745,60 @@ func (ks *cockroachKeySeeker) IsLowerBound(k []byte, syntheticSuffix []byte) boo
 	if len(syntheticSuffix) > 0 {
 		return ComparePointSuffixes(syntheticSuffix, k[len(roachKey)+1:]) >= 0
 	}
+	firstRowWall := ks.mvccWallTimes.At(0)
+	firstLogical := ks.mvccLogical.At(0)
+	// If the first row's WallTime and LogicalTime are both zero, the first row
+	// is either (a) unversioned (and sorts before all other suffixes) or (b) is
+	// a non-MVCC key with an untyped version.
+	if firstRowWall == 0 && firstLogical == 0 {
+		return ComparePointSuffixes(ks.untypedVersions.At(0), version) >= 0
+	}
+
 	var wallTime uint64
 	var logicalTime uint32
 	switch len(version) {
 	case engineKeyNoVersion:
+		// The zero-length version is the smallest possible suffix.
+		return true
 	case engineKeyVersionWallTimeLen:
 		wallTime = binary.BigEndian.Uint64(version[:8])
 	case engineKeyVersionWallAndLogicalTimeLen, engineKeyVersionWallLogicalAndSyntheticTimeLen:
 		wallTime = binary.BigEndian.Uint64(version[:8])
 		logicalTime = binary.BigEndian.Uint32(version[8:12])
 	default:
-		// The provided key `k` is not a MVCC key. Assert that the first key in
-		// the block is also not an MVCC key. If it were, that would mean there
-		// exists both a MVCC key and a non-MVCC key with the same prefix.
+		// The provided key `k` is not a MVCC key.
 		//
-		// TODO(jackson): Double check that we'll never produce index separators
-		// that are invalid version lengths.
-		if invariants.Enabled && ks.mvccWallTimes.At(0) != 0 {
-			panic("comparing timestamp with untyped suffix")
+		// The first row IS an MVCC key. We don't expect this to happen in
+		// practice, so this path is not performance sensitive. We reconsistute
+		// the first row's MVCC suffix and then compare it to the provided key's
+		// non-MVCC suffix.
+
+		//gcassert:noescape
+		var buf [13]byte
+		//gcassert:inline
+		binary.BigEndian.PutUint64(buf[:], firstRowWall)
+		var firstRowSuffix []byte
+		if firstLogical == 0 {
+			buf[8] = 9
+			firstRowSuffix = buf[:9]
+		} else {
+			//gcassert:inline
+			binary.BigEndian.PutUint32(buf[8:], uint32(firstLogical))
+			buf[12] = 13
+			firstRowSuffix = buf[:13]
 		}
-		return ComparePointSuffixes(ks.untypedVersions.At(0), version) >= 0
+		return ComparePointSuffixes(firstRowSuffix, version) >= 0
 	}
 
 	// NB: The sign comparison is inverted because suffixes are sorted such that
 	// the largest timestamps are "smaller" in the lexicographical ordering.
-	if v := cmp.Compare(ks.mvccWallTimes.At(0), wallTime); v != 0 {
+	if v := cmp.Compare(firstRowWall, wallTime); v != 0 {
+		// The empty-suffixed zero-timestamped key sorts first. If the first row
+		// has zero wall and logical times, it sorts before k and k is not a
+		// lower bound.
 		return v < 0
 	}
-	return cmp.Compare(uint32(ks.mvccLogical.At(0)), logicalTime) <= 0
+	return cmp.Compare(uint32(firstLogical), logicalTime) <= 0
 }
 
 // SeekGE is part of the KeySeeker interface.


Test patch:
diff --git a/cockroachkvs/testdata/key_schema_key_seeker b/cockroachkvs/testdata/key_schema_key_seeker
index 9509b416..5eff3c64 100644
--- a/cockroachkvs/testdata/key_schema_key_seeker
+++ b/cockroachkvs/testdata/key_schema_key_seeker
@@ -169,3 +169,75 @@ MaterializeUserKey(-1, 0) = hex:6d6f6f0000000000b2d05e0109
 MaterializeUserKey(0, 1) = hex:6d6f6f0000000000b2d05e00000000020d
 MaterializeUserKey(1, 2) = hex:6d6f6f0000000000b2d05e00000000010d
 MaterializeUserKey(2, 3) = hex:6d6f6f0000000000b2d05e0009
+
+define-block
+moo
+moo @ 3000000002,1
+moo @ 3000000001,1
+moo @ 0000000001,0
+----
+Parse(moo) = hex:6d6f6f00
+Parse(moo @ 3000000002,1) = hex:6d6f6f0000000000b2d05e02000000010d
+Parse(moo @ 3000000001,1) = hex:6d6f6f0000000000b2d05e01000000010d
+Parse(moo @ 0000000001,0) = hex:6d6f6f00000000000000000109
+
+# IsLowerBound should return false for all keys because the first key of the
+# block sorts before all the provided keys. Previously, a bug did not account
+# for the empty suffix sorting first.
+
+is-lower-bound
+moo @ 9000000000,2
+moo @ 8000000000,2
+moo @ 8000000000,1
+moo @ 8000000000,0
+moo @ 7000000000,9
+moo @ 3000000000,2
+moo @ 3000000000,1
+moo @ 3000000000,0
+moo @ 0000000000,1
+----
+IsLowerBound(moo @ 9000000000,2, "") = false
+IsLowerBound(moo @ 8000000000,2, "") = false
+IsLowerBound(moo @ 8000000000,1, "") = false
+IsLowerBound(moo @ 8000000000,0, "") = false
+IsLowerBound(moo @ 7000000000,9, "") = false
+IsLowerBound(moo @ 3000000000,2, "") = false
+IsLowerBound(moo @ 3000000000,1, "") = false
+IsLowerBound(moo @ 3000000000,0, "") = false
+IsLowerBound(moo @ 0000000000,1, "") = false
+
+define-block
+moo @ 0000000000,1
+moo @ 3000000002,1
+moo @ 3000000001,1
+moo @ 0000000001,0
+----
+Parse(moo @ 0000000000,1) = hex:6d6f6f000000000000000000000000010d
+Parse(moo @ 3000000002,1) = hex:6d6f6f0000000000b2d05e02000000010d
+Parse(moo @ 3000000001,1) = hex:6d6f6f0000000000b2d05e01000000010d
+Parse(moo @ 0000000001,0) = hex:6d6f6f00000000000000000109
+
+is-lower-bound
+moo
+moo @ 9000000000,2
+moo @ 8000000000,2
+moo @ 8000000000,1
+moo @ 8000000000,0
+moo @ 7000000000,9
+moo @ 3000000000,2
+moo @ 3000000000,1
+moo @ 3000000000,0
+moo @ 0000000000,1
+moo @ 02073a83c45688420eaf97824255790f1e12
+----
+IsLowerBound(moo, "") = true
+IsLowerBound(moo @ 9000000000,2, "") = true
+IsLowerBound(moo @ 8000000000,2, "") = true
+IsLowerBound(moo @ 8000000000,1, "") = true
+IsLowerBound(moo @ 8000000000,0, "") = true
+IsLowerBound(moo @ 7000000000,9, "") = true
+IsLowerBound(moo @ 3000000000,2, "") = true
+IsLowerBound(moo @ 3000000000,1, "") = true
+IsLowerBound(moo @ 3000000000,0, "") = true
+IsLowerBound(moo @ 0000000000,1, "") = true
+IsLowerBound(moo @ 02073a83c45688420eaf97824255790f1e12, "") = true