Skip to main content

patronus_ark/cache/
memory.rs

1// SPDX-License-Identifier: GPL-3.0-only
2use std::collections::HashMap;
3use std::sync::Mutex;
4
5use super::{CacheError, CacheKey, CachedModelOutput, ExactCacheStore};
6
7#[derive(Debug, Clone, Copy)]
8pub struct MemoryCacheConfig {
9    pub max_entries: usize,
10    pub max_bytes: usize,
11}
12
13impl Default for MemoryCacheConfig {
14    fn default() -> Self {
15        Self {
16            max_entries: 100_000,
17            max_bytes: 128 * 1024 * 1024,
18        }
19    }
20}
21
22struct Entry {
23    output: CachedModelOutput,
24    previous: Option<CacheKey>,
25    next: Option<CacheKey>,
26    estimated_bytes: usize,
27}
28
29#[derive(Default)]
30struct State {
31    entries: HashMap<CacheKey, Entry>,
32    used_bytes: usize,
33    oldest: Option<CacheKey>,
34    newest: Option<CacheKey>,
35}
36
37impl State {
38    fn unlink(&mut self, key: CacheKey) {
39        let entry = &self.entries[&key];
40        let (previous, next) = (entry.previous, entry.next);
41        if let Some(previous) = previous {
42            self.entries.get_mut(&previous).unwrap().next = next;
43        } else {
44            self.oldest = next;
45        }
46        if let Some(next) = next {
47            self.entries.get_mut(&next).unwrap().previous = previous;
48        } else {
49            self.newest = previous;
50        }
51    }
52
53    fn touch(&mut self, key: CacheKey) {
54        if self.newest == Some(key) {
55            return;
56        }
57        self.unlink(key);
58        self.append(key);
59    }
60
61    fn append(&mut self, key: CacheKey) {
62        if let Some(newest) = self.newest {
63            self.entries.get_mut(&newest).unwrap().next = Some(key);
64        } else {
65            self.oldest = Some(key);
66        }
67        let entry = self.entries.get_mut(&key).unwrap();
68        entry.previous = self.newest;
69        entry.next = None;
70        self.newest = Some(key);
71    }
72
73    fn remove(&mut self, key: &CacheKey) {
74        if !self.entries.contains_key(key) {
75            return;
76        }
77        self.unlink(*key);
78        let entry = self.entries.remove(key).unwrap();
79        self.used_bytes = self.used_bytes.saturating_sub(entry.estimated_bytes);
80    }
81}
82
83pub(crate) struct MemoryCacheStore {
84    config: MemoryCacheConfig,
85    state: Mutex<State>,
86}
87
88impl MemoryCacheStore {
89    pub(crate) fn new(config: MemoryCacheConfig) -> Self {
90        Self {
91            config,
92            state: Mutex::new(State::default()),
93        }
94    }
95
96    #[cfg(test)]
97    fn len(&self) -> usize {
98        self.state
99            .lock()
100            .expect("cache mutex poisoned")
101            .entries
102            .len()
103    }
104}
105
106impl ExactCacheStore for MemoryCacheStore {
107    fn get(
108        &self,
109        key: &CacheKey,
110        now_unix_ms: u64,
111    ) -> Result<Option<CachedModelOutput>, CacheError> {
112        let mut state = self.state.lock().expect("cache mutex poisoned");
113        if state
114            .entries
115            .get(key)
116            .is_some_and(|entry| entry.output.is_expired(now_unix_ms))
117        {
118            state.remove(key);
119            return Ok(None);
120        }
121
122        let Some(entry) = state.entries.get(key) else {
123            return Ok(None);
124        };
125        let output = entry.output.clone();
126        state.touch(*key);
127        Ok(Some(output))
128    }
129
130    fn put(&self, key: CacheKey, output: CachedModelOutput) -> Result<(), CacheError> {
131        let estimated_bytes = output.estimated_bytes();
132        if self.config.max_entries == 0
133            || self.config.max_bytes == 0
134            || estimated_bytes > self.config.max_bytes
135        {
136            return Ok(());
137        }
138
139        let mut state = self.state.lock().expect("cache mutex poisoned");
140        state.remove(&key);
141        state.used_bytes = state.used_bytes.saturating_add(estimated_bytes);
142        state.entries.insert(
143            key,
144            Entry {
145                output,
146                previous: None,
147                next: None,
148                estimated_bytes,
149            },
150        );
151        state.append(key);
152        prune(&mut state, self.config);
153        Ok(())
154    }
155
156    fn remove_expired(&self, now_unix_ms: u64) -> Result<usize, CacheError> {
157        let mut state = self.state.lock().expect("cache mutex poisoned");
158        let expired = state
159            .entries
160            .iter()
161            .filter_map(|(key, entry)| entry.output.is_expired(now_unix_ms).then_some(*key))
162            .collect::<Vec<_>>();
163        let removed = expired.len();
164        for key in expired {
165            state.remove(&key);
166        }
167        Ok(removed)
168    }
169
170    fn remove_created_before(&self, until_unix_ms: u64) -> Result<usize, CacheError> {
171        let mut state = self.state.lock().expect("cache mutex poisoned");
172        let stale = state
173            .entries
174            .iter()
175            .filter_map(|(key, entry)| {
176                (entry.output.created_at_unix_ms < until_unix_ms).then_some(*key)
177            })
178            .collect::<Vec<_>>();
179        let removed = stale.len();
180        for key in stale {
181            state.remove(&key);
182        }
183        Ok(removed)
184    }
185}
186
187fn prune(state: &mut State, config: MemoryCacheConfig) {
188    while state.entries.len() > config.max_entries || state.used_bytes > config.max_bytes {
189        let key = state.oldest.expect("nonempty cache has an oldest entry");
190        state.remove(&key);
191    }
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197    use crate::cache::{CacheNamespace, CachedHeadOutput};
198
199    fn key(value: &str) -> CacheKey {
200        CacheKey::for_chunk(
201            CacheNamespace::from_components(1, &[b"test"]),
202            value.as_bytes(),
203        )
204    }
205
206    fn output(expires_at_unix_ms: u64) -> CachedModelOutput {
207        output_created(10, expires_at_unix_ms)
208    }
209
210    fn output_created(created_at_unix_ms: u64, expires_at_unix_ms: u64) -> CachedModelOutput {
211        CachedModelOutput {
212            schema_version: 1,
213            heads: vec![CachedHeadOutput {
214                head: "test".to_string(),
215                logits: vec![0.1, 0.9],
216            }],
217            created_at_unix_ms,
218            expires_at_unix_ms,
219        }
220    }
221
222    #[test]
223    fn expired_entries_are_misses_and_removed() {
224        let store = MemoryCacheStore::new(MemoryCacheConfig::default());
225        store.put(key("expired"), output(20)).unwrap();
226
227        assert!(store.get(&key("expired"), 20).unwrap().is_none());
228        assert_eq!(store.len(), 0);
229    }
230
231    #[test]
232    fn cleanup_removes_only_expired_entries() {
233        let store = MemoryCacheStore::new(MemoryCacheConfig::default());
234        store.put(key("expired"), output(20)).unwrap();
235        store.put(key("current"), output(30)).unwrap();
236
237        assert_eq!(store.remove_expired(20).unwrap(), 1);
238        assert!(store.get(&key("expired"), 20).unwrap().is_none());
239        assert!(store.get(&key("current"), 20).unwrap().is_some());
240    }
241
242    #[test]
243    fn cleanup_removes_entries_created_before_cutoff() {
244        let store = MemoryCacheStore::new(MemoryCacheConfig::default());
245        store.put(key("old"), output_created(10, 100)).unwrap();
246        store.put(key("new"), output_created(20, 100)).unwrap();
247
248        assert_eq!(store.remove_created_before(20).unwrap(), 1);
249        assert!(store.get(&key("old"), 20).unwrap().is_none());
250        assert!(store.get(&key("new"), 20).unwrap().is_some());
251    }
252
253    #[test]
254    fn least_recently_used_entry_is_evicted() {
255        let store = MemoryCacheStore::new(MemoryCacheConfig {
256            max_entries: 2,
257            max_bytes: usize::MAX,
258        });
259        store.put(key("first"), output(100)).unwrap();
260        store.put(key("second"), output(100)).unwrap();
261        store.get(&key("first"), 10).unwrap();
262        store.put(key("third"), output(100)).unwrap();
263
264        assert!(store.get(&key("first"), 10).unwrap().is_some());
265        assert!(store.get(&key("second"), 10).unwrap().is_none());
266        assert!(store.get(&key("third"), 10).unwrap().is_some());
267    }
268
269    #[test]
270    fn oversized_entry_is_not_inserted() {
271        let store = MemoryCacheStore::new(MemoryCacheConfig {
272            max_entries: 10,
273            max_bytes: 1,
274        });
275
276        store.put(key("large"), output(100)).unwrap();
277
278        assert_eq!(store.len(), 0);
279    }
280
281    #[test]
282    fn replacements_and_cleanup_preserve_recency_and_byte_accounting() {
283        let bytes = output(100).estimated_bytes();
284        let store = MemoryCacheStore::new(MemoryCacheConfig {
285            max_entries: 10,
286            max_bytes: bytes * 3,
287        });
288        store.put(key("first"), output(20)).unwrap();
289        store.put(key("second"), output(100)).unwrap();
290        store.put(key("third"), output(100)).unwrap();
291        store.put(key("second"), output(100)).unwrap();
292        assert_eq!(store.remove_expired(20).unwrap(), 1);
293        store.put(key("fourth"), output(100)).unwrap();
294        store.put(key("fifth"), output(100)).unwrap();
295        assert!(store.get(&key("third"), 20).unwrap().is_none());
296        assert!(store.get(&key("second"), 20).unwrap().is_some());
297        let state = store.state.lock().unwrap();
298        assert_eq!(state.used_bytes, bytes * 3);
299        assert_eq!(state.oldest, Some(key("fourth")));
300        assert_eq!(state.newest, Some(key("second")));
301    }
302
303    #[test]
304    fn byte_limit_can_evict_multiple_entries_and_empty_cache_can_be_reused() {
305        let small = output(100);
306        let bytes = small.estimated_bytes();
307        let mut large = small.clone();
308        large.heads[0].logits.resize(bytes / 4 + 4, 0.0);
309        let large_bytes = large.estimated_bytes();
310        assert!(large_bytes > bytes * 2);
311        let store = MemoryCacheStore::new(MemoryCacheConfig {
312            max_entries: 10,
313            max_bytes: large_bytes,
314        });
315        store.put(key("first"), small.clone()).unwrap();
316        store.put(key("second"), small.clone()).unwrap();
317        store.put(key("large"), large).unwrap();
318        assert_eq!(store.len(), 1);
319        assert_eq!(store.remove_expired(100).unwrap(), 1);
320        store.put(key("fresh"), small).unwrap();
321        assert!(store.get(&key("fresh"), 20).unwrap().is_some());
322        let state = store.state.lock().unwrap();
323        assert_eq!(state.oldest, Some(key("fresh")));
324        assert_eq!(state.newest, state.oldest);
325        assert_eq!(state.used_bytes, bytes);
326    }
327}