kvserver: StoreRebalancer is not constraints-aware when comparing stores’ QPS

[aayushshah15]

Load based range rebalancing in CRDB happens at the store level (StoreRebalancer, which rebalances based on QPS) as well as at the per-range level (replicateQueue, which rebalances based on range count). In broad strokes, at the per-range level, we do the following:

1. For each of the current stores that have a replica for the range, we compute a list of “comparable” stores — these are stores that meet the replication constraints or are identical to the existing store in terms of their locality.
2. We compute capacity statistics for each of these comparable subsets of stores.
3. If the existing store is “overfull” relative to its subset of comparable stores, we try to transfer the existing replica away. Likewise, if any other store is “underfull” relative to the subset, we also try to relinquish our replica and move it to such an underfull store.

In contrast to this, in the StoreRebalancer, we simply fetch the list of all stores in the cluster and compute QPS-based statistics across this entire set.

To see the hazard with this, consider a scenario where we have 5 regions with 3 stores each, but all tables are constrained to, say, some single region A. This will very likely result in all the 3 stores in region A fielding higher QPS than the cluster average.

In such a scenario, the coarseness of StoreRebalancer essentially de-activates it because it computes the QPS average across the entire set of stores in the cluster. The StoreRebalancer will not try to achieve balance across the 3 stores that satisfy constraints, but rather across the entire cluster. It will try to rebalance a replica away from these 3 stores but fail because all the other, underfull, stores violate constraints.

This means that the hottest ranges in the system will not be actively rebalanced away based on QPS.
cc @nvanbenschoten

gz#7724

Epic CRDB-6437

[aayushshah15]

This came up in a customer call where they had heterogenous load profiles across the different regions in their cluster -- some regions experiencing a lot more traffic than others. Due to the hazard described above, they were seeing vastly different QPS on stores even within the same region.

I think we can fix this fairly non-invasively by filtering the list of stores the StoreRebalancer computes its QPS average off of.

[awoods187]

Linked to https://cockroachdb.zendesk.com/agent/tickets/7724

[awoods187]

@nvanbenschoten can PTAL when you return?

[nvanbenschoten]

@aayushshah15 thanks for writing this up and discussing it today.

I think we can fix this fairly non-invasively by filtering the list of stores the StoreRebalancer computes its QPS average off of.

Where are you suggesting that we perform the filtering? On a per-range basis in chooseLeaseToTransfer and chooseReplicaToRebalance? It seems to me that we would need to invert some of the control flow in these functions if we start considering different sets of candidates for different ranges. For instance, would qpsMinThreshold and qpsMaxThreshold, which are both functions of the unfiltered storeList, need to be computed per range?

You mentioned that a form of per-range qps rebalancing was recently removed. Do you have a reference to that?

Also, is this issue saying the same thing as #31135?

[aayushshah15]

Where are you suggesting that we perform the filtering?

What you said is pretty much what I had in mind. Do you see anything wrong with it that I may have missed?

You mentioned that a form of per-range qps rebalancing was recently removed

I must have misspoken, I meant "not very recently". It looks like 8e3dad8 removed it. We seem to have made a decision to always just rely on StoreRebalancer for QPS-based rebalancing.

Also, is this issue saying the same thing as #31135?

That issue seems to be talking about a slightly different problem. It's talking about cases where some overfull store has multiple super-hot ranges that the StoreRebalancer cannot move to any other store -- because they will cause every receiving store to also be overfull. Consider something like:

The values in the curly braces indicate ranges' QPS on each of the stores:

store 1: {100, 80, 20} 
store 2: {60}
store 3: {40} 
----

avg QPS = 100
overfull threshold = 105

The ideal placement of ranges here would be something like the following, but the StoreRebalancer will not try to do this.

store 1: {80, 20}
store 2: {60}
store 3: {100, 40}

[blathers-crl]

Hi @nvanbenschoten, please add branch-* labels to identify which branch(es) this release-blocker affects.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

[blathers-crl]

Hi @nvanbenschoten, please add branch-* labels to identify which branch(es) this release-blocker affects.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}