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:
- The GPU never starves. Enough items must be on their way to cover the time downloads take, even when downloads suddenly get slower.
- 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
Gatesits 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 aTicket, 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
IdleProbeon the bottleneck measures how long it sits waiting for input. - A
Pacerlooks at the gate and the probes every couple of seconds, asks aPolicywhat 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.Aimdraises the limit slowly and cuts it when items fail or get slow. It needs no probe, so it suits pipelines without one clear bottleneck.Fixednever 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): addsPacer::spawn, which runs the pacer as a tokio task. Without it, callPacer::stepyourself on a timer.diagnostics: addsPolicy::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 followtokio::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.
- Idle
Guard - Keeps its
IdleProbecounting as idle until dropped. Made byIdleProbe::idle. - Idle
Probe - Measures how long a stage spends waiting for input.
- Pacer
- Adjusts a
Gate’s limit at a regular interval, as itsPolicydecides. - Pacer
Builder - Use builder syntax to set the inputs and finish with
build(). - Pacer
Handle - 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.