scheduler: seed random shuffle of nodes with eval ID

[tgross]

Processing an evaluation is nearly a pure function over the state
snapshot, but we randomly shuffle the nodes. This means that
developers can't take a given state snapshot and pass an evaluation
through it and be guaranteed the same plan results.

But the evaluation ID is already random, so if we use this as the seed
for shuffling the nodes we can greatly reduce the sources of
non-determinism. Unfortunately golang map iteration uses a global
source of randomness and not a goroutine-local one, but arguably
if the scheduler behavior is impacted by this, that's a bug in the
iteration.

---

Reviewers: I've grabbed a random set of folks to look at this but maybe consider this mostly a "working proposal". I'm not certain there aren't side-effects I haven't considered here. But this could have been useful while debugging a large customer's incident recently.

[schmichael]

Oops, forgot to mention a test that asserts shuffleNodes is stable would be nice.

[motobrowning]

Ok

[tgross]

Oops, forgot to mention a test that asserts shuffleNodes is stable would be nice.

Good call.

[schmichael]

I can't believe how many words I'm writing about we need a nonce 😅, however I think there are some subtle pros and cons to this approach:

tl;dr This allows writing reproducible tests against deterministic state stores which is the main improvement we're looking for!

Pros:

1. Subsequent scheduling attempts of the same eval will be shuffled differently! This accomplishes that goal perfectly. 🎉
2. Test cases with deterministic state store updates will make shuffle nodes deterministically.

Cons:

1. When trying to reproduce scheduling behavior from a user's snapshot, the LatestIndex() will be the snapshot's index. The snapshot was likely taken long (in Raft index terms (pun not intended)) after when the scheduling attempt we wish to reproduce was made. Obviously in cases like this the entire state snapshot is likely divergent from the case we wish to inspect, so we can only reduce non-determinism, not remove it. I'm unsure how much value there is in reducing non-determinism in this case.
2. Workers only ever enforce the snapshots are >= a Raft index (Eval.WaitIndex initially, the RefreshIndex on subsequent attempts). Whether the index is == (reproducible shuffle!) or > (oh no) is entirely dependent on races between the Raft/fsm and scheduling subsystems. Even if the indexes are only off-by-1 the nodes will be shuffled completely differently.

[tgross]

Given that the primary use case for this is to make it so that we can have deterministic tests, maybe the right way to deal with this is to just have the index used for the shuffle get logged somewhere. That way we can feed that index to the shuffle function as part of tests?

[schmichael]

Yeah that or the retry # option.

Although I don't think there's a rush as this should work for those tests where we either bypass raft and manually insert objects into the state store or we load a snapshot into an otherwise inactive server and perform some scheduling attempts.

[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.