Skip to main content

starve_not/
lib.rs

1//! Keep the slowest stage of a pipeline busy without letting work pile up.
2//!
3//! Picture a pipeline where items are downloaded, then processed on a GPU. The GPU is the
4//! *bottleneck*, and the whole pipeline goes only as fast as it does. You want two things:
5//!
6//! 1. **The GPU never starves.** Enough items must be on their way to cover the time downloads
7//!    take, even when downloads suddenly get slower.
8//! 2. **Not too much is on its way.** Every item admitted into the pipeline uses memory, and on
9//!    shutdown it takes time for all of them to finish. That should stay short.
10//!
11//! No single fixed number gets both right, because the right number depends on download speed,
12//! GPU speed and batch size, and those change while the program runs. `starve-not` adjusts the
13//! number for you.
14//!
15//! # How it fits together
16//!
17//! - A [`Gate`] sits at the start of the pipeline and lets items in. Each admitted item holds a
18//!   *permit*, and the gate has a *limit* on how many permits are out at once. The permits come
19//!   as a [`Ticket`], which travels with the item until it is done. Items of very different
20//!   cost can take more than one permit each (see [Weighted items](Gate#weighted-items)).
21//! - An [`IdleProbe`] on the bottleneck measures how long it sits waiting for input.
22//! - A [`Pacer`] looks at the gate and the probes every couple of seconds, asks a [`Policy`]
23//!   what the limit should be, and changes the gate's limit.
24//!
25//! Three policies come with the crate:
26//!
27//! - [`DrainBounded`] (the one to start with) raises the limit while the bottleneck starves and
28//!   the gate is nearly full, provided items are succeeding. It checks whether raises improve
29//!   throughput and uses estimated average residence to limit queued work, allowing longer for
30//!   naturally slow pipelines.
31//! - [`Aimd`] raises the limit slowly and cuts it when items fail or get slow. It needs no probe,
32//!   so it suits pipelines without one clear bottleneck.
33//! - [`Fixed`] never changes the limit. It is useful as a baseline when measuring the others.
34//!
35//! # Example
36//!
37//! ```no_run
38//! use starve_not::{DrainBounded, Gate, IdleProbe, Pacer};
39//! # async fn download(_: u64) -> Vec<u8> { vec![] }
40//! # fn infer(_: &[u8]) -> bool { true }
41//!
42//! # #[cfg(feature = "rt")]
43//! # async fn run() {
44//! let gate = Gate::new(1);
45//! let device = IdleProbe::new();
46//! let policy = DrainBounded::builder().floor(16).build();
47//! let _pacer = Pacer::builder(&gate, policy).probe(&device).build().spawn();
48//!
49//! let (tx, mut rx) = tokio::sync::mpsc::channel(64);
50//! tokio::spawn({
51//!     let gate = gate.clone();
52//!     async move {
53//!         for id in 0.. {
54//!             // wait until the gate lets one more item in, then download it alongside the others
55//!             let Ok(ticket) = gate.acquire().await else { break };
56//!             let tx = tx.clone();
57//!             tokio::spawn(async move {
58//!                 let bytes = download(id).await;
59//!                 // if the device has stopped, the ticket drops and its permit goes back
60//!                 let _ = tx.send((bytes, ticket)).await;
61//!             });
62//!         }
63//!     }
64//! });
65//! std::thread::spawn(move || {
66//!     loop {
67//!         let next = {
68//!             let _idle = device.idle(); // counts as idle until the next item arrives
69//!             rx.blocking_recv()
70//!         };
71//!         let Some((bytes, ticket)) = next else { break };
72//!         match infer(&bytes) {
73//!             true => ticket.complete(), // done: the permit goes back to the gate
74//!             false => ticket.release(), // failed: also goes back, but isn't counted as done
75//!         }
76//!     }
77//! });
78//!
79//! // on shutdown: let nothing new in, then wait for the items already inside
80//! gate.close();
81//! gate.drained().await;
82//! # }
83//! ```
84//!
85//! # Several gates
86//!
87//! One gate limits the whole pipeline, but a single stage can have its own limit too. Say
88//! downloads should be limited on their own, because the storage server slows down when
89//! asked for too many bytes at once. Create one gate for downloads and one for the whole
90//! pipeline, each with its own pacer and policy. An item holds a ticket from each: the download
91//! ticket goes back as soon as the download is done, the other one when the item is finished.
92//!
93//! Always take the tickets in the same order, outer gate first. Each gate can count in its own
94//! unit. Here images are resized to the same size once downloaded, so the pipeline counts items,
95//! but downloads differ in size, so the download gate weighs them in megabytes (see
96//! [Weighted items](Gate#weighted-items)).
97//!
98//! ```no_run
99//! use starve_not::{Aimd, DrainBounded, Gate, IdleProbe, Pacer};
100//! # struct Item { id: u64, megabytes: usize }
101//! # async fn download(_: u64) -> Result<Vec<u8>, ()> { Ok(vec![]) }
102//!
103//! # #[cfg(feature = "rt")]
104//! # async fn run(items: Vec<Item>, device: IdleProbe) {
105//! // the whole pipeline, in items: grows while the device waits for input
106//! let pipeline = Gate::new(1);
107//! let policy = DrainBounded::builder().floor(8).build();
108//! let _pacer = Pacer::builder(&pipeline, policy).probe(&device).build().spawn();
109//!
110//! // downloads at once, in megabytes: backs off when downloads fail or get slow
111//! let downloads = Gate::new(1);
112//! let policy = Aimd::builder().floor(64).increase(16).build();
113//! let _download_pacer = Pacer::builder(&downloads, policy).build().spawn();
114//!
115//! for item in items {
116//!     let Ok(ticket) = pipeline.acquire().await else { break };
117//!     let Ok(download_ticket) = downloads.acquire_weighted(item.megabytes).await else { break };
118//!     tokio::spawn(async move {
119//!         match download(item.id).await {
120//!             Ok(bytes) => {
121//!                 download_ticket.complete();
122//!                 // ...send `bytes` and `ticket` on to the device, which completes `ticket`
123//!             }
124//!             // both go back without counting as done
125//!             Err(_) => drop((download_ticket, ticket)),
126//!         }
127//!     });
128//! }
129//! # }
130//! ```
131//!
132//! # Features
133//!
134//! - `rt` (on by default): adds `Pacer::spawn`, which runs the pacer as a tokio task. Without
135//!   it, call [`Pacer::step`] yourself on a timer.
136//! - `diagnostics`: adds `Policy::diagnostics`, the values a policy decided from, for logs and
137//!   metrics. Without it, policies keep nothing extra for them.
138//! - `test-util`: for tests with paused tokio time. Probes then follow `tokio::time::pause`, like a
139//!   spawned pacer. Turn it on in `[dev-dependencies]` only, since it costs a little on every
140//!   probe call.
141
142#![deny(missing_docs, rustdoc::broken_intra_doc_links)]
143#![warn(missing_debug_implementations)]
144
145mod gate;
146mod pacer;
147pub mod policy;
148mod probe;
149mod sample;
150
151pub use gate::{Closed, Gate, Ticket};
152#[cfg(feature = "rt")]
153pub use pacer::PacerHandle;
154pub use pacer::{Decision, Pacer, PacerBuilder};
155#[cfg(feature = "diagnostics")]
156pub use policy::Diagnostics;
157pub use policy::{Aimd, DrainBounded, Fixed, Policy};
158pub use probe::{IdleGuard, IdleProbe};
159pub use sample::Sample;