Skip to main content

nitr_std/
cache.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2// This file is part of Nitr.
3// See https://nitrweb.com/ for more information
4// Copyright (C) 2024-present Jose Quintana <joseluisq.net>
5
6//! `nitr.cache`: a bounded, Rust-owned cache shared by every pooled state.
7//!
8//! This is deliberately *not* a hole in the isolation model. Values are
9//! serialized on the way in and rebuilt on the way out, so no Lua value,
10//! function, or userdata ever crosses between states, and one state can
11//! never reach another's heap through it. Rust owns the memory and the
12//! bound, so the cache cannot grow without limit. It is shared **data**,
13//! not shared **state** — the same relationship Lua already has with
14//! SQLite.
15//!
16//! Two properties applications must know, because building on the opposite
17//! assumption fails quietly:
18//!
19//! - It lives in the process. A restart empties it, and two Nitr processes
20//!   behind a load balancer have two independent caches. Do not put
21//!   sessions, locks, or counters that must be exact in here.
22//! - It survives a reload. A cache that empties every time the handler
23//!   script changes is a cache that never warms, which is worse than not
24//!   having one in development.
25
26use std::collections::HashMap;
27use std::sync::atomic::{AtomicU64, Ordering};
28use std::sync::{Arc, Mutex};
29use std::time::{Duration, Instant};
30
31use mlua::{ExternalResult as _, Lua, LuaSerdeExt as _, Table, UserData, UserDataMethods, Value};
32
33/// Limits and defaults for the shared cache.
34#[derive(Debug, Clone)]
35pub struct CacheOptions {
36    /// Maximum live entries before the least recently used is evicted.
37    pub max_entries: usize,
38    /// Maximum total size of stored values, in bytes.
39    pub max_bytes: u64,
40    /// Seconds an entry lives when `set` does not say; `0` means no expiry.
41    pub default_ttl: u64,
42}
43
44impl Default for CacheOptions {
45    fn default() -> Self {
46        Self {
47            max_entries: 10_000,
48            max_bytes: 32 * 1024 * 1024,
49            default_ttl: 300,
50        }
51    }
52}
53
54struct Entry {
55    /// The value as JSON bytes: plain data, never a Lua handle.
56    value: Vec<u8>,
57    /// `None` for an entry that never expires.
58    expires_at: Option<Instant>,
59    /// Monotonic tick of the last read or write, for LRU eviction.
60    touched: u64,
61}
62
63impl Entry {
64    fn is_live(&self, now: Instant) -> bool {
65        self.expires_at.is_none_or(|at| at > now)
66    }
67}
68
69#[derive(Default)]
70struct Inner {
71    entries: HashMap<String, Entry>,
72    bytes: u64,
73    hits: u64,
74    misses: u64,
75    evictions: u64,
76}
77
78/// The shared cache. Cloning shares the same storage; the server builds one
79/// and hands it to every state.
80#[derive(Clone)]
81pub struct Cache {
82    inner: Arc<Mutex<Inner>>,
83    opts: Arc<CacheOptions>,
84    /// Supplies the LRU ordering. A counter rather than a timestamp: it is
85    /// cheaper and cannot go backwards when the wall clock does.
86    clock: Arc<AtomicU64>,
87}
88
89impl std::fmt::Debug for Cache {
90    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
91        f.debug_struct("Cache")
92            .field("max_entries", &self.opts.max_entries)
93            .field("max_bytes", &self.opts.max_bytes)
94            .finish_non_exhaustive()
95    }
96}
97
98impl Cache {
99    /// Creates an empty cache bounded by the given limits.
100    pub fn new(opts: CacheOptions) -> Self {
101        Self {
102            inner: Arc::new(Mutex::new(Inner::default())),
103            opts: Arc::new(opts),
104            clock: Arc::new(AtomicU64::new(0)),
105        }
106    }
107
108    fn lock(&self) -> mlua::Result<std::sync::MutexGuard<'_, Inner>> {
109        self.inner
110            .lock()
111            .map_err(|_| mlua::Error::RuntimeError("the cache lock is poisoned".into()))
112    }
113
114    fn tick(&self) -> u64 {
115        self.clock.fetch_add(1, Ordering::Relaxed)
116    }
117
118    fn get_raw(&self, key: &str) -> mlua::Result<Option<Vec<u8>>> {
119        let now = Instant::now();
120        let touched = self.tick();
121        let mut inner = self.lock()?;
122
123        match inner.entries.get_mut(key) {
124            Some(entry) if entry.is_live(now) => {
125                entry.touched = touched;
126                let value = entry.value.clone();
127                inner.hits += 1;
128                Ok(Some(value))
129            }
130            // An expired entry is dropped on the way past rather than left
131            // to be evicted later: it is dead weight against both bounds.
132            Some(_) => {
133                if let Some(entry) = inner.entries.remove(key) {
134                    // Saturating (here and at every debit): if the hand-kept
135                    // counter ever drifts, a wrap near `u64::MAX` would make
136                    // eviction expel everything forever; flooring at zero
137                    // merely over-admits until entries cycle out.
138                    inner.bytes = inner.bytes.saturating_sub(entry.value.len() as u64);
139                }
140                inner.misses += 1;
141                Ok(None)
142            }
143            None => {
144                inner.misses += 1;
145                Ok(None)
146            }
147        }
148    }
149
150    fn set_raw(&self, key: String, value: Vec<u8>, ttl: Option<u64>) -> mlua::Result<()> {
151        let size = value.len() as u64;
152        if size > self.opts.max_bytes {
153            return Err(mlua::Error::RuntimeError(format!(
154                "cache value for `{key}` is {size} bytes, larger than the whole \
155                 {} byte cache",
156                self.opts.max_bytes
157            )));
158        }
159        let ttl = ttl.unwrap_or(self.opts.default_ttl);
160        let touched = self.tick();
161        let mut inner = self.lock()?;
162
163        if let Some(previous) = inner.entries.remove(&key) {
164            inner.bytes = inner.bytes.saturating_sub(previous.value.len() as u64);
165        }
166        inner.bytes += size;
167        inner.entries.insert(
168            key,
169            Entry {
170                value,
171                expires_at: (ttl > 0).then(|| Instant::now() + Duration::from_secs(ttl)),
172                touched,
173            },
174        );
175        self.evict(&mut inner);
176        Ok(())
177    }
178
179    /// Brings the cache back inside both bounds, dropping expired entries
180    /// first and then the least recently used.
181    fn evict(&self, inner: &mut Inner) {
182        let now = Instant::now();
183        inner.entries.retain(|_, entry| {
184            let live = entry.is_live(now);
185            if !live {
186                inner.bytes = inner.bytes.saturating_sub(entry.value.len() as u64);
187            }
188            live
189        });
190
191        while inner.entries.len() > self.opts.max_entries || inner.bytes > self.opts.max_bytes {
192            let Some(victim) = inner
193                .entries
194                .iter()
195                .min_by_key(|(_, entry)| entry.touched)
196                .map(|(key, _)| key.clone())
197            else {
198                break;
199            };
200            if let Some(entry) = inner.entries.remove(&victim) {
201                inner.bytes = inner.bytes.saturating_sub(entry.value.len() as u64);
202                inner.evictions += 1;
203            }
204        }
205    }
206}
207
208impl UserData for Cache {
209    fn add_methods<M: UserDataMethods<Self>>(methods: &mut M) {
210        // cache:get(key) -> value | nil
211        methods.add_method("get", |lua, cache, key: String| {
212            match cache.get_raw(&key)? {
213                Some(bytes) => {
214                    let json: serde_json::Value = serde_json::from_slice(&bytes).into_lua_err()?;
215                    lua.to_value(&json)
216                }
217                None => Ok(Value::Nil),
218            }
219        });
220
221        // cache:set(key, value, opts?) — opts is { ttl = seconds }.
222        // The value is serialized here, which is what keeps states isolated
223        // and is also why a function or userdata cannot be cached.
224        methods.add_method(
225            "set",
226            |_, cache, (key, value, opts): (String, Value, Option<Table>)| {
227                let ttl = match &opts {
228                    Some(opts) => opts.get::<Option<u64>>("ttl")?,
229                    None => None,
230                };
231                crate::utils::check_json_depth(&value)?;
232                let bytes = serde_json::to_vec(&value).map_err(|err| {
233                    mlua::Error::RuntimeError(format!(
234                        "cache values must be plain data (a table, string, number or \
235                         boolean); `{key}` is not serializable: {err}"
236                    ))
237                })?;
238                cache.set_raw(key, bytes, ttl)?;
239                Ok(())
240            },
241        );
242
243        // cache:delete(key) -> whether it was there
244        methods.add_method("delete", |_, cache, key: String| {
245            let mut inner = cache.lock()?;
246            match inner.entries.remove(&key) {
247                Some(entry) => {
248                    inner.bytes = inner.bytes.saturating_sub(entry.value.len() as u64);
249                    Ok(true)
250                }
251                None => Ok(false),
252            }
253        });
254
255        methods.add_method("clear", |_, cache, ()| {
256            let mut inner = cache.lock()?;
257            inner.entries.clear();
258            inner.bytes = 0;
259            Ok(())
260        });
261
262        // cache:remember(key, opts?, fn) — get, or compute and store.
263        //
264        // The common shape, worth having as one call: written by hand it is
265        // three lines that are easy to get subtly wrong (caching a nil,
266        // forgetting the TTL).
267        methods.add_async_method(
268            "remember",
269            |lua, cache, (key, arg, f): (String, Value, Option<mlua::Function>)| async move {
270                // remember(key, fn) and remember(key, opts, fn) both work.
271                let (opts, f) = match (arg, f) {
272                    (Value::Function(f), None) => (None, f),
273                    (Value::Table(opts), Some(f)) => (Some(opts), f),
274                    _ => {
275                        return Err(mlua::Error::RuntimeError(
276                            "cache:remember expects (key, fn) or (key, opts, fn)".into(),
277                        ));
278                    }
279                };
280                if let Some(bytes) = cache.get_raw(&key)? {
281                    let json: serde_json::Value = serde_json::from_slice(&bytes).into_lua_err()?;
282                    return lua.to_value(&json);
283                }
284                let ttl = match &opts {
285                    Some(opts) => opts.get::<Option<u64>>("ttl")?,
286                    None => None,
287                };
288                let value: Value = f.call_async(()).await?;
289                // A nil result is not cached: it would be indistinguishable
290                // from a miss on the way out, so every later call would run
291                // the function anyway while occupying an entry.
292                if value.is_nil() {
293                    return Ok(Value::Nil);
294                }
295                crate::utils::check_json_depth(&value)?;
296                let bytes = serde_json::to_vec(&value).map_err(|err| {
297                    mlua::Error::RuntimeError(format!(
298                        "cache:remember value for `{key}` is not serializable: {err}"
299                    ))
300                })?;
301                cache.set_raw(key, bytes, ttl)?;
302                Ok(value)
303            },
304        );
305
306        // cache:stats() — entries, bytes, hits, misses, evictions.
307        methods.add_method("stats", |lua, cache, ()| {
308            let inner = cache.lock()?;
309            let table = lua.create_table()?;
310            table.set("entries", inner.entries.len())?;
311            table.set("bytes", inner.bytes)?;
312            table.set("hits", inner.hits)?;
313            table.set("misses", inner.misses)?;
314            table.set("evictions", inner.evictions)?;
315            table.set("max_entries", cache.opts.max_entries)?;
316            table.set("max_bytes", cache.opts.max_bytes)?;
317            Ok(table)
318        });
319    }
320}
321
322/// Builds the `nitr.cache` handle for one state over the shared storage.
323pub(crate) fn create_cache(lua: &Lua, cache: Cache) -> mlua::Result<mlua::AnyUserData> {
324    lua.create_userdata(cache)
325}
326
327#[cfg(test)]
328mod tests {
329    use super::*;
330
331    fn cache(opts: CacheOptions) -> Cache {
332        Cache::new(opts)
333    }
334
335    /// A chain of `depth` nested Lua tables (the root included).
336    fn deep_table(lua: &Lua, depth: usize) -> Value {
337        let root = lua.create_table().expect("table");
338        let mut cur = root.clone();
339        for _ in 1..depth {
340            let next = lua.create_table().expect("table");
341            cur.set("x", next.clone()).expect("set");
342            cur = next;
343        }
344        Value::Table(root)
345    }
346
347    /// `cache:set` serializes script values: without the depth guard a
348    /// deep chain recursed to a stack-overflow abort here too.
349    #[test]
350    fn set_rejects_values_nested_beyond_the_json_depth_bound() {
351        let lua = Lua::new();
352        let ud = lua
353            .create_userdata(cache(CacheOptions::default()))
354            .expect("ud");
355        lua.globals().set("cache", ud).expect("global");
356        lua.globals()
357            .set("deep", deep_table(&lua, 129))
358            .expect("global");
359        let err: String = lua
360            .load(
361                r#"local ok, err = pcall(function() cache:set("k", deep) end)
362                   assert(not ok)
363                   return tostring(err)"#,
364            )
365            .eval()
366            .expect("eval");
367        assert!(err.contains("nested deeper than 128 levels"), "got: {err}");
368    }
369
370    #[test]
371    fn values_round_trip_and_count_against_the_bounds() {
372        let c = cache(CacheOptions::default());
373        c.set_raw("a".into(), b"{\"n\":1}".to_vec(), None)
374            .expect("set");
375        assert_eq!(
376            c.get_raw("a").expect("get").as_deref(),
377            Some(&b"{\"n\":1}"[..])
378        );
379        assert_eq!(c.get_raw("missing").expect("get"), None);
380
381        let inner = c.inner.lock().expect("lock");
382        assert_eq!(inner.entries.len(), 1);
383        assert_eq!(inner.bytes, 7);
384        assert_eq!((inner.hits, inner.misses), (1, 1));
385    }
386
387    #[test]
388    fn overwriting_a_key_does_not_double_count_its_bytes() {
389        let c = cache(CacheOptions::default());
390        c.set_raw("k".into(), vec![b'x'; 100], None).expect("set");
391        c.set_raw("k".into(), vec![b'y'; 10], None)
392            .expect("overwrite");
393        let inner = c.inner.lock().expect("lock");
394        assert_eq!(inner.entries.len(), 1);
395        assert_eq!(inner.bytes, 10);
396    }
397
398    #[test]
399    fn the_least_recently_used_entry_is_evicted_first() {
400        let c = cache(CacheOptions {
401            max_entries: 2,
402            ..Default::default()
403        });
404        c.set_raw("a".into(), b"1".to_vec(), None).expect("set a");
405        c.set_raw("b".into(), b"2".to_vec(), None).expect("set b");
406        // Touch `a`, so `b` becomes the least recently used.
407        c.get_raw("a").expect("get a");
408        c.set_raw("c".into(), b"3".to_vec(), None).expect("set c");
409
410        assert!(c.get_raw("a").expect("a").is_some());
411        assert!(c.get_raw("b").expect("b").is_none(), "b must be evicted");
412        assert!(c.get_raw("c").expect("c").is_some());
413    }
414
415    #[test]
416    fn the_byte_bound_evicts_too() {
417        let c = cache(CacheOptions {
418            max_bytes: 100,
419            ..Default::default()
420        });
421        c.set_raw("a".into(), vec![b'x'; 60], None).expect("set a");
422        c.set_raw("b".into(), vec![b'x'; 60], None).expect("set b");
423
424        let inner = c.inner.lock().expect("lock");
425        assert!(inner.bytes <= 100, "bytes must stay within the bound");
426        assert_eq!(inner.entries.len(), 1);
427        assert_eq!(inner.evictions, 1);
428    }
429
430    #[test]
431    fn a_value_larger_than_the_whole_cache_is_refused() {
432        let c = cache(CacheOptions {
433            max_bytes: 10,
434            ..Default::default()
435        });
436        let err = c
437            .set_raw("big".into(), vec![b'x'; 11], None)
438            .expect_err("must be refused");
439        assert!(err.to_string().contains("larger than"), "{err}");
440    }
441
442    #[test]
443    fn an_expired_entry_reads_as_a_miss_and_frees_its_bytes() {
444        let c = cache(CacheOptions::default());
445        // A zero TTL means "no expiry", so expiry is set directly here.
446        c.set_raw("k".into(), vec![b'x'; 50], Some(1)).expect("set");
447        {
448            let mut inner = c.inner.lock().expect("lock");
449            let entry = inner.entries.get_mut("k").expect("entry");
450            entry.expires_at = Some(Instant::now() - Duration::from_secs(1));
451        }
452        assert!(c.get_raw("k").expect("get").is_none());
453        assert_eq!(c.inner.lock().expect("lock").bytes, 0);
454    }
455
456    #[test]
457    fn a_zero_ttl_never_expires() {
458        let c = cache(CacheOptions {
459            default_ttl: 0,
460            ..Default::default()
461        });
462        c.set_raw("k".into(), b"v".to_vec(), None).expect("set");
463        assert!(
464            c.inner.lock().expect("lock").entries["k"]
465                .expires_at
466                .is_none()
467        );
468    }
469}