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