Problem:

The current load based splitter is tuned for determining a split point that will evenly divide QPS of a range if it were split. However it is desirable to experiment with new rebalancing signals, which should be symmetric in both the rebalancer and lb splitter to avoid inconsistency where the range doesn’t split yet cannot be rebalanced due to being too large. For example CPU, the LB splitter does not support finding a split key where the magnitude of each span recorded is not 1. A simple solution is to re-record the span against the decider for each increment in magnitude, however due to the sampling method this would not be fairly weighted in finding a split key.

Solution should support:

• Recording a positive integer (n) against a span [start, end] at a specific time (ts). Where the n is some measure of load recorded for a span e.g. Record(ts, n, span).
• Finding a split key such that the load on the resulting split ranges would be as equal as possible according to the recorded loads above e.g. Key().
• Heavier weighting toward more recent recorded spans.
• Splitting the data structure so that after we split the current range by the split key, the resulting split ranges can immediately have knowledge of the load / distribution for potential future splits.
• Being fast and memory-efficient.

Jira issue: CRDB-20841

Epic CRDB-20845