Skip to main content

rainier_middleware/
rate_limit.rs

1//! Where a throttle keeps its counters — [`RateLimitStore`].
2//!
3//! A rate limit is a number and a clock, and the only interesting question is
4//! **who else can see it**. Over an in-process map, five replicas behind a load
5//! balancer enforce "five attempts a minute" five times over, and the effective
6//! limit is twenty-five. For a page-view limiter that is a rounding error; for
7//! a credential limiter it is the difference between a working control and a
8//! decorative one.
9//!
10//! So the counter is a port. [`MemoryRateLimitStore`] is the default and is
11//! honest about being per-process; `rainier-cache` implements this over any
12//! [`Cache`](https://docs.rs/rainier-cache), which puts the counters wherever
13//! `CACHE_DRIVER` already points.
14//!
15//! # Why not depend on the cache directly
16//!
17//! Because a throttle needs *a shared counter*, not *the cache*. Keeping it a
18//! port means a deployment can put its limits somewhere else — a dedicated
19//! rate-limit service, a database table with a unique index — without the
20//! middleware crate learning about any of them. It also keeps
21//! `rainier-middleware` depending on `rainier-http` and nothing else, which is
22//! what lets it compile for a Worker.
23
24use std::collections::HashMap;
25use std::sync::Mutex;
26use std::time::{Duration, Instant};
27
28use rainier_support::{BoxFuture, Result};
29
30/// One key's state after a hit.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct Hit {
33    /// How many hits this key has taken in the current window, including this
34    /// one.
35    pub count: u32,
36    /// How long until the window resets.
37    pub resets_in: Duration,
38}
39
40/// A counter a throttle can share.
41///
42/// Fixed windows rather than a sliding log: one integer and one expiry per key
43/// instead of a timestamp per request, which is the difference between a
44/// limiter that costs nothing and one that is its own scaling problem. The
45/// trade is a boundary effect — a caller can spend a full window's allowance
46/// either side of a reset — and for the things people actually rate-limit that
47/// is an acceptable answer.
48pub trait RateLimitStore: Send + Sync + 'static {
49    /// Record one hit against `key`, in a window of `window`.
50    ///
51    /// Returns the state **after** the hit. The window starts at the first hit
52    /// and expires on its own; nothing needs sweeping.
53    fn hit<'a>(&'a self, key: &'a str, window: Duration) -> BoxFuture<'a, Result<Hit>>;
54
55    /// The state of `key` without recording anything.
56    ///
57    /// `None` when the key has no live window, which is the same answer as
58    /// "zero hits" — an expired window and an absent one are indistinguishable
59    /// to a caller, and both mean the allowance is whole.
60    fn peek<'a>(&'a self, key: &'a str) -> BoxFuture<'a, Result<Option<Hit>>>;
61
62    /// Forget `key`, restoring its full allowance.
63    ///
64    /// What a successful login calls, so a failed-attempt limiter does not
65    /// keep punishing somebody who has just proved who they are.
66    fn clear<'a>(&'a self, key: &'a str) -> BoxFuture<'a, Result<()>>;
67
68    /// Whether other instances of this application see the same counters.
69    ///
70    /// `false` here means a limit of `n` is really `n × replicas`, and the
71    /// application should be told at boot rather than finding out from a
72    /// credential-stuffing run that succeeded.
73    fn is_shared(&self) -> bool;
74
75    /// A label for diagnostics — `"memory"`, `"cache:redis"`.
76    fn name(&self) -> &str;
77}
78
79/// The default: one map, this process, no dependencies.
80///
81/// Right for development, for a single node, and for anything limited for
82/// politeness rather than for safety. Wrong for a credential limiter on more
83/// than one replica — see [`is_shared`](RateLimitStore::is_shared).
84#[derive(Debug, Default)]
85pub struct MemoryRateLimitStore {
86    windows: Mutex<HashMap<String, Window>>,
87}
88
89#[derive(Debug, Clone, Copy)]
90struct Window {
91    count: u32,
92    started: Instant,
93    length: Duration,
94}
95
96impl Window {
97    fn is_live(&self, now: Instant) -> bool {
98        now.duration_since(self.started) < self.length
99    }
100
101    fn resets_in(&self, now: Instant) -> Duration {
102        self.length.saturating_sub(now.duration_since(self.started))
103    }
104}
105
106impl MemoryRateLimitStore {
107    /// An empty store.
108    pub fn new() -> Self {
109        Self::default()
110    }
111
112    /// How many keys are being tracked.
113    ///
114    /// For a test, and for the one operational question this store raises:
115    /// whether it is growing without bound.
116    pub fn tracked(&self) -> usize {
117        self.windows.lock().expect("rate limit lock poisoned").len()
118    }
119}
120
121impl RateLimitStore for MemoryRateLimitStore {
122    fn hit<'a>(&'a self, key: &'a str, window: Duration) -> BoxFuture<'a, Result<Hit>> {
123        Box::pin(async move {
124            let now = Instant::now();
125            let mut windows = self.windows.lock().expect("rate limit lock poisoned");
126
127            // Evict on read rather than resetting in place. A key nobody has
128            // touched since its window ended is dead weight, and a limiter
129            // keyed by IP address accumulates a lot of it — this is what stops
130            // the map growing for the lifetime of the process.
131            windows.retain(|_, existing| existing.is_live(now));
132
133            let existing = windows.entry(key.to_string()).or_insert(Window {
134                count: 0,
135                started: now,
136                length: window,
137            });
138
139            existing.count += 1;
140            Ok(Hit { count: existing.count, resets_in: existing.resets_in(now) })
141        })
142    }
143
144    fn peek<'a>(&'a self, key: &'a str) -> BoxFuture<'a, Result<Option<Hit>>> {
145        Box::pin(async move {
146            let now = Instant::now();
147            let windows = self.windows.lock().expect("rate limit lock poisoned");
148
149            Ok(windows
150                .get(key)
151                .filter(|window| window.is_live(now))
152                .map(|window| Hit { count: window.count, resets_in: window.resets_in(now) }))
153        })
154    }
155
156    fn clear<'a>(&'a self, key: &'a str) -> BoxFuture<'a, Result<()>> {
157        Box::pin(async move {
158            self.windows.lock().expect("rate limit lock poisoned").remove(key);
159            Ok(())
160        })
161    }
162
163    fn is_shared(&self) -> bool {
164        false
165    }
166
167    fn name(&self) -> &str {
168        "memory"
169    }
170}
171
172#[cfg(test)]
173mod tests {
174    use super::*;
175
176    fn store() -> MemoryRateLimitStore {
177        MemoryRateLimitStore::new()
178    }
179
180    #[tokio::test]
181    async fn hits_count_up_within_a_window() {
182        let store = store();
183        let window = Duration::from_secs(60);
184
185        for expected in 1..=3 {
186            let hit = store.hit("ada", window).await.unwrap();
187            assert_eq!(hit.count, expected);
188        }
189    }
190
191    #[tokio::test]
192    async fn keys_are_counted_separately() {
193        let store = store();
194        let window = Duration::from_secs(60);
195
196        store.hit("ada", window).await.unwrap();
197        store.hit("ada", window).await.unwrap();
198        let grace = store.hit("grace", window).await.unwrap();
199
200        assert_eq!(grace.count, 1);
201        assert_eq!(store.peek("ada").await.unwrap().unwrap().count, 2);
202    }
203
204    #[tokio::test]
205    async fn a_window_expires_and_the_allowance_comes_back() {
206        let store = store();
207        let window = Duration::from_millis(30);
208
209        store.hit("ada", window).await.unwrap();
210        store.hit("ada", window).await.unwrap();
211
212        tokio::time::sleep(Duration::from_millis(50)).await;
213
214        assert_eq!(store.hit("ada", window).await.unwrap().count, 1);
215    }
216
217    #[tokio::test]
218    async fn an_expired_window_reads_as_nothing_rather_than_as_a_stale_count() {
219        let store = store();
220        let window = Duration::from_millis(30);
221
222        store.hit("ada", window).await.unwrap();
223        tokio::time::sleep(Duration::from_millis(50)).await;
224
225        assert!(store.peek("ada").await.unwrap().is_none());
226    }
227
228    #[tokio::test]
229    async fn dead_keys_are_evicted_rather_than_accumulating() {
230        // The failure this prevents is not wrong answers; it is a map that
231        // grows for the lifetime of the process, one entry per address that
232        // ever made a request.
233        let store = store();
234        let window = Duration::from_millis(30);
235
236        for i in 0..100 {
237            store.hit(&format!("ip:{i}"), window).await.unwrap();
238        }
239        assert_eq!(store.tracked(), 100);
240
241        tokio::time::sleep(Duration::from_millis(50)).await;
242        store.hit("ip:fresh", window).await.unwrap();
243
244        assert_eq!(store.tracked(), 1, "the expired keys were not evicted");
245    }
246
247    #[tokio::test]
248    async fn clearing_restores_the_whole_allowance() {
249        let store = store();
250        let window = Duration::from_secs(60);
251
252        store.hit("ada", window).await.unwrap();
253        store.hit("ada", window).await.unwrap();
254        store.clear("ada").await.unwrap();
255
256        assert!(store.peek("ada").await.unwrap().is_none());
257        assert_eq!(store.hit("ada", window).await.unwrap().count, 1);
258    }
259
260    #[tokio::test]
261    async fn the_reset_time_counts_down() {
262        let store = store();
263        let window = Duration::from_secs(60);
264
265        let first = store.hit("ada", window).await.unwrap();
266        tokio::time::sleep(Duration::from_millis(20)).await;
267        let second = store.hit("ada", window).await.unwrap();
268
269        assert!(
270            second.resets_in < first.resets_in,
271            "{:?} !< {:?}",
272            second.resets_in,
273            first.resets_in
274        );
275        // And the second hit did not restart the window.
276        assert_eq!(second.count, 2);
277    }
278
279    #[test]
280    fn it_says_it_is_not_shared() {
281        assert!(!store().is_shared());
282        assert_eq!(store().name(), "memory");
283    }
284}