storage,kvserver: rangekeys written with a synthetic MVCC timestamp risk never being unset as part of schema gc

[nicktrav]

When an index or table is dropped, a RANGEKEYSET is placed over the corresponding keyspan as a cheap way of masking it. When the GC period for the index / table has passed, the database writes a RANGEKEYUNSET to "annhilate" the RANGEKEYSET. Given how rangekeys work, the unset will only remove the set is if the rangekey suffixes match.

CRDB places the MVCC timestamp in the rangekey suffix. In prior versions of CRDB, the MVCC timestamp could be synthetic. Thus, a RANGEKEYSET could contain a suffix consisting of a synthetic MVCC timestamp. Synthetic timestamps have since been deprecated and removed, see #101938.

However, when performing a schema GC operation in newer version that does not have synthetic timstamps, when we query the rangekeys to GC, the timestamp generated will never be synthetic. Thus, any RANGEKEYSET written with a synthetic timestamp will never be GC'd: while the RANGEKEYUNSETs written will have corresponding spans, the suffixes will never be equal due to the lack of the synthetic bit.

For example, consider a RANGEKEYSET for a span:

RANGEKEYSET: /Table/2710/{NULL-2/NULL} - 17d1905bc26af86300000002010e

Note the trailing 10e on the timestamp.

The corresponding RANGEKEYUNSET generated as part of GC will be:

RANGEKEYUNSET: /Table/271{0/2/NULL-1/NULL} - 17d1905bc26af863000000020d

The latter has a timestamp that is not synthetic.

The DB would ideally be defensive when encountering these old synthetic timestamps as part of GC (and possibly more generally).

Jira issue: CRDB-41605

[nicktrav]

I narrowed this down some more. The problem looks to be an issue with the codec for the MVCC timestamp now being "lossy".

When we scan through Pebble looking for range keys, the iterator implementations all boil down to a pebbleIterator, which has RangeKeys and a EngineRangeKeys methods, that both call (*pebble.Iterator).RangeKeys. This gives us the raw Pebble range keys - a start key, and a value, which unpacks to the end key, and a suffix. For MVCC keys, the timestamp is in the suffix.

The suffix that we read from the Pebble store is unadulterated, and is an (old) synthetic key. E.g. 17d1905bc26af86300000002010e (note the trailing \x01 bit after the logical time, 2).

For the (*pebble.Iterator).EngineRangeKeys method, we don't muck with the value, and everything is ok.

However, for (*pebble.Iterator).RangeKeys, it decodes the timestamp through DecodeMVCCTimestampSuffix. And as part of #101938, we stopped putting the synthetic bit in the hlc.Timestamp struct (the field was deprecated in 62ebe56, and we stoped writing to and reading from that field in 3773994 and f05520f, respectively). Therefore, we'll lose the synthetic bit when converting from Pebble's representation to the MVCC representation.

This is a problem for rangekeys, because when we write the RANGEKEYUNSET down here in ClearMVCCRangeKey, we call EncodeMVCCTimestampSuffix to generate the suffix, which no longer has knowledge of the synthetic bit, and thus wont write it. We end up with a suffix like 17d1905bc26af863000000020d, which them means this RANGEKEYUNSET cannot wipe out the RANGEKEYSET it was supposed to, because the suffixes don't match.

Here's a test that demonstrates this loss:

func TestTimestampRoundTrip(t *testing.T) {
	const tsHexIn = "17d1905bc26af86300000002010e" // Walltime + Logical + Synthetic
	b, err := hex.DecodeString(tsHexIn)
	require.NoError(t, err)

	// From pebble representation.
	// NOTE: We lose the synthetic bit here.
	ts, err := storage.DecodeMVCCTimestampSuffix(b)
	require.NoError(t, err)

	// Back to pebble representation.
	b = storage.EncodeMVCCTimestampSuffix(ts)
	tsHexOut := hex.EncodeToString(b)

	// Assert we didn't lose anything along the way.
	require.Equal(t, tsHexIn, tsHexOut) // Fails!
}

[nicktrav]

It looks like we then fixed all of this when we fixed the comparators recently, in #128043.

So ... we should be good here?

[nicktrav]

I'm going to close this out, as we have the fix in the following release branches:
- 23.2: #128818
- 24.1: #128817
- 24.2: #128816

Edit: The backports above were not actually addressing the comparator issue. See below.

[RaduBerinde]

The backports above did not address the issue, reopening to track backporting the comparator fixes.

[blathers-crl]

Based on the specified backports for linked PR #129605, I applied the following new label(s) to this issue: branch-release-23.1, branch-release-23.2, branch-release-24.2.1-rc. Please adjust the labels as needed to match the branches actually affected by this issue, including adding any known older branches.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is dev-inf.}

[RaduBerinde]

Reopening since the fixes were backed out.

[jbowens]

Fixed on 24.1, 24.2, 24.2.2 staging, 24.2.3-rc and master.