allocator: voter constraint never satisfied when there are a correct number of replicas and all existing replicas are necessary

[kvoli]

Describe the problem

When there are the correct number of voters/non-voters and all existing replicas are necessarily satisfying some constraint, the allocator may not satisfy any remaining constraints - even though it should.

Consider the example from #98020

Node Localities

# region -> node_id
eu-west-1
  └── [8 9 10]
us-central-1
  └── [5 6 7]
us-east-1
  └── [1 2]
us-west-1
  └── [3 4]

Span config:

num_replicas=6 
num_voters=5 
constraints={'+region=eu-west-1':1,'+region=us-central-1':1,'+region=us-east-1':1,'+region=us-west-1':1} 
voter_constraints={'+region=us-west-1':2,'+region=us-east-1':2}

Existing replicas:

voters=[n1,n2,n4,n5,n8]
non_voters=[n3]

There are the correct number of voters/replicas. All existing replicas are necessary (from allocators perspective) to satisfy the existing constraints—including the non-voter on n3.

n3 should be promoted to a voter, then either n5 (us-central-1) or n8 (eu-west-1) should be demoted to a non-voter. i.e., a rebalance with a promotion and demotion.

However this will never occur, as we get stuck on:

cockroach/pkg/kv/kvserver/allocator/allocatorimpl/allocator_scorer.go

Lines 1644 to 1648 in 5e6cc9e

	if !cand.less(existing) {
	// If `cand` is not worse than `existing`, add it to the list.
	comparableCands = append(comparableCands, cand)
	if !needRebalanceFrom && !needRebalanceTo && existing.less(cand) {

Which checks if the existing replica (necessary=true) is less than the replacement (necessary=true). If the replacement candidate inputs (diversity score) is not greater than the existing, we will never rebalance to satisfy the constraint.

To Reproduce

#106548 reproduces the no rebalance target behavior. Reproduction using the simulator and more directly when calling Allocator.Rebalance(Non)Voter.

Expected behavior

Rebalance action returned with a promotion and demotion.

Environment:
Reproduces on master. Assume all versions affected.

Jira issue: CRDB-29615

[kvoli]

I wonder if this would work with a normalized span config, where num_replicas=sum(num_replicas) in the constraints.

[kvoli]

I can't see how this issue is easily fixed. When there are the correct voters and replicas, considerRebalance is used to fix constraint unsatisfaction.

This case does not work because the voter we should demote is satisfying an all replica constraint conjunction. The rebalance code assumes the rebalance-from store will be removed entirely, so an all-replica constraint will no longer be satisfied.

We could hack in a check for this specific case when rebalancing voters, allowing the voter to be removed - which then triggers up-replication to add a non-voter. This is wasteful, we could instead demote the existing voter and promote the existing non-voter, incurring 0 snapshots.

Ideally, something like the roleSwap in allocator2 would be preferable:

cockroach/pkg/kv/kvserver/allocator/allocator2/constraint.go

Lines 1239 to 1252 in 5e6cc9e

	// Constraint unsatisfaction can happen if constraints or store attributes
	// changed. The presence of two sets of constraints-conjunctions (CCs),
	// complicates matters. Consider CC's A, B, C, that constrain all replicas and
	// require 2 replicas each. And consider CC's A', B', C' that constrain voters
	// and require 1 replica each. And assume that A' permits the same set as A,
	// ... (not that we know that in the code). The current state is 2 non-voters
	// in A, 1 voter and 1 non-voter in B, and 2 voters in C. We can't find
	// anything unsatisfied in the regular constraints. But have an unsatisfied
	// (and oversatisfied) voter constraint. We can decide to satisfy A' and
	// remove a voter from C'. But removing a replica from C' will also unsatisfy
	// C. What this requires is switching a voter in C to non-voter and switching
	// a non-voter in A' to voter.
	// REQUIRES: !notEnoughVoters() && !notEnoughNonVoters()
	func (rac *rangeAnalyzedConstraints) candidatesForRoleSwapForConstraints() (

It would also be preferable to create an AllocatorAction for this situation, so that rebalancing isn't depended on for constraint satisfaction #90110.

[kvoli]

A simpler reproduction:

https://github.com/cockroachdb/cockroach/blob/3eafc8d757c9301a85e8da50e96fd0f0f027c5d0/pkg/kv/kvserver/allocator/allocatorimpl/allocator_test.go#L8288-L8313