tokio_token_bucket/
lib.rs1#![doc = include_str!("../README.md")]
2#![forbid(unsafe_code)]
3
4use std::num::NonZeroU32;
11use std::time::{Duration, Instant};
12
13pub struct TokenBucket {
20 capacity: u32,
21 refill_interval: Duration,
22 tokens: u32,
23 last_refill: Instant,
24}
25
26impl TokenBucket {
27 #[must_use]
33 pub fn new(permits_per_second: NonZeroU32) -> Self {
34 Self::with_burst(permits_per_second, permits_per_second)
35 }
36
37 #[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 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}