storage: provide a way to reset ContainsEstimates via stats recomputation

[tbg]

See #36907 for context. Time series merges and AddSSTable requests can "taint" the range stats by introducing the ContainsEstimates flag. The consistency checker is supposed to notice this and will trigger a stats recomputation. However, it doesn't have a good way to actually reset the ContainsEstimates flag, even after stats are correct. This is because the recomputation relies on the commutativity of stats deltas, but resetting a boolean does not commute with setting that boolean. In other words, if the recomputation attempted to reset the boolean, it couldn't make sure that some other command simultaneously introduces an estimate that is then not reflected in the final, untainted, mvccstats.

A simple fix is to upgrade the MVCCStats.ContainsEstimates field from a bool to a counter that is incremented with each Raft command containing estimates. The stats recomputation would emit the negative count observed on the stats contained in the snapshots it's using to compute a stats delta. In practice, this will almost always lead to ContainsEstimates==0, except when an estimate raced in, in which case it will be counted correctly. ContainsEstimates should never become negative since that could only happen with two concurrent recomputations, and I believe we prevent those already (or they could mangle the stats).

Labeling as E-intermediate because there's a bit of a migration involved.

[tbg]

cc @knz because we talked about this

[tbg]

Pointers to understand/tackle this:

The stats sit on the Replica, here (and in a persisted key that's kept in sync with the in-memory object)

cockroach/pkg/storage/replica.go

Lines 795 to 802 in 947878a

	// GetMVCCStats returns a copy of the MVCC stats object for this range.
	// This accessor is thread-safe, but provides no guarantees about its
	// synchronization with any concurrent writes.
	func (r *Replica) GetMVCCStats() enginepb.MVCCStats {
	r.mu.RLock()
	defer r.mu.RUnlock()
	return *r.mu.state.Stats
	}

Whenever a Raft command applies, we add a corresponding stats update:

cockroach/pkg/storage/replica_raft.go

Lines 2343 to 2348 in 5c6824f

	// Set the range applied state, which includes the last applied raft and
	// lease index along with the mvcc stats, all in one key.
	if err := r.raftMu.stateLoader.SetRangeAppliedState(ctx, writer,
	raftAppliedIndex, leaseAppliedIndex, &ms); err != nil {
	return storagepb.ReplicatedEvalResult{}, errors.Wrap(err, "unable to set range applied state")
	}

This happens on every Replica (i.e. three times with a default 3x replicated range), but it's deterministic, so all replicas should have identical stats (at any given position). If this isn't the case it's bad, but this isn't something we worry about in this issue.

Some Raft commands set the ContainsEstimates field to true. These are commands that don't want to compute the exact stats because it's too expensive for them. Instead, they give some approximation which is added (identically, on each replica, like any stats updated). Once a range has applied such an update, its ContainsEstimates stays true eternally until it is merged away (which for most ranges, is never).

The consistency checker is a queue that periodically computes a checksum across the replicas and makes sure it matches (at the same log position across the replicas).

cockroach/pkg/storage/consistency_queue.go

Line 125 in fcfd9b8

resp, pErr := repl.CheckConsistency(ctx, req)

As a side effect of that (since it has to look at all the data anyway), it can recompute the "true" MVCCStats of the range, and compare it to what the range claims the MVCCStats are. Absent a bug, these stats can only disagree if ContainsEstimates==true on the range.

If a delta is found, the consistency checker initiates a RecomputeStatsRequest:

cockroach/pkg/storage/replica_consistency.go

Lines 198 to 202 in c42e3eb

	log.Infof(ctx, "triggering stats recomputation to resolve delta of %+v", results[0].Response.Delta)
	req := roachpb.RecomputeStatsRequest{
	RequestHeader: roachpb.RequestHeader{Key: startKey},
	}

This request computes the current stats (it's kind of questionable that it scans the range again, but let's leave that alone) and adds the delta to them which is then applied to the stats through a raft command:

cockroach/pkg/storage/batcheval/cmd_recompute_stats.go

Lines 86 to 97 in 2558dcc

	actualMS, err := rditer.ComputeStatsForRange(desc, snap, cArgs.Header.Timestamp.WallTime)
	if err != nil {
	return result.Result{}, err
	}
	currentStats, err := MakeStateLoader(cArgs.EvalCtx).LoadMVCCStats(ctx, snap)
	if err != nil {
	return result.Result{}, err
	}
	delta := actualMS
	delta.Subtract(currentStats)

Now you'd hope that this would also reset ContainsEstimates to false. But this isn't the case because we can't guarantee that there isn't a request that wants to introduce an estimate that applies just before our "reset" of that flag. If that happened, we'd reset the flag even though there is still an estimate. We don't want that.

The solution is to turn the boolean into something that commutes, i.e. integer addition. Instead of ContainsEstimates bool we have ContainsEstimates int64. Each command introducing an estimate would add 1 to it. In the RecomputeStats evaluation, we would emit a delta of -currentStats.ContainsEstimates. When that applies, usually we have ContainsEstimates==0, i.e. there aren't any. If a command slips in ahead of us, we'll add up with a 1. Everything just works.

Steps to do this:

• add a cluster version, see

  cockroach/pkg/settings/cluster/cockroach_versions.go

  Lines 24 to 28 in db1ee68

  	// To add a version:
  	// - Add it at the end of this block.
  	// - Add it at the end of the `Versions` block below.
  	// - For major or minor versions, bump BinaryMinimumSupportedVersion. For
  	// example, if introducing the `1.4` release, bump it from `1.2` to `1.3`.

• change the ContainsEstimates field from a bool to an int64 (double check the proto spec that this is safe, i.e. that it'll happily decode the 1 as true and 0 as false), update the code accordingly (i.e. false corresponds to 0, everything else corresponds to 1 but we'll only see 0 and 1 at this stage).
• a gotcha is that all the commands that introduce ContainsEstimates = true (in pkg/storage/batcheval) need to check the current stats, and only emit a ContainsEstimates==true if it isn't already true (otherwise we'll start generating numbers larger than 1 before we know that all nodes can handle that -- an old node would decode such numbers as true and would diverge from the rest, because true corresponds to 1). Once the cluster version is active however, always emit 1.
• use the cluster version in RecomputeStats: when it's active, we know all nodes know about the integers, and we can emit a delta of -ContainsEstimates. Otherwise, we do what today's code does, i.e. we don't touch ContainsEstimates.

Note that this migration doesn't cover all the bases. There's a case in which the result will be a divergence of the stats. As sort of a pop quiz I'll leave open how that can happen. I have a way out as well. (Updates will be required to the list above).

[giorgosp]

Just a ping that I am working on this although I haven't pinged for several days.
I have wrapped my head around the ContainsEstimates concept and most of my effort was in tracing the related code paths.

On a low level note, I guess the new behavior for AddSSTable should also be implemented for time series merges as well (in updateStatsOnMerge during MVCCMerge).