Skip to main content

sisa_caching_memory/
store.rs

1//! The memory store.
2
3use std::{
4    any::{Any, type_name},
5    collections::HashMap,
6    mem,
7    sync::{
8        Arc, PoisonError, RwLock, RwLockReadGuard, RwLockWriteGuard, TryLockError,
9        atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering},
10    },
11    time::{Duration, Instant},
12};
13
14use sisa_caching_core::{
15    cache::{CacheEntry, CacheError, CacheStore, CacheValue, KeyPrefix},
16    clock::{Clock, SystemClock},
17    locker::Locker,
18    metrics::{Layer, METRICS, Reads},
19    settings::CacheSettings,
20    worker::Worker,
21};
22
23use crate::settings::InMemoryCacheSettings;
24
25/// Runs `work` on the blocking pool inside a tokio runtime, so a walk of every entry or the freeing
26/// of many values holds up no async thread, and here outside one.
27fn off_async_thread(work: impl FnOnce() + Send + 'static) {
28    match tokio::runtime::Handle::try_current() {
29        Ok(runtime) => drop(runtime.spawn_blocking(work)),
30        Err(_) => work(),
31    }
32}
33
34/// A stored value of any type. A read asks for the type it expects and gets it back, or an error.
35type Erased = Arc<dyn Any + Send + Sync>;
36
37/// An entry plus when the store lets it go, on the monotonic clock so wall-clock changes don't
38/// move it, and, in a store with `max_entries`, when it was last stored or read, so a full store
39/// drops the least recently used.
40struct StoredEntry {
41    entry: CacheEntry<Erased>,
42    deadline: Option<Instant>,
43    last_used: AtomicU64,
44}
45
46impl StoredEntry {
47    fn is_expired(&self, now: Instant) -> bool {
48        self.deadline.is_some_and(|deadline| now >= deadline)
49    }
50}
51
52type EntryMap = HashMap<String, StoredEntry>;
53
54/// The entries of a store and its clones, split over `shards` maps by key hash, plus how many
55/// there are, a count of writes that orders their use, and whether a trim is running, as one runs
56/// at a time.
57struct Entries {
58    shards: Box<[RwLock<EntryMap>]>,
59    len: AtomicUsize,
60    uses: AtomicU64,
61    trimming: AtomicBool,
62}
63
64impl Entries {
65    fn new(shards: usize) -> Self {
66        Self {
67            shards: (0..shards).map(|_| RwLock::default()).collect(),
68            len: AtomicUsize::new(0),
69            uses: AtomicU64::new(0),
70            trimming: AtomicBool::new(false),
71        }
72    }
73
74    /// A write's number, above every one before it. A read takes the last write's number, so
75    /// readers don't all update one counter, and entries read since the same write tie.
76    fn next_use(&self) -> u64 {
77        self.uses.fetch_add(1, Ordering::Relaxed) + 1
78    }
79
80    /// The map that holds `key`. One map needs no hash. Each map hashes its keys with SipHash,
81    /// which hostile keys can't make collide, so picking the map only has to spread keys, and a
82    /// multiply per eight bytes does that for far less than a second SipHash. At worst, keys made
83    /// to land on one map crowd it, like every key in a store with one map.
84    fn shard(&self, key: &str) -> &RwLock<EntryMap> {
85        let count = self.shards.len();
86
87        if count == 1 {
88            return &self.shards[0];
89        }
90
91        // FxHash's step, as in rustc-hash 1.
92        let hash = key.as_bytes().chunks(8).fold(0_u64, |hash, chunk| {
93            let mut word = [0; 8];
94
95            word[..chunk.len()].copy_from_slice(chunk);
96            (hash.rotate_left(5) ^ u64::from_le_bytes(word)).wrapping_mul(0x517c_c1b7_2722_0a95)
97        });
98
99        // The multiply mixes the high bits best, so they pick the map.
100        &self.shards[((u128::from(hash) * count as u128) >> 64) as usize]
101    }
102}
103
104fn read(shard: &RwLock<EntryMap>) -> RwLockReadGuard<'_, EntryMap> {
105    shard.read().unwrap_or_else(PoisonError::into_inner)
106}
107
108/// Values the store lets go are freed after this guard is dropped: a value's Drop can run any
109/// code, a call to this store included, which would deadlock under the lock, and freeing many
110/// values would hold up every other caller.
111fn write(shard: &RwLock<EntryMap>) -> RwLockWriteGuard<'_, EntryMap> {
112    shard.write().unwrap_or_else(PoisonError::into_inner)
113}
114
115/// The store's purge task: drops `store`'s expired entries every `interval`, on the blocking pool,
116/// as a purge walks every entry. A panic there stops the task.
117async fn purge_every<C: Clock>(store: InMemoryCacheStore<C>, interval: Duration) {
118    loop {
119        tokio::time::sleep(interval).await;
120
121        let store = store.clone();
122
123        if let Err(error) = tokio::task::spawn_blocking(move || store.purge()).await
124            && error.is_panic()
125        {
126            std::panic::resume_unwind(error.into_panic());
127        }
128    }
129}
130
131/// A started trim. Dropping it lets the next one start, even if it never ran, as when its runtime
132/// shut down first.
133struct Trimming<C>(InMemoryCacheStore<C>);
134
135// Lets the next trim start, whether or not this one ran.
136impl<C> Drop for Trimming<C> {
137    fn drop(&mut self) {
138        // A swap, not a store, as is the one that starts a trim: a write whose swap found a trim
139        // running is then seen by the count the trim checks after this (see `start_trim`).
140        self.0.entries.trimming.swap(false, Ordering::AcqRel);
141    }
142}
143
144/// An in-process store. One store holds values of every type; `get::<User>` and `set(&key, user,
145/// None)` name the type per call, and a read with the wrong type fails with
146/// [`CacheError::TypeMismatch`].
147///
148/// The store drops its expired entries every `memory.purge_interval_secs` of its settings, on a
149/// task it starts on its first write inside a tokio runtime. The task stops when the store's last
150/// clone drops. Inside a runtime, its purges, the trims of a full store and the freeing of what
151/// `remove_prefix` and `clear` took run on the blocking pool, so they hold up no async thread.
152///
153/// `C` is the clock the store reads the time from, [`SystemClock`] unless
154/// [`with_clock`](Self::with_clock) sets another.
155#[derive(Clone)]
156pub struct InMemoryCacheStore<C = SystemClock> {
157    name: KeyPrefix,
158    clock: C,
159    settings: InMemoryCacheSettings,
160    /// The longest the store holds an entry, whatever its TTL: a hybrid store's TTL for its local
161    /// copies. `None`, the default, holds each entry for its whole TTL.
162    local_ttl: Option<Duration>,
163    entries: Arc<Entries>,
164    locker: Arc<Locker>,
165    worker: Worker,
166    reads: &'static Reads,
167}
168
169// Shows the name, the settings and how many entries it holds; never a value.
170impl<C> std::fmt::Debug for InMemoryCacheStore<C> {
171    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
172        formatter
173            .debug_struct("InMemoryCacheStore")
174            .field("name", &self.name)
175            .field("settings", &self.settings)
176            .field("len", &self.entries.len.load(Ordering::Relaxed))
177            .finish_non_exhaustive()
178    }
179}
180
181impl InMemoryCacheStore {
182    /// A store named `name`, such as `app` or `tenant:eu`, on the system clock. Fails with
183    /// [`CacheError::InvalidKey`] when the name is empty or has an empty level.
184    pub fn new(name: &str) -> Result<Self, CacheError> {
185        let name = KeyPrefix::new(name)?;
186        let settings = InMemoryCacheSettings::default();
187
188        Ok(Self {
189            reads: METRICS.reads(&name, Layer::Memory),
190            name,
191            clock: SystemClock,
192            entries: Arc::new(Entries::new(settings.memory.shards())),
193            local_ttl: None,
194            settings,
195            locker: Arc::default(),
196            worker: Worker::new(),
197        })
198    }
199}
200
201impl<C: Clock> InMemoryCacheStore<C> {
202    /// Runs the store on `clock` instead of the system clock, so tests can move time. Set it while
203    /// building the store, before any write: the store keeps its entries but starts a purge task
204    /// of its own, on the new clock.
205    pub fn with_clock<T: Clock>(self, clock: T) -> InMemoryCacheStore<T> {
206        InMemoryCacheStore {
207            name: self.name,
208            clock,
209            settings: self.settings,
210            local_ttl: self.local_ttl,
211            entries: self.entries,
212            locker: self.locker,
213            worker: Worker::new(),
214            reads: self.reads,
215        }
216    }
217
218    /// Replaces the store's settings. Fails when one is out of range, such as a TTL over 365
219    /// days, so a bad value stops setup instead of a later write. The store starts empty, split
220    /// over `shards` maps.
221    pub fn with_settings(mut self, settings: InMemoryCacheSettings) -> Result<Self, CacheError> {
222        settings.validate()?;
223        self.entries = Arc::new(Entries::new(settings.memory.shards()));
224        // New entries need a purge of their own; the store this came from keeps its own.
225        self.worker = Worker::new();
226        self.settings = settings;
227
228        Ok(self)
229    }
230
231    /// Holds each entry for `ttl`, or until it expires if that is sooner; the entry keeps its own
232    /// creation time and TTL. The hybrid store sets it on its local layer, so a copy whose
233    /// invalidation was lost goes stale for at most `ttl`; a store on its own has nothing to
234    /// invalidate.
235    #[doc(hidden)]
236    pub fn with_local_ttl(mut self, ttl: Duration) -> Self {
237        self.local_ttl = Some(ttl);
238
239        self
240    }
241
242    /// The settings the store runs with.
243    pub fn settings(&self) -> &InMemoryCacheSettings {
244        &self.settings
245    }
246
247    /// Drops the expired entries and returns how many. The store's own purge task calls it every
248    /// `purge_interval_secs`; with that off, call it on a schedule of your own. It walks every
249    /// entry on the calling thread.
250    #[tracing::instrument(level = "debug", name = "memory purge", skip_all, fields(store = %self.name, removed))]
251    pub fn purge(&self) -> usize {
252        let now = self.clock.instant();
253        let removed = self.extract(&mut Vec::new(), |_, stored| stored.is_expired(now));
254
255        tracing::Span::current().record("removed", removed);
256
257        removed
258    }
259
260    /// `set_entry`'s work, in its `memory set` span. The span is opened on this sync function, not
261    /// in the async `set_entry` nor on `replace_entry`: measured, a span entered in an async body
262    /// slows every write, by 10% on ARM, and the hybrid store's promotions, which call
263    /// `replace_entry`, are not writes.
264    #[tracing::instrument(level = "debug", name = "memory set", skip_all, fields(key = %self.name.format_key(key)))]
265    fn set_in_span<CV: CacheValue>(&self, key: &str, entry: CacheEntry<CV>) {
266        // The value that was replaced is freed here, once the shard is unlocked (see `write`).
267        drop(self.replace_entry(key, entry));
268    }
269
270    /// Stores `entry` as [`set_entry`](CacheStore::set_entry) does, and hands back the value it
271    /// replaced instead of freeing it, so a caller that holds a lock of its own can free it once
272    /// that lock is released. The hybrid store's promotions do, so a slow `Drop` holds up no
273    /// invalidation.
274    #[doc(hidden)]
275    pub fn replace_entry<CV: CacheValue>(
276        &self,
277        key: &str,
278        entry: CacheEntry<CV>,
279    ) -> impl Send + use<C, CV> {
280        // Entries only come in here, so the purge starts with the first one.
281        if let Some(interval) = self.settings.memory.purge_interval() {
282            self.worker
283                .start("in-memory-cache-purge-worker", &self.name, || {
284                    purge_every(self.for_worker(), interval)
285                });
286        }
287
288        let local_ttl = self.local_ttl;
289        // An entry that never expires, in a store without a local TTL, needs no clock. Otherwise
290        // the monotonic clock goes first: measured, the other order slows writes with a TTL.
291        let now =
292            (entry.expires_at().is_some() || local_ttl.is_some()).then(|| self.clock.instant());
293        // The store holds an entry for its remaining lifetime, or `local_ttl` if that is shorter.
294        let remaining = entry
295            .expires_at()
296            .and_then(|_| entry.remaining_ttl(self.clock.now()));
297        let ttl = match (remaining, local_ttl) {
298            (Some(remaining), Some(local_ttl)) => Some(remaining.min(local_ttl)),
299            (remaining, local_ttl) => remaining.or(local_ttl),
300        };
301
302        // Built before the lock, so the lock covers only the map.
303        let stored = StoredEntry {
304            entry: entry.map(|value| Arc::new(value) as Erased),
305            deadline: ttl.zip(now).and_then(|(ttl, now)| now.checked_add(ttl)),
306            // Only a store with `max_entries` trims, so only it orders its entries by use.
307            last_used: AtomicU64::new(match self.settings.memory.max_entries {
308                Some(_) => self.entries.next_use(),
309                None => 0,
310            }),
311        };
312        let mut entries = write(self.entries.shard(key));
313        // A key that is there keeps its slot, so a write over it allocates no key. Measured, that
314        // makes such a write 17% cheaper, and a new key's second lookup costs it under 1%.
315        let replaced = match entries.get_mut(key) {
316            Some(slot) => Some(mem::replace(slot, stored)),
317            None => {
318                entries.insert(key.to_owned(), stored);
319                // Counted while the map is locked, so a remove never counts down before this
320                // counts up.
321                self.entries.len.fetch_add(1, Ordering::Relaxed);
322
323                None
324            }
325        };
326
327        // Unlock before the caller frees the value that was replaced (see `write`).
328        drop(entries);
329
330        if let Some(max) = self.settings.memory.max_entries
331            && self.entries.len.load(Ordering::Relaxed) > max
332        {
333            self.start_trim(max);
334        }
335
336        replaced
337    }
338
339    /// Starts a trim down to about nine tenths of `max` unless one is running. Inside a tokio
340    /// runtime it runs on the blocking pool, and the write that starts it goes on, as do the
341    /// writes after it.
342    fn start_trim(&self, max: usize) {
343        if self.entries.trimming.swap(true, Ordering::AcqRel) {
344            return;
345        }
346
347        let mut trimming = Trimming(self.for_worker());
348
349        off_async_thread(move || {
350            loop {
351                let removed = trimming.0.trim(max);
352                let store = trimming.0.clone();
353
354                // Let the next trim start, then free what this one dropped.
355                drop(trimming);
356                drop(removed);
357
358                // The writes that came in while this trim ran started none, so trim again if they
359                // left the store over `max`, unless one of them has started a trim since.
360                if store.entries.len.load(Ordering::Relaxed) <= max
361                    || store.entries.trimming.swap(true, Ordering::AcqRel)
362                {
363                    return;
364                }
365
366                trimming = Trimming(store);
367            }
368        });
369    }
370
371    /// Takes out expired entries, then the least recently used, down to about nine tenths of `max`
372    /// so the next inserts need no work, and returns them for the caller to free. The count is
373    /// checked again, as it may have gone down since the trim was started.
374    fn trim(&self, max: usize) -> Vec<(String, StoredEntry)> {
375        let mut removed = Vec::new();
376
377        if self.entries.len.load(Ordering::Relaxed) > max {
378            let now = self.clock.instant();
379            let target = max - max / 10;
380            // Expired entries count as never used, so they go first, and all of them go.
381            let last_use = |stored: &StoredEntry| {
382                if stored.is_expired(now) {
383                    0
384                } else {
385                    stored.last_used.load(Ordering::Relaxed)
386                }
387            };
388            // Sized once, as is `removed` below: grown map by map, these lists would be moved to
389            // new memory several times per trim, and each move touches pages for the first time.
390            let mut uses = Vec::with_capacity(self.entries.len.load(Ordering::Relaxed));
391
392            for shard in &self.entries.shards {
393                uses.extend(read(shard).values().map(last_use));
394            }
395
396            if uses.len() > target {
397                let excess = uses.len() - target;
398                let (below, &mut cutoff, _) = uses.select_nth_unstable(excess - 1);
399                // Entries read since the same write tie, so several can sit at the cutoff: take
400                // only as many of those as the trim needs.
401                let mut ties = excess - below.iter().filter(|&&used| used < cutoff).count();
402
403                removed.reserve(excess);
404
405                let mut expired = 0;
406                let taken = self.extract(&mut removed, |_, stored| {
407                    let used = last_use(stored);
408
409                    if used == 0 {
410                        expired += 1;
411                        return true;
412                    }
413                    if used == cutoff && ties > 0 {
414                        ties -= 1;
415                        return true;
416                    }
417
418                    used < cutoff
419                });
420                let evicted = taken - expired;
421
422                if evicted > 0 {
423                    METRICS.evicted(&self.name, evicted);
424                    tracing::debug!(
425                        store = %self.name,
426                        evicted,
427                        "store full; dropped the least recently used entries"
428                    );
429                }
430            }
431        }
432
433        removed
434    }
435
436    /// A copy that shares the entries but not the `Worker`, for the store's purge worker and its
437    /// trims, which would otherwise keep the purge running after the store's last clone drops.
438    pub(crate) fn for_worker(&self) -> Self {
439        Self {
440            worker: Worker::none(),
441            ..self.clone()
442        }
443    }
444
445    /// Moves every entry `pick` chooses into `taken`, one map at a time, and returns how many.
446    /// The caller frees them.
447    fn extract(
448        &self,
449        taken: &mut Vec<(String, StoredEntry)>,
450        mut pick: impl FnMut(&str, &StoredEntry) -> bool,
451    ) -> usize {
452        let start = taken.len();
453
454        for shard in &self.entries.shards {
455            let before = taken.len();
456
457            taken.extend(write(shard).extract_if(|key, stored| pick(key, stored)));
458            self.entries
459                .len
460                .fetch_sub(taken.len() - before, Ordering::Relaxed);
461        }
462
463        taken.len() - start
464    }
465}
466
467// Marks this as one of the stores that may implement `CacheStore`.
468impl<C: Clock> sisa_caching_core::sealed::Sealed for InMemoryCacheStore<C> {}
469
470// The cache API over the in-process maps.
471impl<C: Clock> CacheStore for InMemoryCacheStore<C> {
472    type Error = CacheError;
473    // The store's own clock: `SystemClock` unless `with_clock` set another.
474    type Clock = C;
475
476    fn name(&self) -> &KeyPrefix {
477        &self.name
478    }
479
480    fn cache_settings(&self) -> &CacheSettings {
481        &self.settings.common
482    }
483
484    fn locker(&self) -> &Locker {
485        &self.locker
486    }
487
488    fn clock(&self) -> &C {
489        &self.clock
490    }
491
492    #[tracing::instrument(level = "debug", name = "memory get", skip_all, fields(key = %self.name.format_key(key)))]
493    async fn get_entry<CV: CacheValue>(
494        &self,
495        key: &str,
496    ) -> Result<Option<CacheEntry<CV>>, CacheError> {
497        let shard = self.entries.shard(key);
498        // Read first even when the entry has no deadline: measured, reading it after the lookup,
499        // only when needed, slows hits on entries with a TTL, which most entries have.
500        let before = self.clock.instant();
501        // A read that waits for a write reads the time again once it holds the map, so an entry
502        // that expired while it waited counts as expired. Measured, reading it under the lock on
503        // every read slows many threads reading through one map.
504        let (entries, now) = match shard.try_read() {
505            Ok(entries) => (entries, before),
506            Err(TryLockError::Poisoned(poisoned)) => (poisoned.into_inner(), before),
507            Err(TryLockError::WouldBlock) => {
508                let entries = read(shard);
509
510                (entries, self.clock.instant())
511            }
512        };
513        // An expired entry stays until a purge, a trim or a write replaces it.
514        let found = entries
515            .get(key)
516            .filter(|stored| !stored.is_expired(now))
517            .map(|stored| {
518                if self.settings.memory.max_entries.is_some() {
519                    let used = self.entries.uses.load(Ordering::Relaxed);
520
521                    // Stored only when it moved, so readers of one entry don't keep taking its
522                    // cache line from each other.
523                    if stored.last_used.load(Ordering::Relaxed) != used {
524                        stored.last_used.store(used, Ordering::Relaxed);
525                    }
526                }
527
528                stored.entry.clone()
529            });
530
531        drop(entries);
532
533        let Some(entry) = found else {
534            self.reads.record(false);
535
536            return Ok(None);
537        };
538
539        let value = entry.value.downcast_ref::<CV>().cloned();
540
541        // A value of another type is a miss too: the caller gets none.
542        self.reads.record(value.is_some());
543
544        let value = value.ok_or(CacheError::type_mismatch(type_name::<CV>()))?;
545
546        Ok(Some(entry.map(|_| value)))
547    }
548
549    async fn set_entry<CV: CacheValue>(
550        &self,
551        key: &str,
552        entry: CacheEntry<CV>,
553    ) -> Result<(), CacheError> {
554        self.set_in_span(key, entry);
555
556        Ok(())
557    }
558
559    #[tracing::instrument(level = "debug", name = "memory remove", skip_all, fields(key = %self.name.format_key(key)))]
560    async fn remove(&self, key: &str) -> Result<bool, CacheError> {
561        let removed = write(self.entries.shard(key)).remove(key);
562
563        if removed.is_some() {
564            self.entries.len.fetch_sub(1, Ordering::Relaxed);
565        }
566
567        // An expired entry goes too, but it wasn't there for a reader, as on Redis. The time is
568        // read after the removal, so one that expired while this waited for the lock counts as
569        // expired, and only for an entry with a deadline: measured, reading it on every removal
570        // slows them by 5% on ARM.
571        Ok(removed.is_some_and(|stored| {
572            stored
573                .deadline
574                .is_none_or(|deadline| self.clock.instant() < deadline)
575        }))
576    }
577
578    #[tracing::instrument(level = "debug", name = "memory remove_prefix", skip_all, fields(store = %self.name, %prefix))]
579    async fn remove_prefix(&self, prefix: &str) -> Result<usize, CacheError> {
580        let prefix = KeyPrefix::new(prefix)?;
581        let now = self.clock.instant();
582        let mut removed = Vec::new();
583
584        self.extract(&mut removed, |key, _| prefix.matches(key));
585
586        let live = removed
587            .iter()
588            .filter(|(_, stored)| !stored.is_expired(now))
589            .count();
590
591        // As for `clear`: freeing many values can take a while.
592        off_async_thread(move || drop(removed));
593
594        Ok(live)
595    }
596
597    #[tracing::instrument(level = "debug", name = "memory clear", skip_all, fields(store = %self.name))]
598    async fn clear(&self) -> Result<(), CacheError> {
599        // Clones share the name, so every key in the maps is this store's: take each map whole.
600        let cleared: Vec<EntryMap> = self
601            .entries
602            .shards
603            .iter()
604            .map(|shard| {
605                let taken = mem::take(&mut *write(shard));
606
607                self.entries.len.fetch_sub(taken.len(), Ordering::Relaxed);
608
609                taken
610            })
611            .collect();
612
613        // The store is empty now; freeing what it held can take a while.
614        off_async_thread(move || drop(cleared));
615
616        Ok(())
617    }
618}
619
620#[cfg(test)]
621mod tests {
622    use std::{
623        convert::Infallible,
624        fmt::Display,
625        future::pending,
626        ops::Range,
627        ptr,
628        sync::{Mutex, atomic::AtomicUsize, mpsc},
629        time::Duration,
630    };
631
632    use futures_util::{FutureExt, future::join_all};
633    use serde::{Deserialize, Serialize};
634    use sisa_caching_core::{CacheKey, CacheOptions, settings::MAX_TTL_SECS};
635    use sisa_caching_testing::{Logs, ManualClock, SlowDrop, eventually};
636
637    use super::*;
638    use crate::settings::MemorySettings;
639
640    fn key(key: impl Display) -> CacheKey {
641        CacheKey::new("user", key).unwrap()
642    }
643
644    fn ttl(secs: u64) -> CacheOptions {
645        CacheOptions::with_ttl(Duration::from_secs(secs))
646    }
647
648    fn secs(secs: u64) -> Duration {
649        Duration::from_secs(secs)
650    }
651
652    fn store(
653        clock: &ManualClock,
654        settings: InMemoryCacheSettings,
655    ) -> InMemoryCacheStore<ManualClock> {
656        InMemoryCacheStore::new("app")
657            .unwrap()
658            .with_clock(clock.clone())
659            .with_settings(settings)
660            .unwrap()
661    }
662
663    fn with_ttl(ttl_secs: u64) -> InMemoryCacheSettings {
664        InMemoryCacheSettings {
665            common: {
666                let mut settings = CacheSettings::default();
667                settings.default_ttl_secs = Some(ttl_secs);
668                settings
669            },
670            ..InMemoryCacheSettings::default()
671        }
672    }
673
674    fn with_limit(max_entries: usize) -> InMemoryCacheSettings {
675        InMemoryCacheSettings {
676            memory: MemorySettings {
677                max_entries: Some(max_entries),
678                ..MemorySettings::default()
679            },
680            ..InMemoryCacheSettings::default()
681        }
682    }
683
684    /// The ids in `ids` the store still holds.
685    async fn held<C: Clock>(store: &InMemoryCacheStore<C>, ids: Range<u32>) -> Vec<u32> {
686        let mut held = Vec::new();
687
688        for id in ids {
689            if store.get::<u32>(&key(id)).await.unwrap().is_some() {
690                held.push(id);
691            }
692        }
693
694        held
695    }
696
697    /// Waits until the store's trim, which runs on the blocking pool, is done.
698    async fn trimmed<C: Clock>(store: &InMemoryCacheStore<C>) {
699        eventually("the trim ends", async || {
700            !store.entries.trimming.load(Ordering::Acquire)
701        })
702        .await;
703    }
704
705    #[tokio::test]
706    async fn debug_shows_the_store_but_never_a_value() {
707        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
708
709        store.set(&key(1), "secret".to_owned(), None).await.unwrap();
710
711        let shown = format!("{store:?}");
712
713        assert!(shown.contains(r#"name: KeyPrefix("app")"#), "{shown}");
714        assert!(shown.contains("len: 1"), "{shown}");
715        assert!(!shown.contains("secret"), "{shown}");
716    }
717
718    #[tokio::test]
719    async fn one_store_holds_values_of_many_types() {
720        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
721
722        store.set(&key(1), "ada".to_owned(), None).await.unwrap();
723        store.set(&key(2), 42_u64, None).await.unwrap();
724
725        assert_eq!(
726            store.get::<String>(&key(1)).await.unwrap().as_deref(),
727            Some("ada")
728        );
729        assert_eq!(store.get::<u64>(&key(2)).await.unwrap(), Some(42));
730        assert!(matches!(
731            store.get::<u64>(&key(1)).await,
732            Err(CacheError::TypeMismatch {
733                expected: "u64",
734                ..
735            })
736        ));
737
738        // Any string is a key.
739        store.set("user:a:b", 3_u8, None).await.unwrap();
740        assert_eq!(store.get::<u8>("user:a:b").await.unwrap(), Some(3));
741
742        // A write replaces the value and its type.
743        store.set(&key(1), 7_u64, None).await.unwrap();
744
745        assert_eq!(store.get::<u64>(&key(1)).await.unwrap(), Some(7));
746    }
747
748    #[tokio::test]
749    async fn values_expire_after_the_default_or_the_per_call_ttl() {
750        let clock = ManualClock::new();
751        let store = store(&clock, with_ttl(10));
752
753        store.set(&key(1), 1_u32, None).await.unwrap();
754        store.set(&key(2), 2_u32, ttl(5)).await.unwrap();
755
756        clock.advance(secs(5));
757        assert_eq!(held(&store, 1..3).await, [1]);
758
759        clock.advance(secs(5));
760        assert!(held(&store, 1..3).await.is_empty());
761    }
762
763    #[tokio::test]
764    async fn a_zero_ttl_removes_the_value() {
765        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
766
767        store.set(&key(1), 1_u32, None).await.unwrap();
768        store
769            .set(&key(1), 1_u32, CacheOptions::with_ttl(Duration::ZERO))
770            .await
771            .unwrap();
772
773        assert!(held(&store, 1..2).await.is_empty());
774    }
775
776    #[tokio::test]
777    async fn a_ttl_over_365_days_is_rejected_and_nothing_is_stored() {
778        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
779
780        assert!(matches!(
781            store
782                .set(&key(1), 1_u32, CacheOptions::with_ttl(Duration::MAX))
783                .await,
784            Err(CacheError::InvalidSettings { field: "ttl", .. })
785        ));
786        assert!(held(&store, 1..2).await.is_empty());
787    }
788
789    #[tokio::test]
790    async fn set_entry_keeps_the_entrys_own_lifetime() {
791        let clock = ManualClock::new();
792        let store = store(&clock, with_ttl(1));
793        let forever = CacheEntry::new(1_u32, clock.now(), None);
794        let created_earlier = CacheEntry::new(2_u32, clock.now() - secs(50), Some(secs(60)));
795
796        store.set_entry(&key(1), forever.clone()).await.unwrap();
797        store
798            .set_entry(&key(2), created_earlier.clone())
799            .await
800            .unwrap();
801        clock.advance(secs(9));
802
803        assert_eq!(store.get_entry(&key(1)).await.unwrap(), Some(forever));
804        assert_eq!(
805            store.get_entry(&key(2)).await.unwrap(),
806            Some(created_earlier)
807        );
808
809        clock.advance(secs(1));
810        assert_eq!(
811            held(&store, 1..3).await,
812            [1],
813            "the 60 s entry had 10 s left"
814        );
815    }
816
817    #[tokio::test]
818    async fn a_local_ttl_shortens_how_long_an_entry_stays_but_keeps_its_metadata() {
819        let clock = ManualClock::new();
820        let store = store(&clock, InMemoryCacheSettings::default()).with_local_ttl(secs(10));
821
822        store.set(&key(1), 1_u32, ttl(60)).await.unwrap();
823        // One that never expires goes too.
824        store.set(&key(2), 2_u32, None).await.unwrap();
825
826        let entry = store.get_entry::<u32>(&key(1)).await.unwrap().unwrap();
827
828        assert_eq!(entry.ttl(), Some(secs(60)));
829        assert_eq!(held(&store, 1..3).await, [1, 2]);
830
831        clock.advance(secs(10));
832        assert!(held(&store, 1..3).await.is_empty());
833    }
834
835    #[tokio::test]
836    async fn a_wall_clock_change_does_not_move_a_deadline() {
837        let clock = ManualClock::new();
838        let store = store(&clock, InMemoryCacheSettings::default());
839
840        store.set(&key(1), 1_u32, ttl(10)).await.unwrap();
841        clock.jump_wall_clock(secs(3600));
842
843        assert_eq!(held(&store, 1..2).await, [1]);
844    }
845
846    #[tokio::test]
847    async fn removals_touch_only_their_keys() {
848        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
849        let username = CacheKey::new("username", 1).unwrap();
850
851        store.set(&key(1), 1_u32, None).await.unwrap();
852        store.set(&key(2), 2_u32, None).await.unwrap();
853        store.set(&username, 3_u32, None).await.unwrap();
854
855        assert!(store.remove(&key(1)).await.unwrap());
856        assert!(!store.remove(&key(1)).await.unwrap(), "already gone");
857        assert_eq!(
858            store.remove_prefix("user").await.unwrap(),
859            1,
860            "`user` does not match `username`"
861        );
862        assert_eq!(store.get::<u32>(&username).await.unwrap(), Some(3));
863
864        for prefix in ["", "user:", "a::b"] {
865            assert!(
866                matches!(
867                    store.remove_prefix(prefix).await,
868                    Err(CacheError::InvalidKey(_))
869                ),
870                "{prefix:?}"
871            );
872        }
873
874        store.clear().await.unwrap();
875        assert_eq!(store.get::<u32>(&username).await.unwrap(), None);
876    }
877
878    #[tokio::test]
879    async fn removals_count_only_live_entries() {
880        let clock = ManualClock::new();
881        let store = store(&clock, InMemoryCacheSettings::default());
882
883        store.set(&key(1), 1_u32, ttl(1)).await.unwrap();
884        store.set(&key(2), 2_u32, ttl(1)).await.unwrap();
885        store.set(&key(3), 3_u32, None).await.unwrap();
886        clock.advance(secs(2));
887
888        assert!(!store.remove(&key(1)).await.unwrap(), "expired");
889        assert_eq!(store.remove_prefix("user").await.unwrap(), 1);
890        assert_eq!(store.purge(), 0, "the expired entries went too");
891    }
892
893    #[tokio::test]
894    async fn an_entry_that_expires_while_a_call_waits_for_its_map_counts_as_expired() {
895        let clock = ManualClock::new();
896        let store = store(
897            &clock,
898            InMemoryCacheSettings {
899                memory: MemorySettings {
900                    shards: Some(1),
901                    ..MemorySettings::default()
902                },
903                ..InMemoryCacheSettings::default()
904            },
905        );
906
907        store.set(&key(1), 1_u32, ttl(1)).await.unwrap();
908        store.set(&key(2), 2_u32, ttl(1)).await.unwrap();
909
910        let held_map = write(&store.entries.shards[0]);
911
912        std::thread::scope(|scope| {
913            let read = scope.spawn(|| store.get::<u32>(&key(1)).now_or_never().unwrap());
914            let removal = scope.spawn(|| store.remove(&key(2)).now_or_never().unwrap());
915
916            // Both wait for the map while the entries expire.
917            std::thread::sleep(Duration::from_millis(50));
918            clock.advance(secs(1));
919            drop(held_map);
920
921            assert_eq!(read.join().unwrap().unwrap(), None);
922            assert!(!removal.join().unwrap().unwrap(), "expired");
923        });
924    }
925
926    #[tokio::test]
927    async fn purge_drops_the_expired_entries() {
928        let clock = ManualClock::new();
929        let store = store(&clock, InMemoryCacheSettings::default());
930
931        store.set(&key(1), 1_u32, ttl(1)).await.unwrap();
932        store.set(&key(2), 2_u32, ttl(1)).await.unwrap();
933        store.set(&key(3), 3_u32, None).await.unwrap();
934        clock.advance(secs(1));
935
936        assert_eq!(store.purge(), 2);
937        assert_eq!(held(&store, 1..4).await, [3]);
938    }
939
940    #[tokio::test(start_paused = true)]
941    async fn the_purge_worker_purges_on_the_blocking_pool() {
942        let clock = ManualClock::new();
943        let store = store(&clock, InMemoryCacheSettings::default());
944        let (slow, dropped, release) = SlowDrop::new();
945
946        store.set(&key(1), slow, ttl(1)).await.unwrap();
947        clock.advance(secs(1));
948        // The worker's first purge, a minute after the write, frees the expired value.
949        dropped.await.unwrap();
950
951        release.send(()).expect("the purge held up the runtime");
952    }
953
954    #[tokio::test]
955    async fn clear_empties_the_store_at_once_and_frees_the_values_on_the_blocking_pool() {
956        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
957        let (slow, dropped, release) = SlowDrop::new();
958
959        store.set(&key(1), slow, None).await.unwrap();
960        store.clear().await.unwrap();
961        dropped.await.unwrap();
962
963        assert!(held(&store, 1..2).await.is_empty());
964        release.send(()).expect("the clear held up the runtime");
965    }
966
967    #[tokio::test]
968    async fn remove_prefix_frees_the_values_on_the_blocking_pool() {
969        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
970        let (slow, dropped, release) = SlowDrop::new();
971
972        store.set(&key(1), slow, None).await.unwrap();
973        assert_eq!(store.remove_prefix("user").await.unwrap(), 1);
974        dropped.await.unwrap();
975
976        assert!(held(&store, 1..2).await.is_empty());
977        release.send(()).expect("the removal held up the runtime");
978    }
979
980    #[tokio::test(start_paused = true)]
981    async fn the_longest_purge_interval_waits_without_panicking() {
982        let store = store(&ManualClock::new(), InMemoryCacheSettings::default()).for_worker();
983        let purging = purge_every(store, Duration::from_secs(MAX_TTL_SECS));
984
985        assert!(
986            tokio::time::timeout(secs(3600), purging).await.is_err(),
987            "the task keeps waiting"
988        );
989    }
990
991    #[tokio::test]
992    async fn without_a_purge_interval_a_write_starts_no_worker() {
993        let store = store(
994            &ManualClock::new(),
995            InMemoryCacheSettings {
996                memory: MemorySettings {
997                    purge_interval_secs: None,
998                    ..MemorySettings::default()
999                },
1000                ..InMemoryCacheSettings::default()
1001            },
1002        );
1003
1004        store.set(&key(1), 1_u32, None).await.unwrap();
1005
1006        assert_eq!(
1007            Arc::strong_count(&store.entries),
1008            1,
1009            "no worker holds a copy"
1010        );
1011    }
1012
1013    #[tokio::test]
1014    async fn a_full_store_drops_the_least_recently_used() {
1015        let store = store(&ManualClock::new(), with_limit(10));
1016
1017        for id in 0..10_u32 {
1018            store.set(&key(id), id, None).await.unwrap();
1019        }
1020        // Reading 0 makes 1 and 2 the least recently used.
1021        store.get::<u32>(&key(0)).await.unwrap();
1022        store.set(&key(10), 10_u32, None).await.unwrap();
1023        trimmed(&store).await;
1024
1025        assert_eq!(held(&store, 0..11).await, [0, 3, 4, 5, 6, 7, 8, 9, 10]);
1026    }
1027
1028    #[tokio::test]
1029    async fn a_trim_drops_only_as_many_entries_read_together_as_it_needs() {
1030        let store = store(&ManualClock::new(), with_limit(10));
1031
1032        for id in 0..10_u32 {
1033            store.set(&key(id), id, None).await.unwrap();
1034        }
1035        // Read since the same write, all ten tie as the least recently used.
1036        held(&store, 0..10).await;
1037        store.set(&key(10), 10_u32, None).await.unwrap();
1038        trimmed(&store).await;
1039
1040        let held = held(&store, 0..11).await;
1041
1042        assert_eq!(held.len(), 9, "{held:?}");
1043        assert!(held.contains(&10), "{held:?}");
1044    }
1045
1046    #[tokio::test]
1047    async fn a_full_store_drops_expired_entries_first() {
1048        let clock = ManualClock::new();
1049        let store = store(&clock, with_limit(10));
1050
1051        for id in 0..10_u32 {
1052            let options = (id < 5).then(|| ttl(1));
1053
1054            store.set(&key(id), id, options).await.unwrap();
1055        }
1056        clock.advance(secs(1));
1057        store.set(&key(10), 10_u32, None).await.unwrap();
1058        trimmed(&store).await;
1059
1060        assert_eq!(held(&store, 5..11).await, [5, 6, 7, 8, 9, 10]);
1061    }
1062
1063    #[tokio::test]
1064    async fn a_full_store_trims_to_nine_tenths_of_its_limit() {
1065        let clock = ManualClock::new();
1066        let store = store(&clock, with_limit(10));
1067
1068        store.set(&key(0), 0_u32, ttl(1)).await.unwrap();
1069        for id in 1..10_u32 {
1070            store.set(&key(id), id, None).await.unwrap();
1071        }
1072        clock.advance(secs(1));
1073        // Dropping the expired entry alone gets back to the limit, but the trim goes on to 9, so
1074        // the next writes need no work.
1075        store.set(&key(10), 10_u32, None).await.unwrap();
1076        trimmed(&store).await;
1077
1078        assert_eq!(held(&store, 0..11).await, [2, 3, 4, 5, 6, 7, 8, 9, 10]);
1079    }
1080
1081    #[tokio::test]
1082    async fn a_trim_runs_on_the_blocking_pool_while_the_write_goes_on() {
1083        let store = store(&ManualClock::new(), with_limit(1));
1084        let (slow, dropped, release) = SlowDrop::new();
1085
1086        store.set(&key(0), slow, None).await.unwrap();
1087        // Past the limit: the trim drops 0, the least recently used.
1088        store.set(&key(1), 1_u32, None).await.unwrap();
1089        dropped.await.unwrap();
1090
1091        // The test runtime has one thread, so 0 is being freed on another while this runs.
1092        release.send(()).expect("the trim held up the write");
1093        assert_eq!(held(&store, 0..2).await, [1]);
1094    }
1095
1096    #[tokio::test]
1097    async fn a_store_filled_again_during_a_trim_is_trimmed_again() {
1098        let store = store(
1099            &ManualClock::new(),
1100            InMemoryCacheSettings {
1101                memory: MemorySettings {
1102                    max_entries: Some(100),
1103                    shards: Some(4),
1104                    ..MemorySettings::default()
1105                },
1106                ..InMemoryCacheSettings::default()
1107            },
1108        );
1109        let last_map = &store.entries.shards[3];
1110        let mut ids = (0_u32..).filter(|&id| !ptr::eq(store.entries.shard(&key(id)), last_map));
1111        let mut set = |count| {
1112            for id in ids.by_ref().take(count) {
1113                store
1114                    .set(&key(id), id, None)
1115                    .now_or_never()
1116                    .unwrap()
1117                    .unwrap();
1118            }
1119        };
1120
1121        set(100);
1122        let held_map = write(last_map);
1123        // Past the limit: the trim counts the entries of the other maps, then waits for this one.
1124        set(1);
1125        std::thread::sleep(Duration::from_millis(50));
1126        // The trim is running, so these start none, and it counted none of them.
1127        set(100);
1128        drop(held_map);
1129
1130        eventually("the store is back under its limit", async || {
1131            !store.entries.trimming.load(Ordering::Acquire)
1132                && store.entries.len.load(Ordering::Relaxed) <= 100
1133        })
1134        .await;
1135    }
1136
1137    #[test]
1138    fn keys_spread_over_every_map() {
1139        let entries = Entries::new(16);
1140        let mut counts = [0; 16];
1141
1142        for id in 0..1_600 {
1143            let shard = entries.shard(&key(id));
1144            let index = entries.shards.iter().position(|it| ptr::eq(it, shard));
1145
1146            counts[index.unwrap()] += 1;
1147        }
1148
1149        // 100 on average.
1150        assert!(
1151            counts.iter().all(|count| (75..=125).contains(count)),
1152            "{counts:?}"
1153        );
1154    }
1155
1156    #[tokio::test]
1157    async fn every_write_and_removal_keeps_the_entry_count_right() {
1158        let clock = ManualClock::new();
1159        let store = store(
1160            &clock,
1161            InMemoryCacheSettings {
1162                memory: MemorySettings {
1163                    max_entries: Some(10),
1164                    shards: Some(4),
1165                    ..MemorySettings::default()
1166                },
1167                ..InMemoryCacheSettings::default()
1168            },
1169        );
1170        let order = |id: u32| CacheKey::new("order", id).unwrap();
1171
1172        for id in 0..10_u32 {
1173            store
1174                .set_entry(&key(id), CacheEntry::new(id, clock.now(), None))
1175                .await
1176                .unwrap();
1177        }
1178        // Replaced; removed twice; removed by a zero TTL twice: 8 left.
1179        store.set(&key(0), 0_u32, None).await.unwrap();
1180        store.remove(&key(1)).await.unwrap();
1181        store.remove(&key(1)).await.unwrap();
1182        for _ in 0..2 {
1183            store
1184                .set(&key(2), 2_u32, CacheOptions::with_ttl(Duration::ZERO))
1185                .await
1186                .unwrap();
1187        }
1188        // Expired, then found by a read and by a purge: 6 left.
1189        store.set(&key(3), 3_u32, ttl(1)).await.unwrap();
1190        store.set(&key(4), 4_u32, ttl(1)).await.unwrap();
1191        clock.advance(secs(1));
1192        store.get::<u32>(&key(3)).await.unwrap();
1193        store.purge();
1194        // Added, then removed by prefix: 6 left.
1195        store.set(&order(1), 1_u32, None).await.unwrap();
1196        store.set(&order(2), 2_u32, None).await.unwrap();
1197        store.remove_prefix("order").await.unwrap();
1198
1199        for id in 10..14_u32 {
1200            store.set(&key(id), id, None).await.unwrap();
1201        }
1202        assert_eq!(
1203            held(&store, 0..14).await.len(),
1204            10,
1205            "at the limit, nothing goes"
1206        );
1207
1208        store.set(&key(14), 14_u32, None).await.unwrap();
1209        trimmed(&store).await;
1210        assert_eq!(
1211            held(&store, 0..15).await.len(),
1212            9,
1213            "past it, trimmed to nine tenths"
1214        );
1215
1216        store.clear().await.unwrap();
1217        for id in 0..10_u32 {
1218            store.set(&key(id), id, None).await.unwrap();
1219        }
1220        assert_eq!(
1221            held(&store, 0..10).await.len(),
1222            10,
1223            "a clear counts down to zero"
1224        );
1225    }
1226
1227    #[tokio::test]
1228    async fn get_or_set_loads_a_missing_value_once_for_every_caller() {
1229        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
1230        let loads = AtomicUsize::new(0);
1231        let load = async || {
1232            loads.fetch_add(1, Ordering::SeqCst);
1233            tokio::time::sleep(Duration::from_millis(10)).await;
1234
1235            Ok::<_, Infallible>("ada".to_owned())
1236        };
1237        let user = key(1);
1238
1239        let values = join_all((0..10).map(|_| store.get_or_set(&user, load, None))).await;
1240
1241        assert!(values.iter().all(|value| value.as_deref() == Ok("ada")));
1242        assert_eq!(loads.load(Ordering::SeqCst), 1);
1243        assert_eq!(
1244            store.get::<String>(&user).await.unwrap().as_deref(),
1245            Some("ada")
1246        );
1247    }
1248
1249    #[tokio::test]
1250    async fn get_or_set_waits_for_no_load_of_the_same_key_on_another_store() {
1251        let clock = ManualClock::new();
1252        let (first, second) = (
1253            store(&clock, InMemoryCacheSettings::default()),
1254            store(&clock, InMemoryCacheSettings::default()),
1255        );
1256        // The first store's load never finishes, so it holds its lock on the key for good.
1257        let user = key(1);
1258        let mut stuck =
1259            Box::pin(first.get_or_set(&user, pending::<Result<String, Infallible>>, None));
1260
1261        assert!((&mut stuck).now_or_never().is_none());
1262
1263        let loaded = tokio::time::timeout(
1264            secs(1),
1265            second.get_or_set(&user, async || Ok::<_, Infallible>("ada".to_owned()), None),
1266        )
1267        .await
1268        .expect("each store has locks of its own");
1269
1270        assert_eq!(loaded.as_deref(), Ok("ada"));
1271    }
1272
1273    #[tokio::test]
1274    async fn get_or_set_stops_waiting_for_another_load_after_the_lock_timeout() {
1275        let store = store(
1276            &ManualClock::new(),
1277            InMemoryCacheSettings {
1278                common: {
1279                    let mut settings = CacheSettings::default();
1280                    settings.lock_timeout_ms = Some(20);
1281                    settings
1282                },
1283                ..InMemoryCacheSettings::default()
1284            },
1285        );
1286        // The first load never finishes, so it holds the key's lock for good.
1287        let user = key(1);
1288        let mut stuck =
1289            Box::pin(store.get_or_set(&user, pending::<Result<String, Infallible>>, None));
1290
1291        assert!((&mut stuck).now_or_never().is_none());
1292
1293        let loaded = tokio::time::timeout(
1294            secs(1),
1295            store.get_or_set(
1296                &key(1),
1297                async || Ok::<_, Infallible>("ada".to_owned()),
1298                None,
1299            ),
1300        )
1301        .await
1302        .expect("the lock timeout ends the wait");
1303
1304        assert_eq!(loaded.as_deref(), Ok("ada"));
1305    }
1306
1307    #[tokio::test]
1308    async fn get_or_set_stores_over_a_value_of_another_type() {
1309        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
1310
1311        store.set(&key(1), 42_u64, None).await.unwrap();
1312
1313        let loaded = store
1314            .get_or_set(
1315                &key(1),
1316                async || Ok::<_, Infallible>("ada".to_owned()),
1317                None,
1318            )
1319            .await;
1320
1321        assert_eq!(loaded.as_deref(), Ok("ada"));
1322        assert_eq!(
1323            store.get::<String>(&key(1)).await.unwrap().as_deref(),
1324            Some("ada")
1325        );
1326    }
1327
1328    #[tokio::test]
1329    async fn get_or_set_logs_a_run_of_failed_reads_once_and_never_the_key() {
1330        let logs = Logs::default();
1331        let _logging = tracing::subscriber::set_default(logs.clone());
1332        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
1333        let load = async || Ok::<_, Infallible>("ada".to_owned());
1334        let email = |id| key(format!("ada{id}@example.com"));
1335
1336        // Each key holds another type, so both reads of each call fail.
1337        for id in 0..3 {
1338            store.set(&email(id), 42_u64, None).await.unwrap();
1339            store.get_or_set(&email(id), load, None).await.unwrap();
1340        }
1341        // What the last call stored over its key reads.
1342        store.get_or_set(&email(2), load, None).await.unwrap();
1343
1344        let logged = logs.lines();
1345        let lines: Vec<&String> = logged
1346            .iter()
1347            .filter(|line| line.contains("operation="))
1348            .collect();
1349
1350        assert_eq!(lines.len(), 2, "{lines:?}");
1351        assert!(lines[0].starts_with("WARN"), "{lines:?}");
1352        assert!(lines[0].contains(r#"operation="get""#), "{lines:?}");
1353        assert!(lines[0].contains("store=app"), "{lines:?}");
1354        assert!(lines[1].starts_with("INFO"), "{lines:?}");
1355        assert!(lines[1].contains("store calls work again"), "{lines:?}");
1356        assert!(!logged.join(" ").contains("@example.com"), "{logged:?}");
1357    }
1358
1359    #[tokio::test]
1360    async fn the_purge_worker_logs_its_start_and_stops_with_the_last_clone() {
1361        let logs = Logs::default();
1362        let _logging = tracing::subscriber::set_default(logs.clone());
1363        let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
1364        let clone = store.clone();
1365        let entries = Arc::downgrade(&store.entries);
1366        let logged = |message: &str| logs.lines().iter().any(|line| line.contains(message));
1367
1368        store.set(&key(1), 1_u32, None).await.unwrap();
1369        eventually("the worker starts", async || logged("worker started")).await;
1370        drop(store);
1371        drop(clone);
1372        eventually("the worker stops and drops its copy", async || {
1373            logged("worker stopped") && entries.upgrade().is_none()
1374        })
1375        .await;
1376
1377        for line in logs.lines() {
1378            assert!(line.contains("store=app"), "{line}");
1379            assert!(line.contains("in-memory-cache-purge-worker"), "{line}");
1380        }
1381    }
1382
1383    #[tokio::test]
1384    async fn get_or_set_refreshes_ahead_and_keeps_the_old_value_if_that_fails() {
1385        let clock = ManualClock::new();
1386        let store = store(
1387            &clock,
1388            InMemoryCacheSettings {
1389                common: {
1390                    let mut settings = CacheSettings::default();
1391                    settings.default_ttl_secs = Some(10);
1392                    settings.refresh_threshold = Some(0.8);
1393                    settings
1394                },
1395                ..InMemoryCacheSettings::default()
1396            },
1397        );
1398        let user = key(1);
1399        let get_or_set = |loaded: Result<&'static str, &'static str>| {
1400            store.get_or_set(&user, async move || loaded.map(str::to_owned), None)
1401        };
1402
1403        store.set(&key(1), "old".to_owned(), None).await.unwrap();
1404
1405        clock.advance(secs(7));
1406        assert_eq!(
1407            get_or_set(Ok("new")).await.as_deref(),
1408            Ok("old"),
1409            "not due yet"
1410        );
1411
1412        clock.advance(secs(1));
1413        assert_eq!(
1414            get_or_set(Err("down")).await.as_deref(),
1415            Ok("old"),
1416            "failed refresh"
1417        );
1418        assert_eq!(
1419            get_or_set(Ok("new")).await.as_deref(),
1420            Ok("new"),
1421            "refreshed"
1422        );
1423        assert_eq!(
1424            store.get::<String>(&user).await.unwrap().as_deref(),
1425            Some("new")
1426        );
1427    }
1428
1429    #[tokio::test]
1430    async fn a_failed_refresh_serves_the_cached_value_only_while_the_store_holds_it() {
1431        let clock = ManualClock::new();
1432        let store = store(
1433            &clock,
1434            InMemoryCacheSettings {
1435                common: {
1436                    let mut settings = CacheSettings::default();
1437                    settings.default_ttl_secs = Some(10);
1438                    settings.refresh_threshold = Some(0.5);
1439                    settings
1440                },
1441                ..InMemoryCacheSettings::default()
1442            },
1443        )
1444        .with_local_ttl(secs(8));
1445        let user = key(1);
1446        let refresh = |advance: u64| {
1447            let clock = clock.clone();
1448
1449            store.get_or_set(
1450                &user,
1451                async move || {
1452                    clock.advance(secs(advance));
1453                    Err::<String, _>("down")
1454                },
1455                None,
1456            )
1457        };
1458
1459        // Still held: the cached value.
1460        store.set(&user, "old".to_owned(), None).await.unwrap();
1461        clock.advance(secs(6));
1462        assert_eq!(refresh(0).await.as_deref(), Ok("old"));
1463
1464        // The 8-second local TTL passes during the load, though the entry's TTL is 10 seconds.
1465        assert_eq!(refresh(3).await, Err("down"));
1466        assert_eq!(store.get::<String>(&user).await.unwrap(), None);
1467
1468        // The entry's own TTL passes during the load.
1469        store.set(&user, "old".to_owned(), ttl(4)).await.unwrap();
1470        clock.advance(secs(3));
1471        assert_eq!(refresh(2).await, Err("down"));
1472
1473        // A write removes it during the load.
1474        store.set(&user, "old".to_owned(), None).await.unwrap();
1475        clock.advance(secs(6));
1476
1477        let loaded = store
1478            .get_or_set(
1479                &user,
1480                async || {
1481                    store.remove(&user).await.unwrap();
1482                    Err::<String, _>("down")
1483                },
1484                None,
1485            )
1486            .await;
1487
1488        assert_eq!(loaded, Err("down"));
1489    }
1490
1491    type Hook = Box<dyn FnOnce() + Send>;
1492
1493    /// A manual clock that runs a hook once, the next time a store reads the wall-clock time.
1494    #[derive(Clone)]
1495    struct HookClock(ManualClock, Arc<Mutex<Option<Hook>>>);
1496
1497    // Runs the hook once, then reads the manual clock.
1498    impl Clock for HookClock {
1499        fn now(&self) -> std::time::SystemTime {
1500            let hook = self.1.lock().unwrap().take();
1501
1502            if let Some(hook) = hook {
1503                hook();
1504            }
1505
1506            self.0.now()
1507        }
1508
1509        fn instant(&self) -> Instant {
1510            self.0.instant()
1511        }
1512    }
1513
1514    #[tokio::test]
1515    async fn get_or_set_skips_a_refresh_another_caller_made_since_its_read() {
1516        let clock = HookClock(ManualClock::new(), Arc::default());
1517        let store = InMemoryCacheStore::new("app")
1518            .unwrap()
1519            .with_clock(clock.clone())
1520            .with_settings(InMemoryCacheSettings {
1521                common: {
1522                    let mut settings = CacheSettings::default();
1523                    settings.default_ttl_secs = Some(10);
1524                    settings.refresh_threshold = Some(0.5);
1525                    settings
1526                },
1527                ..InMemoryCacheSettings::default()
1528            })
1529            .unwrap();
1530        let loads = Arc::new(AtomicUsize::new(0));
1531        let load = {
1532            let loads = Arc::clone(&loads);
1533
1534            move || {
1535                loads.fetch_add(1, Ordering::SeqCst);
1536                async { Ok::<_, Infallible>("new".to_owned()) }
1537            }
1538        };
1539
1540        store.set(&key(1), "old".to_owned(), None).await.unwrap();
1541        clock.0.advance(secs(6));
1542
1543        // `get_or_set` reads the time once it has read the entry, before it takes the lock:
1544        // another caller refreshes the key right then.
1545        let (other, refresh) = (store.clone(), load.clone());
1546
1547        *clock.1.lock().unwrap() = Some(Box::new(move || {
1548            let refreshed = other.get_or_set(&key(1), refresh, None).now_or_never();
1549
1550            assert_eq!(refreshed.unwrap().as_deref(), Ok("new"));
1551        }));
1552
1553        let loaded = store.get_or_set(&key(1), load, None).await;
1554
1555        assert_eq!(loaded.as_deref(), Ok("new"));
1556        assert_eq!(loads.load(Ordering::SeqCst), 1);
1557    }
1558
1559    /// Calls its store from `clone` and `drop`, as a value holding a handle to its own cache
1560    /// might. A store that cloned or freed values under its lock would deadlock on it.
1561    #[derive(Serialize, Deserialize)]
1562    struct CallsTheStore {
1563        #[serde(skip)]
1564        store: Option<InMemoryCacheStore<ManualClock>>,
1565    }
1566
1567    // Calls the store, as a value's `Clone` may.
1568    impl Clone for CallsTheStore {
1569        fn clone(&self) -> Self {
1570            if let Some(store) = &self.store {
1571                store.purge();
1572            }
1573
1574            Self {
1575                store: self.store.clone(),
1576            }
1577        }
1578    }
1579
1580    // Calls the store, as a value's `Drop` may.
1581    impl Drop for CallsTheStore {
1582        fn drop(&mut self) {
1583            if let Some(store) = &self.store {
1584                store.purge();
1585            }
1586        }
1587    }
1588
1589    #[test]
1590    fn a_value_may_call_the_store_from_its_clone_or_drop() {
1591        let clock = ManualClock::new();
1592        let store = store(
1593            &clock,
1594            InMemoryCacheSettings {
1595                memory: MemorySettings {
1596                    max_entries: Some(2),
1597                    shards: Some(4),
1598                    ..MemorySettings::default()
1599                },
1600                ..InMemoryCacheSettings::default()
1601            },
1602        );
1603        let (finished, done) = mpsc::channel();
1604
1605        std::thread::spawn(move || {
1606            let run = |call: &mut dyn FnMut() -> Result<(), CacheError>| call().unwrap();
1607            let value = || CallsTheStore {
1608                store: Some(store.clone()),
1609            };
1610            let set = |id: u32, options: Option<CacheOptions>| {
1611                store
1612                    .set(&key(id), value(), options)
1613                    .now_or_never()
1614                    .unwrap()
1615            };
1616
1617            // Read, replaced, removed, and replaced by an entry with no time left.
1618            run(&mut || set(1, None));
1619            run(&mut || {
1620                store
1621                    .get::<CallsTheStore>(&key(1))
1622                    .now_or_never()
1623                    .unwrap()
1624                    .map(drop)
1625            });
1626            run(&mut || set(1, None));
1627            run(&mut || store.remove(&key(1)).now_or_never().unwrap().map(drop));
1628            run(&mut || set(1, None));
1629            run(&mut || set(1, Some(CacheOptions::with_ttl(Duration::ZERO))));
1630            // Expired, then found by a read and by a purge.
1631            run(&mut || set(2, Some(ttl(1))));
1632            clock.advance(secs(1));
1633            run(&mut || {
1634                store
1635                    .get::<CallsTheStore>(&key(2))
1636                    .now_or_never()
1637                    .unwrap()
1638                    .map(drop)
1639            });
1640            run(&mut || set(2, Some(ttl(1))));
1641            clock.advance(secs(1));
1642            store.purge();
1643            // Past the limit of 2: the expired entry goes first, then the least recently used.
1644            run(&mut || set(1, Some(ttl(1))));
1645            clock.advance(secs(1));
1646            for id in 2..5_u32 {
1647                run(&mut || set(id, None));
1648            }
1649            // Removed by prefix, then cleared.
1650            run(&mut || {
1651                store
1652                    .remove_prefix("user")
1653                    .now_or_never()
1654                    .unwrap()
1655                    .map(drop)
1656            });
1657            run(&mut || set(1, None));
1658            run(&mut || store.clear().now_or_never().unwrap());
1659
1660            finished.send(()).unwrap();
1661        });
1662
1663        done.recv_timeout(Duration::from_secs(5))
1664            .expect("a value called the store while the store held its lock");
1665    }
1666}