storage: must never reuse state from old replicaIDs

[tbg]

I was looking at the range merge tests and in particular
TestStoreRangeMergeAddReplicaRace (at its time of introduction; it has since
changed due to learners and lost a lot of its context), see

ce93650

The worry is roughly that when a snapshot that does not contain a merge is
sitting on some store (which is not part of the range) and this store is then
added to the range, the replica will likely blow up while applying the merge
trigger, is the subsumed replica is very unlikely to be present - this colocation
is only achieved for the duration of the merge txn and for the stores that
are members of the range.

At the time of the below comment, the way such a situation would come to be is
because preemptive snapshots were sent before starting the replica change txn.
So you'd send a snapshot, then do a merge, and (before we introduced the range
desc generation for that purpose) the upreplication could succeed, boom.

However, this sequence of events might unfold just the same without any preemptive snaps:

1. add replica on store
2. remove replica from store; replicaGC is delayed
3. run a merge
4. readd store

Here, in 4 I don't mean "re-add as a learner and promote to voter"! It's enough to
readd it as a learner. Raft will start catching up the old snapshot and boom, we
hit the problem above.

This actually seems like a likely problem to occur in practice if replicas are
removed and re-added frequently while merges occur, though the fact that we still
send explicit learner snapshots could mask it somewhat (that snapshot will postdate
the merge, so it can hide the problem by fast-forwarding the old replica past the
merge).

Fixing this is probably not easy. We want to "not reuse old snapshots", i.e. when the
replicaID changes we want to delete all our state and start anew. This is far from a
trivial change, but it's in the spirit of changes that we want to make anyway to lower
the complexity in the storage package. Anyway the first step here is reproducing the
problem.

cc @danhhz @nvanbenschoten

// TestStoreRangeMergeAddReplicaRace verifies that an add replica request that
// occurs concurrently with a merge is aborted.
//
// To see why aborting the add replica request is necessary, consider two
// adjacent and collocated ranges, Q and R. Say the replicate queue decides to
// rebalance Q onto store S4. It will initiate a ChangeReplicas command that
// will send S4 a preemptive snapshot, then launch a replica-change transaction
// to update R's range descriptor with the new replica. Now say the merge queue
// decides to merge Q and R after the preemptive snapshot of Q has been sent to
// S4 but before the replica-change transaction has started. The merge can
// succeed because the ranges are still collocated. (The new replica of Q is
// only considered added once the replica-change transaction commits.) If the
// replica-change transaction were to commit, the new replica of Q on S4 would
// have a snapshot of Q that predated the merge. In order to catch up, it would
// need to apply the merge trigger, but the merge trigger will explode because
// S4 does not have a replica of R.
//
// To avoid this scenario, ChangeReplicas commands will abort if they discover
// the range descriptor has changed between when the snapshot is sent and when
// the replica-change transaction starts.
//
// There is a particularly diabolical edge case here. Consider the same
// situation as above, except that Q and R merge together and then split at
// exactly the same key, all before the replica-change transaction starts. Q's
// range descriptor will have the same start key, end key, and next replica ID
// that it did when the preemptive snapshot started. That is, it will look
// unchanged! To protect against this, range descriptors contain a generation
// counter, which is incremented on every split or merge. The presence of this
// counter means that ChangeReplicas commands can detect and abort if any merges
// have occurred since the preemptive snapshot, even if the sequence of splits
// or merges left the keyspan of the range unchanged. This diabolical edge case
// is tested here.

[tbg]

Another aspect of this came up in https://github.com/cockroachdb/cockroach/pull/39796/files. (see commit message of the testing commit). If a peer is removed, it seems possible that it would be caught up past the replication change that removes it. At the time of writing, this happens routinely when peers are removed and re-added without undergoing replicaGC in the meantime, but it's always an awkward situation to handle. With #40459 it will become the exception, so we want to make sure that it's not possible at all.

@ajwerner this is closely related to #40459. There, I think your latest approach drops incoming raft messages until the state has been GC'ed. What we want to do here is basically that when a replica sees itself get removed in a ChangeReplicasTrigger log entry, it needs to replicaGC itself. There's not anything to "drop" really, so I don't think we can use the strategy of "stalling" until the replicaGCQueue comes along. We sort of need the replica to just stop existing in-place, I think. Curious if you had any thoughts on this.

[ajwerner]

We sort of need the replica to just stop existing in-place, I think. Curious if you had any thoughts on this.

Just to check my understanding, the issue is that we need this replica to stop applying raft entries as soon as it notices that it has been removed.

cockroach/pkg/storage/replica_application_result.go

Lines 296 to 312 in 1dcd427

	func (r *Replica) handleChangeReplicasResult(ctx context.Context, chng *storagepb.ChangeReplicas) {
	storeID := r.store.StoreID()
	var found bool
	for _, rDesc := range chng.Replicas() {
	if rDesc.StoreID == storeID {
	found = true
	break
	}
	}
	if !found {
	// This wants to run as late as possible, maximizing the chances
	// that the other nodes have finished this command as well (since
	// processing the removal from the queue looks up the Range at the
	// lease holder, being too early here turns this into a no-op).
	r.store.replicaGCQueue.AddAsync(ctx, r, replicaGCPriorityRemoved)
	}
	}

It seems like if the replica were to set its destroyStatus and then find a way to bail out of entry application at that point then we'd be okay waiting for replicaGC.

Additionally we should probably ignore ticks for destroyed replicas.

Another concern I have is the tight loop spinning waiting for replicaGC in tryGetOrCreateReplica():

cockroach/pkg/storage/store.go

Line 3955 in 1dcd427

} else if ds := repl.mu.destroyStatus; ds.reason == destroyReasonRemoved {

[ajwerner]

It seems like we're ultimately trying to eliminate setReplicaID(). Is there any reason why we want that method to continue to exist after we have learners and we prevent processing entries across a remove and re-add?

[tbg]

Just to check my understanding,

Yep, exactly. We don't want it to advance on the log past its removal. In fact we'd do well to not even process the removal itself (or it will be harder to manage the case in which a node restarts immediately after).

It seems like if the replica were to set its destroyStatus and then find a way to bail out of entry application at that point then we'd be okay waiting for replicaGC.

Yeah, that's the part I wasn't sure we could achieve reasonably well. It seems conceptually OK (propagate a "stop" flag when we see a raft command that would remove the replica from the desc and handle that in the right place to set the destroy status, and make it such that replicas which are destroyed never handle readies)

Also cc @danhhz because we spent many a merry 1:1 discussing how good it would be if we had this invariant about replicas always being in their range descriptor, and now it seems that we might be getting it earlier than we thought it possible.