Skip to main content

spec_stream_cache/
eviction.rs

1//! # Cache Eviction Policies & Memory Pressure Management
2//!
3//! Provides intelligent sequence eviction strategies (LRU) when the physical
4//! KV-cache block pool encounters high memory pressure.
5
6use std::collections::{HashMap, VecDeque};
7use std::time::Instant;
8
9/// Abstract interface for sequence cache eviction policies.
10pub trait EvictionPolicy: Send + Sync {
11    /// Records or refreshes access activity for an active sequence.
12    fn record_access(&mut self, seq_id: u64);
13
14    /// Unregisters a sequence when it finishes or is dropped.
15    fn remove_sequence(&mut self, seq_id: u64);
16
17    /// Selects the best candidate sequence to evict under memory pressure.
18    fn select_eviction_candidate(&self) -> Option<u64>;
19
20    /// Number of tracked active sequences.
21    fn len(&self) -> usize;
22
23    /// Whether any sequences are currently tracked.
24    fn is_empty(&self) -> bool {
25        self.len() == 0
26    }
27}
28
29/// Least-Recently-Used (LRU) eviction policy tracking access timestamps.
30#[derive(Debug, Default)]
31pub struct LruEvictionPolicy {
32    queue: VecDeque<u64>,
33    timestamps: HashMap<u64, Instant>,
34}
35
36impl LruEvictionPolicy {
37    pub fn new() -> Self {
38        Self {
39            queue: VecDeque::new(),
40            timestamps: HashMap::new(),
41        }
42    }
43}
44
45impl EvictionPolicy for LruEvictionPolicy {
46    fn record_access(&mut self, seq_id: u64) {
47        self.timestamps.insert(seq_id, Instant::now());
48        self.queue.retain(|&id| id != seq_id);
49        self.queue.push_back(seq_id);
50    }
51
52    fn remove_sequence(&mut self, seq_id: u64) {
53        self.timestamps.remove(&seq_id);
54        self.queue.retain(|&id| id != seq_id);
55    }
56
57    fn select_eviction_candidate(&self) -> Option<u64> {
58        self.queue.front().copied()
59    }
60
61    fn len(&self) -> usize {
62        self.queue.len()
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_lru_eviction_policy() {
72        let mut policy = LruEvictionPolicy::new();
73        policy.record_access(101);
74        policy.record_access(102);
75        policy.record_access(103);
76
77        // 101 was accessed first -> least recently used
78        assert_eq!(policy.select_eviction_candidate(), Some(101));
79
80        // Access 101 again -> 102 becomes least recently used
81        policy.record_access(101);
82        assert_eq!(policy.select_eviction_candidate(), Some(102));
83
84        // Remove 102 -> 103 becomes candidate
85        policy.remove_sequence(102);
86        assert_eq!(policy.select_eviction_candidate(), Some(103));
87    }
88}