Tokio Gives Progress, Not Ordering: Scheduling 1M Tasks | Hacker News Reader

Tokio Gives Progress, Not Ordering: Scheduling 1M Tasks

pranitha.dev

60 pointspranitha_m9 comments

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.

First time I heard about "AI-complete" and you mentioned it twice here.

Same, and it led me discover there was already a wikipedia article about it: https://en.wikipedia.org/wiki/AI-complete

Shouldn't it just be I-complete? Humans can obviously solve these tasks too

The concept has not always had this name, that is more recent branding. ~25 years ago it was formalized by a proof that optimal generalized learning is a universal sequence prediction problem. An unfortunate property of universal sequence prediction problems is that they are profoundly intractable and we really don't have a good idea of how to reduce these problems to a tractable approximation on real hardware.

Many basic concepts in computer science are in this class: data compression (see: the Hutter Prize), indexing (see: "learned indexing"), cache replacement algorithms (see: Bélády optimality theorem), etc. We narrowly specialize these algorithms such that they look very different to be computationally feasible but at the limit they are the same algorithm problem.

I find it interesting that database engines are essentially a giant bucket of algorithms all in this class.

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.

It's hard to tell how much care was put into futures_orchestra crate. The docs are generated. I don't see any benchmark in the repo. Performance claims without measurements are a red flag.

There are no performance claims, you misread.

The problem is that the system is RAM-constrained but the work scheduler doesn't use a RAM pressure signal.

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.

Reply on news.ycombinator.com