//! A map whose entries expire: the server's memory of what it looked up, //! each kept as long as its kind says. It holds at most `cap` entries and //! about `bytes` bytes, each entry weighed as it is put (`Weigh`); past //! either, the expired go, then those nearest their end, until it is three //! quarters full, which costs only lookups made again. A value weighing //! more than a quarter of `bytes` is not kept at all. Each lookup is //! counted, a hit or a miss, for `/metrics` and the summary each minute. //! //! A `Shared` is a `Ttl` filled once for all who ask for a key at once: //! the first to ask fills it, and the rest wait for that answer. use serde_json::Value; use std::collections::{BTreeMap, HashMap}; use std::hash::Hash; use std::mem::size_of; use std::sync::atomic::{AtomicBool, AtomicU64, Ordering}; use std::sync::{Arc, Mutex, MutexGuard, PoisonError}; use std::time::{Duration, Instant}; use tokio::sync::watch; /// About how many bytes a value holds, on the heap and inline. pub trait Weigh { fn weigh(&self) -> usize; } impl Weigh for String { fn weigh(&self) -> usize { size_of::() + self.len() } } impl Weigh for Value { fn weigh(&self) -> usize { size_of::() + match self { Value::String(s) => s.len(), Value::Array(a) => a.iter().map(Weigh::weigh).sum(), // A map entry: its key and value, and the map's own links. Value::Object(o) => o.iter().map(|(k, v)| k.weigh() + v.weigh() + 16).sum(), _ => 0, } } } impl Weigh for Arc { fn weigh(&self) -> usize { size_of::() + T::weigh(self) } } impl Weigh for Option { fn weigh(&self) -> usize { self.as_ref().map_or(size_of::(), Weigh::weigh) } } impl Weigh for Result { fn weigh(&self) -> usize { match self { Ok(v) => v.weigh(), Err(e) => e.weigh(), } } } impl Weigh for Vec { fn weigh(&self) -> usize { size_of::() + self.iter().map(Weigh::weigh).sum::() } } impl Weigh for BTreeMap { fn weigh(&self) -> usize { size_of::() + self .iter() .map(|(k, v)| k.weigh() + v.weigh() + 16) .sum::() } } impl Weigh for (A, B) { fn weigh(&self) -> usize { self.0.weigh() + self.1.weigh() } } impl Weigh for crate::pds::Record { fn weigh(&self) -> usize { self.uri.weigh() + self.cid.weigh() + self.value.weigh() } } impl Weigh for crate::backlinks::Count { fn weigh(&self) -> usize { size_of::() } } impl Weigh for crate::interactions::Generator { fn weigh(&self) -> usize { self.did.weigh() + size_of::() } } impl Weigh for crate::feeds::SavedFeed { fn weigh(&self) -> usize { self.name.weigh() + self.uri.weigh() + size_of::() } } impl Weigh for crate::xrpc::Asking { fn weigh(&self) -> usize { self.viewer.weigh() + self.service.weigh() + self.method.weigh() + self.pairs.weigh() } } /// What a cache holds now: its entries and their weight. #[derive(Clone, Copy, Debug, Default, PartialEq, Eq)] pub struct Held { pub entries: usize, pub bytes: usize, } /// The map's own cost of an entry, beside its key and value. const ENTRY: usize = 48; struct Inner { entries: HashMap, bytes: usize, } pub struct Ttl { inner: Mutex>, cap: usize, bytes: usize, hits: AtomicU64, misses: AtomicU64, } impl Ttl { /// A cache of at most `cap` entries and about `bytes` bytes. pub fn new(cap: usize, bytes: usize) -> Ttl { Ttl { inner: Mutex::new(Inner { entries: HashMap::new(), bytes: 0, }), cap, bytes, hits: AtomicU64::new(0), misses: AtomicU64::new(0), } } fn lock(&self) -> MutexGuard<'_, Inner> { self.inner.lock().unwrap_or_else(PoisonError::into_inner) } /// The value kept for `key`, if it has not expired. pub fn get(&self, key: &K) -> Option { let found = self.found(key); let counted = match found { Some(_) => &self.hits, None => &self.misses, }; counted.fetch_add(1, Ordering::Relaxed); found } fn found(&self, key: &K) -> Option { let mut inner = self.lock(); match inner.entries.get(key) { Some((until, _, v)) if *until > Instant::now() => Some(v.clone()), Some(_) => { inner.bytes -= inner.entries.remove(key).map_or(0, |(_, w, _)| w); None } None => None, } } /// Its hits and misses since it was made. pub fn lookups(&self) -> (u64, u64) { let hits = self.hits.load(Ordering::Relaxed); (hits, self.misses.load(Ordering::Relaxed)) } /// Keep `value` for `key` for `ttl`, unless it weighs too much to. pub fn put(&self, key: K, value: V, ttl: Duration) { let weight = ENTRY + key.weigh() + value.weigh(); let mut inner = self.lock(); if let Some((_, w, _)) = inner.entries.remove(&key) { inner.bytes -= w; } if weight > self.bytes / 4 { return; } if inner.entries.len() >= self.cap || inner.bytes + weight > self.bytes { self.evict(&mut inner); } inner.bytes += weight; inner .entries .insert(key, (Instant::now() + ttl, weight, value)); } /// The expired out, then those nearest their end, to three quarters full. fn evict(&self, inner: &mut Inner) { let now = Instant::now(); let mut freed = 0; inner.entries.retain(|_, (until, w, _)| { let keep = *until > now; if !keep { freed += *w; } keep }); inner.bytes -= freed; let (cap, bytes) = (self.cap * 3 / 4, self.bytes * 3 / 4); if inner.entries.len() <= cap && inner.bytes <= bytes { return; } let mut by_end: Vec<(Instant, K)> = inner .entries .iter() .map(|(k, (until, _, _))| (*until, k.clone())) .collect(); by_end.sort_unstable_by_key(|(until, _)| *until); for (_, k) in by_end { if inner.entries.len() <= cap && inner.bytes <= bytes { break; } inner.bytes -= inner.entries.remove(&k).map_or(0, |(_, w, _)| w); } } /// Forget every entry whose key `gone` picks. pub fn forget(&self, gone: impl Fn(&K) -> bool) { let mut inner = self.lock(); let mut freed = 0; inner.entries.retain(|k, (_, w, _)| { let keep = !gone(k); if !keep { freed += *w; } keep }); inner.bytes -= freed; } /// What it holds now. pub fn held(&self) -> Held { let inner = self.lock(); Held { entries: inner.entries.len(), bytes: inner.bytes, } } } /// A `Ttl` filled once for all who ask for a key at once: the first to ask /// fills it, and the rest wait for that answer. An error is shared with /// those waiting but never kept. A filler dropped before it answers (what /// asked stopped waiting) leaves those waiting to ask again, one of them /// filling. What is forgotten while it is filled is not kept. pub struct Shared { kept: Ttl, flying: Mutex>>, } /// A fill under way: its answer once it comes, and whether what it fills /// was forgotten since it began. struct Flight { answer: watch::Receiver>>, stale: Arc, } impl Shared { /// A cache of at most `cap` entries and about `bytes` bytes. pub fn new(cap: usize, bytes: usize) -> Shared { Shared { kept: Ttl::new(cap, bytes), flying: Mutex::new(HashMap::new()), } } fn flying(&self) -> MutexGuard<'_, HashMap>> { self.flying.lock().unwrap_or_else(PoisonError::into_inner) } /// The value kept for `key`; else the answer of the fill under way for /// it; else `fill`'s, a value kept for `ttl`. pub async fn get_or( &self, key: K, ttl: Duration, fill: impl Future>, ) -> Result { let lead = loop { let mut answer = { let mut flying = self.flying(); if let Some(v) = self.kept.get(&key) { return Ok(v); } match flying.get(&key) { Some(f) => f.answer.clone(), None => { let (tx, answer) = watch::channel(None); let stale = Arc::new(AtomicBool::new(false)); let flight = Flight { answer, stale: stale.clone(), }; flying.insert(key.clone(), flight); break Landing { shared: self, key: &key, tx, stale, }; } } }; // None where the filler was dropped: ask again. let got = answer.wait_for(Option::is_some).await.ok(); if let Some(got) = got.and_then(|a| a.clone()) { return got; } }; let got = fill.await; lead.land(&got, ttl); got } /// Forget every value whose key `gone` picks, and keep none that a fill /// under way for one answers. pub fn forget(&self, gone: &dyn Fn(&K) -> bool) { let mut flying = self.flying(); flying.retain(|k, f| { let keep = !gone(k); if !keep { f.stale.store(true, Ordering::Relaxed); } keep }); self.kept.forget(gone); } /// What it holds now. pub fn held(&self) -> Held { self.kept.held() } /// Its hits and misses since it was made. pub fn lookups(&self) -> (u64, u64) { self.kept.lookups() } } /// The fill a caller leads: it lands the answer, and dropped, answered or /// not, takes its flight off the board, so those asking next fill anew. struct Landing<'a, K: Eq + Hash, V, E> { shared: &'a Shared, key: &'a K, tx: watch::Sender>>, stale: Arc, } impl Landing<'_, K, V, E> { /// Keep a value unless it was forgotten as it flew (under the board's /// lock, as `forget` forgets), then give those waiting the answer. fn land(&self, got: &Result, ttl: Duration) { let flying = self.shared.flying(); if let Ok(v) = got && !self.stale.load(Ordering::Relaxed) { self.shared.kept.put(self.key.clone(), v.clone(), ttl); } drop(flying); self.tx.send_replace(Some(got.clone())); } } impl Drop for Landing<'_, K, V, E> { fn drop(&mut self) { let mut flying = self .shared .flying .lock() .unwrap_or_else(PoisonError::into_inner); // Its own flight, unless it was forgotten and another took its place. if flying .get(self.key) .is_some_and(|f| Arc::ptr_eq(&f.stale, &self.stale)) { flying.remove(self.key); } } } #[cfg(test)] mod tests { use super::*; use serde_json::json; #[test] fn expires_and_caps() { let c = Ttl::new(2, 1 << 20); let s = |v: &str| v.to_string(); c.put(s("a"), s("1"), Duration::from_secs(60)); c.put(s("gone"), s("2"), Duration::ZERO); assert_eq!(c.get(&s("a")), Some(s("1"))); assert_eq!(c.get(&s("gone")), None); assert_eq!(c.get(&s("never")), None); c.put(s("b"), s("3"), Duration::from_secs(60)); c.put(s("c"), s("4"), Duration::from_secs(60)); assert_eq!(c.get(&s("c")), Some(s("4"))); assert!(c.held().entries <= 2); } #[test] fn the_expired_go_first_and_alone_when_that_is_room_enough() { let c = Ttl::new(4, 1 << 20); let s = |v: &str| v.to_string(); for k in ["a", "b", "c"] { c.put(s(k), s("live"), Duration::from_secs(60)); } c.put(s("stale"), s("old"), Duration::ZERO); // Full: the expired one makes room, and nothing live goes. c.put(s("d"), s("new"), Duration::from_secs(60)); for k in ["a", "b", "c", "d"] { assert_eq!( c.get(&s(k)).as_deref(), Some(if k == "d" { "new" } else { "live" }) ); } let held = c.held(); assert_eq!(held.entries, 4); assert_eq!( held.bytes, c.lock().entries.values().map(|(_, w, _)| w).sum::() ); } #[test] fn records_weigh_their_text() { let record = |text: &str| crate::pds::Record { uri: "at://did:plc:x/a.b.c/1".into(), cid: "bafy".into(), value: json!({ "text": text }), }; let small = Arc::new(vec![record("")]).weigh(); let large = Arc::new(vec![record(&"x".repeat(10_000)), record("")]).weigh(); assert!( large >= small + record("").weigh() + 10_000, "{small} {large}" ); // A repository's records too heavy for a members cache are not kept. let c: Ttl>> = Ttl::new(10, 16 * 1024); c.put( "light".into(), Arc::new(vec![record("")]), Duration::from_secs(60), ); c.put( "heavy".into(), Arc::new(vec![record(&"x".repeat(10_000))]), Duration::from_secs(60), ); assert!(c.get(&"light".to_string()).is_some()); assert!(c.get(&"heavy".to_string()).is_none()); } #[test] fn bounded_by_bytes() { let c: Ttl = Ttl::new(1_000, 64 * 1024); let big = json!({ "text": "x".repeat(1_000) }); for i in 0..200 { c.put(format!("k{i}"), big.clone(), Duration::from_secs(60 + i)); assert!(c.held().bytes <= 64 * 1024, "{:?}", c.held()); } // Those nearest their end went first: the latest are kept. assert!(c.get(&"k199".to_string()).is_some()); assert!(c.get(&"k0".to_string()).is_none()); // One too heavy for it is not kept, and leaves nothing behind. c.put( "k199".into(), json!("x".repeat(17 * 1024)), Duration::from_secs(60), ); assert!(c.get(&"k199".to_string()).is_none()); let held = c.held(); assert_eq!( held.bytes, c.lock().entries.values().map(|(_, w, _)| w).sum::() ); } #[test] fn weighs_json() { let small = json!({ "a": 1 }).weigh(); let large = json!({ "a": "x".repeat(10_000) }).weigh(); assert!(large > small + 10_000 - 1); } type Strings = Shared<(String, String), String, String>; /// A key: who asked, and what. fn key(who: &str, what: &str) -> (String, String) { (who.to_string(), what.to_string()) } /// A fill answering `answer` after a moment, counted in `calls` as it /// starts. async fn counted(calls: &AtomicU64, answer: Result<&str, &str>) -> Result { calls.fetch_add(1, Ordering::SeqCst); tokio::time::sleep(Duration::from_millis(20)).await; answer.map(str::to_string).map_err(str::to_string) } #[tokio::test] async fn shared_keeps_a_value_its_time_and_never_an_error() { let c = Strings::new(10, 1 << 20); let calls = AtomicU64::new(0); let ttl = Duration::from_millis(200); let ask = |what: &str, answer| c.get_or(key("a", what), ttl, counted(&calls, answer)); // Filled, then within its time kept: the second fill is never run. assert_eq!(ask("q", Ok("1")).await, Ok("1".into())); assert_eq!(ask("q", Ok("2")).await, Ok("1".into())); assert_eq!(calls.load(Ordering::SeqCst), 1); // Past it, filled again. tokio::time::sleep(ttl).await; assert_eq!(ask("q", Ok("2")).await, Ok("2".into())); // An error is not kept: the next ask fills. assert_eq!(ask("e", Err("down")).await, Err("down".into())); assert_eq!(ask("e", Ok("up")).await, Ok("up".into())); assert_eq!(calls.load(Ordering::SeqCst), 4); assert_eq!(c.lookups(), (1, 4)); assert_eq!(c.held().entries, 2); } #[tokio::test] async fn shared_fills_once_for_all_asking_at_once() { let c = Strings::new(10, 1 << 20); let calls = AtomicU64::new(0); let ttl = Duration::from_secs(60); let answers = ["1", "2", "3", "4", "5"]; let asks = answers.map(|a| c.get_or(key("a", "q"), ttl, counted(&calls, Ok(a)))); let got = futures::future::join_all(asks).await; assert_eq!(got, vec![Ok("1".to_string()); 5]); assert_eq!(calls.load(Ordering::SeqCst), 1); // An error too is had by all asking at once, and not kept. let asks = (0..3).map(|_| c.get_or(key("a", "e"), ttl, counted(&calls, Err("down")))); let got = futures::future::join_all(asks).await; assert_eq!(got, vec![Err("down".to_string()); 3]); assert_eq!(calls.load(Ordering::SeqCst), 2); let again = c.get_or(key("a", "e"), ttl, counted(&calls, Ok("up"))); assert_eq!(again.await, Ok("up".into())); assert_eq!(calls.load(Ordering::SeqCst), 3); } #[tokio::test] async fn shared_asks_again_where_its_filler_stopped_waiting() { let c = Strings::new(10, 1 << 20); let calls = AtomicU64::new(0); let ttl = Duration::from_secs(60); // The first to ask stops waiting before its fill answers; the one // waiting on it fills. let first = tokio::time::timeout( Duration::from_millis(5), c.get_or(key("a", "q"), ttl, counted(&calls, Ok("1"))), ); let second = c.get_or(key("a", "q"), ttl, counted(&calls, Ok("2"))); let (first, second) = tokio::join!(first, second); assert!(first.is_err()); assert_eq!(second, Ok("2".into())); assert_eq!(calls.load(Ordering::SeqCst), 2); let kept = c.get_or(key("a", "q"), ttl, counted(&calls, Ok("3"))); assert_eq!(kept.await, Ok("2".into())); } #[tokio::test] async fn shared_forgets_what_it_is_told_to_and_what_flew_meanwhile() { let c = Strings::new(10, 1 << 20); let calls = AtomicU64::new(0); let ttl = Duration::from_secs(60); let ask = |who: &str, answer| c.get_or(key(who, "q"), ttl, counted(&calls, answer)); ask("alice", Ok("a1")).await.unwrap(); ask("bob", Ok("b1")).await.unwrap(); // Alice's alone forgotten. c.forget(&|(who, _)| who == "alice"); assert_eq!(ask("alice", Ok("a2")).await, Ok("a2".into())); assert_eq!(ask("bob", Ok("b2")).await, Ok("b1".into())); // Forgotten as it flies: who asked has its answer, but it is not // kept, and who asks after asks anew. let (sent, landed) = tokio::sync::oneshot::channel::<()>(); let slow = async { landed.await.unwrap(); Ok("old".to_string()) }; let flying = c.get_or(key("carol", "q"), ttl, slow); let after = async { tokio::task::yield_now().await; // Another's forgotten, Carol's flies on; then hers. c.forget(&|(who, _)| who == "dave"); c.forget(&|(who, _)| who == "carol"); let anew = ask("carol", Ok("new")).await; sent.send(()).unwrap(); anew }; let (flown, anew) = tokio::join!(flying, after); assert_eq!((flown, anew), (Ok("old".into()), Ok("new".into()))); assert_eq!(ask("carol", Ok("x")).await, Ok("new".into())); } }