Tokio Gives Progress, Not Ordering: Scheduling 1M Tasks

jandrewrogers

I think everyone learns these lessons the hard way. I know I did. 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.

excerionsforte

You learn very early that Tokio doesn't order, ordering is one of the enemies of high performance. Roll your own solution or use a third party solution, pay the tax, but you get what you expect. 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.