kvserver: incorrect DistSender leaseholder processing for non-VOTERs

[erikgrinaker]

ReplicaDescriptor.Type is a pointer rather than a scalar value:

cockroach/pkg/roachpb/metadata.proto

Line 151 in aee773a

optional ReplicaType type = 4 [(gogoproto.moretags) = "yaml:\"ReplicaType,omitempty\""];

We often use regular equality comparisons on replica descriptors, notably in the DistSender and gRPC transport:

cockroach/pkg/kv/kvclient/kvcoord/dist_sender.go

Line 2209 in f77e393

if *lh != curReplica || sameReplicaRetries < sameReplicaRetryLimit {

cockroach/pkg/kv/kvclient/kvcoord/transport.go

Line 258 in 9ad06da

if gt.replicas[i] == replica {

But recall that equality for pointers will check that the memory address is the same, rather than that the value is the same. Thus two identical replica descriptors with a type different from VOTER (the zero value) will be considered unequal if they are stored in different memory locations.

One immediate effect of this is that the DistSender will not prioritize new leaseholders with a VOTER_INCOMING type. In #74546, VOTER_INCOMING was allowed to receive the lease and thus included in the DistSender's replica list with the RoutingPolicy_LEASEHOLDER policy:

cockroach/pkg/kv/kvclient/kvcoord/dist_sender.go

Lines 1932 to 1943 in f77e393

	// Filter the replicas to only those that are relevant to the routing policy.
	var replicaFilter ReplicaSliceFilter
	switch ba.RoutingPolicy {
	case roachpb.RoutingPolicy_LEASEHOLDER:
	replicaFilter = OnlyPotentialLeaseholders
	case roachpb.RoutingPolicy_NEAREST:
	replicaFilter = AllExtantReplicas
	default:
	log.Fatalf(ctx, "unknown routing policy: %s", ba.RoutingPolicy)
	}
	leaseholder := routing.Leaseholder()
	replicas, err := NewReplicaSlice(ctx, ds.nodeDescs, desc, leaseholder, replicaFilter)

However, when it receives the NLHE it attempts to move the new leaseholder to the front of the transport list:

cockroach/pkg/kv/kvclient/kvcoord/dist_sender.go

Lines 2201 to 2212 in f77e393

	if lh := routing.Leaseholder(); lh != nil {
	// If the leaseholder is the replica that we've just tried, and
	// we've tried this replica a bunch of times already, let's move on
	// and not try it again. This prevents us getting stuck on a replica
	// that we think has the lease but keeps returning redirects to us
	// (possibly because it hasn't applied its lease yet). Perhaps that
	// lease expires and someone else gets a new one, so by moving on we
	// get out of possibly infinite loops.
	if *lh != curReplica || sameReplicaRetries < sameReplicaRetryLimit {
	transport.MoveToFront(*lh)
	}
	}

But this won't happen because the non-nil Type doesn't satisfy the equality check in MoveToFront:

cockroach/pkg/kv/kvclient/kvcoord/transport.go

Line 258 in 9ad06da

if gt.replicas[i] == replica {

Jira issue: CRDB-18022

[blathers-crl]

cc @cockroachdb/replication

[erikgrinaker]

There's an additional issue with the DistSender here in that the transport will keep the initial range descriptor across all retries, regardless of whether we update the range descriptor in the meanwhile. This means that it will be vulnerable to changes in a replica's type during these retries regardless of the type change as well. I'll keep this issue to cover both.

[arulajmani]

There's an additional issue with the DistSender here in that the transport will keep the initial range descriptor across all retries, regardless of whether we update the range descriptor in the meanwhile.

@erikgrinaker I'm currently working on addressing exactly that with my patch for #75742 which is caused by what you describe. My current thinking is that we should recognize if the routing (range desc, lease) has been updated to a point where it's no longer compatible with the transport, in which case, we should bail early and just retry.

[erikgrinaker]

Cool! I have a minor fix for the immediate problem here as well in #85140, which ignores the replica type when comparing replicas.

What you're saying makes sense. I suppose the alternative would be to update the transport on-the-fly, but I don't know if we really gain much performance-wise over just bailing and retrying.

What do you mean by compatible? I imagine it will bail if the given leaseholder isn't in the range descriptor. What about a partially matching range descriptor? Will it bail immediately, or keep trying the ones they have in common? Does it care about replica types?

I suppose the risk if it was too sensitive would be that it could start flapping between two replicas with very different views of the range descriptor. Although the generation would prevent that, I guess.

[arulajmani]

I suppose the alternative would be to update the transport on-the-fly, but I don't know if we really gain much performance-wise over just bailing and retrying.

We recently started shipping back range descriptors inside of NotLeaseHolderErrors. We currently don't make use of them, but the idea is to update the RangeCache with a fresher range descriptor if one was returned in the NLHE. This means bailing and retrying shouldn't cause a cache eviction + lookup, which should help reduce any performance concerns.

What do you mean by compatible? I imagine it will bail if the given leaseholder isn't in the range descriptor. What about a partially matching range descriptor? Will it bail immediately, or keep trying the ones they have in common? Does it care about replica types?

I was imagining that we'd bail if the leaseholder wasn't part of the transport. Even though the routing can have stale lease information/range descriptor we never expect it to regress. So, if the routing has been updated such that the leaseholder is not part of the transport, I don't think we get much by exhausting the transport before retrying. We should be able to bail early and retry with a new transport constructed with a fresh(er) range descriptor.
I'm detecting this by having MoveToFront return whether the leaseholder was successfully moved to the front or not. So, given the changes in your PR, it'll be agnostic to the replica type.

I suppose the risk if it was too sensitive would be that it could start flapping between two replicas with very different views of the range descriptor. Although the generation would prevent that, I guess.

Yup, things mostly work as expected with the lease sequences/range descriptor generation to make sure our cache never regresses. The only subtlety I found was around speculative leases -- whenever there's a speculative lease coming from a replica that has an older view of the range descriptor, we simply disregard it.

I'll add you to the PR as well once it's out.

[erikgrinaker]

Sounds good, thanks!