sstable: audit and clean up instances of improper key comparisons in the presence of synthetic prefixes/suffixes

[itsbilal]

Currently, a lot of the code around synthetic prefixes assumes that the comparer holds the property of Compare(x+a, x+b) == Compare(a, b) for any prefix x and arbitrary bytes a,b. This is true for the metamorphic test's comparer, but not for the Cockroach comparer where if the bytes immediately after x denote a local or range-local key, they'll sort before all other keys and break this property.

Here's an example of CopySpan being called with the prefix trimmed away:

pebble/compaction.go

Line 2440 in 1af22dc

start.UserKey = syntheticPrefix.Invert(start.UserKey)

And here we call the comparer with the trimmed key, which is invalid:

pebble/sstable/copier.go

Line 253 in 1af22dc

if r.Compare(end.UserKey, entry.sep) <= 0 {

In the rowblk (and probably also colblk) iterator code, we also do a similar trimming of synthetic prefixes from seek keys before calling the comparer on the remainder, which is invalid:

pebble/sstable/rowblk/rowblk_iter.go

Line 542 in 1af22dc

searchKey = key[len(syntheticPrefix):]

For this reason, in the presence of synthetic prefixes and prefixless sstables, we should materialize the full key before calling the comparer anywhere.

Cockroach companion issue: cockroachdb/cockroach#134168

Jira issue: PEBBLE-296

[jbowens]

Note that we do require that MVCC prefixes (base.Split.Prefix(k)) be comparable with bytes.Compare now and that should hold for the Cockroach comparator as well:

pebble/internal/base/comparer.go

Lines 33 to 34 in 1af22dc

	// Compare(a, b) = bytes.Compare(prefix(a), prefix(b)) if not 0,
	// otherwise ComparePointSuffixes(suffix(a), suffix(b))

Is the issue that we're not split-ing the key in some places before performing the comparison?

[itsbilal]

@jbowens We call the Comparer on the remainder of the key after the synthetic prefix, and the synthetic prefix is actually not the same as the prefix returned by Split - it's much shorter than that. But upon closer inspection I realized that should be okay - the normalization we do in the Cockroach comparer is all about the suffix, not the prefix, so I should better scrutinize the synthetic suffix logic instead of the synthetic prefix logic.

[itsbilal]

I'll close this issue for now as it's a non-issue the way it's currently spelled out. However, the parent issue cockroachdb/cockroach#134168 still stands until we've investigated this properly and gotten a new reproduction + figured out a root cause.