Architecture change for IO

[mratsim]

As of 0.2, the repo is a 1-1 copy of Constantine's threadpool: https://github.com/mratsim/constantine/tree/master/constantine/threadpool

That threadpool is optimized for compute tasks, i.e. tuned for throughput.

As explained in "Multithreading flavors: choosing the right scheduler for the right job", IO is a completely different beast and the scheduler should be tuned for task fairness and latency.

In short, tasks should be processed in a roughly first-in first-out basis at the very least, or with time budget/quotas or even priority support.

This outlines the steps needed to modify Weave-IO 0.2 to achieve this:

• The thread-local taskqueue https://github.com/mratsim/weave-io/blob/v0.2.0/weave_io/crossthread/taskqueues.nim
  should be changed from LIFO to FIFO. Also, IO tasks tend to be small in scope so implementing steal-half is likely necessary.

  • For additional throughput, a slot can be kept for latest enqueued task, which will be hot in cache
  • This is also helpful for message-passing patterns, to optimize them.
  • See go presentation: https://2019.hydraconf.com/2019/talks/7336ginp0kke7n4yxxjvld/
    • direct video: https://www.youtube.com/watch?v=-K11rY57K7k
    • direct slides: https://assets.ctfassets.net/oxjq45e8ilak/48lwQdnyDJr2O64KUsUB5V/5d8343da0119045c4b26eb65a83e786f/100545_516729073_DMITRII_VIUKOV_Go_scheduler_Implementing_language_with_lightweight_concurrency.pdf

• A global taskqueue is necessary so that threads from outside the runtime can enqueue new tasks easily.
  The global taskqueue can be MPSC with the producer side being any thread, and the consumer side being protected by a lock, rarely taken, when all the thread-local queues are empty.

  • For fairness, workers can regularly pick a task from that queue.
  • This queue can serve as an overflow queue for thread-local taskqueue, meaning, if it helps, taskqueues can be fixed size.
  • The MPSC queue can be based on Weave's queue which is unbounded and supports batch enqueue/dequeue: https://github.com/mratsim/weave/blob/b6255af/weave/cross_thread_com/channels_mpsc_unbounded_batch.nim

  An alternative would be to randomly pick a worker, but then we need an unbounded queue. This is the approach used in Weave with submit: Weave as a background service weave#136 but the setupSubmitterThread(Weave) ceremony feels a bit icky.

• Events / Precise task dependencies
  Those can reuse Weave FlowEvents which are executor agnostic: https://github.com/mratsim/weave/blob/b6255af/weave/cross_thread_com/flow_events.nim

Architectural open problems:

• Blocking threads:
  Unlike Go, it is unrealistic to support preemption https://github.com/golang/proposal/blob/master/design/24543-non-cooperative-preemption.md. Dealing with signals on all OS AND not interfering with Go signals or Java signals seem like an uphill battle. Some threads might be blocked for user input (for example reading for stdin) or long compute that cannot be preempted. In that case we need either a declarative spawnBlocking solution where users tag a blocking call or a solution where we create a new thread after some threshold of a blocked call.
  When too many threads are active, the extra ones can be parked.
• Integration with async runtimes
  yasync (https://github.com/yglukhov/yasync) is executor agnostic, and also in-line with my own vision of separating async/await transformation from scheduling it (see https://github.com/mratsim/weave-io-research/blob/master/design/design_2_continuations.md ) and so should probably be first try.
  We should also support Asynchronous thread notification mechanism. status-im/nim-chronos#406 which is how Chronos integrates with nim-taskpools.
• Actors
  To Be Described
• Cancellation
  Cancellation is hard, To Be Described, see background: https://gist.github.com/Matthias247/ffc0f189742abf6aa41a226fe07398a8
• AsyncStreams
  To Be Described