Skip to main content

tokio_token_bucket/
lib.rs

1#![doc = include_str!("../README.md")]
2#![forbid(unsafe_code)]
3
4//! Bounded asynchronous rate limiting for Tokio tasks.
5//!
6//! [`TokenBucket`] gates the start of work at a configured rate. It contains
7//! no work queue and spawns no background task: callers await one permit
8//! immediately before starting one operation.
9
10use std::num::NonZeroU32;
11use std::time::{Duration, Instant};
12
13/// A bounded token bucket for asynchronous rate limiting.
14///
15/// The bucket starts full, allowing an initial burst up to its configured
16/// capacity. After that, one token becomes available at each rate interval,
17/// up to the capacity. The bucket stores only its counters and timestamps; it
18/// never stores waiting operations or payloads.
19pub struct TokenBucket {
20    capacity: u32,
21    refill_interval: Duration,
22    tokens: u32,
23    last_refill: Instant,
24}
25
26impl TokenBucket {
27    /// Creates a bucket whose burst capacity equals its per-second rate.
28    ///
29    /// The bucket starts full. For example, a rate of four permits per second
30    /// allows four immediate acquisitions, then spaces later acquisitions by
31    /// approximately 250 milliseconds.
32    #[must_use]
33    pub fn new(permits_per_second: NonZeroU32) -> Self {
34        Self::with_burst(permits_per_second, permits_per_second)
35    }
36
37    /// Creates a bucket with an independent sustained rate and burst capacity.
38    ///
39    /// `permits_per_second` controls how quickly tokens return. `burst_capacity`
40    /// controls the maximum number of immediately available permits.
41    #[must_use]
42    pub fn with_burst(permits_per_second: NonZeroU32, burst_capacity: NonZeroU32) -> Self {
43        let rate = u64::from(permits_per_second.get());
44        let interval_nanos = (1_000_000_000 / rate).max(1);
45        Self {
46            capacity: burst_capacity.get(),
47            refill_interval: Duration::from_nanos(interval_nanos),
48            tokens: burst_capacity.get(),
49            last_refill: Instant::now(),
50        }
51    }
52
53    /// Waits for and consumes one permit.
54    ///
55    /// The future performs no allocation and does not enqueue work. If it is
56    /// cancelled while waiting, no permit is consumed.
57    pub async fn acquire(&mut self) {
58        loop {
59            let now = Instant::now();
60            self.refill(now);
61            if self.tokens > 0 {
62                self.tokens -= 1;
63                return;
64            }
65
66            tokio::time::sleep(self.time_until_next_token(now)).await;
67        }
68    }
69
70    fn refill(&mut self, now: Instant) {
71        if self.tokens >= self.capacity {
72            return;
73        }
74
75        let elapsed = now.duration_since(self.last_refill);
76        let interval_nanos = self.refill_interval.as_nanos();
77        let elapsed_intervals = elapsed.as_nanos() / interval_nanos;
78        if elapsed_intervals == 0 {
79            return;
80        }
81
82        let missing = u128::from(self.capacity - self.tokens);
83        let added = elapsed_intervals.min(missing);
84        self.tokens += u32::try_from(added).expect("refill cannot exceed bucket capacity");
85
86        if added == missing {
87            self.last_refill = now;
88        } else {
89            let elapsed_nanos = interval_nanos.saturating_mul(added);
90            let elapsed_duration = Duration::from_nanos(
91                u64::try_from(elapsed_nanos).expect("refill duration must fit in a Duration"),
92            );
93            self.last_refill += elapsed_duration;
94        }
95    }
96
97    fn time_until_next_token(&self, now: Instant) -> Duration {
98        let elapsed = now.duration_since(self.last_refill);
99        let remainder_nanos = elapsed.as_nanos() % self.refill_interval.as_nanos();
100        let wait_nanos = self.refill_interval.as_nanos() - remainder_nanos;
101        Duration::from_nanos(
102            u64::try_from(wait_nanos).expect("refill interval must fit in a Duration"),
103        )
104    }
105}
106
107#[cfg(test)]
108mod tests {
109    use super::TokenBucket;
110    use std::num::NonZeroU32;
111    use std::time::Duration;
112
113    fn non_zero(value: u32) -> NonZeroU32 {
114        NonZeroU32::new(value).expect("test rate must be non-zero")
115    }
116
117    #[tokio::test(start_paused = true)]
118    async fn starts_with_burst_capacity() {
119        let mut bucket = TokenBucket::with_burst(non_zero(4), non_zero(2));
120
121        bucket.acquire().await;
122        bucket.acquire().await;
123
124        let mut pending = Box::pin(bucket.acquire());
125        assert!(
126            tokio::time::timeout(Duration::ZERO, &mut pending)
127                .await
128                .is_err()
129        );
130    }
131
132    #[tokio::test(start_paused = true)]
133    async fn refills_at_the_configured_rate() {
134        let mut bucket = TokenBucket::with_burst(non_zero(4), non_zero(1));
135        bucket.acquire().await;
136
137        let mut pending = Box::pin(bucket.acquire());
138        tokio::time::advance(Duration::from_millis(249)).await;
139        assert!(
140            tokio::time::timeout(Duration::ZERO, &mut pending)
141                .await
142                .is_err()
143        );
144
145        tokio::time::advance(Duration::from_millis(1)).await;
146        pending.await;
147    }
148
149    #[tokio::test(start_paused = true)]
150    async fn excess_elapsed_time_does_not_exceed_burst_capacity() {
151        let mut bucket = TokenBucket::with_burst(non_zero(2), non_zero(2));
152        bucket.acquire().await;
153        bucket.acquire().await;
154        tokio::time::advance(Duration::from_secs(10)).await;
155
156        bucket.acquire().await;
157        bucket.acquire().await;
158
159        let mut pending = Box::pin(bucket.acquire());
160        assert!(
161            tokio::time::timeout(Duration::ZERO, &mut pending)
162                .await
163                .is_err()
164        );
165    }
166}