1use 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}