storage: MVCC range keys sometimes omitted by `MVCCIncrementalIterator`

[erikgrinaker]

I'm seeing something that indicates a bug with range key defragmentation and block property filters.

In #86256, I'm adding a metamorphic test parameter for TestMVCCHistories which causes Pebble to use very small blocks, and to flush after every write operation. Try running this a few times:

dev test pkg/storage -f 'TestMVCCHistories' --ignore-cache -v --rewrite

Quite often (depending on the metamorphic parameters), this will generate changes in export and range_key_iter_incremental that either truncate range keys (so e.g. [a-k) is truncated to [a-b)), or fragments disappear completely (e.g. [b-c) disappears from a longer chain of connected fragments). This leads me to suspect a bug in Pebble defragmentation, since I don't see any mechanism in CRDB that would truncate range keys like this.

Both of these test cases use MVCCIncrementalIterator, using a TBI paired with a normal iterator. However, it must be the normal iterator that's surfacing these truncated range keys -- it's still a bit unclear what's happening.

See also cockroachdb/pebble#1895.

Jira issue: CRDB-18652

Epic CRDB-2624

[blathers-crl]

cc @cockroachdb/replication

[erikgrinaker]

I see what's happening now: the TBI and normal iterator have a different view of the range key fragmentation. Consider this case:

• A range key covering [a-f)@3.
• The main iter sees [a-b)@3, [b-d)@3, and [d-f)@3, because of fragmentation by other range keys.
• The TBI limited to the time range [3-3] only sees the defragmented [a-f)@3.
• The TBI is positioned on key a.
• The iterator is positioned on key b, at the start of [b-d@3).
• The TBI wants to catch up to the iterator, so it calls NextKey(). This will skip past the entire [a-f)@3 range key. The iter sees the TBI ahead of itself and seeks to its position, skipping all the fragments in between.

cockroach/pkg/storage/mvcc_incremental_iterator.go

Lines 299 to 310 in 179f935

	// If the iterKey got ahead of the TBI key, advance the TBI Key.
	//
	// We fast-path the case where the main iterator is referencing the next
	// key that would be visited by the TBI. In that case, after the following
	// NextKey call, we will have iterKey == tbiKey. This means that for the
	// incremental iterator to perform a Next or NextKey will require only 1
	// extra NextKey invocation while they remain in lockstep. This case will
	// be common if most keys are modified, or the modifications are clustered
	// in keyspace, which makes the incremental iterator optimization
	// ineffective. And so in this case we want to minimize the extra cost of
	// using the incremental iterator, by avoiding a SeekGE.
	i.timeBoundIter.NextKey()