Task, Timer, I/O stealing and pathological starvation

[armanbilge]

As of CE 3.6, the WorkStealingThreadPool is a fully-integrated runtime, where tasks, timers, and I/O are scheduled locally on the WorkerThread where they were created. By doing so, we avoid a great deal of context switches and synchronization and overall have better cache utilization. Unfortunately, this optimization leaves us vulnerable to pathological starvation: if a WorkerThread gets stuck on some long-running task (e.g. CPU bound or a rogue blocking op) then it cannot run its other tasks, or trigger its timers, or poll for I/O.

One possible mitigation for this sort of starvation is stealing, which we've currently implemented for tasks and timers. It empowers threads to steal tasks and timers from another thread that may be starving in that moment. However, currently a thread will only attempt to steal if it has no work of its own. This means that under load, when all threads are fully occupied with their own work, there are no threads available to rescue tasks and timers from a starving thread. Also, threads will only attempt to steal expired timers before giving up, but a starved thread may need help with its unexpired timers in the near future.

To properly mitigate against starvation, threads would need to make deliberate attempts to steal from other threads even when they already have their own work. Furthermore, unnecessarily moving work across threads is not ideal, so I imagine a WorkerThread should keep some timestamp of its last iteration through its runloop that can be used by other threads to determine if it is starving or not and thus whether its work should be aggressively stolen.

There's also the problem that implementing I/O stealing is non-trivial and generally will require some form of locking, which we want to avoid as it undermines the aforementioned optimizations. So it's possible that I/O is fundamentally vulnerable to pathological starvation and it begs the question whether it is worth working so hard to create mitigations for tasks and timers when we cannot solve the problem in general.

[durban]

I'm still thinking this through, but a few comments:

• I think the main question (do we want to mitigate against starvation) can go either way: either we say, that even in case of pathological behavior, we try to do our best; or we say that if a task is not well-behaved, we allow it to starve others. I like the first option more.
• For tasks and timers, fixing starvation should be "easy": in the WorkerThread loop we periodically try to steal (like currently for the external queue).
• It's not clear to me, what happens to an "I/O task", if the WorkerThread gets into an infinite loop? Looking at https://github.com/armanbilge/fs2-io_uring, it seems to me that the I/O operations are IOConts. Wouldn't they be stealed by other WorkerThreads? (I probably still don't really understand polling systems...)

[armanbilge]

it seems to me that the I/O operations are IOConts. Wouldn't they be stealed by other by other WorkerThreads?

Timers are also essentially IOCont's. Does that mean they are stolen? :)

BTW, it might be helpful to study the SelectorSystem, it's quite a bit simpler than the io_uring stuff.

cats-effect/core/jvm/src/main/scala/cats/effect/unsafe/SelectorSystem.scala

Line 27 in 04cc47b

final class SelectorSystem private (provider: SelectorProvider) extends PollingSystem {

I/O polling is really quite similar to timers. You put the callback into a threadlocal datastructure (for timers, the heap), so the callback will only resurface in the same datastructure that you originally put it in. Unless you have a threadsafe way for other workers to interact with that datastructure (easier when it is a heap you implemented yourself, very difficult when it is a kernel structure like epoll, kqueue, io_uring) then only the owner worker thread is able to interact with that structure.

Does that make sense?

[durban]

Yes, thank you, it makes much more sense now 👍

[armanbilge]

• For tasks and timers, fixing starvation should be "easy": in the WorkerThread loop we periodically try to steal (like currently for the external queue).

I don't think that's sufficient. I think we would also need to change the behavior of sleeping WorkerThreads to periodically wake up and check that active WorkerThreads are not starving.

[durban]

Yeah. (First I thought that it's enough to be really careful before going to sleep, but due to expiring timers it is not. Although, before sleeping, we could check all timers... I'm not sure if that's enough.)

[armanbilge]

There's also the problem that implementing I/O stealing is non-trivial and generally will require some form of locking, which we want to avoid as it undermines the aforementioned optimizations. So it's possible that I/O is fundamentally vulnerable to pathological starvation and it begs the question whether it is worth working so hard to create mitigations for tasks and timers when we cannot solve the problem in general.

I've been thinking about this and I am fairly confident that we can implement I/O stealing for io_uring without locking. io_uring is special in this regard because we can directly read completion queue events from memory without needing to make any syscalls.

[He-Pin]

The current implementation will generating unexpected results if you using the timer to generate lock step frames, that's why I use a dedicated HashWheelTimer for this

[djspiewak]

I have some thoughts on this. Going to fork off into a separate discussion since I think it's philosophically interesting in its own right, but the bottom line is that starvation mitigation is best-effort; we'll take what we can get, and we won't intentionally create suboptimal behavior, but we also won't compromise on the primary purpose. The primary purpose of stealing is balancing load across available workers to improve throughput.

[durban]

So that means #3781 is a go, right? I guess I'm fine with that. It's an illusion anyway to think that we can guarantee anything. If a user is determined enough, they can definitely make everything hang...

[djspiewak]

It is indeed a go! I think this is actually a great example of striking precisely the right set of tradeoffs.

If a user is determined enough, they can definitely make everything hang

Absolutely. And that's really the essence of the userspace scheduler tradeoff; no point in fighting it.