storage: revisit Raft log truncation and Raft snapshots

[petermattis]

In normal operation, all of the replicas for a range are close to the commit index and raft log truncation deletes unnecessary state. When one replica falls too far behind, the raft log queue will decide to truncate the raft log for the range in such a way that will force that replica to be "caught up" via a snapshot. Once this occurs, there is not much point in keeping that original replica as part of the range as it no longer contributes to the Range quorum.

Raft-initiated snapshots involve a decent amount of complexity in the code (i.e. Replica.mu.{outSnap,outSnapDone}). As an alternative to that complexity, we could replace the Raft related snapshot code with a small bit of code to enqueue the replica in the replicate queue when a Raft snapshot is requested. I think this would involve lying to Raft to indicate that the snapshot was generated and then having the replicate queue remove any replica which is in state ProgressStateSnapshot. In addition to the code simplification, this approach would have the benefit of proactively rebalancing active ranges away from slow nodes. There is some additional overhead to going through the Raft group configuration change to remove a replica and add a new one, but I think that will be lost in the noise.

There is some exploration to do here to make sure I'm not missing anything. @bdarnell please point out the flaws in this idea.

Cc @cockroachdb/stability

[bdarnell]

My biggest concern is that during the two replica change operations, we're at increased risk of failure: If one of the healthy nodes dies, we're at 1/2 (instead of 2/3 with one of the two nodes unhealthy but recoverable with a snapshot). Raft snapshots make some failures recoverable which would be a total loss if we got rid of them. As long as this situation is rare (comparable to other causes of node failure), then that may acceptable; a 3-replica configuration can't guarantee survival after two near-simultaneous failures. But I'm concerned that since we'll be doing this with nodes that are slow but not completely failed, it might end up being more common (and silent!) leaving us in a more fragile state.

There are also some edge cases: in a cluster with only three nodes, the remove-and-re-add dance is pure risk with no real benefit because there's no healthier node to rebalance onto.

I think that most of the complexity around raft snapshots could be removed with a simple (but slightly backwards-incompatible) change to upstream raft to pass the target replica ID to the Snapshot method. Then we could send them more like preemptive snapshots.

I think this would involve lying to Raft to indicate that the snapshot was generated and then having the replicate queue remove any replica which is in state ProgressStateSnapshot.

No need to lie to raft; we could do this in the raft log queue when we truncate the log to a position that is after some replica's acknowledged position. I think it's a good idea to use this event as an input to the rebalancer even if we don't get rid of raft snapshots completely.

[petermattis]

Ah, that's fascinating: a 3 replica group with 1 replica dead and 1 replica behind can recover to a quorum via a Raft snapshot. But a 2 replica group with 1 replica dead is stuck until the dead replica recovers. I need to etch that into my brain as I've had that epiphany before and forgotten it.

I think that most of the complexity around raft snapshots could be removed with a simple (but slightly backwards-incompatible) change to upstream raft to pass the target replica ID to the Snapshot method. Then we could send them more like preemptive snapshots.

A change to the upstream Raft interface would make this easier, but I don't think it is necessary. We could change Replica.Snapshot to always return a non-empty but bogus raftpb.Snapshot. Then in Replica.handleRaftReady we could notice this bogus snapshot and instead of sending it on we notify replicateQueue. replicateQueue could then either notice that the replica is in ProgressStateSnapshot and either perform a snapshot (without a ChangeReplicas) or add a new replica and remove the behind replica.