Tokio Gives Progress, Not Ordering: Scheduling 1M Tasks

This is a prequel to my previous article, Your Rust Service Isn't Leaking — It Could Be the Allocator.

In that post, I wrote about why RSS stayed high after a bursty Rust service had already freed most of its heap state. But before asking why memory was retained after the burst, there was an earlier question:

Why did the process reach such a high memory watermark during the burst in the first place?

Part of the answer was our fan-out pattern.

Our service was event-driven:

1. Read events from a message queue.
2. For each event, spawn a Tokio task to process it.
3. Inside that event task, fan out to many per-user tasks.
4. Wait for all responses and emit one response event.

Our Task Pattern

Each event contained a payload and a list of user tokens. For every token, we hit an outbound API and collected the response.

A simplified version looked like this:

struct Event { 
    payload: Bytes,  // ~4KB
    user_tokens: Vec<String>, // up to 1000 tokens
    // other fields
}

...
// in main
loop {
    let event: Event = fetch_next_event().await; 

    tokio::spawn(async move {
        let data = event.payload.clone();

        let mut tasks = JoinSet::new();
        for token in &event.user_tokens {
            let token = token.clone();
            let data = data.clone();
            tasks.spawn(async move {
                // hits an outbound API and returns response
                process(token, data).await
            });
        }

        let mut responses = Vec::with_capacity(event.user_tokens.len());
        while let Some(res) = tasks.join_next().await {
            responses.push(res)
        }

        generate_response_event(event, responses);
    });
}

Although this is an unbounded fan-out, I assumed it wouldn't become practically unbounded. The per-user tasks spent almost all of their lifetime waiting on outbound I/O, completed within a few milliseconds, and were immediately dropped. I expected earlier events to naturally drain while newer events were still being submitted, even if individual API calls completed out of order.

The requirement was that every outbound call had to go out and the burst should complete within our SLA.

The burst did complete within the expected time. So at first glance, there was no obvious correctness issue.

What the Logs Looked Like

started: event 1, user 1
started: event 1, user 2
started: event 1, user 3
started: event 2, user 1
started: event 2, user 2
started: event 3, user 3

...

finished: event 79
finished: event 76

started: event 900, user 1
started: event 900, user 2
started: event 1, user 998
started: event 1, user 999

...

finished: event 2
finished: event 3

The exact event and user IDs are less important than the shape: events were submitted in order but token tasks from earlier events were still receiving their first poll much later.

I did not expect strict ordering. The API calls could complete in any order, and that was fine. What surprised me was how far polling order could drift from submission order when the Tokio runtime was given around a million independent tasks. Tokio still made progress, but it did not preserve my application-level unit of fairness: the event.

Inside Tokio's Scheduler

Tokio’s scheduler gives a progress guarantee, not an ordering guarantee.

Once tasks become independently schedulable, Tokio no longer associates them with the event that created them. From the scheduler's perspective, they're simply runnable tasks competing for polls.

Structurally, Tokio’s multi-threaded runtime has a fixed number of worker threads, one global queue, and a local queue per worker. A worker-local queue has 256 slots and on overflow it spills half of it to the global queue. Workers prefer pulling from their own local queue, check the global queue occasionally, and steal from other workers when they run dry.

A simplified picture looks like this:

                       
                                 global queue        
                        ┌────────────────────────────┐
                        │ * overflow from local      │
                        │ * remotely scheduled tasks │
                        │ * mixed older/newer work   │
                        └──────────────┬─────────────┘
                                       │
         ┌─────────────────────────────┼─────────────────────────────┐
         │                             │                             │
         ▼                             ▼                             ▼                              
     worker 0                      worker 1                      worker 2    
  ┌─────────────┐               ┌─────────────┐               ┌─────────────┐
  │ local queue │               │ local queue │               │ local queue │
  │ up to 256   │               │ up to 256   │               │ up to 256   │
  └──────┬──────┘               └──────┬──────┘               └──────┬──────┘
         │                             │                             │
         ▼                             ▼                             ▼
      poll task                     poll task                     poll task

This design is optimized for throughput and low synchronization overhead. A strict global FIFO scheduler would require workers to constantly coordinate through one central ordering point. Tokio avoids that by letting workers make local progress, occasionally synchronize through the global queue, and steal work when needed.

With this architecture, once an event fans out into 1000 token tasks, those tasks are mixed with token tasks from other events, parent event tasks waiting on JoinSet, and tasks waking from I/O readiness.

That is how polling order can drift from submission order.

And the core distinction is:

task created != task polled != task completed

While Tokio continues making progress on every task, memory is affected by how much task state is alive at once.

Every token task carries some state. None of that is huge individually, but when multiplied by hundreds of thousands of tasks sitting alive at the same time, it adds up fast.

Tokio's scheduling model helps explain why so many tasks remained alive simultaneously. The allocator explains why RSS stayed high after — which is the subject of the earlier post I linked at the top.

Task Creation Needs a Bound

spawn is not backpressure.

A worker-local queue capacity of 256 is not a concurrency limit either. It is an internal scheduling detail. When local queues overflow, work can be moved to the global queue. It does not mean Tokio stops accepting tasks.

So if the application can create 1M tasks, the runtime can end up owning 1M tasks.

Tokio will keep making progress, but it will not stop the application from exposing too much work at once. That bound has to come from the application.

Our original shape had no ceiling:

read events as fast as possible
  └── spawn one event task per event
        └── spawn up to 1000 token tasks per event

1000 events × 1000 users is a million token tasks. As the number of events grows, the amount of scheduler-visible work grows proportionally.

The bounded shape which worked for us is:

allow only N events into processing at once
  └── each event still fans out internally
        └── but total exposed work is capped by N × users_per_event

This doesn't make individual HTTP calls any faster. What it changes is how much work the runtime is allowed to see at once. Events still queue up and still get processed eventually, they just aren't all expanded into a million Tokio tasks the moment they arrive.

An important detail is that even with this bounded structure, the burst finished within our SLA while reducing the peak memory significantly.

Not a Tokio Problem

None of this was really a Tokio problem. Tokio did exactly what it says it does. It kept every task moving forward until the burst finished on time. The gap was between what I assumed (the event is the unit of work) and what the runtime actually sees (a task is a task, whichever event it came from).

That gap is easy to miss because it doesn't show up as a bug: nothing crashes (until limits are hit), nothing hangs, nothing produces incorrect results. It shows up as a memory graph that spikes higher than it should, for reasons that don't appear anywhere in application logic.

Conclusion

If there's a unit you actually care about (an event, a request, a customer), the runtime has no idea it exists. That boundary only exists if you build it.

So before you tokio::spawn inside a loop, ask what the largest possible number of live tasks is. If you can't answer that with a real number, that could be the bound you're missing.

And,

• spawned early doesn't mean first-polled early
• first-polled early doesn't mean completed early
• completed eventually doesn't mean peak memory stays low