use std::{
any::{Any, type_name},
collections::HashMap,
mem,
sync::{
Arc, PoisonError, RwLock, RwLockReadGuard, RwLockWriteGuard, TryLockError,
atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering},
},
time::{Duration, Instant},
};
use sisa_caching_core::{
cache::{CacheEntry, CacheError, CacheStore, CacheValue, KeyPrefix},
clock::{Clock, SystemClock},
locker::Locker,
metrics::{Layer, METRICS, Reads},
settings::CacheSettings,
worker::Worker,
};
use crate::settings::InMemoryCacheSettings;
fn off_async_thread(work: impl FnOnce() + Send + 'static) {
match tokio::runtime::Handle::try_current() {
Ok(runtime) => drop(runtime.spawn_blocking(work)),
Err(_) => work(),
}
}
type Erased = Arc<dyn Any + Send + Sync>;
struct StoredEntry {
entry: CacheEntry<Erased>,
deadline: Option<Instant>,
last_used: AtomicU64,
}
impl StoredEntry {
fn is_expired(&self, now: Instant) -> bool {
self.deadline.is_some_and(|deadline| now >= deadline)
}
}
type EntryMap = HashMap<String, StoredEntry>;
struct Entries {
shards: Box<[RwLock<EntryMap>]>,
len: AtomicUsize,
uses: AtomicU64,
trimming: AtomicBool,
}
impl Entries {
fn new(shards: usize) -> Self {
Self {
shards: (0..shards).map(|_| RwLock::default()).collect(),
len: AtomicUsize::new(0),
uses: AtomicU64::new(0),
trimming: AtomicBool::new(false),
}
}
fn next_use(&self) -> u64 {
self.uses.fetch_add(1, Ordering::Relaxed) + 1
}
fn shard(&self, key: &str) -> &RwLock<EntryMap> {
let count = self.shards.len();
if count == 1 {
return &self.shards[0];
}
let hash = key.as_bytes().chunks(8).fold(0_u64, |hash, chunk| {
let mut word = [0; 8];
word[..chunk.len()].copy_from_slice(chunk);
(hash.rotate_left(5) ^ u64::from_le_bytes(word)).wrapping_mul(0x517c_c1b7_2722_0a95)
});
&self.shards[((u128::from(hash) * count as u128) >> 64) as usize]
}
}
fn read(shard: &RwLock<EntryMap>) -> RwLockReadGuard<'_, EntryMap> {
shard.read().unwrap_or_else(PoisonError::into_inner)
}
fn write(shard: &RwLock<EntryMap>) -> RwLockWriteGuard<'_, EntryMap> {
shard.write().unwrap_or_else(PoisonError::into_inner)
}
async fn purge_every<C: Clock>(store: InMemoryCacheStore<C>, interval: Duration) {
loop {
tokio::time::sleep(interval).await;
let store = store.clone();
if let Err(error) = tokio::task::spawn_blocking(move || store.purge()).await
&& error.is_panic()
{
std::panic::resume_unwind(error.into_panic());
}
}
}
struct Trimming<C>(InMemoryCacheStore<C>);
impl<C> Drop for Trimming<C> {
fn drop(&mut self) {
self.0.entries.trimming.swap(false, Ordering::AcqRel);
}
}
#[derive(Clone)]
pub struct InMemoryCacheStore<C = SystemClock> {
name: KeyPrefix,
clock: C,
settings: InMemoryCacheSettings,
local_ttl: Option<Duration>,
entries: Arc<Entries>,
locker: Arc<Locker>,
worker: Worker,
reads: &'static Reads,
}
impl<C> std::fmt::Debug for InMemoryCacheStore<C> {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
formatter
.debug_struct("InMemoryCacheStore")
.field("name", &self.name)
.field("settings", &self.settings)
.field("len", &self.entries.len.load(Ordering::Relaxed))
.finish_non_exhaustive()
}
}
impl InMemoryCacheStore {
pub fn new(name: &str) -> Result<Self, CacheError> {
let name = KeyPrefix::new(name)?;
let settings = InMemoryCacheSettings::default();
Ok(Self {
reads: METRICS.reads(&name, Layer::Memory),
name,
clock: SystemClock,
entries: Arc::new(Entries::new(settings.memory.shards())),
local_ttl: None,
settings,
locker: Arc::default(),
worker: Worker::new(),
})
}
}
impl<C: Clock> InMemoryCacheStore<C> {
pub fn with_clock<T: Clock>(self, clock: T) -> InMemoryCacheStore<T> {
InMemoryCacheStore {
name: self.name,
clock,
settings: self.settings,
local_ttl: self.local_ttl,
entries: self.entries,
locker: self.locker,
worker: Worker::new(),
reads: self.reads,
}
}
pub fn with_settings(mut self, settings: InMemoryCacheSettings) -> Result<Self, CacheError> {
settings.validate()?;
self.entries = Arc::new(Entries::new(settings.memory.shards()));
self.worker = Worker::new();
self.settings = settings;
Ok(self)
}
#[doc(hidden)]
pub fn with_local_ttl(mut self, ttl: Duration) -> Self {
self.local_ttl = Some(ttl);
self
}
pub fn settings(&self) -> &InMemoryCacheSettings {
&self.settings
}
#[tracing::instrument(level = "debug", name = "memory purge", skip_all, fields(store = %self.name, removed))]
pub fn purge(&self) -> usize {
let now = self.clock.instant();
let removed = self.extract(&mut Vec::new(), |_, stored| stored.is_expired(now));
tracing::Span::current().record("removed", removed);
removed
}
#[tracing::instrument(level = "debug", name = "memory set", skip_all, fields(key = %self.name.format_key(key)))]
fn set_in_span<CV: CacheValue>(&self, key: &str, entry: CacheEntry<CV>) {
drop(self.replace_entry(key, entry));
}
#[doc(hidden)]
pub fn replace_entry<CV: CacheValue>(
&self,
key: &str,
entry: CacheEntry<CV>,
) -> impl Send + use<C, CV> {
if let Some(interval) = self.settings.memory.purge_interval() {
self.worker
.start("in-memory-cache-purge-worker", &self.name, || {
purge_every(self.for_worker(), interval)
});
}
let local_ttl = self.local_ttl;
let now =
(entry.expires_at().is_some() || local_ttl.is_some()).then(|| self.clock.instant());
let remaining = entry
.expires_at()
.and_then(|_| entry.remaining_ttl(self.clock.now()));
let ttl = match (remaining, local_ttl) {
(Some(remaining), Some(local_ttl)) => Some(remaining.min(local_ttl)),
(remaining, local_ttl) => remaining.or(local_ttl),
};
let stored = StoredEntry {
entry: entry.map(|value| Arc::new(value) as Erased),
deadline: ttl.zip(now).and_then(|(ttl, now)| now.checked_add(ttl)),
last_used: AtomicU64::new(match self.settings.memory.max_entries {
Some(_) => self.entries.next_use(),
None => 0,
}),
};
let mut entries = write(self.entries.shard(key));
let replaced = match entries.get_mut(key) {
Some(slot) => Some(mem::replace(slot, stored)),
None => {
entries.insert(key.to_owned(), stored);
self.entries.len.fetch_add(1, Ordering::Relaxed);
None
}
};
drop(entries);
if let Some(max) = self.settings.memory.max_entries
&& self.entries.len.load(Ordering::Relaxed) > max
{
self.start_trim(max);
}
replaced
}
fn start_trim(&self, max: usize) {
if self.entries.trimming.swap(true, Ordering::AcqRel) {
return;
}
let mut trimming = Trimming(self.for_worker());
off_async_thread(move || {
loop {
let removed = trimming.0.trim(max);
let store = trimming.0.clone();
drop(trimming);
drop(removed);
if store.entries.len.load(Ordering::Relaxed) <= max
|| store.entries.trimming.swap(true, Ordering::AcqRel)
{
return;
}
trimming = Trimming(store);
}
});
}
fn trim(&self, max: usize) -> Vec<(String, StoredEntry)> {
let mut removed = Vec::new();
if self.entries.len.load(Ordering::Relaxed) > max {
let now = self.clock.instant();
let target = max - max / 10;
let last_use = |stored: &StoredEntry| {
if stored.is_expired(now) {
0
} else {
stored.last_used.load(Ordering::Relaxed)
}
};
let mut uses = Vec::with_capacity(self.entries.len.load(Ordering::Relaxed));
for shard in &self.entries.shards {
uses.extend(read(shard).values().map(last_use));
}
if uses.len() > target {
let excess = uses.len() - target;
let (below, &mut cutoff, _) = uses.select_nth_unstable(excess - 1);
let mut ties = excess - below.iter().filter(|&&used| used < cutoff).count();
removed.reserve(excess);
let mut expired = 0;
let taken = self.extract(&mut removed, |_, stored| {
let used = last_use(stored);
if used == 0 {
expired += 1;
return true;
}
if used == cutoff && ties > 0 {
ties -= 1;
return true;
}
used < cutoff
});
let evicted = taken - expired;
if evicted > 0 {
METRICS.evicted(&self.name, evicted);
tracing::debug!(
store = %self.name,
evicted,
"store full; dropped the least recently used entries"
);
}
}
}
removed
}
pub(crate) fn for_worker(&self) -> Self {
Self {
worker: Worker::none(),
..self.clone()
}
}
fn extract(
&self,
taken: &mut Vec<(String, StoredEntry)>,
mut pick: impl FnMut(&str, &StoredEntry) -> bool,
) -> usize {
let start = taken.len();
for shard in &self.entries.shards {
let before = taken.len();
taken.extend(write(shard).extract_if(|key, stored| pick(key, stored)));
self.entries
.len
.fetch_sub(taken.len() - before, Ordering::Relaxed);
}
taken.len() - start
}
}
impl<C: Clock> sisa_caching_core::sealed::Sealed for InMemoryCacheStore<C> {}
impl<C: Clock> CacheStore for InMemoryCacheStore<C> {
type Error = CacheError;
type Clock = C;
fn name(&self) -> &KeyPrefix {
&self.name
}
fn cache_settings(&self) -> &CacheSettings {
&self.settings.common
}
fn locker(&self) -> &Locker {
&self.locker
}
fn clock(&self) -> &C {
&self.clock
}
#[tracing::instrument(level = "debug", name = "memory get", skip_all, fields(key = %self.name.format_key(key)))]
async fn get_entry<CV: CacheValue>(
&self,
key: &str,
) -> Result<Option<CacheEntry<CV>>, CacheError> {
let shard = self.entries.shard(key);
let before = self.clock.instant();
let (entries, now) = match shard.try_read() {
Ok(entries) => (entries, before),
Err(TryLockError::Poisoned(poisoned)) => (poisoned.into_inner(), before),
Err(TryLockError::WouldBlock) => {
let entries = read(shard);
(entries, self.clock.instant())
}
};
let found = entries
.get(key)
.filter(|stored| !stored.is_expired(now))
.map(|stored| {
if self.settings.memory.max_entries.is_some() {
let used = self.entries.uses.load(Ordering::Relaxed);
if stored.last_used.load(Ordering::Relaxed) != used {
stored.last_used.store(used, Ordering::Relaxed);
}
}
stored.entry.clone()
});
drop(entries);
let Some(entry) = found else {
self.reads.record(false);
return Ok(None);
};
let value = entry.value.downcast_ref::<CV>().cloned();
self.reads.record(value.is_some());
let value = value.ok_or(CacheError::type_mismatch(type_name::<CV>()))?;
Ok(Some(entry.map(|_| value)))
}
async fn set_entry<CV: CacheValue>(
&self,
key: &str,
entry: CacheEntry<CV>,
) -> Result<(), CacheError> {
self.set_in_span(key, entry);
Ok(())
}
#[tracing::instrument(level = "debug", name = "memory remove", skip_all, fields(key = %self.name.format_key(key)))]
async fn remove(&self, key: &str) -> Result<bool, CacheError> {
let removed = write(self.entries.shard(key)).remove(key);
if removed.is_some() {
self.entries.len.fetch_sub(1, Ordering::Relaxed);
}
Ok(removed.is_some_and(|stored| {
stored
.deadline
.is_none_or(|deadline| self.clock.instant() < deadline)
}))
}
#[tracing::instrument(level = "debug", name = "memory remove_prefix", skip_all, fields(store = %self.name, %prefix))]
async fn remove_prefix(&self, prefix: &str) -> Result<usize, CacheError> {
let prefix = KeyPrefix::new(prefix)?;
let now = self.clock.instant();
let mut removed = Vec::new();
self.extract(&mut removed, |key, _| prefix.matches(key));
let live = removed
.iter()
.filter(|(_, stored)| !stored.is_expired(now))
.count();
off_async_thread(move || drop(removed));
Ok(live)
}
#[tracing::instrument(level = "debug", name = "memory clear", skip_all, fields(store = %self.name))]
async fn clear(&self) -> Result<(), CacheError> {
let cleared: Vec<EntryMap> = self
.entries
.shards
.iter()
.map(|shard| {
let taken = mem::take(&mut *write(shard));
self.entries.len.fetch_sub(taken.len(), Ordering::Relaxed);
taken
})
.collect();
off_async_thread(move || drop(cleared));
Ok(())
}
}
#[cfg(test)]
mod tests {
use std::{
convert::Infallible,
fmt::Display,
future::pending,
ops::Range,
ptr,
sync::{Mutex, atomic::AtomicUsize, mpsc},
time::Duration,
};
use futures_util::{FutureExt, future::join_all};
use serde::{Deserialize, Serialize};
use sisa_caching_core::{CacheKey, CacheOptions, settings::MAX_TTL_SECS};
use sisa_caching_testing::{Logs, ManualClock, SlowDrop, eventually};
use super::*;
use crate::settings::MemorySettings;
fn key(key: impl Display) -> CacheKey {
CacheKey::new("user", key).unwrap()
}
fn ttl(secs: u64) -> CacheOptions {
CacheOptions::with_ttl(Duration::from_secs(secs))
}
fn secs(secs: u64) -> Duration {
Duration::from_secs(secs)
}
fn store(
clock: &ManualClock,
settings: InMemoryCacheSettings,
) -> InMemoryCacheStore<ManualClock> {
InMemoryCacheStore::new("app")
.unwrap()
.with_clock(clock.clone())
.with_settings(settings)
.unwrap()
}
fn with_ttl(ttl_secs: u64) -> InMemoryCacheSettings {
InMemoryCacheSettings {
common: {
let mut settings = CacheSettings::default();
settings.default_ttl_secs = Some(ttl_secs);
settings
},
..InMemoryCacheSettings::default()
}
}
fn with_limit(max_entries: usize) -> InMemoryCacheSettings {
InMemoryCacheSettings {
memory: MemorySettings {
max_entries: Some(max_entries),
..MemorySettings::default()
},
..InMemoryCacheSettings::default()
}
}
async fn held<C: Clock>(store: &InMemoryCacheStore<C>, ids: Range<u32>) -> Vec<u32> {
let mut held = Vec::new();
for id in ids {
if store.get::<u32>(&key(id)).await.unwrap().is_some() {
held.push(id);
}
}
held
}
async fn trimmed<C: Clock>(store: &InMemoryCacheStore<C>) {
eventually("the trim ends", async || {
!store.entries.trimming.load(Ordering::Acquire)
})
.await;
}
#[tokio::test]
async fn debug_shows_the_store_but_never_a_value() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
store.set(&key(1), "secret".to_owned(), None).await.unwrap();
let shown = format!("{store:?}");
assert!(shown.contains(r#"name: KeyPrefix("app")"#), "{shown}");
assert!(shown.contains("len: 1"), "{shown}");
assert!(!shown.contains("secret"), "{shown}");
}
#[tokio::test]
async fn one_store_holds_values_of_many_types() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
store.set(&key(1), "ada".to_owned(), None).await.unwrap();
store.set(&key(2), 42_u64, None).await.unwrap();
assert_eq!(
store.get::<String>(&key(1)).await.unwrap().as_deref(),
Some("ada")
);
assert_eq!(store.get::<u64>(&key(2)).await.unwrap(), Some(42));
assert!(matches!(
store.get::<u64>(&key(1)).await,
Err(CacheError::TypeMismatch {
expected: "u64",
..
})
));
store.set("user:a:b", 3_u8, None).await.unwrap();
assert_eq!(store.get::<u8>("user:a:b").await.unwrap(), Some(3));
store.set(&key(1), 7_u64, None).await.unwrap();
assert_eq!(store.get::<u64>(&key(1)).await.unwrap(), Some(7));
}
#[tokio::test]
async fn values_expire_after_the_default_or_the_per_call_ttl() {
let clock = ManualClock::new();
let store = store(&clock, with_ttl(10));
store.set(&key(1), 1_u32, None).await.unwrap();
store.set(&key(2), 2_u32, ttl(5)).await.unwrap();
clock.advance(secs(5));
assert_eq!(held(&store, 1..3).await, [1]);
clock.advance(secs(5));
assert!(held(&store, 1..3).await.is_empty());
}
#[tokio::test]
async fn a_zero_ttl_removes_the_value() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
store.set(&key(1), 1_u32, None).await.unwrap();
store
.set(&key(1), 1_u32, CacheOptions::with_ttl(Duration::ZERO))
.await
.unwrap();
assert!(held(&store, 1..2).await.is_empty());
}
#[tokio::test]
async fn a_ttl_over_365_days_is_rejected_and_nothing_is_stored() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
assert!(matches!(
store
.set(&key(1), 1_u32, CacheOptions::with_ttl(Duration::MAX))
.await,
Err(CacheError::InvalidSettings { field: "ttl", .. })
));
assert!(held(&store, 1..2).await.is_empty());
}
#[tokio::test]
async fn set_entry_keeps_the_entrys_own_lifetime() {
let clock = ManualClock::new();
let store = store(&clock, with_ttl(1));
let forever = CacheEntry::new(1_u32, clock.now(), None);
let created_earlier = CacheEntry::new(2_u32, clock.now() - secs(50), Some(secs(60)));
store.set_entry(&key(1), forever.clone()).await.unwrap();
store
.set_entry(&key(2), created_earlier.clone())
.await
.unwrap();
clock.advance(secs(9));
assert_eq!(store.get_entry(&key(1)).await.unwrap(), Some(forever));
assert_eq!(
store.get_entry(&key(2)).await.unwrap(),
Some(created_earlier)
);
clock.advance(secs(1));
assert_eq!(
held(&store, 1..3).await,
[1],
"the 60 s entry had 10 s left"
);
}
#[tokio::test]
async fn a_local_ttl_shortens_how_long_an_entry_stays_but_keeps_its_metadata() {
let clock = ManualClock::new();
let store = store(&clock, InMemoryCacheSettings::default()).with_local_ttl(secs(10));
store.set(&key(1), 1_u32, ttl(60)).await.unwrap();
store.set(&key(2), 2_u32, None).await.unwrap();
let entry = store.get_entry::<u32>(&key(1)).await.unwrap().unwrap();
assert_eq!(entry.ttl(), Some(secs(60)));
assert_eq!(held(&store, 1..3).await, [1, 2]);
clock.advance(secs(10));
assert!(held(&store, 1..3).await.is_empty());
}
#[tokio::test]
async fn a_wall_clock_change_does_not_move_a_deadline() {
let clock = ManualClock::new();
let store = store(&clock, InMemoryCacheSettings::default());
store.set(&key(1), 1_u32, ttl(10)).await.unwrap();
clock.jump_wall_clock(secs(3600));
assert_eq!(held(&store, 1..2).await, [1]);
}
#[tokio::test]
async fn removals_touch_only_their_keys() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
let username = CacheKey::new("username", 1).unwrap();
store.set(&key(1), 1_u32, None).await.unwrap();
store.set(&key(2), 2_u32, None).await.unwrap();
store.set(&username, 3_u32, None).await.unwrap();
assert!(store.remove(&key(1)).await.unwrap());
assert!(!store.remove(&key(1)).await.unwrap(), "already gone");
assert_eq!(
store.remove_prefix("user").await.unwrap(),
1,
"`user` does not match `username`"
);
assert_eq!(store.get::<u32>(&username).await.unwrap(), Some(3));
for prefix in ["", "user:", "a::b"] {
assert!(
matches!(
store.remove_prefix(prefix).await,
Err(CacheError::InvalidKey(_))
),
"{prefix:?}"
);
}
store.clear().await.unwrap();
assert_eq!(store.get::<u32>(&username).await.unwrap(), None);
}
#[tokio::test]
async fn removals_count_only_live_entries() {
let clock = ManualClock::new();
let store = store(&clock, InMemoryCacheSettings::default());
store.set(&key(1), 1_u32, ttl(1)).await.unwrap();
store.set(&key(2), 2_u32, ttl(1)).await.unwrap();
store.set(&key(3), 3_u32, None).await.unwrap();
clock.advance(secs(2));
assert!(!store.remove(&key(1)).await.unwrap(), "expired");
assert_eq!(store.remove_prefix("user").await.unwrap(), 1);
assert_eq!(store.purge(), 0, "the expired entries went too");
}
#[tokio::test]
async fn an_entry_that_expires_while_a_call_waits_for_its_map_counts_as_expired() {
let clock = ManualClock::new();
let store = store(
&clock,
InMemoryCacheSettings {
memory: MemorySettings {
shards: Some(1),
..MemorySettings::default()
},
..InMemoryCacheSettings::default()
},
);
store.set(&key(1), 1_u32, ttl(1)).await.unwrap();
store.set(&key(2), 2_u32, ttl(1)).await.unwrap();
let held_map = write(&store.entries.shards[0]);
std::thread::scope(|scope| {
let read = scope.spawn(|| store.get::<u32>(&key(1)).now_or_never().unwrap());
let removal = scope.spawn(|| store.remove(&key(2)).now_or_never().unwrap());
std::thread::sleep(Duration::from_millis(50));
clock.advance(secs(1));
drop(held_map);
assert_eq!(read.join().unwrap().unwrap(), None);
assert!(!removal.join().unwrap().unwrap(), "expired");
});
}
#[tokio::test]
async fn purge_drops_the_expired_entries() {
let clock = ManualClock::new();
let store = store(&clock, InMemoryCacheSettings::default());
store.set(&key(1), 1_u32, ttl(1)).await.unwrap();
store.set(&key(2), 2_u32, ttl(1)).await.unwrap();
store.set(&key(3), 3_u32, None).await.unwrap();
clock.advance(secs(1));
assert_eq!(store.purge(), 2);
assert_eq!(held(&store, 1..4).await, [3]);
}
#[tokio::test(start_paused = true)]
async fn the_purge_worker_purges_on_the_blocking_pool() {
let clock = ManualClock::new();
let store = store(&clock, InMemoryCacheSettings::default());
let (slow, dropped, release) = SlowDrop::new();
store.set(&key(1), slow, ttl(1)).await.unwrap();
clock.advance(secs(1));
dropped.await.unwrap();
release.send(()).expect("the purge held up the runtime");
}
#[tokio::test]
async fn clear_empties_the_store_at_once_and_frees_the_values_on_the_blocking_pool() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
let (slow, dropped, release) = SlowDrop::new();
store.set(&key(1), slow, None).await.unwrap();
store.clear().await.unwrap();
dropped.await.unwrap();
assert!(held(&store, 1..2).await.is_empty());
release.send(()).expect("the clear held up the runtime");
}
#[tokio::test]
async fn remove_prefix_frees_the_values_on_the_blocking_pool() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
let (slow, dropped, release) = SlowDrop::new();
store.set(&key(1), slow, None).await.unwrap();
assert_eq!(store.remove_prefix("user").await.unwrap(), 1);
dropped.await.unwrap();
assert!(held(&store, 1..2).await.is_empty());
release.send(()).expect("the removal held up the runtime");
}
#[tokio::test(start_paused = true)]
async fn the_longest_purge_interval_waits_without_panicking() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default()).for_worker();
let purging = purge_every(store, Duration::from_secs(MAX_TTL_SECS));
assert!(
tokio::time::timeout(secs(3600), purging).await.is_err(),
"the task keeps waiting"
);
}
#[tokio::test]
async fn without_a_purge_interval_a_write_starts_no_worker() {
let store = store(
&ManualClock::new(),
InMemoryCacheSettings {
memory: MemorySettings {
purge_interval_secs: None,
..MemorySettings::default()
},
..InMemoryCacheSettings::default()
},
);
store.set(&key(1), 1_u32, None).await.unwrap();
assert_eq!(
Arc::strong_count(&store.entries),
1,
"no worker holds a copy"
);
}
#[tokio::test]
async fn a_full_store_drops_the_least_recently_used() {
let store = store(&ManualClock::new(), with_limit(10));
for id in 0..10_u32 {
store.set(&key(id), id, None).await.unwrap();
}
store.get::<u32>(&key(0)).await.unwrap();
store.set(&key(10), 10_u32, None).await.unwrap();
trimmed(&store).await;
assert_eq!(held(&store, 0..11).await, [0, 3, 4, 5, 6, 7, 8, 9, 10]);
}
#[tokio::test]
async fn a_trim_drops_only_as_many_entries_read_together_as_it_needs() {
let store = store(&ManualClock::new(), with_limit(10));
for id in 0..10_u32 {
store.set(&key(id), id, None).await.unwrap();
}
held(&store, 0..10).await;
store.set(&key(10), 10_u32, None).await.unwrap();
trimmed(&store).await;
let held = held(&store, 0..11).await;
assert_eq!(held.len(), 9, "{held:?}");
assert!(held.contains(&10), "{held:?}");
}
#[tokio::test]
async fn a_full_store_drops_expired_entries_first() {
let clock = ManualClock::new();
let store = store(&clock, with_limit(10));
for id in 0..10_u32 {
let options = (id < 5).then(|| ttl(1));
store.set(&key(id), id, options).await.unwrap();
}
clock.advance(secs(1));
store.set(&key(10), 10_u32, None).await.unwrap();
trimmed(&store).await;
assert_eq!(held(&store, 5..11).await, [5, 6, 7, 8, 9, 10]);
}
#[tokio::test]
async fn a_full_store_trims_to_nine_tenths_of_its_limit() {
let clock = ManualClock::new();
let store = store(&clock, with_limit(10));
store.set(&key(0), 0_u32, ttl(1)).await.unwrap();
for id in 1..10_u32 {
store.set(&key(id), id, None).await.unwrap();
}
clock.advance(secs(1));
store.set(&key(10), 10_u32, None).await.unwrap();
trimmed(&store).await;
assert_eq!(held(&store, 0..11).await, [2, 3, 4, 5, 6, 7, 8, 9, 10]);
}
#[tokio::test]
async fn a_trim_runs_on_the_blocking_pool_while_the_write_goes_on() {
let store = store(&ManualClock::new(), with_limit(1));
let (slow, dropped, release) = SlowDrop::new();
store.set(&key(0), slow, None).await.unwrap();
store.set(&key(1), 1_u32, None).await.unwrap();
dropped.await.unwrap();
release.send(()).expect("the trim held up the write");
assert_eq!(held(&store, 0..2).await, [1]);
}
#[tokio::test]
async fn a_store_filled_again_during_a_trim_is_trimmed_again() {
let store = store(
&ManualClock::new(),
InMemoryCacheSettings {
memory: MemorySettings {
max_entries: Some(100),
shards: Some(4),
..MemorySettings::default()
},
..InMemoryCacheSettings::default()
},
);
let last_map = &store.entries.shards[3];
let mut ids = (0_u32..).filter(|&id| !ptr::eq(store.entries.shard(&key(id)), last_map));
let mut set = |count| {
for id in ids.by_ref().take(count) {
store
.set(&key(id), id, None)
.now_or_never()
.unwrap()
.unwrap();
}
};
set(100);
let held_map = write(last_map);
set(1);
std::thread::sleep(Duration::from_millis(50));
set(100);
drop(held_map);
eventually("the store is back under its limit", async || {
!store.entries.trimming.load(Ordering::Acquire)
&& store.entries.len.load(Ordering::Relaxed) <= 100
})
.await;
}
#[test]
fn keys_spread_over_every_map() {
let entries = Entries::new(16);
let mut counts = [0; 16];
for id in 0..1_600 {
let shard = entries.shard(&key(id));
let index = entries.shards.iter().position(|it| ptr::eq(it, shard));
counts[index.unwrap()] += 1;
}
assert!(
counts.iter().all(|count| (75..=125).contains(count)),
"{counts:?}"
);
}
#[tokio::test]
async fn every_write_and_removal_keeps_the_entry_count_right() {
let clock = ManualClock::new();
let store = store(
&clock,
InMemoryCacheSettings {
memory: MemorySettings {
max_entries: Some(10),
shards: Some(4),
..MemorySettings::default()
},
..InMemoryCacheSettings::default()
},
);
let order = |id: u32| CacheKey::new("order", id).unwrap();
for id in 0..10_u32 {
store
.set_entry(&key(id), CacheEntry::new(id, clock.now(), None))
.await
.unwrap();
}
store.set(&key(0), 0_u32, None).await.unwrap();
store.remove(&key(1)).await.unwrap();
store.remove(&key(1)).await.unwrap();
for _ in 0..2 {
store
.set(&key(2), 2_u32, CacheOptions::with_ttl(Duration::ZERO))
.await
.unwrap();
}
store.set(&key(3), 3_u32, ttl(1)).await.unwrap();
store.set(&key(4), 4_u32, ttl(1)).await.unwrap();
clock.advance(secs(1));
store.get::<u32>(&key(3)).await.unwrap();
store.purge();
store.set(&order(1), 1_u32, None).await.unwrap();
store.set(&order(2), 2_u32, None).await.unwrap();
store.remove_prefix("order").await.unwrap();
for id in 10..14_u32 {
store.set(&key(id), id, None).await.unwrap();
}
assert_eq!(
held(&store, 0..14).await.len(),
10,
"at the limit, nothing goes"
);
store.set(&key(14), 14_u32, None).await.unwrap();
trimmed(&store).await;
assert_eq!(
held(&store, 0..15).await.len(),
9,
"past it, trimmed to nine tenths"
);
store.clear().await.unwrap();
for id in 0..10_u32 {
store.set(&key(id), id, None).await.unwrap();
}
assert_eq!(
held(&store, 0..10).await.len(),
10,
"a clear counts down to zero"
);
}
#[tokio::test]
async fn get_or_set_loads_a_missing_value_once_for_every_caller() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
let loads = AtomicUsize::new(0);
let load = async || {
loads.fetch_add(1, Ordering::SeqCst);
tokio::time::sleep(Duration::from_millis(10)).await;
Ok::<_, Infallible>("ada".to_owned())
};
let user = key(1);
let values = join_all((0..10).map(|_| store.get_or_set(&user, load, None))).await;
assert!(values.iter().all(|value| value.as_deref() == Ok("ada")));
assert_eq!(loads.load(Ordering::SeqCst), 1);
assert_eq!(
store.get::<String>(&user).await.unwrap().as_deref(),
Some("ada")
);
}
#[tokio::test]
async fn get_or_set_waits_for_no_load_of_the_same_key_on_another_store() {
let clock = ManualClock::new();
let (first, second) = (
store(&clock, InMemoryCacheSettings::default()),
store(&clock, InMemoryCacheSettings::default()),
);
let user = key(1);
let mut stuck =
Box::pin(first.get_or_set(&user, pending::<Result<String, Infallible>>, None));
assert!((&mut stuck).now_or_never().is_none());
let loaded = tokio::time::timeout(
secs(1),
second.get_or_set(&user, async || Ok::<_, Infallible>("ada".to_owned()), None),
)
.await
.expect("each store has locks of its own");
assert_eq!(loaded.as_deref(), Ok("ada"));
}
#[tokio::test]
async fn get_or_set_stops_waiting_for_another_load_after_the_lock_timeout() {
let store = store(
&ManualClock::new(),
InMemoryCacheSettings {
common: {
let mut settings = CacheSettings::default();
settings.lock_timeout_ms = Some(20);
settings
},
..InMemoryCacheSettings::default()
},
);
let user = key(1);
let mut stuck =
Box::pin(store.get_or_set(&user, pending::<Result<String, Infallible>>, None));
assert!((&mut stuck).now_or_never().is_none());
let loaded = tokio::time::timeout(
secs(1),
store.get_or_set(
&key(1),
async || Ok::<_, Infallible>("ada".to_owned()),
None,
),
)
.await
.expect("the lock timeout ends the wait");
assert_eq!(loaded.as_deref(), Ok("ada"));
}
#[tokio::test]
async fn get_or_set_stores_over_a_value_of_another_type() {
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
store.set(&key(1), 42_u64, None).await.unwrap();
let loaded = store
.get_or_set(
&key(1),
async || Ok::<_, Infallible>("ada".to_owned()),
None,
)
.await;
assert_eq!(loaded.as_deref(), Ok("ada"));
assert_eq!(
store.get::<String>(&key(1)).await.unwrap().as_deref(),
Some("ada")
);
}
#[tokio::test]
async fn get_or_set_logs_a_run_of_failed_reads_once_and_never_the_key() {
let logs = Logs::default();
let _logging = tracing::subscriber::set_default(logs.clone());
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
let load = async || Ok::<_, Infallible>("ada".to_owned());
let email = |id| key(format!("ada{id}@example.com"));
for id in 0..3 {
store.set(&email(id), 42_u64, None).await.unwrap();
store.get_or_set(&email(id), load, None).await.unwrap();
}
store.get_or_set(&email(2), load, None).await.unwrap();
let logged = logs.lines();
let lines: Vec<&String> = logged
.iter()
.filter(|line| line.contains("operation="))
.collect();
assert_eq!(lines.len(), 2, "{lines:?}");
assert!(lines[0].starts_with("WARN"), "{lines:?}");
assert!(lines[0].contains(r#"operation="get""#), "{lines:?}");
assert!(lines[0].contains("store=app"), "{lines:?}");
assert!(lines[1].starts_with("INFO"), "{lines:?}");
assert!(lines[1].contains("store calls work again"), "{lines:?}");
assert!(!logged.join(" ").contains("@example.com"), "{logged:?}");
}
#[tokio::test]
async fn the_purge_worker_logs_its_start_and_stops_with_the_last_clone() {
let logs = Logs::default();
let _logging = tracing::subscriber::set_default(logs.clone());
let store = store(&ManualClock::new(), InMemoryCacheSettings::default());
let clone = store.clone();
let entries = Arc::downgrade(&store.entries);
let logged = |message: &str| logs.lines().iter().any(|line| line.contains(message));
store.set(&key(1), 1_u32, None).await.unwrap();
eventually("the worker starts", async || logged("worker started")).await;
drop(store);
drop(clone);
eventually("the worker stops and drops its copy", async || {
logged("worker stopped") && entries.upgrade().is_none()
})
.await;
for line in logs.lines() {
assert!(line.contains("store=app"), "{line}");
assert!(line.contains("in-memory-cache-purge-worker"), "{line}");
}
}
#[tokio::test]
async fn get_or_set_refreshes_ahead_and_keeps_the_old_value_if_that_fails() {
let clock = ManualClock::new();
let store = store(
&clock,
InMemoryCacheSettings {
common: {
let mut settings = CacheSettings::default();
settings.default_ttl_secs = Some(10);
settings.refresh_threshold = Some(0.8);
settings
},
..InMemoryCacheSettings::default()
},
);
let user = key(1);
let get_or_set = |loaded: Result<&'static str, &'static str>| {
store.get_or_set(&user, async move || loaded.map(str::to_owned), None)
};
store.set(&key(1), "old".to_owned(), None).await.unwrap();
clock.advance(secs(7));
assert_eq!(
get_or_set(Ok("new")).await.as_deref(),
Ok("old"),
"not due yet"
);
clock.advance(secs(1));
assert_eq!(
get_or_set(Err("down")).await.as_deref(),
Ok("old"),
"failed refresh"
);
assert_eq!(
get_or_set(Ok("new")).await.as_deref(),
Ok("new"),
"refreshed"
);
assert_eq!(
store.get::<String>(&user).await.unwrap().as_deref(),
Some("new")
);
}
#[tokio::test]
async fn a_failed_refresh_serves_the_cached_value_only_while_the_store_holds_it() {
let clock = ManualClock::new();
let store = store(
&clock,
InMemoryCacheSettings {
common: {
let mut settings = CacheSettings::default();
settings.default_ttl_secs = Some(10);
settings.refresh_threshold = Some(0.5);
settings
},
..InMemoryCacheSettings::default()
},
)
.with_local_ttl(secs(8));
let user = key(1);
let refresh = |advance: u64| {
let clock = clock.clone();
store.get_or_set(
&user,
async move || {
clock.advance(secs(advance));
Err::<String, _>("down")
},
None,
)
};
store.set(&user, "old".to_owned(), None).await.unwrap();
clock.advance(secs(6));
assert_eq!(refresh(0).await.as_deref(), Ok("old"));
assert_eq!(refresh(3).await, Err("down"));
assert_eq!(store.get::<String>(&user).await.unwrap(), None);
store.set(&user, "old".to_owned(), ttl(4)).await.unwrap();
clock.advance(secs(3));
assert_eq!(refresh(2).await, Err("down"));
store.set(&user, "old".to_owned(), None).await.unwrap();
clock.advance(secs(6));
let loaded = store
.get_or_set(
&user,
async || {
store.remove(&user).await.unwrap();
Err::<String, _>("down")
},
None,
)
.await;
assert_eq!(loaded, Err("down"));
}
type Hook = Box<dyn FnOnce() + Send>;
#[derive(Clone)]
struct HookClock(ManualClock, Arc<Mutex<Option<Hook>>>);
impl Clock for HookClock {
fn now(&self) -> std::time::SystemTime {
let hook = self.1.lock().unwrap().take();
if let Some(hook) = hook {
hook();
}
self.0.now()
}
fn instant(&self) -> Instant {
self.0.instant()
}
}
#[tokio::test]
async fn get_or_set_skips_a_refresh_another_caller_made_since_its_read() {
let clock = HookClock(ManualClock::new(), Arc::default());
let store = InMemoryCacheStore::new("app")
.unwrap()
.with_clock(clock.clone())
.with_settings(InMemoryCacheSettings {
common: {
let mut settings = CacheSettings::default();
settings.default_ttl_secs = Some(10);
settings.refresh_threshold = Some(0.5);
settings
},
..InMemoryCacheSettings::default()
})
.unwrap();
let loads = Arc::new(AtomicUsize::new(0));
let load = {
let loads = Arc::clone(&loads);
move || {
loads.fetch_add(1, Ordering::SeqCst);
async { Ok::<_, Infallible>("new".to_owned()) }
}
};
store.set(&key(1), "old".to_owned(), None).await.unwrap();
clock.0.advance(secs(6));
let (other, refresh) = (store.clone(), load.clone());
*clock.1.lock().unwrap() = Some(Box::new(move || {
let refreshed = other.get_or_set(&key(1), refresh, None).now_or_never();
assert_eq!(refreshed.unwrap().as_deref(), Ok("new"));
}));
let loaded = store.get_or_set(&key(1), load, None).await;
assert_eq!(loaded.as_deref(), Ok("new"));
assert_eq!(loads.load(Ordering::SeqCst), 1);
}
#[derive(Serialize, Deserialize)]
struct CallsTheStore {
#[serde(skip)]
store: Option<InMemoryCacheStore<ManualClock>>,
}
impl Clone for CallsTheStore {
fn clone(&self) -> Self {
if let Some(store) = &self.store {
store.purge();
}
Self {
store: self.store.clone(),
}
}
}
impl Drop for CallsTheStore {
fn drop(&mut self) {
if let Some(store) = &self.store {
store.purge();
}
}
}
#[test]
fn a_value_may_call_the_store_from_its_clone_or_drop() {
let clock = ManualClock::new();
let store = store(
&clock,
InMemoryCacheSettings {
memory: MemorySettings {
max_entries: Some(2),
shards: Some(4),
..MemorySettings::default()
},
..InMemoryCacheSettings::default()
},
);
let (finished, done) = mpsc::channel();
std::thread::spawn(move || {
let run = |call: &mut dyn FnMut() -> Result<(), CacheError>| call().unwrap();
let value = || CallsTheStore {
store: Some(store.clone()),
};
let set = |id: u32, options: Option<CacheOptions>| {
store
.set(&key(id), value(), options)
.now_or_never()
.unwrap()
};
run(&mut || set(1, None));
run(&mut || {
store
.get::<CallsTheStore>(&key(1))
.now_or_never()
.unwrap()
.map(drop)
});
run(&mut || set(1, None));
run(&mut || store.remove(&key(1)).now_or_never().unwrap().map(drop));
run(&mut || set(1, None));
run(&mut || set(1, Some(CacheOptions::with_ttl(Duration::ZERO))));
run(&mut || set(2, Some(ttl(1))));
clock.advance(secs(1));
run(&mut || {
store
.get::<CallsTheStore>(&key(2))
.now_or_never()
.unwrap()
.map(drop)
});
run(&mut || set(2, Some(ttl(1))));
clock.advance(secs(1));
store.purge();
run(&mut || set(1, Some(ttl(1))));
clock.advance(secs(1));
for id in 2..5_u32 {
run(&mut || set(id, None));
}
run(&mut || {
store
.remove_prefix("user")
.now_or_never()
.unwrap()
.map(drop)
});
run(&mut || set(1, None));
run(&mut || store.clear().now_or_never().unwrap());
finished.send(()).unwrap();
});
done.recv_timeout(Duration::from_secs(5))
.expect("a value called the store while the store held its lock");
}
}