Some nits and questions mostly otherwise looks sensible.

Reviewed 61 of 61 files at r8, 6 of 6 files at r9, 19 of 19 files at r10, 16 of 16 files at r11, 2 of 2 files at r12, 2 of 2 files at r13, 2 of 2 files at r14, 6 of 6 files at r15, 32 of 32 files at r16, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aliher1911, @erikgrinaker, @jbowens, and @sumeerbhola)

pkg/kv/kvserver/batcheval/cmd_delete_range.go, line 119 at r16 (raw file):

	startKey, endKey, rangeStart, rangeEnd roachpb.Key,
) (roachpb.Key, roachpb.Key) {
	const prevKeyLength = 8192

Is there any significance to this const? Worth a comment?

flushing some questions

Reviewed 13 of 61 files at r8, 1 of 16 files at r11, 1 of 27 files at r55, 10 of 44 files at r56, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aliher1911, @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

pkg/kv/kvserver/replica_raft.go line 2152 at r56 (raw file):

	prefixEnd := prefix.PrefixEnd()
	iter := reader.NewMVCCIterator(storage.MVCCKeyIterKind, storage.IterOptions{
		KeyTypes:   storage.IterKeyTypePointsAndRanges,

there won't be mvcc delete ranges in the raft log, right?

pkg/kv/kvserver/batcheval/cmd_end_transaction.go line 1316 at r56 (raw file):

	// Calculate the RHS adjustment, which turns out to be equivalent to the stats
	// contribution of the range key fragmentation. The naïve calculation would be
	// rhs.EncodedSize() - (keyLen(rhs.EndKey) - keyLen(lhs.EndKey))

should this say

 rhs.EncodedSize() - (keyLen(rhs.StartKey) - keyLen(lhs.EndKey))

?

pkg/kv/kvserver/batcheval/cmd_truncate_log.go line 124 at r56 (raw file):

		LowerBound: start,
		UpperBound: end,
	})

same question about raft log having range keys

pkg/kv/kvserver/batcheval/split_stats_helper.go line 34 at r56 (raw file):

//   AbsPostSplit{Left,Right}Fn, and so we don't expect ContainsEstimates to be
//   set in them. The choice of which side to scan is controlled by ScanRightFirst.
// - DeltaRangeKey: the stats delta that must be added to the non-computed

nit: this is referenced as DeltaRangeKeyRight down below, but is defined as DeltaRangeKey here. should they be unified?

pkg/storage/engine.go line 268 at r56 (raw file):

	// This isn't currently done in order to do spanset assertions on it, but this
	// could be better solved by checking the iterator bounds in NewMVCCIterator
	// and requiring callers to set them appropriately.

🎉 This will allow us to drop an end-key comparison in ComputeStatsForRange: #41899

pkg/storage/mvcc.go line 902 at r56 (raw file):

which is not affected by MVCC range tombstones

can you explain this? A MVCC Range tombstone at t2 that covers the key k@t1 does cause k@t1 to contribute to GCByesAge from t2 on, just like a point tombstone would, right?

is this saying that a MVCC range tombstone that's shadowed at prefix k doesn't itself apply to prefix k's GCBytesAge?

do MVCC range tombstones themselves that are shadowed ever contribute to GCBytesAge? Eg, a MVCCDeleteRange([a,z)@t10) and a MVCCDeleteRange([a,z)@t3)?

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aliher1911, @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

pkg/kv/kvserver/replica_raft.go line 2152 at r56 (raw file):

No, shouldn't be. I figured we might as well enable range keys for all stats calculations, since I assumed the overall overhead would be negligible and better safe than sorry, but we can be more selective about it too.

pkg/kv/kvserver/batcheval/cmd_end_transaction.go line 1316 at r56 (raw file):

No -- that would just be 0, because rhs.StartKey == lhs.EndKey after the split.

What we're trying to adjust for here is really the change in the LHS' end key, from before the split to after the split. Before the split, the range key's end key way rhs.EndKey, while post-split it's lhs.EndKey. But as luck would have it, we can express rhs.EndKey in terms of rhs.StartKey via EncodedSize(), eliminating the dependence on rhs.EndKey.

pkg/kv/kvserver/batcheval/split_stats_helper.go line 34 at r56 (raw file):

Ah, thanks. Yeah, it used to be the case that we always scanned the LHS and then used that to compute the RHS, but some time ago we made it possible to scan either side (since the RHS would often be empty). Forgot to update the names everywhere.

pkg/storage/engine.go line 268 at r56 (raw file):

Ah, nice -- definitely seems worthwhile.

pkg/storage/mvcc.go line 902 at r56 (raw file):

This really only comes up when there are multiple tombstones above a value. With point keys, the prefix contribution to GCBytesAge only starts at the last tombstone. So with a non-tombstone value k@1 with tombstones at k@2, k@3, the GCBytesAge contribution of the prefix starts accumulating from k@3, since GCing below that won't affect the prefix contribution to KeyBytes. However, if we instead had range tombstones [a-z)@2 and [a-z)@3 then the point key ceases to exist at @2, and starts accumulating GCBytesAge from there, because if we GCed up to @2 then we would remove all k point keys, so it would no longer contribute to KeyBytes.

Range keys contribute to GCBytesAge too, but only for the range key as a whole, and per fragment stack. This works in much the same way as point keys: the prefix/key contribution to GCBytesAge begins at the latest range key in the stack, which is where the range key ceases to exist (if it is a range tombstone, which it currently always is). The key contribution of range keys and point keys to stats are independent (they contribute to KeyBytes and RangeKeyBytes separately), and thus the key's contribution to GCBytesAge is also mostly independent, except for range tombstones determining the visibility of point keys.

Reviewed 1 of 27 files at r55, 27 of 44 files at r56, 1 of 1 files at r57, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aliher1911, @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

pkg/storage/mvcc.go line 902 at r56 (raw file):

Ah, thanks, that makes a lot of sense.

pkg/storage/mvcc.go line 2686 at r57 (raw file):

				case 1: // fragment
					fragmentRangeKeys(iter.RangeKeys(), startKey)
				case 0: // merge

To avoid the duplication of this defragmenting logic, could we create an iterator that reads through a batch containing the new range-key iterator? If the SeekLT(startKey) lands on a range key whose end boundary extends beyond startKey, the addition of the new range key merged two fragments. If the surfaced range key has an end boundary equal to startKey, the addition of the range key fragmented a key at the left bound.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aliher1911, @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

pkg/storage/mvcc.go line 2686 at r57 (raw file):

That might work here, but we're going to need similar logic in a bunch of other places where I don't think that's viable, e.g. during AddSSTable, ClearRange, RevertRange, as well as during splits/merges. That said, this code is rather ugly. The plan is to consolidate it with logic elsewhere and clean it up once we've implemented stats handling everywhere at the KV layer. I added a TODO explaining this. Wdyt?

Reviewed 1 of 37 files at r25, 4 of 60 files at r26, 11 of 31 files at r52, 16 of 27 files at r55, 7 of 44 files at r56.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @aliher1911, @erikgrinaker, @jbowens, @nicktrav, and @sumeerbhola)

pkg/storage/mvcc.go line 2686 at r57 (raw file):

Yeah, fine by me. When we get there, we might consider exposing what we need from Pebble if it'll help contain the complexity.