Line data Source code
1 : use std::borrow::Borrow;
2 : use std::hash::Hash;
3 : use std::time::{Duration, Instant};
4 :
5 : // This seems to make more sense than `lru` or `cached`:
6 : //
7 : // * `near/nearcore` ditched `cached` in favor of `lru`
8 : // (https://github.com/near/nearcore/issues?q=is%3Aissue+lru+is%3Aclosed).
9 : //
10 : // * `lru` methods use an obscure `KeyRef` type in their contraints (which is deliberately excluded from docs).
11 : // This severely hinders its usage both in terms of creating wrappers and supported key types.
12 : //
13 : // On the other hand, `hashlink` has good download stats and appears to be maintained.
14 : use hashlink::{LruCache, linked_hash_map::RawEntryMut};
15 : use tracing::debug;
16 :
17 : use super::Cache;
18 : use super::common::Cached;
19 :
20 : /// An implementation of timed LRU cache with fixed capacity.
21 : /// Key properties:
22 : ///
23 : /// * Whenever a new entry is inserted, the least recently accessed one is evicted.
24 : /// The cache also keeps track of entry's insertion time (`created_at`) and TTL (`expires_at`).
25 : ///
26 : /// * If `update_ttl_on_retrieval` is `true`. When the entry is about to be retrieved, we check its expiration timestamp.
27 : /// If the entry has expired, we remove it from the cache; Otherwise we bump the
28 : /// expiration timestamp (e.g. +5mins) and change its place in LRU list to prolong
29 : /// its existence.
30 : ///
31 : /// * There's an API for immediate invalidation (removal) of a cache entry;
32 : /// It's useful in case we know for sure that the entry is no longer correct.
33 : /// See [`Cached`] for more information.
34 : ///
35 : /// * Expired entries are kept in the cache, until they are evicted by the LRU policy,
36 : /// or by a successful lookup (i.e. the entry hasn't expired yet).
37 : /// There is no background job to reap the expired records.
38 : ///
39 : /// * It's possible for an entry that has not yet expired entry to be evicted
40 : /// before expired items. That's a bit wasteful, but probably fine in practice.
41 : pub(crate) struct TimedLru<K, V> {
42 : /// Cache's name for tracing.
43 : name: &'static str,
44 :
45 : /// The underlying cache implementation.
46 : cache: parking_lot::Mutex<LruCache<K, Entry<V>>>,
47 :
48 : /// Default time-to-live of a single entry.
49 : ttl: Duration,
50 :
51 : update_ttl_on_retrieval: bool,
52 : }
53 :
54 : impl<K: Hash + Eq, V> Cache for TimedLru<K, V> {
55 : type Key = K;
56 : type Value = V;
57 : type LookupInfo<Key> = Key;
58 :
59 6 : fn invalidate(&self, info: &Self::LookupInfo<K>) {
60 6 : self.invalidate_raw(info);
61 6 : }
62 : }
63 :
64 : struct Entry<T> {
65 : created_at: Instant,
66 : expires_at: Instant,
67 : ttl: Duration,
68 : update_ttl_on_retrieval: bool,
69 : value: T,
70 : }
71 :
72 : impl<K: Hash + Eq, V> TimedLru<K, V> {
73 : /// Construct a new LRU cache with timed entries.
74 13 : pub(crate) fn new(
75 13 : name: &'static str,
76 13 : capacity: usize,
77 13 : ttl: Duration,
78 13 : update_ttl_on_retrieval: bool,
79 13 : ) -> Self {
80 13 : Self {
81 13 : name,
82 13 : cache: LruCache::new(capacity).into(),
83 13 : ttl,
84 13 : update_ttl_on_retrieval,
85 13 : }
86 13 : }
87 :
88 : /// Drop an entry from the cache if it's outdated.
89 : #[tracing::instrument(level = "debug", fields(cache = self.name), skip_all)]
90 : fn invalidate_raw(&self, key: &K) {
91 : // Do costly things before taking the lock.
92 : let mut cache = self.cache.lock();
93 : let entry = match cache.raw_entry_mut().from_key(key) {
94 : RawEntryMut::Vacant(_) => return,
95 : RawEntryMut::Occupied(x) => x.remove(),
96 : };
97 : drop(cache); // drop lock before logging
98 :
99 : let Entry {
100 : created_at,
101 : expires_at,
102 : ..
103 : } = entry;
104 :
105 : debug!(
106 : ?created_at,
107 : ?expires_at,
108 : "processed a cache entry invalidation event"
109 : );
110 : }
111 :
112 : /// Try retrieving an entry by its key, then execute `extract` if it exists.
113 : #[tracing::instrument(level = "debug", fields(cache = self.name), skip_all)]
114 : fn get_raw<Q, R>(&self, key: &Q, extract: impl FnOnce(&K, &Entry<V>) -> R) -> Option<R>
115 : where
116 : K: Borrow<Q>,
117 : Q: Hash + Eq + ?Sized,
118 : {
119 : let now = Instant::now();
120 :
121 : // Do costly things before taking the lock.
122 : let mut cache = self.cache.lock();
123 : let mut raw_entry = match cache.raw_entry_mut().from_key(key) {
124 : RawEntryMut::Vacant(_) => return None,
125 : RawEntryMut::Occupied(x) => x,
126 : };
127 :
128 : // Immeditely drop the entry if it has expired.
129 : let entry = raw_entry.get();
130 : if entry.expires_at <= now {
131 : raw_entry.remove();
132 : return None;
133 : }
134 :
135 : let value = extract(raw_entry.key(), entry);
136 : let (created_at, expires_at) = (entry.created_at, entry.expires_at);
137 :
138 : // Update the deadline and the entry's position in the LRU list.
139 : let deadline = now.checked_add(raw_entry.get().ttl).expect("time overflow");
140 : if raw_entry.get().update_ttl_on_retrieval {
141 : raw_entry.get_mut().expires_at = deadline;
142 : }
143 : raw_entry.to_back();
144 :
145 : drop(cache); // drop lock before logging
146 : debug!(
147 : created_at = format_args!("{created_at:?}"),
148 : old_expires_at = format_args!("{expires_at:?}"),
149 : new_expires_at = format_args!("{deadline:?}"),
150 : "accessed a cache entry"
151 : );
152 :
153 : Some(value)
154 : }
155 :
156 : /// Insert an entry to the cache. If an entry with the same key already
157 : /// existed, return the previous value and its creation timestamp.
158 : #[tracing::instrument(level = "debug", fields(cache = self.name), skip_all)]
159 : fn insert_raw(&self, key: K, value: V) -> (Instant, Option<V>) {
160 : self.insert_raw_ttl(key, value, self.ttl, self.update_ttl_on_retrieval)
161 : }
162 :
163 : /// Insert an entry to the cache. If an entry with the same key already
164 : /// existed, return the previous value and its creation timestamp.
165 : #[tracing::instrument(level = "debug", fields(cache = self.name), skip_all)]
166 : fn insert_raw_ttl(
167 : &self,
168 : key: K,
169 : value: V,
170 : ttl: Duration,
171 : update: bool,
172 : ) -> (Instant, Option<V>) {
173 : let created_at = Instant::now();
174 : let expires_at = created_at.checked_add(ttl).expect("time overflow");
175 :
176 : let entry = Entry {
177 : created_at,
178 : expires_at,
179 : ttl,
180 : update_ttl_on_retrieval: update,
181 : value,
182 : };
183 :
184 : // Do costly things before taking the lock.
185 : let old = self
186 : .cache
187 : .lock()
188 : .insert(key, entry)
189 : .map(|entry| entry.value);
190 :
191 : debug!(
192 : created_at = format_args!("{created_at:?}"),
193 : expires_at = format_args!("{expires_at:?}"),
194 : replaced = old.is_some(),
195 : "created a cache entry"
196 : );
197 :
198 : (created_at, old)
199 : }
200 : }
201 :
202 : impl<K: Hash + Eq + Clone, V: Clone> TimedLru<K, V> {
203 0 : pub(crate) fn insert_ttl(&self, key: K, value: V, ttl: Duration) {
204 0 : self.insert_raw_ttl(key, value, ttl, false);
205 0 : }
206 :
207 17 : pub(crate) fn insert_unit(&self, key: K, value: V) -> (Option<V>, Cached<&Self, ()>) {
208 17 : let (_, old) = self.insert_raw(key.clone(), value);
209 :
210 17 : let cached = Cached {
211 17 : token: Some((self, key)),
212 17 : value: (),
213 17 : };
214 :
215 17 : (old, cached)
216 17 : }
217 : }
218 :
219 : impl<K: Hash + Eq, V: Clone> TimedLru<K, V> {
220 : /// Retrieve a cached entry in convenient wrapper, alongside timing information.
221 0 : pub(crate) fn get_with_created_at<Q>(
222 0 : &self,
223 0 : key: &Q,
224 0 : ) -> Option<Cached<&Self, (<Self as Cache>::Value, Instant)>>
225 0 : where
226 0 : K: Borrow<Q> + Clone,
227 0 : Q: Hash + Eq + ?Sized,
228 : {
229 0 : self.get_raw(key, |key, entry| Cached {
230 0 : token: Some((self, key.clone())),
231 0 : value: (entry.value.clone(), entry.created_at),
232 0 : })
233 0 : }
234 : }
|
