Tokio Gives Progress, Not Ordering: Scheduling 1M Tasks

The difficulty of designing robust schedulers in real systems comes from the confluence of two properties: a theoretically optimal schedule guarantees no bound on task latency and runtime scheduling is AI-complete.

In practice, we need latencies to be bounded, often tightly. The scheduler implementation must operate within a limited memory and compute budget, which is not a property of anything that requires "AI-complete" algorithms -- best you can do is extremely narrow and very loose approximations.

Because of these constraints, any general purpose scheduler will be brittle or have poor efficiency (typically both). At the same time, designing a bespoke implementation-specific scheduler is exceedingly non-trivial for all but the simplest applications. Closest simple examples with literature are cache replacement algorithms, which are a very narrow case of scheduling where unbounded latency is not a problem.

Solving these kinds of design problems has historically fallen under the rubric of "latency-hiding" (e.g. in HPC). There is vanishingly little literature for software and hardware has many constraints and properties that don't apply to software.

We could solve this with a crate that rate-limits new tasks based on heap usage.

We could build this into the runtime and make it apply to all task spawns. That could be problematic since any spawn could block.

It would probably be better to make it opt-in and less granular, releasing groups of tasks at a time.

futures_orchestra (https://crates.io/crates/futures_orchestra) handles the problem of limiting concurrency, queuing and ordering. I think I'm underselling it really, haha.