yaiko_core/
singleflight_cache.rs1use std::collections::HashMap;
4use std::future::Future;
5use std::sync::Arc;
6use std::time::{Duration, Instant};
7use tokio::sync::{oneshot, Mutex};
8
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub enum CacheError {
11 Capacity,
12 Producer(String),
13 Cancelled,
14}
15
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub enum CacheLookup<V> {
18 Fresh(V),
19 Stale(V),
20}
21
22#[derive(Clone)]
23pub struct SingleFlightCache<V> {
24 state: Arc<Mutex<State<V>>>,
25 capacity: usize,
26}
27
28struct Entry<V> {
29 value: V,
30 stale_at: Instant,
31 expires_at: Instant,
32}
33struct State<V> {
34 entries: HashMap<String, Entry<V>>,
35 flights: HashMap<String, Vec<oneshot::Sender<Result<V, String>>>>,
36}
37
38impl<V: Clone + Send + Sync + 'static> SingleFlightCache<V> {
39 pub fn new(capacity: usize) -> Self {
40 Self {
41 state: Arc::new(Mutex::new(State {
42 entries: HashMap::new(),
43 flights: HashMap::new(),
44 })),
45 capacity: capacity.max(1),
46 }
47 }
48 pub async fn get(&self, key: &str) -> Option<CacheLookup<V>> {
49 let now = Instant::now();
50 let mut state = self.state.lock().await;
51 let entry = state.entries.get(key)?;
52 if now >= entry.expires_at {
53 state.entries.remove(key);
54 return None;
55 }
56 Some(if now >= entry.stale_at {
57 CacheLookup::Stale(entry.value.clone())
58 } else {
59 CacheLookup::Fresh(entry.value.clone())
60 })
61 }
62 pub async fn insert(
63 &self,
64 key: impl Into<String>,
65 value: V,
66 ttl: Duration,
67 stale_window: Duration,
68 ) -> Result<(), CacheError> {
69 if ttl.is_zero() || stale_window > ttl {
70 return Err(CacheError::Capacity);
71 }
72 let key = key.into();
73 let now = Instant::now();
74 let mut state = self.state.lock().await;
75 if state.entries.len() >= self.capacity && !state.entries.contains_key(&key) {
76 let victim = state
77 .entries
78 .keys()
79 .next()
80 .cloned()
81 .ok_or(CacheError::Capacity)?;
82 state.entries.remove(&victim);
83 }
84 state.entries.insert(
85 key,
86 Entry {
87 value,
88 stale_at: now + ttl.saturating_sub(stale_window),
89 expires_at: now + ttl,
90 },
91 );
92 Ok(())
93 }
94 pub async fn invalidate(&self, key: &str) {
95 self.state.lock().await.entries.remove(key);
96 }
97 pub async fn len(&self) -> usize {
98 self.state.lock().await.entries.len()
99 }
100 pub async fn is_empty(&self) -> bool {
101 self.len().await == 0
102 }
103 pub async fn get_or_compute<F, Fut>(
104 &self,
105 key: impl Into<String>,
106 ttl: Duration,
107 stale_window: Duration,
108 producer: F,
109 ) -> Result<V, CacheError>
110 where
111 F: FnOnce() -> Fut,
112 Fut: Future<Output = Result<V, String>> + Send,
113 {
114 let key = key.into();
115 if let Some(CacheLookup::Fresh(value) | CacheLookup::Stale(value)) = self.get(&key).await {
116 return Ok(value);
117 }
118 let receiver = {
119 let mut state = self.state.lock().await;
120 if let Some(waiters) = state.flights.get_mut(&key) {
121 let (sender, receiver) = oneshot::channel();
122 waiters.push(sender);
123 Some(receiver)
124 } else {
125 state.flights.insert(key.clone(), Vec::new());
126 None
127 }
128 };
129 if let Some(receiver) = receiver {
130 return receiver
131 .await
132 .map_err(|_| CacheError::Cancelled)?
133 .map_err(CacheError::Producer);
134 }
135 let result = producer().await;
136 let waiters = {
137 let mut state = self.state.lock().await;
138 if let Ok(value) = &result {
139 if !ttl.is_zero() && stale_window <= ttl {
140 if state.entries.len() >= self.capacity && !state.entries.contains_key(&key) {
141 if let Some(victim) = state.entries.keys().next().cloned() {
142 state.entries.remove(&victim);
143 }
144 }
145 state.entries.insert(
146 key.clone(),
147 Entry {
148 value: value.clone(),
149 stale_at: Instant::now() + ttl.saturating_sub(stale_window),
150 expires_at: Instant::now() + ttl,
151 },
152 );
153 }
154 }
155 state.flights.remove(&key).unwrap_or_default()
156 };
157 for waiter in waiters {
158 let _ = waiter.send(result.clone());
159 }
160 result.map_err(CacheError::Producer)
161 }
162}
163
164#[cfg(test)]
165mod tests {
166 use super::*;
167 use std::sync::atomic::{AtomicUsize, Ordering};
168 #[tokio::test]
169 async fn caches_fresh_and_stale_values() {
170 let cache = SingleFlightCache::new(2);
171 cache
172 .insert("a", 1, Duration::from_secs(1), Duration::from_millis(900))
173 .await
174 .unwrap();
175 assert_eq!(cache.get("a").await, Some(CacheLookup::Fresh(1)));
176 tokio::time::sleep(Duration::from_millis(150)).await;
177 assert!(matches!(cache.get("a").await, Some(CacheLookup::Stale(1))));
178 }
179 #[tokio::test]
180 async fn deduplicates_concurrent_misses() {
181 let cache = Arc::new(SingleFlightCache::new(2));
182 let calls = Arc::new(AtomicUsize::new(0));
183 let mut tasks = Vec::new();
184 for _ in 0..8 {
185 let cache = cache.clone();
186 let calls = calls.clone();
187 tasks.push(tokio::spawn(async move {
188 cache
189 .get_or_compute("key", Duration::from_secs(1), Duration::ZERO, || async {
190 calls.fetch_add(1, Ordering::SeqCst);
191 tokio::time::sleep(Duration::from_millis(10)).await;
192 Ok::<_, String>(42)
193 })
194 .await
195 .unwrap()
196 }));
197 }
198 for task in tasks {
199 assert_eq!(task.await.unwrap(), 42);
200 }
201 assert_eq!(calls.load(Ordering::SeqCst), 1);
202 }
203 #[tokio::test]
204 async fn expires_and_invalidates_entries() {
205 let cache = SingleFlightCache::new(1);
206 cache
207 .insert("a", "x", Duration::from_millis(10), Duration::ZERO)
208 .await
209 .unwrap();
210 cache.invalidate("a").await;
211 assert!(cache.is_empty().await);
212 }
213 #[tokio::test]
214 async fn bounds_capacity() {
215 let cache = SingleFlightCache::new(1);
216 cache
217 .insert("a", 1, Duration::from_secs(1), Duration::ZERO)
218 .await
219 .unwrap();
220 cache
221 .insert("b", 2, Duration::from_secs(1), Duration::ZERO)
222 .await
223 .unwrap();
224 assert_eq!(cache.len().await, 1);
225 }
226}