rt: reduce no-op wakeups in the multi-threaded scheduler

[carllerche]

This PR reduces the number of times worker threads wake up without having work to do in the multi-threaded scheduler. Unnecessary wake-ups are expensive and slow down the scheduler. I have observed this change reduce no-op wakes by up to 50%.

The multi-threaded scheduler is work-stealing. When a worker has tasks to process, and other workers are idle (parked), these idle workers must be unparked so that they can steal work from the busy worker. However, unparking threads is expensive, so there is an optimization that avoids unparking a worker if there already exists workers in a "searching" state (the worker is unparked and looking for work). This works pretty well, but transitioning from 1 "searching" worker to 0 searching workers introduces a race condition where a thread unpark can be lost:

• thread 1: last searching worker about to exit searching state
• thread 2: needs to unpark a thread, but skip because there is a searching worker.
• thread 1: exits searching state w/o seeing thread 2's work.

Because this should be a rare condition, Tokio solves this by always unparking a new worker when the current worker:

• is the last searching worker
• is transitioning out of searching
• has work to process.

When the newly unparked worker wakes, if the race condition described above happened, "thread 2"'s work will be found. Otherwise, it will just go back to sleep.

Now we come to the issue at hand. A bug incorrectly set a worker to "searching" when the I/O driver unparked the thread. In a situation where the scheduler was only partially under load and is able to operate with 1 active worker, the I/O driver would unpark the thread when new I/O events are received, incorrectly transition it to "searching", find new work generated by inbound I/O events, incorrectly transition itself from the last searcher -> no searchers, and unpark a new thread. This new thread would wake, find no work and go back to sleep.

Note that, when the scheduler is fully saturated, this change will make no impact as most workers are always unparked and the optimization to avoid unparking threads described at the top applies.

Benchmarks

Hyper

This benches Hyper's "hello" server using wrk -t1 -c400 -d10s http://127.0.0.1:3000/

master

Requests/sec: 118495.92
Transfer/sec: 9.94MB

this PR

Requests/sec: 135261.99
Transfer/sec: 11.35MB

mini-redis

This benches mini-redis using redis-benchmark -c 5 -t get,set

master

====== SET ======
  100000 requests completed in 1.03 seconds
  5 parallel clients
  3 bytes payload
  keep alive: 1
  multi-thread: no

99.17% <= 0.1 milliseconds
99.82% <= 0.2 milliseconds
99.92% <= 0.3 milliseconds
99.98% <= 0.4 milliseconds
99.99% <= 0.5 milliseconds
100.00% <= 0.6 milliseconds
96711.80 requests per second

====== GET ======
  100000 requests completed in 1.03 seconds
  5 parallel clients
  3 bytes payload
  keep alive: 1
  multi-thread: no

99.68% <= 0.1 milliseconds
99.82% <= 0.2 milliseconds
99.93% <= 0.3 milliseconds
99.98% <= 0.4 milliseconds
100.00% <= 0.5 milliseconds
100.00% <= 0.7 milliseconds
100.00% <= 0.7 milliseconds
97370.98 requests per second

this PR

====== SET ======
  100000 requests completed in 0.83 seconds
  5 parallel clients
  3 bytes payload
  keep alive: 1
  multi-thread: no

99.11% <= 0.1 milliseconds
99.72% <= 0.2 milliseconds
99.92% <= 0.3 milliseconds
99.98% <= 0.4 milliseconds
100.00% <= 0.5 milliseconds
100.00% <= 0.6 milliseconds
120627.27 requests per second

====== GET ======
  100000 requests completed in 0.81 seconds
  5 parallel clients
  3 bytes payload
  keep alive: 1
  multi-thread: no

99.72% <= 0.1 milliseconds
99.85% <= 0.2 milliseconds
99.89% <= 0.3 milliseconds
99.97% <= 0.4 milliseconds
100.00% <= 0.5 milliseconds
100.00% <= 0.5 milliseconds
123152.71 requests per second

[carllerche]

This is the key bit. When the worker wakes, it only enters the "searching" state if it was unparked by another thread. This distinguishes unparks from other threads to signal to the worker that it should steal work vs. the I/O driver unparked the thread because events arrived.

[hawkw]

it might be worth having a comment in the code explaining that? not a hard blocker though.

[carllerche]

done

[carllerche]

@Darksonn @hawkw this should be ready for review, it would be nice to have it confirmed in a "real app" too.

[blt]

@Darksonn @hawkw this should be ready for review, it would be nice to have it confirmed in a "real app" too.

I'm planning on wiring this up into vector and running it through our integrated benchmarks. Assuming all goes well I'll link numbers here in a handful of hours.

[hawkw]

This looks good to me --- the actual change is pretty simple and makes sense based on the explanation in the PR description.

It might be nice to add a bit to the comments in this code explaining this behavior, but that's not a hard blocker.

I'd like to test this out in Linkerd today or tomorrow, I'll post benchmark results if I get a chance to do that!

[hawkw]

it might be worth having a comment in the code explaining that? not a hard blocker though.

[blt]

No change in observed vector throughput, per these results. That said, we don't track CPU use in our experimental setup and the observation duration in a PR is constrained to 200 seconds to make turn-around time feasible.

[carllerche]

@blt thanks for checking. It would be interesting to know the CPU load as that would let us know if it falls within the scope of this change. If you are saturating all workers in your tests, then there would be no visible improvement as it only applies when only a few workers are actually kept busy.

[blt]

Unfortunately we don't capture that kind of saturation information yet, though we do have an issue for it: vectordotdev/vector#10456. That said, we're intending to fully saturate vector so it's reasonable to believe there's little idle time.