cockroachdb / cockroachdb/cockroach
allocator: overfull threshold should be constraint-aware
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
Both the single-metric allocator (SMA) and the multi-metric allocator (MMA)
determine whether a store is "overloaded" by comparing its load against a
threshold derived from cluster-wide means. This threshold can be significantly
diluted by stores that are not viable targets for the ranges hosted on the store
being evaluated. When this happens, all viable stores can appear permanently
overloaded, causing the store rebalancer to enter shedding mode every tick even
when load is perfectly balanced among the stores that matter.
The SMA is worse off here: it will actively thrash leases between overloaded
stores (see #162590 for details). MMA has guardrails ("target must not be
overloaded", "transfer must not make target worse") that prevent fruitless
transfers, but the root cause is the same: the store still *thinks* it's
overloaded and enters shedding mode every tick, just to find no viable
candidates.
This is a general problem that arises whenever constraints cause constraint-group
means to diverge significantly from cluster-wide means.
**Example: SQL gateway topology**
An extreme but real-world instance is a topology with SQL-only (gateway) nodes
alongside KV nodes. Gateway nodes don't hold range data, so their stores report
~0 load.
* 100 SQL-only nodes (no range data, ~0 load)
* 50 KV nodes, each at ~0.5 cores of load
* Cluster-wide mean: `(50 * 0.5) / 150 = 0.16 cores`
* Load-based overfull threshold (at default 10%): `0.16 * 1.10 = 0.18 cores`
* Actual load on each KV node: `0.5 cores`, well above the threshold
Even though load is perfectly balanced across the 50 KV nodes, they all appear
overfull. The gateway nodes don't need to outnumber the KV nodes for this to
happen -- any significant number of idle stores can drag the mean down enough
that the 10% threshold is exceeded by all KV nodes.
**Other examples**
The same problem can occur in any deployment where zone configs, lease
preferences, or locality constraints partition the set of stores into groups with
materially different load profiles. For instance:
- Ranges constrained to a specific region (e.g. `+region=us-east`) are compared
against a mean that also includes stores in `us-west` that are lightly loaded
because most traffic is US-East-constrained.
- Ranges with lease preferences that pin leases to a subset of stores, inflating
the mean from the perspective of that subset.
**Observed behavior**
When every KV node exceeds the overfull threshold, the store rebalancer enters
shedding mode every tick. With SMA, this leads to active thrashing of small
unconstrained leases (like the liveness range) between KV nodes. With MMA, the
shedding attempts fail harmlessly but still represent wasted work on every tick.
## Proposed Fix
Lift constraint awareness into the overload check. A store should be considered
overloaded (on any dimension) relative to "fungible" stores -- stores that could
plausibly take on its load -- rather than relative to the full cluster.
A rough sketch:
1. **Group ranges by their effective constraints.** This includes zone config
constraints, lease preferences, and voter constraints. Ranges that share the
same set of constraints form an equivalence class.
2. **For equivalence classes with significant cumulative weight,** partition the
set of stores into candidate groups relative to those range groups. That is,
for each high-weight constraint class, find the set of stores that could
(according to constraints) replace the current store for those ranges.
3. **Compute means relative to those candidate stores only.** The overfull
threshold for a store should be the max of the thresholds across all
constraint classes it participates in, rather than a single cluster-wide
threshold.
This is conceptually straightforward but defining "fungible" precisely is tricky:
- The equivalence classes aren't necessarily disjoint (a store can be a candidate
for multiple constraint classes), and constraint evaluation itself is not free.
An approximation that covers the common cases (e.g. weighting only by the
dominant 1-3 constraint classes by load) may be sufficient.
- Each store only knows the per-range load for ranges it holds the lease for. To
group ranges by constraints and weight those groups, the store would need load
information for ranges whose leases are elsewhere. This information isn't
readily available today; an approximation (e.g. using the store's own
leaseholder ranges as a representative sample, or aggregating constraint-class
weights from gossip/store descriptors) would likely be necessary.
**See also**
https://github.com/cockroachdb/cockroach/issues/162590#issuecomment-3885467490 outlines some other use cases where constraints are used to pin non-voters voters to nodes that are likely to run into this issue as well.
x-ref #162590
x-ref https://github.com/cockroachlabs/support/issues/3544
Epic CRDB-66473
Jira issue: CRDB-60295
Contributor guide
Assessment
This issue has not been assessed yet.