Skip to main content

Crate starve_not

Crate starve_not 

Source
Expand description

Keep the slowest stage of a pipeline busy without letting work pile up.

Picture a pipeline where items are downloaded, then processed on a GPU. The GPU is the bottleneck, and the whole pipeline goes only as fast as it does. You want two things:

  1. The GPU never starves. Enough items must be on their way to cover the time downloads take, even when downloads suddenly get slower.
  2. Not too much is on its way. Every item admitted into the pipeline uses memory, and on shutdown it takes time for all of them to finish. That should stay short.

No single fixed number gets both right, because the right number depends on download speed, GPU speed and batch size, and those change while the program runs. starve-not adjusts the number for you.

§How it fits together

  • A Gate sits at the start of the pipeline and lets items in. Each admitted item holds a permit, and the gate has a limit on how many permits are out at once. The permits come as a Ticket, which travels with the item until it is done. Items of very different cost can take more than one permit each (see Weighted items).
  • An IdleProbe on the bottleneck measures how long it sits waiting for input.
  • A Pacer looks at the gate and the probes every couple of seconds, asks a Policy what the limit should be, and changes the gate’s limit.

Three policies come with the crate:

  • DrainBounded (the one to start with) raises the limit while the bottleneck starves and the gate is nearly full, provided items are succeeding. It checks whether raises improve throughput and uses estimated average residence to limit queued work, allowing longer for naturally slow pipelines.
  • Aimd raises the limit slowly and cuts it when items fail or get slow. It needs no probe, so it suits pipelines without one clear bottleneck.
  • Fixed never changes the limit. It is useful as a baseline when measuring the others.

§Example

use starve_not::{DrainBounded, Gate, IdleProbe, Pacer};

let gate = Gate::new(1);
let device = IdleProbe::new();
let policy = DrainBounded::builder().floor(16).build();
let _pacer = Pacer::builder(&gate, policy).probe(&device).build().spawn();

let (tx, mut rx) = tokio::sync::mpsc::channel(64);
tokio::spawn({
    let gate = gate.clone();
    async move {
        for id in 0.. {
            // wait until the gate lets one more item in, then download it alongside the others
            let Ok(ticket) = gate.acquire().await else { break };
            let tx = tx.clone();
            tokio::spawn(async move {
                let bytes = download(id).await;
                // if the device has stopped, the ticket drops and its permit goes back
                let _ = tx.send((bytes, ticket)).await;
            });
        }
    }
});
std::thread::spawn(move || {
    loop {
        let next = {
            let _idle = device.idle(); // counts as idle until the next item arrives
            rx.blocking_recv()
        };
        let Some((bytes, ticket)) = next else { break };
        match infer(&bytes) {
            true => ticket.complete(), // done: the permit goes back to the gate
            false => ticket.release(), // failed: also goes back, but isn't counted as done
        }
    }
});

// on shutdown: let nothing new in, then wait for the items already inside
gate.close();
gate.drained().await;

§Several gates

One gate limits the whole pipeline, but a single stage can have its own limit too. Say downloads should be limited on their own, because the storage server slows down when asked for too many bytes at once. Create one gate for downloads and one for the whole pipeline, each with its own pacer and policy. An item holds a ticket from each: the download ticket goes back as soon as the download is done, the other one when the item is finished.

Always take the tickets in the same order, outer gate first. Each gate can count in its own unit. Here images are resized to the same size once downloaded, so the pipeline counts items, but downloads differ in size, so the download gate weighs them in megabytes (see Weighted items).

use starve_not::{Aimd, DrainBounded, Gate, IdleProbe, Pacer};

// the whole pipeline, in items: grows while the device waits for input
let pipeline = Gate::new(1);
let policy = DrainBounded::builder().floor(8).build();
let _pacer = Pacer::builder(&pipeline, policy).probe(&device).build().spawn();

// downloads at once, in megabytes: backs off when downloads fail or get slow
let downloads = Gate::new(1);
let policy = Aimd::builder().floor(64).increase(16).build();
let _download_pacer = Pacer::builder(&downloads, policy).build().spawn();

for item in items {
    let Ok(ticket) = pipeline.acquire().await else { break };
    let Ok(download_ticket) = downloads.acquire_weighted(item.megabytes).await else { break };
    tokio::spawn(async move {
        match download(item.id).await {
            Ok(bytes) => {
                download_ticket.complete();
                // ...send `bytes` and `ticket` on to the device, which completes `ticket`
            }
            // both go back without counting as done
            Err(_) => drop((download_ticket, ticket)),
        }
    });
}

§Features

  • rt (on by default): adds Pacer::spawn, which runs the pacer as a tokio task. Without it, call Pacer::step yourself on a timer.
  • diagnostics: adds Policy::diagnostics, the values a policy decided from, for logs and metrics. Without it, policies keep nothing extra for them.
  • test-util: for tests with paused tokio time. Probes then follow tokio::time::pause, like a spawned pacer. Turn it on in [dev-dependencies] only, since it costs a little on every probe call.

Re-exports§

pub use policy::Diagnostics;
pub use policy::Aimd;
pub use policy::DrainBounded;
pub use policy::Fixed;
pub use policy::Policy;

Modules§

policy
Policies: the rules that decide the gate’s limit.

Structs§

Closed
Returned when the gate has been closed with Gate::close, so it lets nothing new in.
Decision
What the pacer decided on one tick, and why.
Gate
Limits how much work is inside the pipeline at once.
IdleGuard
Keeps its IdleProbe counting as idle until dropped. Made by IdleProbe::idle.
IdleProbe
Measures how long a stage spends waiting for input.
Pacer
Adjusts a Gate’s limit at a regular interval, as its Policy decides.
PacerBuilder
Use builder syntax to set the inputs and finish with build().
PacerHandle
Keeps a spawned pacer running.
Sample
What happened in the pipeline since the pacer last looked.
Ticket
Permission for some items to be inside the pipeline, from a Gate.