grafos_cache/
ttl.rs

1//! TTL-driven object cache with poll-based expiry pruning.
2//!
3//! [`TtlObjectCache`] stores values with per-entry TTLs and tracks their
4//! locations via [`MemRegionLocator`]. Expired entries are removed by
5//! calling [`tick`](TtlObjectCache::tick) or
6//! [`prune_expired`](TtlObjectCache::prune_expired) with the current
7//! unix timestamp.
8//!
9//! The cache is integrated with [`RenewalPolicy`] for configuring
10//! renewal thresholds, though actual lease renewal is the caller's
11//! responsibility.
12
13extern crate alloc;
14use alloc::collections::BTreeMap;
15use alloc::string::String;
16use alloc::vec::Vec;
17
18use grafos_leasekit::RenewalPolicy;
19use grafos_locator::locator::MemRegionLocator;
20
21/// Statistics returned by [`TtlObjectCache::tick`].
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub struct CacheStats {
24    /// Total entries after pruning.
25    pub total: usize,
26    /// Number of entries pruned in this tick.
27    pub pruned: usize,
28    /// Number of entries that will expire within 25% of their original TTL.
29    pub near_expiry: usize,
30}
31
32struct CacheEntry<V> {
33    value: V,
34    locator: MemRegionLocator,
35    expires_at: u64,
36    created_at: u64,
37    last_accessed: u64,
38}
39
40/// Object cache with per-entry TTL and poll-driven expiry.
41///
42/// Values are indexed by string keys and associated with a
43/// [`MemRegionLocator`] describing their location in fabric memory.
44/// Expired entries are not returned by [`get`](Self::get) and are
45/// removed by [`prune_expired`](Self::prune_expired) or
46/// [`tick`](Self::tick).
47///
48/// # Example
49///
50/// ```rust
51/// use grafos_cache::ttl::{TtlObjectCache, CacheStats};
52/// use grafos_leasekit::RenewalPolicy;
53/// use grafos_locator::locator::MemRegionLocator;
54///
55/// let mut cache = TtlObjectCache::<u64>::new(RenewalPolicy::default());
56/// let loc = MemRegionLocator::new(1, 0, 1024);
57///
58/// cache.put("sensor-a".into(), 42, loc, 60, 1000);
59/// assert_eq!(cache.get("sensor-a", 1030), Some(&42));
60/// assert_eq!(cache.get("sensor-a", 1061), None); // expired
61/// ```
62pub struct TtlObjectCache<V> {
63    index: BTreeMap<String, CacheEntry<V>>,
64    renewal_policy: RenewalPolicy,
65}
66
67impl<V> TtlObjectCache<V> {
68    /// Create a new empty cache with the given renewal policy.
69    pub fn new(policy: RenewalPolicy) -> Self {
70        TtlObjectCache {
71            index: BTreeMap::new(),
72            renewal_policy: policy,
73        }
74    }
75
76    /// Look up a value by key.
77    ///
78    /// Returns `None` if the key does not exist or has expired. On a
79    /// successful hit, `last_accessed` is updated to `now`.
80    pub fn get(&mut self, key: &str, now: u64) -> Option<&V> {
81        let entry = self.index.get_mut(key)?;
82        if now >= entry.expires_at {
83            return None;
84        }
85        entry.last_accessed = now;
86        Some(&entry.value)
87    }
88
89    /// Look up the locator for a cached entry.
90    ///
91    /// Returns `None` if the key does not exist or has expired.
92    pub fn locator(&mut self, key: &str, now: u64) -> Option<&MemRegionLocator> {
93        let entry = self.index.get_mut(key)?;
94        if now >= entry.expires_at {
95            return None;
96        }
97        entry.last_accessed = now;
98        Some(&entry.locator)
99    }
100
101    /// Insert or replace a cached value with the given TTL.
102    ///
103    /// `locator` tracks the value's location in fabric memory.
104    /// `ttl_secs` is the time-to-live from `now`.
105    pub fn put(
106        &mut self,
107        key: String,
108        value: V,
109        locator: MemRegionLocator,
110        ttl_secs: u64,
111        now: u64,
112    ) {
113        let entry = CacheEntry {
114            value,
115            locator,
116            expires_at: now.saturating_add(ttl_secs),
117            created_at: now,
118            last_accessed: now,
119        };
120        self.index.insert(key, entry);
121    }
122
123    /// Remove an entry by key, returning the value if it existed.
124    pub fn remove(&mut self, key: &str) -> Option<V> {
125        self.index.remove(key).map(|e| e.value)
126    }
127
128    /// Remove all expired entries, returning the number pruned.
129    pub fn prune_expired(&mut self, now: u64) -> usize {
130        let expired_keys: Vec<String> = self
131            .index
132            .iter()
133            .filter(|(_, e)| now >= e.expires_at)
134            .map(|(k, _)| k.clone())
135            .collect();
136        let count = expired_keys.len();
137        for key in expired_keys {
138            self.index.remove(&key);
139        }
140        count
141    }
142
143    /// Prune expired entries and return cache statistics.
144    ///
145    /// An entry is "near expiry" if its remaining TTL is at most 25% of
146    /// its original TTL (i.e. it has consumed 75% or more of its lifetime).
147    pub fn tick(&mut self, now: u64) -> CacheStats {
148        let pruned = self.prune_expired(now);
149        let mut near_expiry = 0;
150        for entry in self.index.values() {
151            let total_ttl = entry.expires_at.saturating_sub(entry.created_at);
152            let remaining = entry.expires_at.saturating_sub(now);
153            // Near expiry: remaining <= 25% of total TTL
154            if total_ttl > 0 && remaining * 4 <= total_ttl {
155                near_expiry += 1;
156            }
157        }
158        CacheStats {
159            total: self.index.len(),
160            pruned,
161            near_expiry,
162        }
163    }
164
165    /// Number of entries currently in the cache (including expired but
166    /// not yet pruned).
167    pub fn len(&self) -> usize {
168        self.index.len()
169    }
170
171    /// Returns `true` if the cache contains no entries.
172    pub fn is_empty(&self) -> bool {
173        self.index.is_empty()
174    }
175
176    /// Access the renewal policy associated with this cache.
177    pub fn renewal_policy(&self) -> &RenewalPolicy {
178        &self.renewal_policy
179    }
180}
181
182#[cfg(test)]
183mod tests {
184    use super::*;
185    use grafos_locator::locator::MemRegionLocator;
186
187    fn make_locator(id: u128) -> MemRegionLocator {
188        MemRegionLocator::new(id, 0, 1024)
189    }
190
191    #[test]
192    fn put_and_get_within_ttl() {
193        let mut cache = TtlObjectCache::new(RenewalPolicy::default());
194        cache.put("key-a".into(), 42u64, make_locator(1), 60, 1000);
195        cache.put("key-b".into(), 99u64, make_locator(2), 120, 1000);
196
197        assert_eq!(cache.get("key-a", 1030), Some(&42));
198        assert_eq!(cache.get("key-b", 1100), Some(&99));
199        assert_eq!(cache.get("missing", 1000), None);
200        assert_eq!(cache.len(), 2);
201    }
202
203    #[test]
204    fn get_after_ttl_expiry_returns_none() {
205        let mut cache = TtlObjectCache::new(RenewalPolicy::default());
206        cache.put("ephemeral".into(), 7u32, make_locator(1), 10, 1000);
207
208        // At t=1009, still valid (expires_at = 1010)
209        assert_eq!(cache.get("ephemeral", 1009), Some(&7));
210        // At t=1010, expired
211        assert_eq!(cache.get("ephemeral", 1010), None);
212        // At t=1050, definitely expired
213        assert_eq!(cache.get("ephemeral", 1050), None);
214    }
215
216    #[test]
217    fn prune_expired_removes_stale() {
218        let mut cache = TtlObjectCache::new(RenewalPolicy::default());
219        cache.put("short".into(), 1u32, make_locator(1), 10, 1000);
220        cache.put("medium".into(), 2u32, make_locator(2), 30, 1000);
221        cache.put("long".into(), 3u32, make_locator(3), 60, 1000);
222
223        assert_eq!(cache.len(), 3);
224
225        // At t=1015: "short" expired
226        let pruned = cache.prune_expired(1015);
227        assert_eq!(pruned, 1);
228        assert_eq!(cache.len(), 2);
229
230        // At t=1035: "medium" expired too
231        let pruned = cache.prune_expired(1035);
232        assert_eq!(pruned, 1);
233        assert_eq!(cache.len(), 1);
234
235        // "long" still alive
236        assert_eq!(cache.get("long", 1035), Some(&3));
237    }
238
239    #[test]
240    fn tick_returns_correct_stats() {
241        let mut cache = TtlObjectCache::new(RenewalPolicy::default());
242        // TTL=100, so near_expiry threshold is remaining <= 25 (i.e. t >= 1075)
243        cache.put("a".into(), 10u32, make_locator(1), 100, 1000);
244        cache.put("b".into(), 20u32, make_locator(2), 100, 1000);
245        // TTL=10, expires at 1010
246        cache.put("c".into(), 30u32, make_locator(3), 10, 1000);
247
248        // At t=1005: nothing expired, nothing near expiry
249        let stats = cache.tick(1005);
250        assert_eq!(stats.pruned, 0);
251        assert_eq!(stats.total, 3);
252        assert_eq!(stats.near_expiry, 0);
253
254        // At t=1015: "c" expired, "a" and "b" not near expiry
255        let stats = cache.tick(1015);
256        assert_eq!(stats.pruned, 1);
257        assert_eq!(stats.total, 2);
258        assert_eq!(stats.near_expiry, 0);
259
260        // At t=1080: "a" and "b" near expiry (remaining=20, total=100, 20*4=80 <= 100)
261        let stats = cache.tick(1080);
262        assert_eq!(stats.pruned, 0);
263        assert_eq!(stats.total, 2);
264        assert_eq!(stats.near_expiry, 2);
265
266        // At t=1100: both expired
267        let stats = cache.tick(1100);
268        assert_eq!(stats.pruned, 2);
269        assert_eq!(stats.total, 0);
270        assert_eq!(stats.near_expiry, 0);
271    }
272
273    #[test]
274    fn remove_returns_value() {
275        let mut cache = TtlObjectCache::new(RenewalPolicy::default());
276        cache.put("x".into(), 42u32, make_locator(1), 60, 1000);
277
278        assert_eq!(cache.remove("x"), Some(42));
279        assert_eq!(cache.remove("x"), None);
280        assert_eq!(cache.len(), 0);
281    }
282
283    #[test]
284    fn put_overwrites_existing() {
285        let mut cache = TtlObjectCache::new(RenewalPolicy::default());
286        cache.put("k".into(), 1u32, make_locator(1), 60, 1000);
287        cache.put("k".into(), 2u32, make_locator(2), 120, 1000);
288
289        assert_eq!(cache.get("k", 1050), Some(&2));
290        assert_eq!(cache.len(), 1);
291    }
292
293    #[test]
294    fn get_updates_last_accessed() {
295        let mut cache = TtlObjectCache::new(RenewalPolicy::default());
296        cache.put("item".into(), 99u32, make_locator(1), 60, 1000);
297
298        cache.get("item", 1020);
299        // Access again at a later time
300        cache.get("item", 1040);
301        // Still accessible
302        assert_eq!(cache.get("item", 1059), Some(&99));
303    }
304
305    #[test]
306    fn empty_cache_operations() {
307        let mut cache = TtlObjectCache::<u32>::new(RenewalPolicy::default());
308        assert!(cache.is_empty());
309        assert_eq!(cache.len(), 0);
310        assert_eq!(cache.get("nothing", 0), None);
311        assert_eq!(cache.remove("nothing"), None);
312        assert_eq!(cache.prune_expired(0), 0);
313
314        let stats = cache.tick(0);
315        assert_eq!(
316            stats,
317            CacheStats {
318                total: 0,
319                pruned: 0,
320                near_expiry: 0,
321            }
322        );
323    }
324}
grafos_cache/ttl.rs

grafos_cache/
ttl.rs
