use std::collections::BTreeMap;
use std::sync::Arc;
use crate::entry::Entry;
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct EvictionConfig {
pub budget_bytes: usize,
pub half_life_commits: f64,
}
impl Default for EvictionConfig {
fn default() -> Self {
EvictionConfig {
budget_bytes: 64 * 1024 * 1024,
half_life_commits: 1000.0,
}
}
}
impl EvictionConfig {
pub fn with_budget(budget_bytes: usize) -> Self {
EvictionConfig {
budget_bytes,
..Self::default()
}
}
#[must_use]
pub fn half_life(mut self, commits: f64) -> Self {
self.half_life_commits = commits;
self
}
}
pub fn score(importance: f32, head_seq: u64, last_access_seq: u64, half_life: f64) -> f64 {
let age = head_seq.saturating_sub(last_access_seq) as f64;
if half_life <= 0.0 {
return f64::from(importance);
}
f64::from(importance) * 0.5_f64.powf(age / half_life)
}
pub fn entry_size(key: &str, entry: &Entry) -> usize {
const OVERHEAD: usize = 128;
let embedding = entry.embedding.as_ref().map_or(0, |v| v.len() * 4);
let meta: usize = entry.meta.iter().map(|(k, v)| k.len() + v.len() + 48).sum();
OVERHEAD + key.len() + entry.value.len() + embedding + meta
}
#[derive(Debug, Clone)]
pub struct Evicted {
pub key: String,
pub entry: Arc<Entry>,
pub score: f64,
pub bytes: usize,
}
pub fn choose<'a, I>(
entries: I,
head_seq: u64,
access: &BTreeMap<String, u64>,
config: &EvictionConfig,
) -> Vec<Evicted>
where
I: Iterator<Item = (&'a String, &'a Arc<Entry>)>,
{
let mut scored: Vec<Evicted> = entries
.map(|(key, entry)| {
let last = access
.get(key)
.copied()
.unwrap_or(entry.last_access_seq)
.max(entry.last_access_seq);
Evicted {
score: score(entry.importance, head_seq, last, config.half_life_commits),
bytes: entry_size(key, entry),
key: key.clone(),
entry: Arc::clone(entry),
}
})
.collect();
let total: usize = scored.iter().map(|e| e.bytes).sum();
if total <= config.budget_bytes {
return Vec::new();
}
scored.sort_by(|a, b| a.score.total_cmp(&b.score).then_with(|| a.key.cmp(&b.key)));
let mut freed = 0usize;
let mut chosen = Vec::new();
for candidate in scored {
if total - freed <= config.budget_bytes {
break;
}
freed += candidate.bytes;
chosen.push(candidate);
}
chosen
}
pub type OnEvict = Arc<dyn Fn(&[Evicted]) + Send + Sync>;
#[cfg(test)]
mod tests {
use super::*;
use crate::Value;
fn entry(importance: f32, last_access: u64, bytes: usize) -> Arc<Entry> {
let mut e = Value::new("x".repeat(bytes)).with_importance(importance);
e.importance = importance;
Arc::new(e.into_entry(last_access, last_access))
}
#[test]
fn the_score_is_the_formula_in_the_spec() {
assert!((score(1.0, 100, 0, 100.0) - 0.5).abs() < 1e-12);
assert!((score(1.0, 200, 0, 100.0) - 0.25).abs() < 1e-12);
assert!((score(0.8, 100, 100, 100.0) - f64::from(0.8_f32)).abs() < 1e-12);
assert!((score(0.5, 100, 0, 100.0) - 0.25).abs() < 1e-12);
}
#[test]
fn importance_beats_recency_when_it_should() {
let important_but_old = score(1.0, 100, 0, 100.0);
let worthless_but_new = score(0.1, 100, 100, 100.0);
assert!(important_but_old > worthless_but_new);
}
#[test]
fn nothing_is_evicted_under_budget() {
let entries = [("a".to_owned(), entry(0.5, 0, 10))];
let refs: Vec<(&String, &Arc<Entry>)> = entries.iter().map(|(k, v)| (k, v)).collect();
let chosen = choose(
refs.into_iter(),
0,
&BTreeMap::new(),
&EvictionConfig::with_budget(1024 * 1024),
);
assert!(chosen.is_empty());
}
#[test]
fn the_lowest_scoring_entries_go_first() {
let entries = [
("keep".to_owned(), entry(1.0, 100, 100)),
("drop".to_owned(), entry(0.01, 0, 100)),
("middle".to_owned(), entry(0.5, 50, 100)),
];
let refs: Vec<(&String, &Arc<Entry>)> = entries.iter().map(|(k, v)| (k, v)).collect();
let total: usize = entries.iter().map(|(k, e)| entry_size(k, e)).sum::<usize>();
let chosen = choose(
refs.into_iter(),
100,
&BTreeMap::new(),
&EvictionConfig::with_budget(total - 1).half_life(50.0),
);
assert_eq!(chosen.len(), 1);
assert_eq!(chosen[0].key, "drop");
}
#[test]
fn ties_break_on_the_key_so_the_choice_is_reproducible() {
let entries: Vec<(String, Arc<Entry>)> = ["c", "a", "b"]
.iter()
.map(|k| ((*k).to_owned(), entry(0.5, 0, 100)))
.collect();
let run = || {
let refs: Vec<(&String, &Arc<Entry>)> = entries.iter().map(|(k, v)| (k, v)).collect();
choose(
refs.into_iter(),
0,
&BTreeMap::new(),
&EvictionConfig::with_budget(entry_size("a", &entries[0].1) * 2),
)
.into_iter()
.map(|e| e.key)
.collect::<Vec<_>>()
};
assert_eq!(run(), vec!["a".to_owned()]);
assert_eq!(run(), run());
}
#[test]
fn a_recorded_read_protects_an_entry() {
let entries = [
("read".to_owned(), entry(0.5, 0, 100)),
("unread".to_owned(), entry(0.5, 0, 100)),
];
let refs: Vec<(&String, &Arc<Entry>)> = entries.iter().map(|(k, v)| (k, v)).collect();
let mut access = BTreeMap::new();
access.insert("read".to_owned(), 100u64);
let chosen = choose(
refs.into_iter(),
100,
&access,
&EvictionConfig::with_budget(entry_size("read", &entries[0].1) + 1).half_life(10.0),
);
assert_eq!(chosen.len(), 1);
assert_eq!(chosen[0].key, "unread");
}
}