rt: add rng_seed option to runtime::Builder

[hds]

Motivation

In certain circumstances (e.g. running tests with loom), it may be desirable
to have deterministic behavior when running tokio.

Partly this may be achieved by seeding the random number generator used
by the tokio::select! macro.

This PR is more a proof of concept that a real proposed change, it needs work
before it could be merged.

Refs: #4879

Open Questions

There are a number of open questions (or rather things that I need help with):

• Currently we seed all threads with the same value. This is important because
  when using a multi-threaded runtime, the thread that a task will be scheduled
  on is not deterministic. Is this acceptable?
• Answer: Threads are now each seeded with a value generated by a seed generator.
  This makes the values deterministic, but not the same.
• Is there a way to make the thread that a task is run on deterministic?
• Answer: This is outside the scope of this change.
• The API provided takes a u64 as a seed. This is not very flexible, but avoids
  the need to hash or otherwise reduce some other value to a u64 to seed the
  actual RNG. This was done deliberately, because it's the easiest thing to change
  in this PR before merging. Opinions?
• Answer: Changed the value to an opaque RngSeed type which can be constructed
  from a byte slice.
• Starting multiple runtimes from a single thread will overwrite the RNG seed. This
  feels ugly to me, but I don't see a better way without sacrificing performance by,
  e.g. making the RNG global. Suggestions?
• Answer: The Handle::enter pattern is used to set the seed when a runtime is entered
  from a thread, when the thread leaves the runtime, the previous thread local value is
  restored.

Solution

The tokio::select! macro polls branches in a random order. While this
is desirable in production, for testing purposes a more deterministic
approach can be useul.

This change adds an additional parameter to the runtime Builder to set
the random number generator seed. This value is then used to reset the
seed on the current thread when the runtime is entered into (restoring the
previous value when the thread leaves the runtime). All threads created
explicitly by the runtime also have a seed set as the runtime is built. Each
thread is set with a seed from a deterministic sequence.

This guarantees that calls to the tokio::select! macro which are
performed in the same order on the same thread will poll branches in the
same order.

Both the builder parameter as well as the RngSeed struct are marked
unstable initially.

[carllerche]

Thanks for taking this on! I will look shortly, but first I will answer some of the questions.

Currently we seed all threads with the same value. This is important because
when using a multi-threaded runtime, the thread that a task will be scheduled
on is not deterministic. Is this acceptable?

We probably don't want to do this as it will make the order of rands identical on each thread. What we can do is use the seed for a "seed random generator" and use that to generate a per-thread seed.

Pseudo code:

let seed_rng = Rng::new(seed_from_builder);

for _ in thread_to_spawn.iter() {
    let thread_seed = seed.rng.next_seed();
   spawn_thread_with_seed(thread_seed);
}
```

Hopefully, this makes some sense.

> Is there a way to make the thread that a task is run on deterministic?

Not entirely, but this is out of scope. For the use cases in question, they control enough to make sure it is deterministic. In theory, if you use the current_thread scheduler and strickly control I/O and other input, you can make it deterministic. Even better is to mock out I/O.

[carllerche]

The API provided takes a u64 as a seed. This is not very flexible, but avoids
the need to hash or otherwise reduce some other value to a u64 to seed the
actual RNG. This was done deliberately, because it's the easiest thing to change
in this PR before merging. Opinions?

Hmm, I don't think we want to expose u64 there as each rng algorithm has a different seed format. I am not sure what we do want to expose yet, but what we can do is start by flagging this setting as tokio_unstable and punt :). My guess is we will want to define an opaque type RngSeed or something and conversions to it.

[carllerche]

Starting multiple runtimes from a single thread will overwrite the RNG seed. This
feels ugly to me, but I don't see a better way without sacrificing performance by,
e.g. making the RNG global. Suggestions?

Can you use the Handle::enter pattern here? When one "enters" a runtime, the rng is set in the thread local. Any prior rng is stored and replaced when the enter guard drops.

[hds]

OK, that was a fun rabbit hole I ended up running down following the Handle:enter pattern. Thanks for that. (-;

We now have a public RngSeed which can be created from a byte slice, and also a RngSeedGenerator which is stored on the runtime handle and the spawner for the BlockingPool in order to seed the RNG for the runtime and the blocking threads respectively.

For the runtime, we do set the seed when entering the runtime and keep the old seed in the EnterGuard (not sure how happy everyone is to extend the size and functionality of that struct). When the guard is dropped we reset the RNG back to the state it had prior to entering the runtime. Because the runtime may be accessed in parallel from multiple threads, we make no attempt to update its handle with the state of local RNG upon dropping the enter guard. Instead, each time a thread "enters" a runtime, the next seed from the seed generator is used. This should provide the necessary deterministic behavior, although there are caveats such as that calling select! twice within a single call to block_on is not equivalent to calling select! within two sequential calls to block_on.

Some questions:

• Do we want to make this API unstable initially (perhaps not a bad idea)?
• Should this functionality be dependent on the macros feature (the only place its being used currently - this affects how I fix the failing CI jobs)?
• Do we want to extend the deterministic seeding to the RNG used to pick a random neighbor worker to steal work from (would not be a big change)?

[hds]

@carllerche I think I've covered everything in your comments and added the necessary documentation, so this PR is ready for review again when you've got a moment.

[carllerche]

I skimmed it, and it looks fine to me. I would suggest keeping the new APIs as unstable initially as we let consumers try out the API. To do this, I would just make the public APIs unstable, the implementation can stay as it is.

[hds]

I've made the new API unstable, now just waiting to see whether I've got the right visibility everywhere to satisfy clippy on stable and unstable builds.

[carllerche]

Is this ready to go? It looks like there are a few merge conflicts now.

[hds]

Yep, it's ready to go once approved (and now once I fix the merge conflicts). I'll try to merge master in it this afternoon.

[carllerche]

LGTM, a couple of suggestions that you can apply if you want.