Skip to main content

byte_lru_cache/
lib.rs

1#![doc = include_str!("../README.md")]
2
3//! A thread-safe LRU cache whose admission is governed by a byte budget.
4
5use std::hash::Hash;
6use std::num::NonZeroU64;
7use std::sync::atomic::{
8    AtomicU64,
9    Ordering,
10};
11use std::sync::{
12    Arc,
13    Mutex,
14};
15
16/// Monotonic counters collected by a [`ByteLruCache`].
17#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
18pub struct CacheStats {
19    /// Successful lookups.
20    pub hits: u64,
21    /// Lookups that did not find an entry.
22    pub misses: u64,
23    /// Entries removed by LRU eviction or cap reduction.
24    pub evictions: u64,
25}
26
27/// A thread-safe LRU cache governed by a caller-supplied byte budget.
28///
29/// Values are stored behind [`Arc`] so callers can hold a value without
30/// copying it. Each entry carries a strictly positive weight. The cache
31/// evicts least-recently-used entries until the sum of weights is at most
32/// `max_bytes`.
33///
34/// The weight is an accounting value supplied by the caller. It should be a
35/// conservative estimate of the memory retained by the value; the cache
36/// cannot measure an arbitrary `V`'s heap allocation itself.
37pub struct ByteLruCache<K, V> {
38    inner: Mutex<Inner<K, V>>,
39    hits: AtomicU64,
40    misses: AtomicU64,
41    evictions: AtomicU64,
42    label: String,
43}
44
45struct Inner<K, V> {
46    entries: lru::LruCache<K, Weighted<V>>,
47    current_bytes: u64,
48    max_bytes: u64,
49}
50
51struct Weighted<V> {
52    value: Arc<V>,
53    weight_bytes: NonZeroU64,
54}
55
56impl<K, V> ByteLruCache<K, V>
57where
58    K: Eq + Hash + Send + Sync,
59    V: Send + Sync,
60{
61    /// Creates an empty cache with the supplied byte ceiling and label.
62    ///
63    /// A zero ceiling is valid and causes every inserted entry to be
64    /// immediately evicted. This is useful when a caller disables a cache
65    /// without changing its construction path.
66    #[must_use]
67    pub fn new(max_bytes: u64, label: impl Into<String>) -> Self {
68        Self {
69            inner: Mutex::new(Inner {
70                entries: lru::LruCache::unbounded(),
71                current_bytes: 0,
72                max_bytes,
73            }),
74            hits: AtomicU64::new(0),
75            misses: AtomicU64::new(0),
76            evictions: AtomicU64::new(0),
77            label: label.into(),
78        }
79    }
80
81    /// Returns the caller-supplied label for this cache.
82    #[must_use]
83    pub fn label(&self) -> &str {
84        &self.label
85    }
86
87    /// Looks up a key and promotes a hit to the most-recently-used position.
88    ///
89    /// # Panics
90    ///
91    /// Panics if another thread poisoned the cache lock.
92    #[must_use]
93    pub fn get(&self, key: &K) -> Option<Arc<V>> {
94        let mut guard = self.inner.lock().expect("cache lock poisoned");
95        if let Some(entry) = guard.entries.get(key) {
96            self.hits.fetch_add(1, Ordering::Relaxed);
97            Some(Arc::clone(&entry.value))
98        } else {
99            self.misses.fetch_add(1, Ordering::Relaxed);
100            None
101        }
102    }
103
104    /// Inserts or replaces an entry and evicts least-recently-used entries
105    /// until the byte ceiling is satisfied.
106    ///
107    /// The `weight_bytes` argument is non-zero by construction, so the
108    /// cache's entry count cannot grow without consuming the configured
109    /// byte budget.
110    ///
111    /// # Panics
112    ///
113    /// Panics if another thread poisoned the cache lock.
114    pub fn insert(&self, key: K, value: Arc<V>, weight_bytes: NonZeroU64) {
115        let mut guard = self.inner.lock().expect("cache lock poisoned");
116        if let Some(previous) = guard.entries.peek(&key) {
117            guard.current_bytes = guard
118                .current_bytes
119                .saturating_sub(previous.weight_bytes.get());
120        }
121        guard.current_bytes = guard.current_bytes.saturating_add(weight_bytes.get());
122        guard.entries.put(
123            key,
124            Weighted {
125                value,
126                weight_bytes,
127            },
128        );
129        self.evict_until_under_cap(&mut guard);
130    }
131
132    /// Removes a key if it is present.
133    ///
134    /// # Panics
135    ///
136    /// Panics if another thread poisoned the cache lock.
137    pub fn evict(&self, key: &K) {
138        let mut guard = self.inner.lock().expect("cache lock poisoned");
139        if let Some(entry) = guard.entries.pop(key) {
140            guard.current_bytes = guard.current_bytes.saturating_sub(entry.weight_bytes.get());
141        }
142    }
143
144    /// Returns the sum of the weights currently retained by the cache.
145    ///
146    /// # Panics
147    ///
148    /// Panics if another thread poisoned the cache lock.
149    #[must_use]
150    pub fn current_bytes(&self) -> u64 {
151        self.inner
152            .lock()
153            .expect("cache lock poisoned")
154            .current_bytes
155    }
156
157    /// Returns the configured byte ceiling.
158    ///
159    /// # Panics
160    ///
161    /// Panics if another thread poisoned the cache lock.
162    #[must_use]
163    pub fn max_bytes(&self) -> u64 {
164        self.inner.lock().expect("cache lock poisoned").max_bytes
165    }
166
167    /// Changes the byte ceiling and immediately evicts entries if necessary.
168    ///
169    /// # Panics
170    ///
171    /// Panics if another thread poisoned the cache lock.
172    pub fn set_max_bytes(&self, max_bytes: u64) {
173        let mut guard = self.inner.lock().expect("cache lock poisoned");
174        guard.max_bytes = max_bytes;
175        self.evict_until_under_cap(&mut guard);
176    }
177
178    /// Returns a point-in-time copy of the cache counters.
179    #[must_use]
180    pub fn stats(&self) -> CacheStats {
181        CacheStats {
182            hits: self.hits.load(Ordering::Relaxed),
183            misses: self.misses.load(Ordering::Relaxed),
184            evictions: self.evictions.load(Ordering::Relaxed),
185        }
186    }
187
188    /// Returns the number of retained entries.
189    ///
190    /// # Panics
191    ///
192    /// Panics if another thread poisoned the cache lock.
193    #[must_use]
194    pub fn len(&self) -> usize {
195        self.inner
196            .lock()
197            .expect("cache lock poisoned")
198            .entries
199            .len()
200    }
201
202    /// Returns whether the cache has no retained entries.
203    #[must_use]
204    pub fn is_empty(&self) -> bool {
205        self.len() == 0
206    }
207
208    fn evict_until_under_cap(&self, guard: &mut Inner<K, V>) {
209        while guard.current_bytes > guard.max_bytes {
210            let Some((_, entry)) = guard.entries.pop_lru() else {
211                break;
212            };
213            guard.current_bytes = guard.current_bytes.saturating_sub(entry.weight_bytes.get());
214            self.evictions.fetch_add(1, Ordering::Relaxed);
215        }
216    }
217}
218
219#[cfg(test)]
220mod tests {
221    use std::num::NonZeroU64;
222    use std::sync::Arc;
223
224    use super::{
225        ByteLruCache,
226        CacheStats,
227    };
228
229    fn weight(bytes: u64) -> NonZeroU64 {
230        NonZeroU64::new(bytes).expect("test weights are positive")
231    }
232
233    #[test]
234    fn stores_and_retrieves_generic_values() {
235        let cache = ByteLruCache::new(64, "values");
236        cache.insert("answer", Arc::new(42_u32), weight(4));
237
238        assert_eq!(cache.get(&"answer").as_deref(), Some(&42));
239        assert_eq!(cache.current_bytes(), 4);
240        assert_eq!(cache.stats().hits, 1);
241    }
242
243    #[test]
244    fn misses_are_counted() {
245        let cache: ByteLruCache<u32, String> = ByteLruCache::new(64, "values");
246
247        assert!(cache.get(&7).is_none());
248        assert_eq!(cache.stats().misses, 1);
249    }
250
251    #[test]
252    fn least_recently_used_entry_is_evicted() {
253        let cache = ByteLruCache::new(20, "values");
254        cache.insert(1, Arc::new("one"), weight(8));
255        cache.insert(2, Arc::new("two"), weight(8));
256        let _ = cache.get(&1);
257        cache.insert(3, Arc::new("three"), weight(8));
258
259        assert!(cache.get(&1).is_some());
260        assert!(cache.get(&2).is_none());
261        assert!(cache.get(&3).is_some());
262        assert!(cache.current_bytes() <= 20);
263        assert_eq!(cache.stats().evictions, 1);
264    }
265
266    #[test]
267    fn replacement_updates_weight_without_double_counting() {
268        let cache = ByteLruCache::new(64, "values");
269        cache.insert(1, Arc::new(1_u32), weight(10));
270        cache.insert(1, Arc::new(2_u32), weight(30));
271
272        assert_eq!(cache.current_bytes(), 30);
273        assert_eq!(cache.get(&1).as_deref(), Some(&2));
274    }
275
276    #[test]
277    fn reducing_the_ceiling_evicts_immediately() {
278        let cache = ByteLruCache::new(1_000, "values");
279        for key in 0..10_u32 {
280            cache.insert(key, Arc::new(key), weight(100));
281        }
282
283        cache.set_max_bytes(250);
284
285        assert!(cache.current_bytes() <= 250);
286        assert_eq!(cache.len(), 2);
287    }
288
289    #[test]
290    fn zero_ceiling_retains_nothing() {
291        let cache = ByteLruCache::new(0, "disabled");
292        cache.insert(1_u32, Arc::new(1_u32), weight(1));
293
294        assert!(cache.is_empty());
295        assert_eq!(cache.current_bytes(), 0);
296        assert_eq!(cache.stats().evictions, 1);
297    }
298
299    #[test]
300    fn labels_and_empty_stats_are_stable() {
301        let cache: ByteLruCache<u32, u32> = ByteLruCache::new(64, "test-cache");
302
303        assert_eq!(cache.label(), "test-cache");
304        assert!(cache.is_empty());
305        assert_eq!(cache.stats(), CacheStats::default());
306    }
307}
308
309#[cfg(feature = "memory-budget")]
310impl<K, V> memory_budget::Resizable for ByteLruCache<K, V>
311where
312    K: Eq + std::hash::Hash + Send + Sync,
313    V: Send + Sync,
314{
315    fn name(&self) -> &str {
316        self.label()
317    }
318
319    fn current_bytes(&self) -> u64 {
320        self.current_bytes()
321    }
322
323    fn max_bytes(&self) -> u64 {
324        self.max_bytes()
325    }
326
327    fn set_max_bytes(&self, new: u64) {
328        self.set_max_bytes(new);
329    }
330
331    fn stats(&self) -> memory_budget::ResizableStats {
332        let stats = self.stats();
333        memory_budget::ResizableStats {
334            hits: stats.hits,
335            misses: stats.misses,
336            evictions: stats.evictions,
337        }
338    }
339}
340
341#[cfg(all(test, feature = "memory-budget"))]
342mod resizable_tests {
343    use std::num::NonZeroU64;
344    use std::sync::Arc;
345
346    use memory_budget::Resizable;
347
348    use super::ByteLruCache;
349
350    #[test]
351    fn the_cache_is_governable_through_the_resizable_seam() {
352        let cache = ByteLruCache::new(1024, "governed");
353        cache.insert(
354            "answer",
355            Arc::new(42_u32),
356            NonZeroU64::new(64).expect("positive weight"),
357        );
358        let governed: &dyn Resizable = &cache;
359        assert_eq!(governed.name(), "governed");
360        assert_eq!(governed.current_bytes(), 64);
361        assert_eq!(governed.max_bytes(), 1024);
362        governed.set_max_bytes(32);
363        assert_eq!(governed.current_bytes(), 0, "lowering the cap evicts");
364        let _ = cache.get(&"answer");
365        assert_eq!(governed.stats().misses, 1);
366        assert_eq!(governed.stats().evictions, 1);
367    }
368}