use std::collections::{BTreeSet, HashMap};
use std::sync::Arc;
use std::time::{Duration, Instant};
use tokio::sync::Mutex;
const MAX_ENTRIES: usize = 100_000;
const MIN_WINDOW_SECS: u64 = 1;
#[derive(Clone)]
struct WindowEntry {
window_start: Instant,
count: usize,
}
struct RateLimiterState {
windows: HashMap<String, WindowEntry>,
oldest_first: BTreeSet<(Instant, String)>,
}
pub struct RateLimiter {
windows: Arc<Mutex<RateLimiterState>>,
}
impl RateLimiter {
pub fn new() -> Self {
Self {
windows: Arc::new(Mutex::new(RateLimiterState {
windows: HashMap::new(),
oldest_first: BTreeSet::new(),
})),
}
}
pub async fn allow(&self, key: &str, max_requests: usize, window: Duration) -> bool {
if max_requests == 0 {
return false;
}
let window_secs = window.as_secs().max(MIN_WINDOW_SECS);
let now = Instant::now();
let mut windows = self.windows.lock().await;
if !windows.windows.contains_key(key)
&& windows.windows.len() >= MAX_ENTRIES
&& let Some((_, oldest_key)) = windows.oldest_first.pop_first()
{
windows.windows.remove(&oldest_key);
}
if let Some(window_start) = windows.windows.get(key).map(|entry| entry.window_start) {
if now.saturating_duration_since(window_start).as_secs() >= window_secs {
windows
.oldest_first
.remove(&(window_start, key.to_string()));
let entry = windows.windows.get_mut(key).expect("entry exists");
entry.window_start = now;
entry.count = 0;
windows.oldest_first.insert((now, key.to_string()));
}
} else {
windows.windows.insert(
key.to_string(),
WindowEntry {
window_start: now,
count: 0,
},
);
windows.oldest_first.insert((now, key.to_string()));
}
let entry = windows.windows.get_mut(key).expect("entry inserted above");
if entry.count >= max_requests {
return false;
}
entry.count += 1;
true
}
#[cfg(test)]
async fn window_start_for(&self, key: &str) -> Option<Instant> {
let windows = self.windows.lock().await;
windows.windows.get(key).map(|entry| entry.window_start)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[tokio::test]
async fn test_allow_within_limit() {
let limiter = RateLimiter::new();
assert!(
limiter
.allow("192.168.1.1", 5, Duration::from_secs(60))
.await
);
assert!(
limiter
.allow("192.168.1.1", 5, Duration::from_secs(60))
.await
);
assert!(
limiter
.allow("192.168.1.1", 5, Duration::from_secs(60))
.await
);
}
#[tokio::test]
async fn test_deny_at_limit() {
let limiter = RateLimiter::new();
for _ in 0..3 {
assert!(limiter.allow("10.0.0.1", 3, Duration::from_secs(60)).await);
}
assert!(!limiter.allow("10.0.0.1", 3, Duration::from_secs(60)).await);
}
#[tokio::test]
async fn test_separate_keys_independent() {
let limiter = RateLimiter::new();
for _ in 0..2 {
assert!(limiter.allow("key-a", 2, Duration::from_secs(60)).await);
}
assert!(!limiter.allow("key-a", 2, Duration::from_secs(60)).await);
assert!(limiter.allow("key-b", 2, Duration::from_secs(60)).await);
}
#[tokio::test]
async fn server_budgets_do_not_consume_each_others_keys() {
let limiter = RateLimiter::new();
for _ in 0..2 {
assert!(
limiter
.allow("metrics-auth", 2, Duration::from_secs(60))
.await
);
}
assert!(
!limiter
.allow("metrics-auth", 2, Duration::from_secs(60))
.await
);
assert!(
limiter
.allow("register-global", 2, Duration::from_secs(60))
.await,
"an exhausted metrics budget must not affect registration"
);
assert!(
limiter
.allow("register:203.0.113.7", 2, Duration::from_secs(60))
.await,
"a peer-address budget is a separate key from the global budget"
);
assert!(
limiter
.allow("register-global", 2, Duration::from_secs(60))
.await
);
assert!(
!limiter
.allow("register-global", 2, Duration::from_secs(60))
.await,
"the global registration budget is bounded"
);
assert!(
limiter
.allow("metrics-auth-other", 1, Duration::from_secs(60))
.await,
"unrelated buckets remain usable"
);
}
#[tokio::test]
async fn test_window_expiry_resets_count() {
let limiter = RateLimiter::new();
for _ in 0..2 {
assert!(
limiter
.allow("expire-test", 2, Duration::from_secs(1))
.await
);
}
assert!(
!limiter
.allow("expire-test", 2, Duration::from_secs(1))
.await
);
tokio::time::sleep(Duration::from_secs(2)).await;
assert!(
limiter
.allow("expire-test", 2, Duration::from_secs(1))
.await
);
}
#[tokio::test]
async fn test_zero_max_requests_deny_all() {
let limiter = RateLimiter::new();
assert!(!limiter.allow("zero", 0, Duration::from_secs(60)).await);
}
#[tokio::test]
async fn zero_length_window_still_enforces_the_limit() {
let limiter = RateLimiter::new();
assert!(limiter.allow("zero-window", 2, Duration::ZERO).await);
assert!(limiter.allow("zero-window", 2, Duration::ZERO).await);
assert!(!limiter.allow("zero-window", 2, Duration::ZERO).await);
}
#[tokio::test]
async fn zero_length_window_with_zero_budget_denies_everything() {
let limiter = RateLimiter::new();
assert!(!limiter.allow("zero-zero", 0, Duration::ZERO).await);
}
#[tokio::test]
async fn window_bookkeeping_uses_a_monotonic_clock() {
let limiter = RateLimiter::new();
assert!(limiter.allow("monotonic", 5, Duration::from_secs(60)).await);
let window_start = limiter
.window_start_for("monotonic")
.await
.expect("the window must exist after an allowed request");
let now = Instant::now();
assert!(
window_start <= now,
"window start {window_start:?} must not be in the future"
);
assert!(
now.duration_since(window_start) < Duration::from_secs(5),
"window start must track the monotonic clock"
);
}
}