1use std::collections::BTreeMap;
13use std::sync::Arc;
14
15use crate::entry::Entry;
16
17#[derive(Debug, Clone, Copy, PartialEq)]
19pub struct EvictionConfig {
20 pub budget_bytes: usize,
23 pub half_life_commits: f64,
29}
30
31impl Default for EvictionConfig {
32 fn default() -> Self {
33 EvictionConfig {
34 budget_bytes: 64 * 1024 * 1024,
37 half_life_commits: 1000.0,
38 }
39 }
40}
41
42impl EvictionConfig {
43 pub fn with_budget(budget_bytes: usize) -> Self {
45 EvictionConfig {
46 budget_bytes,
47 ..Self::default()
48 }
49 }
50
51 #[must_use]
53 pub fn half_life(mut self, commits: f64) -> Self {
54 self.half_life_commits = commits;
55 self
56 }
57}
58
59pub fn score(importance: f32, head_seq: u64, last_access_seq: u64, half_life: f64) -> f64 {
65 let age = head_seq.saturating_sub(last_access_seq) as f64;
68 if half_life <= 0.0 {
69 return f64::from(importance);
71 }
72 f64::from(importance) * 0.5_f64.powf(age / half_life)
73}
74
75pub fn entry_size(key: &str, entry: &Entry) -> usize {
81 const OVERHEAD: usize = 128;
83 let embedding = entry.embedding.as_ref().map_or(0, |v| v.len() * 4);
84 let meta: usize = entry.meta.iter().map(|(k, v)| k.len() + v.len() + 48).sum();
85 OVERHEAD + key.len() + entry.value.len() + embedding + meta
86}
87
88#[derive(Debug, Clone)]
90pub struct Evicted {
91 pub key: String,
93 pub entry: Arc<Entry>,
95 pub score: f64,
97 pub bytes: usize,
99}
100
101pub fn choose<'a, I>(
106 entries: I,
107 head_seq: u64,
108 access: &BTreeMap<String, u64>,
109 config: &EvictionConfig,
110) -> Vec<Evicted>
111where
112 I: Iterator<Item = (&'a String, &'a Arc<Entry>)>,
113{
114 let mut scored: Vec<Evicted> = entries
115 .map(|(key, entry)| {
116 let last = access
119 .get(key)
120 .copied()
121 .unwrap_or(entry.last_access_seq)
122 .max(entry.last_access_seq);
123 Evicted {
124 score: score(entry.importance, head_seq, last, config.half_life_commits),
125 bytes: entry_size(key, entry),
126 key: key.clone(),
127 entry: Arc::clone(entry),
128 }
129 })
130 .collect();
131
132 let total: usize = scored.iter().map(|e| e.bytes).sum();
133 if total <= config.budget_bytes {
134 return Vec::new();
135 }
136
137 scored.sort_by(|a, b| a.score.total_cmp(&b.score).then_with(|| a.key.cmp(&b.key)));
140
141 let mut freed = 0usize;
142 let mut chosen = Vec::new();
143 for candidate in scored {
144 if total - freed <= config.budget_bytes {
145 break;
146 }
147 freed += candidate.bytes;
148 chosen.push(candidate);
149 }
150 chosen
151}
152
153pub type OnEvict = Arc<dyn Fn(&[Evicted]) + Send + Sync>;
160
161#[cfg(test)]
162mod tests {
163 use super::*;
164 use crate::Value;
165
166 fn entry(importance: f32, last_access: u64, bytes: usize) -> Arc<Entry> {
167 let mut e = Value::new("x".repeat(bytes)).with_importance(importance);
168 e.importance = importance;
169 Arc::new(e.into_entry(last_access, last_access))
170 }
171
172 #[test]
173 fn the_score_is_the_formula_in_the_spec() {
174 assert!((score(1.0, 100, 0, 100.0) - 0.5).abs() < 1e-12);
176 assert!((score(1.0, 200, 0, 100.0) - 0.25).abs() < 1e-12);
177 assert!((score(0.8, 100, 100, 100.0) - f64::from(0.8_f32)).abs() < 1e-12);
181 assert!((score(0.5, 100, 0, 100.0) - 0.25).abs() < 1e-12);
183 }
184
185 #[test]
186 fn importance_beats_recency_when_it_should() {
187 let important_but_old = score(1.0, 100, 0, 100.0);
191 let worthless_but_new = score(0.1, 100, 100, 100.0);
192 assert!(important_but_old > worthless_but_new);
193 }
194
195 #[test]
196 fn nothing_is_evicted_under_budget() {
197 let entries = [("a".to_owned(), entry(0.5, 0, 10))];
198 let refs: Vec<(&String, &Arc<Entry>)> = entries.iter().map(|(k, v)| (k, v)).collect();
199 let chosen = choose(
200 refs.into_iter(),
201 0,
202 &BTreeMap::new(),
203 &EvictionConfig::with_budget(1024 * 1024),
204 );
205 assert!(chosen.is_empty());
206 }
207
208 #[test]
209 fn the_lowest_scoring_entries_go_first() {
210 let entries = [
211 ("keep".to_owned(), entry(1.0, 100, 100)),
212 ("drop".to_owned(), entry(0.01, 0, 100)),
213 ("middle".to_owned(), entry(0.5, 50, 100)),
214 ];
215 let refs: Vec<(&String, &Arc<Entry>)> = entries.iter().map(|(k, v)| (k, v)).collect();
216 let total: usize = entries.iter().map(|(k, e)| entry_size(k, e)).sum::<usize>();
217
218 let chosen = choose(
220 refs.into_iter(),
221 100,
222 &BTreeMap::new(),
223 &EvictionConfig::with_budget(total - 1).half_life(50.0),
224 );
225 assert_eq!(chosen.len(), 1);
226 assert_eq!(chosen[0].key, "drop");
227 }
228
229 #[test]
230 fn ties_break_on_the_key_so_the_choice_is_reproducible() {
231 let entries: Vec<(String, Arc<Entry>)> = ["c", "a", "b"]
232 .iter()
233 .map(|k| ((*k).to_owned(), entry(0.5, 0, 100)))
234 .collect();
235 let run = || {
236 let refs: Vec<(&String, &Arc<Entry>)> = entries.iter().map(|(k, v)| (k, v)).collect();
237 choose(
238 refs.into_iter(),
239 0,
240 &BTreeMap::new(),
241 &EvictionConfig::with_budget(entry_size("a", &entries[0].1) * 2),
242 )
243 .into_iter()
244 .map(|e| e.key)
245 .collect::<Vec<_>>()
246 };
247 assert_eq!(run(), vec!["a".to_owned()]);
248 assert_eq!(run(), run());
249 }
250
251 #[test]
252 fn a_recorded_read_protects_an_entry() {
253 let entries = [
256 ("read".to_owned(), entry(0.5, 0, 100)),
257 ("unread".to_owned(), entry(0.5, 0, 100)),
258 ];
259 let refs: Vec<(&String, &Arc<Entry>)> = entries.iter().map(|(k, v)| (k, v)).collect();
260 let mut access = BTreeMap::new();
261 access.insert("read".to_owned(), 100u64);
262
263 let chosen = choose(
264 refs.into_iter(),
265 100,
266 &access,
267 &EvictionConfig::with_budget(entry_size("read", &entries[0].1) + 1).half_life(10.0),
268 );
269 assert_eq!(chosen.len(), 1);
270 assert_eq!(chosen[0].key, "unread");
271 }
272}