Skip to main content

yaiko_core/
singleflight_cache.rs

1//! Bounded cache with single-flight miss protection.
2
3use 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}