Reviewed 2 of 2 files at r1.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aayushshah15, @andreimatei, and @nvanbenschoten)

pkg/kv/kvserver/allocator_scorer.go, line 846 at r2 (raw file):

// candidate for having a replica removed from it given the candidate store
// list. This method returns true if there are any ranges that are on stores
// that lie _outside of the [underfullThreshold, overfullThreshold] window_ for

I think the comment you've added is not quite right; it doesn't reference the one particular store that this method deals with.

pkg/kv/kvserver/allocator_scorer.go, line 1383 at r2 (raw file):

}

func overfullRangeThreshold(options scorerOptions, mean float64) float64 {

should all these functions error of fatal if the field they each want in options isn't set?

pkg/kv/kvserver/allocator_scorer.go, line 1391 at r2 (raw file):

}

func overfullQPSThreshold(options scorerOptions, mean float64) float64 {

nit: I liked this function more with mean factored out of the math.Min.
Same for underfullQPSThreshold below

pkg/kv/kvserver/allocator_scorer.go, line 1399 at r2 (raw file):

}

// rebalanceFromConvergesScore returns a 1 iff rebalancing a replica away from

nit: s/a 1 iff/1 if :P

pkg/kv/kvserver/allocator_scorer.go, line 1400 at r2 (raw file):

// rebalanceFromConvergesScore returns a 1 iff rebalancing a replica away from
// `sc` will _not_ converge its range count towards the mean of stores in `sl`.

You've left one "range count" in there. You probably want it to adapt it to the new "options"

pkg/kv/kvserver/allocator_scorer.go, line 1409 at r2 (raw file):

) int {
	if options.qpsRebalanceThreshold > 0 {
		// if `qpsRebalanceThreshold` is set, we disable the `convergesScore`.

Can you expand this comment? Why doesn't convergence apply to qps ?
Same in the function below

pkg/kv/kvserver/allocator_scorer.go, line 461 at r3 (raw file):

}

// rankedCandidateListForRemoval creates a candidate list of all existing

nit: I think it'd help if the comment on this method talked a bit about the context. So, someone has decided that one of the replicas of a range needs to go, and this function orders the replicas by load?

It'd also help to comment that sl contains the replicas. Perhaps rename to replicas.

pkg/kv/kvserver/allocator_scorer.go, line 491 at r3 (raw file):

		})
	}
	if options.deterministic {

if you can, please add a comment to options.deterministic and explain what that field is about

pkg/kv/kvserver/allocator_scorer.go, line 498 at r3 (raw file):

	// We compute the converges and balance scores only in relation to stores that
	// are the top candidates for removal based on diversity (i.e. only among
	// candidates that are non-diverse relative to the rest of the replicas).

Can you expand on this comment, and spell out that, in the example below, we want 1 and 2 to be scored higher than 3 and 4? And then could you explain in prose how come the scoring will end up like that?

Another thing that would help is expanding the comments on the worst method. Right now it says something about "sharing the lowest constraint score", but I don't understand what that means.

pkg/kv/kvserver/allocator_scorer.go, line 515 at r3 (raw file):

	// likely to be picked for removal, even if one of those is on a store that is
	// better or worse than the other.
	candidates = candidates.worst()

can this be a copy() ?

pkg/kv/kvserver/store_rebalancer.go, line 209 at r2 (raw file):

}

func (sr *StoreRebalancer) rebalanceStore(

consider giving this method a comment

pkg/kv/kvserver/store_rebalancer.go, line 216 at r2 (raw file):

		qpsRebalanceThreshold: qpsRebalanceThreshold.Get(&sr.st.SV),
	}
	qpsMinThreshold := underfullQPSThreshold(options, storeList.candidateQueriesPerSecond.mean)

consider putting a comment about these thresholds - how we only look at stores over the MaxThreshold and how we only transfer leases to streos below MinThreshold (right?)

Exciting to see this!

I am curious to get your take on the backportability of the changes here.

Reviewed 2 of 2 files at r1, 7 of 7 files at r2, 2 of 2 files at r3, 7 of 7 files at r4.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @aayushshah15 and @andreimatei)

pkg/kv/kvserver/allocator_scorer.go, line 1361 at r1 (raw file):

// the mean.
func rebalanceFromConvergesScore(sl StoreList, sc roachpb.StoreCapacity) int {
	if rebalanceConvergesOnMean(sl, sc, sc.RangeCount-1) {

minor nit: I think this would be slightly easier to read and contrast with rebalanceToConvergesScore with if !rebalanceConvergesOnMean(...) { return 1 } return 0. Up to you.

pkg/kv/kvserver/allocator_scorer.go, line 184 at r2 (raw file):

		return -(2 + float64(o.convergesScore-c.convergesScore)/10.0)
	}
	if !scoresAlmostEqual(float64(c.balanceScore), float64(o.balanceScore)) {

Any reason to cast to float64 in this line and the next? It seems like we should be using int arithmetic as long as possible, like we do with convergesScore.

pkg/kv/kvserver/allocator_scorer.go, line 851 at r2 (raw file):

// NB: If the given `options` have `qpsRebalanceThreshold` set, this method
// makes its determination based on QPS. Otherwise, we fall back on using range
// count as a signal.

So we're only ever considering either QPS or range count, but not both? If so, let's be more explicit about that.

pkg/kv/kvserver/allocator_scorer.go, line 888 at r2 (raw file):

// If we reached this point, we're happy with the range where it is.

Let's add this here as well.

pkg/kv/kvserver/allocator_scorer.go, line 1347 at r2 (raw file):

//
// If the given options have qpsRebalanceThreshold set, we use that for
// computing the balanceScore.

"Otherwise ..."

pkg/kv/kvserver/allocator_scorer.go, line 1349 at r2 (raw file):

// computing the balanceScore.
//
// TODO(aayush): It would be nice to be able to compose the two dimensions of

Have we thought about what affect this PR will have if we merge it without addressing this TODO? Will we no longer make any effort to balance based on range count? Are we relying on some callers setting qpsRebalanceThreshold and others not?

pkg/kv/kvserver/allocator_scorer.go, line 1351 at r2 (raw file):

// TODO(aayush): It would be nice to be able to compose the two dimensions of
// balanceScore (QPS or RangeCount) and allow the `options` to simply specify an
// order of precedence. Callers who care about the balancing out QPS across

s/out/of/

pkg/kv/kvserver/allocator_scorer.go, line 1383 at r2 (raw file):

+1

pkg/kv/kvserver/allocator_scorer.go, line 1409 at r2 (raw file):

I'm also interested in this.

pkg/kv/kvserver/allocator_scorer.go, line 429 at r3 (raw file):

		diversityScore := diversityAllocateScore(s, existingStoreLocalities)
		balanceScore := balanceScore(candidateStores, s.Capacity, options)
		var convergesScore int

Why did we remove this? I would have expected it to use rebalanceToConvergesScore.

pkg/kv/kvserver/allocator_scorer.go, line 514 at r3 (raw file):

	// has more data constrained to it, both replicas 1 and 2 would be equally
	// likely to be picked for removal, even if one of those is on a store that is
	// better or worse than the other.

The implicit assumption here that tripped me up for a while is that, by comparing against region B and C, both replicas in region A will get a discrete balance score of moreThanMean (or overfull), and so their balance will look equivalent. If the balance score was some kind of higher-resolution proportion, then we wouldn't run into this problem, because regardless of the denominator, the replica with more QPS would get a higher score.

Do you mind weaving something about this into the comment?

pkg/kv/kvserver/allocator_scorer.go, line 515 at r3 (raw file):

Or at least a pre-allocated list.

pkg/kv/kvserver/allocator_scorer.go, line 515 at r3 (raw file):

	// likely to be picked for removal, even if one of those is on a store that is
	// better or worse than the other.
	candidates = candidates.worst()

So this means that only the worst candidates will be returned, right? So this function is no longer returning a ranked list of all stores in the input, it's returning a ranked list of the stores in the input with the worst diversity score. I think that's ok, given how the return value is used, but is that what you were expecting? Do we need to change the contract here?

pkg/kv/kvserver/allocator_scorer_test.go, line 1533 at r2 (raw file):

	}{
		{sEmpty, underfull},
		{sMean, moreThanMean},

Do we want to add a test case that results in lessThanMean?

pkg/kv/kvserver/allocator_scorer_test.go, line 1556 at r2 (raw file):

		expBalanceScore balanceStatus
	}{
		{0, 1},

Want to use your new enums here?

pkg/kv/kvserver/allocator_test.go, line 1363 at r2 (raw file):

			// We don't expect any QPS based rebalancing when all stores are serving
			// the same QPS.
			testStores: allStoresEqual,

nit: it's worth being explicit: expectRebalance: false,

pkg/kv/kvserver/allocator_test.go, line 1446 at r3 (raw file):

		{
			StoreID:  5,
			Node:     roachpb.NodeDescriptor{NodeID: 5, Locality: region("a")},

nit: any reason this is store 5 but has the same region as store 1? This tripped me up.

pkg/kv/kvserver/store_pool.go, line 657 at r4 (raw file):

}

// excludeInvalid takes a store list and removes stores that would be explicitly invalid

Want to pull this rename into a separate commit? That's probably better than having a complex change mixed in with a refactor.

pkg/kv/kvserver/store_rebalancer.go, line 209 at r4 (raw file):

// NB: The StoreRebalancer only cares about the convergence of QPS across
// stores, not the convergence of range count. So, we don't use the allocator's
// `scorerOptions` here, which set the range count rebalance threshold.

"Instead, we use our own scorerOptions, which sets the qps rebalance threshold."

pkg/kv/kvserver/store_rebalancer.go, line 400 at r4 (raw file):

		}

		if shouldNotMoveAway(ctx, replWithStats, localDesc, now, minQPS) {

Should we inline this call, now that it's not used down below?

pkg/kv/kvserver/store_rebalancer.go, line 650 at r4 (raw file):

	ctx context.Context, rbCtx rangeRebalanceContext,
) (finalVoterTargets, finalNonVoterTargets []roachpb.ReplicaDescriptor) {
	options := scorerOptions{

sr.scorerOptions()?

pkg/kv/kvserver/store_rebalancer_test.go, line 255 at r4 (raw file):

		expectedRebalancedVoters, expectedRebalancedNonVoters []roachpb.StoreID
	}{
		{

We seem to be deleting a lot of test cases. Is this because we're expecting the test coverage provided by TestChooseRangeToRebalance to be subsumed by TestChooseRangeToRebalanceRandom? I wonder if we should keep both. Randomized and table-driven tests that exercise similar logic can live side-by-side. In fact, they're a great combination. One finds new kinds of failures and one protects against regressions on known test cases.

pkg/kv/kvserver/store_rebalancer_test.go, line 391 at r4 (raw file):

	ctx context.Context, allStores, deadStores []*roachpb.StoreDescriptor, meanQPS float64,
) {
	var summary bytes.Buffer

nit: strings.Builder

pkg/kv/kvserver/store_rebalancer_test.go, line 617 at r4 (raw file):

		},
		// Two replicas are in the hot region, both on relatively heavily loaded
		// nodes. We one of those replicas to be moved to a less busy store within

"We expect one"

pkg/kv/kvserver/store_rebalancer_test.go, line 652 at r4 (raw file):

			expRebalancedVoters: []roachpb.StoreID{8, 6, 3},
			qps:                 50,
		},

Do you think it's worth adding some test cases that use constraints that look exactly like we'll generate in multi-region databases (for zone and region survival)?

Thanks a lot for working through this patch with me. I'll merge on green CI to get it in before the branch cut.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 2 stale) (waiting on @andreimatei and @nvanbenschoten)

pkg/kv/kvserver/allocator.go, line 1432 at r24 (raw file):

Makes sense. One difference between the two approaches is in the case where there are two candidates with the lowest QPS, but seems like your expression does the right thing in that scenario anyway. Done.

pkg/kv/kvserver/allocator_test.go, line 393 at r49 (raw file):

Done.

pkg/kv/kvserver/store_rebalancer.go, line 228 at r21 (raw file):

Filed: #69901

Reviewed 1 of 7 files at r51, 4 of 6 files at r61, 8 of 8 files at r62.
Reviewable status: complete! 1 of 0 LGTMs obtained (and 1 stale) (waiting on @aayushshah15 and @andreimatei)

pkg/kv/kvserver/allocator.go, line 1453 at r62 (raw file):

		leaseholderReplQPS, _ := stats.avgQPS()
		currentDelta := getQPSDelta(storeQPSMap, existing)
		bestOption := getCandidateWithMinQPS(storeQPSMap, existing)

Is the leaseholder included in existing? If so, can it be returned from bestOption? Are we just relying on the (leaseholderStoreQPS-leaseholderReplQPS) > storeQPSMap[bestOption.StoreID] evaluating to false in that case? I think that seems fine as long as leaseholderReplQPS > 0, but consider being more explicit about that. (this can be in a separate PR if you decide to do something here).