I don't fully understand the motivation for this change. Before making the change, I'd like to better understand how things will work with and without it. Specifically, what will happen to a RangeCache that contains a descriptor coming from an intent in the following three cases:

1. the split completes successfully and resolves the intent
2. the split fails and rolls back the intent
3. the split stalls while continuing to heartbeat its txn record

In all three cases, we want to minimize the disruption that the RangeCache will have on foreground traffic trying to access the data on the splitting range.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten)

In all 3 cases, the intent descriptor will be put in the cache upon eviction of the original (modulo the problem that said eviction needs to happen specifically through the EvictionToken coming from the original insertion of the pre-split descriptor; evictions resulting from other cache operations won't do).
This patch does not change whether the speculative descriptor makes it into the cache or not. It just changes how vulnerable it is once it made it into the cache. Before, it would make it into the cache with its speculative Generation. Which is bad in case 2 (intent getting rolled back) because then the future real descriptor with that Generation will have trouble getting into the cache because it won't be NewerThan the speculative one. Most likely what will happen is that the insertion of the future descriptor will panic because it will detect a non-copacetic desc with the same generation:

This patch fixes this by inserting the post-split descriptor with a Generation of 0, which makes the respective cache entry look older than any would-be replacement - in particular than the replacement with the same Generation as the rolled-back intent, or even the original descriptor (with a lower generation) if it turns out that we have wrongly evicted it.
This works for the split case, but not for the merge case. For merges, let's say we had [a,b) being merged with [b,c). Once we evict [a,b) we'll try to insert the speculative [a,c). Inserting [a,c) with a generation of 0 will fail if we have [b,c) in the cache. This seems funky, but the current behavior (evicting [b,c)) also seems funky to me. It's one thing to replace empty space in the cache with a speculative descriptor, it's another thing to replace an entry like [b,c) which might be fine for all we know. But I could be convinced otherwise, and we could fix it by finding another way of tracking the "speculative" character of [a,c).

If you buy this, I can update the commit msg.
But I'm interested in discussing the possibility of getting out of this speculation game, just because it seems complex to me and I'm scared of it. In what circumstances does the current speculation actually help? It only helps nodes that read meta2 during the split/merge txn. Which should be ~nobody, right? I think a better way to minimize the impact of splits/merges is to gossip the descriptor updates (as @knz and I keep talking about doing). If we do that gossiping, then I guess we have an analogous question about whether we should gossip speculatively before the split commit, or after the commit. But I'd just start with after and take it from there.
On the other hand, I was thinking that, perhaps, the point of the current speculative descriptor is not really to help with minimizing the impact of splits on traffic; instead maybe it's required for splits to work in the first place - I kinda remember something about these transactions relying on these intents in a subtle way (perhaps for cleaning up the intent itself because, after the commit, only the intent has the right descriptor in it?). Do you know anything about this?

Reviewable status: complete! 0 of 0 LGTMs obtained

So you'd want an explicit speculative flag in the RangeCacheEntry? Can do, but then I guess that forces our hand to have a way of resetting the speculative flag too when we know that the speculation has worked out. I guess this part becomes easy with #51437 when a successful RPC either returns an updated descriptor or implicitly confirms that the caller had it right. So I guess I can piggy-back an EvictionToken.Confirm() method on that PR - which would be a no-op for non-speculative descriptors and an eviction and reinsertion as non-speculative for the rest. Sounds like a plan?

Btw, @aayushshah15 demonstrated badness caused by the issue this PR is addressing using the kvnemesis with merges enabled. And I'm now pretty sure that this is also the cause of the assertion failure seen in #50995. So I guess I should write a test.

Reviewable status: complete! 0 of 0 LGTMs obtained

Probably all we have is this comment:

Note to self: what I've discussed with Nathan is adding some type safety around speculative range cache entries by having the cache contain an interface as elements, with two implementations and a comparison function with a type switch.

Reviewable status: complete! 0 of 0 LGTMs obtained

The latest round is much better! Promoting speculative descriptors and leases to be front and center makes this all much easier to reason about.

Reviewed 5 of 5 files at r1, 2 of 2 files at r2, 2 of 2 files at r3, 13 of 13 files at r4.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @andreimatei)

pkg/kv/kvbase/range_cache.go, line 35 at r4 (raw file):

	// DescSpeculative returns true if the descriptor in the entry is "speculative"
	// - i.e. it doesn't correspond to a committed value. Such descriptors have been
	// inserted in the cache with Generation=0.

Add a sentence describing how this is possible (i.e. that they were taken from intents).

pkg/kv/kvbase/range_cache.go, line 42 at r4 (raw file):

	Leaseholder() *roachpb.ReplicaDescriptor

	// Lease returns the cached lease, if known. Returns nil if no lease is known. It's

nit: rewrap some of these lines.

pkg/kv/kvclient/kvcoord/dist_sender.go, line 1749 at r4 (raw file):

				replicas.MoveToFront(idx)
			} else {
				log.Eventf(ctx, "leaseholder %s missing from replicas", leaseholder)

Is this possible? Do we want it to be?

pkg/kv/kvclient/kvcoord/dist_sender.go, line 1809 at r4 (raw file):

			// "speculative". Even if the speculation is correct, we want the serve to
			// return an update, at which point the cached entry will no longer be
			// "speculative".

nit: reference the DescSpeculative() method here.

pkg/kv/kvclient/kvcoord/range_cache.go, line 226 at r4 (raw file):

	// the opportunity to use this nextDesc; if another actor races to evict the
	// respective cache entry and wins, nextDesc becomes useless.
	nextDesc *roachpb.RangeDescriptor

Consider renaming this here and elsewhere to "speculativeDesc" and adding a bit of a comment describing its role.

pkg/kv/kvclient/kvcoord/range_cache.go, line 314 at r4 (raw file):

//
// It's legal to pass in a lease with a zero Sequence; it will be treated as a
// speculative lease and considered newer than any existing lease.

But will be immediately replaced by any update, right?

pkg/kv/kvclient/kvcoord/range_cache.go, line 836 at r4 (raw file):

		if cachedEntry != nil && descsCompatible(cachedEntry.Desc(), entry.Desc()) {
			return false, cachedEntry
			//// cachedEntry is almost certainly newer than entry, but we still check

Did you mean to remove this?

pkg/kv/kvclient/kvcoord/range_cache.go, line 1106 at r4 (raw file):

// - i.e. it doesn't correspond to a committed lease. Such leases have been
// inserted in the cache with Sequence=0.
func (e *rangeCacheEntry) leaseSpeculative() bool {

Is it worth adding this to the interface as well? If only to show the symmetry to between DescSpeculative and LeaseSpeculative?

pkg/kv/kvclient/kvcoord/range_cache.go, line 1125 at r4 (raw file):

// can't be determined what information is newer is when at least one of the
// descriptors is "speculative" (generation=0), or when the lease information is
// speculative.

nit: might as well give this word the same treatment: "speculative (sequence=0).

pkg/roachpb/errors.go, line 424 at r1 (raw file):

		return e.rangesInternal
	}
	// Fallback for 20.1 errors. Remove in 20.3.

Giving up hope?

pkg/roachpb/errors.proto, line 41 at r3 (raw file):

  //
  // It's possible for leases returned here to represent speculative leases, not
  // actual committed leasea. In this case, the lease will not have its Sequence

s/leasea/leases/

pkg/roachpb/errors.proto, line 42 at r3 (raw file):

  // It's possible for leases returned here to represent speculative leases, not
  // actual committed leasea. In this case, the lease will not have its Sequence
  // set.

Should we codify this rule in a (Lease) Speculative method?

Also, do we need to worry about leases without sequence numbers on legacy clusters? I don't think so because it seems like any active lease will have begun incrementing the lease sequence a few releases ago, but it's worth going through the thought experiment.

pkg/sql/physicalplan/replicaoracle/oracle.go, line 71 at r1 (raw file):

	// about any of the nodes that might be tried.
	ChoosePreferredReplica(
		ctx context.Context, rng *roachpb.RangeDescriptor, leaseHolder *roachpb.ReplicaDescriptor, qState QueryState,

nit: is leaseholder one word or two? I don't have strong preferences, but let's be consistent. What do we do elsewhere?

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten)

pkg/kv/kvbase/range_cache.go, line 35 at r4 (raw file):

done

pkg/kv/kvbase/range_cache.go, line 42 at r4 (raw file):

done

pkg/kv/kvclient/kvcoord/dist_sender.go, line 1749 at r4 (raw file):

I think so. Added a comment explaining how it can happen.

pkg/kv/kvclient/kvcoord/dist_sender.go, line 1809 at r4 (raw file):

done

pkg/kv/kvclient/kvcoord/range_cache.go, line 226 at r4 (raw file):

see now

pkg/kv/kvclient/kvcoord/range_cache.go, line 314 at r4 (raw file):

expanded the comment

pkg/kv/kvclient/kvcoord/range_cache.go, line 836 at r4 (raw file):

yeah, thanks
I've removed it cause I thought handling it's not worth the code (and it was giving me some other trouble too I think)

pkg/kv/kvclient/kvcoord/range_cache.go, line 1106 at r4 (raw file):

done

but btw I'm gonna move the range cache to its own package and get rid of the RangeCacheEntry iface in kvbase

pkg/kv/kvclient/kvcoord/range_cache.go, line 1125 at r4 (raw file):

done

pkg/roachpb/errors.go, line 424 at r1 (raw file):

:)

pkg/roachpb/errors.proto, line 41 at r3 (raw file):

done

pkg/roachpb/errors.proto, line 42 at r3 (raw file):

Should we codify this rule in a (Lease) Speculative method?

done, and used the new method in the next commit

Also, do we need to worry about leases without sequence numbers on legacy clusters? I don't think so because it seems like any active lease will have begun incrementing the lease sequence a few releases ago, but it's worth going through the thought experiment.

yeah, I've thought about this and I don't think we need to worry about it. One thing that I've tested is that a new cluster doesn't produce leases with seq=0 even immediately after bootstrapping, and it doesn't.

pkg/sql/physicalplan/replicaoracle/oracle.go, line 71 at r1 (raw file):

one word is more prevalent (at least when there's not other words in the variable name). Switched to that.

Reviewed 3 of 18 files at r5, 2 of 3 files at r7, 13 of 13 files at r8.
Reviewable status: complete! 1 of 0 LGTMs obtained

pkg/roachpb/errors.proto, line 42 at r3 (raw file):

Thanks for running that test. The moment after bootstrapping was also concerning me.

bors r+

Reviewable status: complete! 1 of 0 LGTMs obtained