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:

https://github.com/cockroachdb/pebble/blob/1af22dc322eb38a77c35f41910139149999c418a/compaction.go#L2440

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

https://github.com/cockroachdb/pebble/blob/1af22dc322eb38a77c35f41910139149999c418a/sstable/copier.go#L253

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:

https://github.com/cockroachdb/pebble/blob/1af22dc322eb38a77c35f41910139149999c418a/sstable/rowblk/rowblk_iter.go#L542

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: https://github.com/cockroachdb/cockroach/issues/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: https://github.com/cockroachdb/pebble/blob/1af22dc322eb38a77c35f41910139149999c418a/internal/base/comparer.go#L33-L34

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 https://github.com/cockroachdb/cockroach/issues/134168 still stands until we've investigated this properly and gotten a new reproduction + figured out a root cause.