scheduler: fix quadratic performance with spread blocks

[tgross]

When the scheduler picks a node for each evaluation, the
LimitIterator provides at most 2 eligible nodes for the
MaxScoreIterator to choose from. This keeps scheduling fast while
producing acceptable results because the results are binpacked.

Jobs with a spread block (or node affinity) remove this limit in
order to produce correct spread scoring. This means that every
allocation within a job with a spread block is evaluated against
all eligible nodes. Operators of large clusters have reported that
jobs with spread blocks that are eligible on a large number of nodes
can take longer than the nack timeout to evaluate (60s). Typical
evaluations are processed in milliseconds.

In practice, it's not necessary to evaluate every eligible node for
every allocation on large clusters, because the RandomIterator at
the base of the scheduler stack produces enough variation in each pass
that the likelihood of an uneven spread is negligible. Note that
feasibility is checked before the limit, so this only impacts the
number of eligible nodes available for scoring, not the total number
of nodes.

This changeset sets the iterator limit for "large" spread block and
node affinity jobs to be equal to the number of desired
allocations. This brings an example problematic job evaluation down
from ~3min to ~10s. The included tests ensure that we have acceptable
spread results across a variety of large cluster topologies.

---

Note for reviewers: I have some additional PRs to make that'll improve our ability to debug this kind of problem in the future (ex. instrumenting the iterators, tooling for handling large snapshots), but I've intentionally kept them out of this PR so we have a clean bugfix for backporting. I'll push those PRs up over the next couple days.

[schmichael]

Great work. I wonder if we should improve our documentation too. I think this paragraph could be expanded from:

Spread criteria are treated as a soft preference by the Nomad scheduler. If no nodes match a given spread criteria, placement is still successful.

To something like:

Spread criteria are treated as a soft preference by the Nomad scheduler. If no nodes match a given spread criteria, placement is still successful. To avoid scoring every node for every placement, allocations may not be perfectly spread. Spread works best on attributes with similar number of nodes: identically configured racks or similarly configured datacenters.

If anyone needs absolute precision with spread we could make the timeout for evaluations configurable. Given the high concurrency of scheduling workers, operators may tolerate a small number of very slow (eg 5 minute) evaluations.

[tgross]

I've picked up your suggestions and added the docs change. I've adjusted the test so that it's a bit less strict (effectively allowing for [0, 1, 2] which we need for the large rack counts) and produces more readable error outputs.

I've also added a note to the change in stack.go that notes that the limit value was empirically determined so that future developers will know there's nothing magical about 100 so they can feel free to adjust in the future if the scheduler changes significantly.

[github-actions]

I'm going to lock this pull request because it has been closed for 120 days ⏳. This helps our maintainers find and focus on the active contributions.
If you have found a problem that seems related to this change, please open a new issue and complete the issue template so we can capture all the details necessary to investigate further.