Great to see this! A drive-by question I had is whether the backport of this will be problematic, and whether we're planning a surgical fix to backport instead.

LGTM!

Reviewed 5 of 5 files at r5, 3 of 3 files at r6, 4 of 4 files at r7, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten)

Nice! Always a pleasure to see shifty ad-hoc code gone.

Reviewed 5 of 5 files at r5, 3 of 3 files at r6, 4 of 4 files at r7, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aayushshah15 and @nvanbenschoten)

pkg/kv/kvserver/allocator.go, line 1502 at r6 (raw file):

	candidates := make([]roachpb.ReplicaDescriptor, 0, len(existing))
	for i := range existing {
		if existing[i].GetType() != roachpb.VOTER_FULL {

Is this correct? I thought we now possibly transferred leases to a VOTER_INCOMING. Is this only occurring on a separate ad-hoc path?

pkg/kv/kvserver/allocator.go, line 1570 at r6 (raw file):

		}
	}
	if !leaseholderInExisting && !buildutil.CrdbTestBuild {

It's unusual to have an assertion that's only in production but not in tests. Could you add a comment on why that is necessary? It might be cleaner to use a testing knob here to selectively disable the assertion. I also think we may want to avoid fataling in prod for something like this, when there is the reasonable enough option to "do nothing". I wouldn't want to deal with the fatal error in prod, as it will be hard to contain and thus difficult to keep the cluster alive.

pkg/kv/kvserver/allocator.go, line 1620 at r6 (raw file):

	opts transferLeaseOptions,
) roachpb.ReplicaDescriptor {
	checkTransferLeaseSource := opts.checkTransferLeaseSource

I wonder if it's worth to pull through and rename this parameter to allowLeaseRepl. checkTransferLeaseSource seems cryptic.

pkg/kv/kvserver/allocator.go, line 1640 at r6 (raw file):

	}

	existing = a.ValidLeaseTargets(

😍

pkg/kv/kvserver/allocator.go, line 1865 at r6 (raw file):

	stats *replicaStats,
) bool {
	if a.leaseholderViolatesPreferences(ctx, conf, leaseRepl, existing) {

Maybe this method would be more aptly named leaseholderShouldMoveDueToPreferences, since this makes it clear that the method checks more than just a violation of preferences (it also verifies that there's a better place to put the lease according to prefs)

pkg/kv/kvserver/replica_command.go, line 3331 at r7 (raw file):

			targetStoreID := potentialLeaseTargets[newLeaseholderIdx].StoreID
			if targetStoreID != r.store.StoreID() {
				log.VEventf(ctx, 2, "randomly transferring lease to s%d", targetStoreID)

Does ctx have the repl in it? With these kinds of messages you always want the range we're talking about.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aayushshah15, @kvoli, @nvanbenschoten, and @tbg)

pkg/kv/kvserver/allocator.go, line 1502 at r6 (raw file):

We do transfer leases to incoming voters now, but that's ad-hoc code for replication changes. AdminChangeReplicas calling into the allocator was always a bit fraught, and we're no longer doing that now since #77841.

pkg/kv/kvserver/allocator.go, line 1570 at r6 (raw file):

All the current callers of this do include the leaseRepl in the slice of existing replicas, so I just wanted some regression insurance for this. Based on your comment, I've downgraded this to a log.Error for now.

pkg/kv/kvserver/allocator.go, line 1620 at r6 (raw file):

Added it as the final commit in this PR.

pkg/kv/kvserver/allocator.go, line 1865 at r6 (raw file):

Done.

pkg/kv/kvserver/replica_command.go, line 3331 at r7 (raw file):

Yep, It should be added here:

Optimistically merging based on the approvals. TFTRs!

bors r+

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aayushshah15, @kvoli, @nvanbenschoten, and @tbg)

Reviewed 8 of 8 files at r11, 4 of 4 files at r12, 6 of 6 files at r13, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aayushshah15 and @nvanbenschoten)

pkg/kv/kvserver/allocator.go, line 1570 at r11 (raw file):

	}
	if !leaseholderInExisting {
		log.Errorf(ctx, "programming error: expected leaseholder store to be in the slice of existing replicas")

But then don't you want to return?

pkg/kv/kvserver/allocator.go, line 1653 at r11 (raw file):

			ctx, source, existing, stats, nil, candidateLeasesMean,
		)
		if !excludeLeaseRepl {

Hadn't read this code before. I don't understand it. You're sure this is all correct, right? I know you're not changing anything in this PR, so just a drive by comment.

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

pkg/kv/kvserver/allocator.go, line 1570 at r11 (raw file):

Done.

pkg/kv/kvserver/allocator.go, line 1653 at r11 (raw file):

I don't really understand why it's written the way it is, and it could use some further clean-up. I'll try and do something about it soon™.