storage: corrupt ReverseScan response after DeleteRangeUsingTombstone

[tbg]

Describe the problem

Check out bba9fd0 from #89477

./dev test --test-args '-show-logs' --stress ./pkg/kv/kvnemesis/ --filter TestKVNemesisSingleNode --stress-args='--failure=invalid.checksum'

> /Table/100/"66893d3c4df432d2": invalid checksum (95cae8e4) value [0a 48 0a 10 6c c0 7a 91 50 0a 42 af a2 c7 44 c5 cf bf d1 d4 1a 14 ec 12 36 36 38 39 33 64 33 63 34 64 66 34 33 32 64 32 00 01 2a 0a 08 a0 ed 8d e8 ff fc d8 90 17 30 b5 9b 16 38 01 4a 0a 08 a0 ed 8d e8 ff fc d8 90 17 50 01 12 0c 08 a0 ed 8d e8 ff fc d8 90 17 10 00 18 00 20 0c 28 11 48 01]
I221025 18:39:45.138935 1114 util/ctxgroup/ctxgroup.go:177  [-] 166 +  | (1) /Table/100/"66893d3c4df432d2": invalid checksum (95cae8e4) value [0a 48 0a 10 6c c0 7a 91 50 0a 42 af a2 c7 44 c5 cf bf d1 d4 1a 14 ec 12 36 36 38 39 33 64 33 63 34 64 66 34 33 32 64 32 00 01 2a 0a 08 a0 ed 8d e8 ff fc d8 90 17 30 b5 9b 16 38 01 4a 0a 08 a0 ed 8d e8 ff fc d8 90 17 50 01 12 0c 08 a0 ed 8d e8 ff fc d8 90 17 10 00 18 00 20 0c 28 11 48 01]

To Reproduce

See above. Adding this to cmd_scan_reverse.go triggers it closer to the source, too:

if err := reply.Verify(nil); err != nil {
  panic(err)
}

Note that (*ReverseScanResponse).Verify doesn't use any data from the request, it looks exclusively at reply.Rows. So this is likely a real bug, not some memory handling problem in kvnemesis.

Unfortunately, I can't reproduce under --race.

Expected behavior

Just works

Additional data / screenshots

If DeleteRangeUsingTombstone is disabled in kvnemesis' generator, this problem does not readily reproduce.

Environment:

master, see PR

Additional context

Jira issue: CRDB-20867

Epic CRDB-20465

[blathers-crl]

Hi @tbg, please add branch-* labels to identify which branch(es) this release-blocker affects.

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

[blathers-crl]

cc @cockroachdb/replication

[erikgrinaker]

We've identified the problem. Excerpt from internal Slack thread:

Basically, dynamically enabling point synthesis in the reverse direction may omit a (valid) synthetic point tombstone when it's triggered on a point key colocated with the range tombstone's start key. We emit synthetic points for all range key timestamps at their start key, but in the reverse direction, the parent iterator may only discover the range key when landing on a point key that's above a range key timestamp. Thus, in the reverse direction, the synthetic point was never emitted for the lower range key, so we'll need to step to it.

This is a bit problematic in that we may not know which synthetic point to position on, as it depends on what the previous positioning operation was (it may e.g. have been a versioned SeekLT which would mandate omitting certain synthetic points). Will need some thought.

[erikgrinaker]

Here's a descriptive test case:

# Regression test for https://github.com/cockroachdb/cockroach/issues/90642.
#
#  REAL DATASET          SYNTHETIC DATASET
#  2    a2 [b2]          2   a2 [b2]
#  1    [---)            1   x
#       a   b                a   b
#
# Recall that pebbleMVCCScanner only enables pointSynthesizingIter when it
# encounters a range key. In the case above, during a reverse scan, the [a-b)@1
# range key will first become visible to pebbleMVCCScanner when it lands on a@2,
# so it enabled point synthesis positioned at the a@2 point key. Notice how the
# iterator has now skipped over the synthetic point tombstone a@1.
#
# This is particularly problematic when combined with pebbleMVCCScanner peeking,
# which assumes that following a iterPeekPrev() call, an iterNext() call can
# step the parent iterator forward once to get back to the original position.
# With the above bug, that is no longer true, as it instead lands on the 
# synthetic point tombstone which was skipped during reverse iteration. During
# intent processing for b@2, such an iterNext() call is expected to land on the
# intent's provisional value at b@2, but it instead lands on the intent itself
# at b@0. This in turn caused a value checksum or decoding failure, where it was
# expecting the current key to be b@2, but the actual key was b@0.
run ok
del_range_ts k=a end=b ts=1
put k=a ts=2 v=a2
with t=A
  txn_begin k=b ts=2
  put k=b v=b2
----
>> at end:
txn: "A" meta={id=00000000 key="b" pri=0.00000000 epo=0 ts=2.000000000,0 min=0,0 seq=0} lock=true stat=PENDING rts=2.000000000,0 wto=false gul=0,0
rangekey: {a-b}/[1.000000000,0=/<empty>]
data: "a"/2.000000000,0 -> /BYTES/a2
meta: "b"/0,0 -> txn={id=00000000 key="b" pri=0.00000000 epo=0 ts=2.000000000,0 min=0,0 seq=0} ts=2.000000000,0 del=false klen=12 vlen=7 mergeTs=<nil> txnDidNotUpdateMeta=true
data: "b"/2.000000000,0 -> /BYTES/b2

run ok
scan t=A k=a end=z reverse
----
scan: "b" -> /<err: unknown tag: UNKNOWN> @0,0
scan: "a" -> /BYTES/a2 @2.000000000,0