Skip to main content

rok_db_core/
cache.rs

1use std::any::Any;
2use std::collections::HashMap;
3use std::fmt;
4use std::sync::{Arc, Mutex, MutexGuard, Weak};
5use std::time::{Duration, Instant};
6
7/// An in-memory cache for memoized query results.
8///
9/// Enable it on a pool with [`DbBuilder::query_cache`](crate::DbBuilder::query_cache)
10/// and opt queries in with [`Select::memoize`](crate::Select::memoize):
11///
12/// ```ignore
13/// let db = Db::builder().query_cache(10_000).connect(url).await?;
14/// let admins = User::filter(User::ROLE.eq("admin"))
15///     .memoize(Duration::from_secs(30))
16///     .all(&db)
17///     .await?;
18/// ```
19///
20/// Entries expire after their time-to-live, and every write that rok-db
21/// performs on a table (insert, save, upsert, delete, bulk update/delete —
22/// including inside transactions, again on commit) invalidates that table's
23/// entries. Changes rok-db can't see are not tracked: writes from other
24/// processes, [`raw`](crate::raw) SQL that doesn't declare
25/// [`Raw::invalidates`](crate::Raw::invalidates), and rows changed by
26/// `ON DELETE CASCADE`, `ON UPDATE` actions or triggers on *other* tables.
27/// For those, call [`invalidate`](Self::invalidate) yourself or rely on a
28/// short TTL.
29///
30/// The cache is local to the process; cloning it is cheap and shares state.
31#[derive(Clone)]
32pub struct QueryCache {
33    inner: Arc<Mutex<Inner>>,
34}
35
36pub(crate) struct Inner {
37    /// Publishes local invalidations to other instances (see
38    /// [`DbBuilder::shared_cache_invalidation`](crate::DbBuilder::shared_cache_invalidation)).
39    broadcast: Option<tokio::sync::mpsc::UnboundedSender<String>>,
40    capacity: usize,
41    entries: HashMap<String, Entry>,
42    generations: HashMap<String, u64>,
43    hits: u64,
44    misses: u64,
45}
46
47struct Entry {
48    value: Arc<dyn Any + Send + Sync>,
49    /// Every table the result was read from, with its generation then.
50    tables: Stamp,
51    expires: Instant,
52}
53
54/// The generations of the tables a query reads, taken before it runs.
55pub(crate) type Stamp = Vec<(&'static str, u64)>;
56
57/// Counters describing how a [`QueryCache`] is performing.
58#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
59pub struct CacheStats {
60    /// Lookups answered from the cache.
61    pub hits: u64,
62    /// Lookups that had to query the database.
63    pub misses: u64,
64    /// Entries currently stored (including expired ones not yet evicted).
65    pub entries: usize,
66}
67
68impl QueryCache {
69    /// A cache holding at most `capacity` query results.
70    pub fn new(capacity: usize) -> Self {
71        Self {
72            inner: Arc::new(Mutex::new(Inner {
73                broadcast: None,
74                capacity: capacity.max(1),
75                entries: HashMap::new(),
76                generations: HashMap::new(),
77                hits: 0,
78                misses: 0,
79            })),
80        }
81    }
82
83    fn lock(&self) -> MutexGuard<'_, Inner> {
84        // A panic while holding the lock can't leave the map inconsistent.
85        self.inner.lock().unwrap_or_else(|e| e.into_inner())
86    }
87
88    /// Drop every cached result read from `table` (on every instance, when
89    /// shared invalidation is enabled).
90    pub fn invalidate(&self, table: &str) {
91        let mut inner = self.lock();
92        inner.invalidate(table);
93        if let Some(tx) = &inner.broadcast {
94            let _ = tx.send(table.to_owned());
95        }
96    }
97
98    /// Drop every cached result (on every instance, when shared
99    /// invalidation is enabled).
100    pub fn clear(&self) {
101        let mut inner = self.lock();
102        if let Some(tx) = &inner.broadcast {
103            let _ = tx.send(String::new());
104        }
105        inner.clear();
106    }
107
108    pub(crate) fn downgrade(&self) -> Weak<Mutex<Inner>> {
109        Arc::downgrade(&self.inner)
110    }
111
112    /// Route future invalidations to `tx` as well.
113    pub(crate) fn set_broadcast(&self, tx: tokio::sync::mpsc::UnboundedSender<String>) {
114        self.lock().broadcast = Some(tx);
115    }
116}
117
118/// Apply an invalidation received from another instance (`""` = clear all).
119pub(crate) fn apply_remote(inner: &Mutex<Inner>, table: &str) {
120    let mut inner = inner.lock().unwrap_or_else(|e| e.into_inner());
121    if table.is_empty() {
122        inner.clear();
123    } else {
124        inner.invalidate(table);
125    }
126}
127
128impl Inner {
129    fn invalidate(&mut self, table: &str) {
130        *self.generations.entry(table.to_owned()).or_default() += 1;
131        self.entries
132            .retain(|_, e| !e.tables.iter().any(|(t, _)| *t == table));
133    }
134
135    fn clear(&mut self) {
136        let inner = self;
137        // Bumping the global generation (keyed by "") also rejects results
138        // that were computed before this call but stored after it.
139        *inner.generations.entry(String::new()).or_default() += 1;
140        inner.entries.clear();
141    }
142}
143
144impl QueryCache {
145    /// Hit/miss counters and the current size.
146    pub fn stats(&self) -> CacheStats {
147        let inner = self.lock();
148        CacheStats {
149            hits: inner.hits,
150            misses: inner.misses,
151            entries: inner.entries.len(),
152        }
153    }
154
155    /// The current generations of `tables`; a result computed under an
156    /// older generation of any of them is discarded instead of stored.
157    pub(crate) fn stamp(&self, tables: &[&'static str]) -> Stamp {
158        let inner = self.lock();
159        tables.iter().map(|t| (*t, inner.generation(t))).collect()
160    }
161
162    pub(crate) fn get<T: Clone + 'static>(&self, key: &str) -> Option<T> {
163        let mut inner = self.lock();
164        let now = Instant::now();
165        let fresh = inner.entries.get(key).and_then(|e| {
166            (e.expires > now && inner.is_current(&e.tables))
167                .then(|| e.value.downcast_ref::<T>().cloned())
168                .flatten()
169        });
170        match fresh {
171            Some(value) => {
172                inner.hits += 1;
173                crate::metrics::cache(true);
174                Some(value)
175            }
176            None => {
177                inner.misses += 1;
178                crate::metrics::cache(false);
179                inner.entries.remove(key);
180                None
181            }
182        }
183    }
184
185    pub(crate) fn put<T: Send + Sync + 'static>(
186        &self,
187        key: String,
188        tables: Stamp,
189        ttl: Duration,
190        value: T,
191    ) {
192        let mut inner = self.lock();
193        if !inner.is_current(&tables) {
194            return; // A write happened while the query ran.
195        }
196        let now = Instant::now();
197        if inner.entries.len() >= inner.capacity && !inner.entries.contains_key(&key) {
198            inner.entries.retain(|_, e| e.expires > now);
199            if inner.entries.len() >= inner.capacity {
200                let oldest = inner
201                    .entries
202                    .iter()
203                    .min_by_key(|(_, e)| e.expires)
204                    .map(|(k, _)| k.clone());
205                if let Some(oldest) = oldest {
206                    inner.entries.remove(&oldest);
207                }
208            }
209        }
210        inner.entries.insert(
211            key,
212            Entry {
213                value: Arc::new(value),
214                tables,
215                expires: now + ttl,
216            },
217        );
218    }
219}
220
221impl Inner {
222    fn is_current(&self, stamp: &Stamp) -> bool {
223        stamp.iter().all(|(t, g)| *g == self.generation(t))
224    }
225
226    fn generation(&self, table: &str) -> u64 {
227        let global = self.generations.get("").copied().unwrap_or(0);
228        let table = self.generations.get(table).copied().unwrap_or(0);
229        global.wrapping_add(table)
230    }
231}
232
233impl fmt::Debug for QueryCache {
234    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
235        let inner = self.lock();
236        f.debug_struct("QueryCache")
237            .field("capacity", &inner.capacity)
238            .field("entries", &inner.entries.len())
239            .field("hits", &inner.hits)
240            .field("misses", &inner.misses)
241            .finish()
242    }
243}
244
245#[cfg(test)]
246mod tests {
247    use super::*;
248
249    #[test]
250    fn get_put_invalidate() {
251        let cache = QueryCache::new(2);
252        let ttl = Duration::from_secs(60);
253        let g = cache.stamp(&["users"]);
254        cache.put("a".into(), g.clone(), ttl, vec![1, 2]);
255        assert_eq!(cache.get::<Vec<i32>>("a"), Some(vec![1, 2]));
256        assert_eq!(cache.get::<String>("a"), None, "type mismatch is a miss");
257
258        cache.put("a".into(), g.clone(), ttl, vec![1, 2]);
259        cache.invalidate("users");
260        assert_eq!(cache.get::<Vec<i32>>("a"), None);
261
262        // A result computed before an invalidation is not stored.
263        cache.put("b".into(), g, ttl, 5);
264        assert_eq!(cache.get::<i32>("b"), None);
265
266        let g = cache.stamp(&["users"]);
267        cache.put("c".into(), g, Duration::ZERO, 5);
268        assert_eq!(cache.get::<i32>("c"), None, "expired");
269
270        let stats = cache.stats();
271        assert_eq!((stats.hits, stats.misses), (1, 4));
272    }
273
274    #[test]
275    fn multi_table_entries() {
276        let cache = QueryCache::new(10);
277        let g = cache.stamp(&["posts", "users"]);
278        cache.put("joined".into(), g, Duration::from_secs(60), 1);
279        assert_eq!(cache.get::<i32>("joined"), Some(1));
280        cache.invalidate("users");
281        assert_eq!(
282            cache.get::<i32>("joined"),
283            None,
284            "any joined table invalidates"
285        );
286    }
287
288    #[test]
289    fn capacity_and_clear() {
290        let cache = QueryCache::new(2);
291        let ttl = Duration::from_secs(60);
292        for (i, key) in ["a", "b", "c"].into_iter().enumerate() {
293            let g = cache.stamp(&["t"]);
294            cache.put(key.into(), g, ttl + Duration::from_secs(i as u64), i);
295        }
296        assert_eq!(cache.stats().entries, 2);
297        assert_eq!(cache.get::<usize>("a"), None, "oldest evicted");
298        let g = cache.stamp(&["other"]);
299        cache.clear();
300        cache.put("d".into(), g, ttl, 1);
301        assert_eq!(cache.get::<usize>("d"), None);
302    }
303}