yaiko_core/
distributed_rate_limit.rs1use async_trait::async_trait;
8use std::collections::HashMap;
9use std::sync::{Arc, Mutex};
10use std::time::{Duration, Instant};
11
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub enum DistributedRateLimitError {
14 Backend,
15 InvalidPolicy,
16}
17
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub struct WindowPolicy {
20 pub limit: u32,
21 pub window: Duration,
22}
23
24impl WindowPolicy {
25 pub fn new(limit: u32, window: Duration) -> Result<Self, DistributedRateLimitError> {
26 if limit == 0 || window.is_zero() {
27 return Err(DistributedRateLimitError::InvalidPolicy);
28 }
29 Ok(Self { limit, window })
30 }
31}
32
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub struct DistributedDecision {
35 pub allowed: bool,
36 pub limit: u32,
37 pub remaining: u32,
38 pub retry_after: Duration,
39}
40
41#[async_trait]
42pub trait RateLimitStore: Clone + Send + Sync + 'static {
43 async fn increment(
44 &self,
45 key: &str,
46 policy: WindowPolicy,
47 ) -> Result<DistributedDecision, DistributedRateLimitError>;
48}
49
50#[derive(Clone)]
51pub struct DistributedRateLimiter<S> {
52 store: S,
53 policy: WindowPolicy,
54}
55
56impl<S: RateLimitStore> DistributedRateLimiter<S> {
57 pub fn new(store: S, policy: WindowPolicy) -> Self {
58 Self { store, policy }
59 }
60 pub async fn check(
61 &self,
62 key: impl AsRef<str>,
63 ) -> Result<DistributedDecision, DistributedRateLimitError> {
64 self.store.increment(key.as_ref(), self.policy).await
65 }
66 pub fn policy(&self) -> WindowPolicy {
67 self.policy
68 }
69}
70
71#[derive(Debug, Clone)]
72struct Window {
73 count: u32,
74 reset_at: Instant,
75}
76
77#[derive(Clone)]
78pub struct MemoryRateLimitStore {
79 entries: Arc<Mutex<HashMap<String, Window>>>,
80 max_entries: usize,
81}
82
83impl MemoryRateLimitStore {
84 pub fn new(max_entries: usize) -> Self {
85 Self {
86 entries: Arc::new(Mutex::new(HashMap::new())),
87 max_entries: max_entries.max(1),
88 }
89 }
90 pub fn len(&self) -> usize {
91 self.entries
92 .lock()
93 .expect("rate limit store lock poisoned")
94 .len()
95 }
96 pub fn is_empty(&self) -> bool {
97 self.len() == 0
98 }
99 pub fn clear(&self) {
100 self.entries
101 .lock()
102 .expect("rate limit store lock poisoned")
103 .clear();
104 }
105}
106
107#[async_trait]
108impl RateLimitStore for MemoryRateLimitStore {
109 async fn increment(
110 &self,
111 key: &str,
112 policy: WindowPolicy,
113 ) -> Result<DistributedDecision, DistributedRateLimitError> {
114 let now = Instant::now();
115 let mut entries = self
116 .entries
117 .lock()
118 .map_err(|_| DistributedRateLimitError::Backend)?;
119 if entries.len() >= self.max_entries && !entries.contains_key(key) {
120 if let Some(oldest) = entries
121 .iter()
122 .min_by_key(|(_, value)| value.reset_at)
123 .map(|(key, _)| key.clone())
124 {
125 entries.remove(&oldest);
126 }
127 }
128 let window = entries.entry(key.to_owned()).or_insert(Window {
129 count: 0,
130 reset_at: now + policy.window,
131 });
132 if now >= window.reset_at {
133 window.count = 0;
134 window.reset_at = now + policy.window;
135 }
136 window.count = window.count.saturating_add(1);
137 let allowed = window.count <= policy.limit;
138 let remaining = policy.limit.saturating_sub(window.count.min(policy.limit));
139 Ok(DistributedDecision {
140 allowed,
141 limit: policy.limit,
142 remaining,
143 retry_after: if allowed {
144 Duration::ZERO
145 } else {
146 window.reset_at.saturating_duration_since(now)
147 },
148 })
149 }
150}
151
152#[cfg(test)]
153mod tests {
154 use super::*;
155 #[tokio::test]
156 async fn atomically_enforces_a_window() {
157 let store = MemoryRateLimitStore::new(10);
158 let policy = WindowPolicy::new(2, Duration::from_secs(60)).unwrap();
159 let limiter = Arc::new(DistributedRateLimiter::new(store, policy));
160 let mut tasks = Vec::new();
161 for _ in 0..8 {
162 let limiter = limiter.clone();
163 tasks.push(tokio::spawn(async move {
164 limiter.check("same-key").await.unwrap().allowed
165 }));
166 }
167 let mut allowed = 0;
168 for task in tasks {
169 if task.await.unwrap() {
170 allowed += 1;
171 }
172 }
173 assert_eq!(allowed, 2);
174 }
175 #[tokio::test]
176 async fn isolates_keys_and_bounds_storage() {
177 let store = MemoryRateLimitStore::new(2);
178 let policy = WindowPolicy::new(1, Duration::from_secs(60)).unwrap();
179 let limiter = DistributedRateLimiter::new(store.clone(), policy);
180 assert!(limiter.check("a").await.unwrap().allowed);
181 assert!(limiter.check("b").await.unwrap().allowed);
182 assert_eq!(store.len(), 2);
183 assert!(limiter.check("c").await.unwrap().allowed);
184 assert_eq!(store.len(), 2);
185 }
186 #[tokio::test]
187 async fn reports_retry_after_when_denied() {
188 let store = MemoryRateLimitStore::new(2);
189 let limiter = DistributedRateLimiter::new(
190 store,
191 WindowPolicy::new(1, Duration::from_secs(60)).unwrap(),
192 );
193 assert!(limiter.check("key").await.unwrap().allowed);
194 let denied = limiter.check("key").await.unwrap();
195 assert!(!denied.allowed);
196 assert!(denied.retry_after > Duration::ZERO);
197 assert_eq!(denied.remaining, 0);
198 }
199}