cockroachdb / cockroachdb/cockroach
sql: "span stats" algorithm is sub-optimal in a way that causes correctness issues
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
The "span stats" algorithms aims to collect MVCC stats across replicas, and also do this while minimizing fan-outs and tolerating failures.
Recently some improvement was made to failure tolerance. However we've also found that it gathers stale MVCC stats because it asks follower replicas directly for stats.
The following was extracted from a [past review comment](https://github.com/cockroachdb/cockroach/issues/106097#issuecomment-1641794871).
## Current algorithm (pseudo-code)
1. list the nodes that have at least one _replica_ that overlaps with the target span(s) (`nodeIDsForSpan`)
2. on each node:
1. call `getLocalStats` with the list of spans known to have a replica on this node
2. for each span:
- for those ranges that are fully contained in a span, use a KV batch containing a collection of `RangeStatsRequest` via distsender (which is expected to hit locally) - `flushBatchedContainedKeys`
- for those ranges that overlap partially (first and last range), call `storage.ComputeStats` which is a local call.
- only data from local replicas is collected, which may be stale
## Areas for improvement
In decreasing order of impact:
- all this fan-out complexity is because `storage.ComputeStats` is a local call. If there was a KV request type that could handle ComputeStats, DistSender could own the entire networking here and the entire algorithm could collapse into a very small function.
- DistSender would also ensure the stats are not stale.
- it seems strange we hit all nodes with at least one replica. Should we not restrict the fanout to the leaseholders only?
- we only use the distsender fast path inside the inner loop. The case of fully-included ranges should be hoisted at the top of the outer loop instead. DistSender can own the reaching out to leaseholder over the network.
- the KV batch constructed by `flushBatchedContainedKeys` may grow to become arbitrary large. This should be cut up in smaller pieces (maybe 100 ranges at a time).
Jira issue: CRDB-30634
Epic: CRDB-30635
Contributor guide
Assessment
This issue has not been assessed yet.