Skip to main content

memfork_core/
evict.rs

1//! Semantic eviction (DESIGN §4.4).
2//!
3//! When a branch outgrows its memory budget, the entries that go are the ones
4//! worth least: low importance, long unread. Not the oldest, which is what an
5//! LRU would take — an agent's most important memory is often one it wrote
6//! early and has not needed since.
7//!
8//! Eviction is itself a commit, carrying [`Op::Evict`] rather than
9//! [`Op::Delete`], so it appears in the log as what it was and time travel can
10//! still reach the evicted value for as long as history is retained.
11
12use std::collections::BTreeMap;
13use std::sync::Arc;
14
15use crate::entry::Entry;
16
17/// When to evict, and what to keep.
18#[derive(Debug, Clone, Copy, PartialEq)]
19pub struct EvictionConfig {
20    /// Approximate ceiling on a branch's entries, in bytes. Accounting is an
21    /// estimate: it counts the data, not the allocator's overhead.
22    pub budget_bytes: usize,
23    /// How many commits it takes for an unread entry's score to halve.
24    ///
25    /// Small values forget quickly; large values keep things around on the
26    /// strength of one early read. Measured in commits rather than seconds,
27    /// so a database that sits idle forgets nothing.
28    pub half_life_commits: f64,
29}
30
31impl Default for EvictionConfig {
32    fn default() -> Self {
33        EvictionConfig {
34            // Enough for a large working set, small enough to bound a
35            // long-running agent. Callers with a real figure should set one.
36            budget_bytes: 64 * 1024 * 1024,
37            half_life_commits: 1000.0,
38        }
39    }
40}
41
42impl EvictionConfig {
43    /// A budget in bytes, with the default half-life.
44    pub fn with_budget(budget_bytes: usize) -> Self {
45        EvictionConfig {
46            budget_bytes,
47            ..Self::default()
48        }
49    }
50
51    /// Set the half-life.
52    #[must_use]
53    pub fn half_life(mut self, commits: f64) -> Self {
54        self.half_life_commits = commits;
55        self
56    }
57}
58
59/// What an entry is worth keeping, per DESIGN §4.4:
60/// `importance * 0.5^((head_seq - last_access_seq) / half_life)`.
61///
62/// Deterministic: the same inputs give the same score on every platform, so
63/// two databases fed the same operations evict the same entries.
64pub fn score(importance: f32, head_seq: u64, last_access_seq: u64, half_life: f64) -> f64 {
65    // An entry cannot have been read in the future; if the clock says
66    // otherwise, treat it as read now rather than scoring it above 1.
67    let age = head_seq.saturating_sub(last_access_seq) as f64;
68    if half_life <= 0.0 {
69        // No decay at all: importance alone decides.
70        return f64::from(importance);
71    }
72    f64::from(importance) * 0.5_f64.powf(age / half_life)
73}
74
75/// Approximate stored size of one entry, in bytes.
76///
77/// Counts the data the caller gave us plus a fixed allowance for the
78/// bookkeeping around it. It is an estimate, and DESIGN §4.4 says so: the point
79/// is a stable ordering and a bound that tracks reality, not an exact figure.
80pub fn entry_size(key: &str, entry: &Entry) -> usize {
81    /// `Arc` header, sequence numbers, importance, the map node holding it.
82    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/// A key chosen for eviction, and why.
89#[derive(Debug, Clone)]
90pub struct Evicted {
91    /// The key that was evicted.
92    pub key: String,
93    /// The entry as it was.
94    pub entry: Arc<Entry>,
95    /// The score it was evicted at.
96    pub score: f64,
97    /// How many bytes it was holding.
98    pub bytes: usize,
99}
100
101/// Choose what to evict from a branch to get back under budget.
102///
103/// Lowest score first; ties broken by key ascending, so the choice is
104/// reproducible rather than dependent on iteration order.
105pub 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            // An entry never read since it was written falls back to when it
117            // was written, which is what the entry itself records.
118            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    // `total_cmp` is a total order over every f64, so the comparator can never
138    // be inconsistent, and the key tie-break makes the result reproducible.
139    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
153/// Called with the entries about to be evicted, before they go.
154///
155/// DESIGN §4.4: the hook receives them first, so a caller can write them
156/// somewhere durable — a summary, a vector store, a file — rather than lose
157/// them. Eviction proceeds whatever the hook does; it is a notification, not a
158/// veto, because a hook that could block eviction could also exhaust memory.
159pub 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        // Unread for exactly one half-life: half the importance.
175        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        // Just written: importance, undecayed. Compared against the f32 value
178        // widened to f64, because 0.8 is not exactly representable in f32 and
179        // the score carries that through rather than hiding it.
180        assert!((score(0.8, 100, 100, 100.0) - f64::from(0.8_f32)).abs() < 1e-12);
181        // Importance scales it linearly, and 0.5 is exact in both widths.
182        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        // A important entry unread for one half-life still outranks a
188        // worthless one written moments ago. That is the whole point of
189        // scoring rather than using an LRU.
190        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        // A budget that forces exactly one eviction.
219        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        // The side structure is what makes reading count: without it, an entry
254        // written long ago and read constantly would look stale.
255        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}