stretto/
lib.rs

1//! Stretto is a pure Rust implementation for <https://github.com/dgraph-io/ristretto>.
2//!
3//! A high performance thread-safe memory-bound Rust cache.
4//!
5#![deny(missing_docs)]
6#![allow(clippy::too_many_arguments, clippy::type_complexity)]
7#![cfg_attr(docsrs, feature(doc_cfg))]
8#![cfg_attr(docsrs, allow(unused_attributes))]
9mod bbloom;
10mod cache;
11mod error;
12mod histogram;
13mod metrics;
14/// This package includes multiple probabalistic data structures needed for
15/// admission/eviction metadata. Most are Counting Bloom Filter variations, but
16/// a caching-specific feature that is also required is a "freshness" mechanism,
17/// which basically serves as a "lifetime" process. This freshness mechanism
18/// was described in the original TinyLFU paper [1], but other mechanisms may
19/// be better suited for certain data distributions.
20///
21/// [1]: https://arxiv.org/abs/1512.00727
22#[allow(dead_code)]
23mod policy;
24mod ring;
25mod sketch;
26mod store;
27mod ttl;
28pub(crate) mod utils;
29
30extern crate atomic;
31
32#[cfg(feature = "log")]
33extern crate log;
34
35#[cfg(feature = "serde")]
36extern crate serde;
37
38#[cfg(feature = "async")]
39#[cfg_attr(docsrs, doc(cfg(feature = "async")))]
40pub(crate) mod axync {
41    pub(crate) use async_channel::{bounded, unbounded, Receiver, RecvError, Sender};
42    pub(crate) use futures::select;
43    pub(crate) type WaitGroup = wg::AsyncWaitGroup;
44    pub(crate) fn stop_channel() -> (Sender<()>, Receiver<()>) {
45        bounded(1)
46    }
47}
48#[cfg(feature = "async")]
49#[cfg_attr(docsrs, doc(cfg(feature = "async")))]
50pub use cache::{AsyncCache, AsyncCacheBuilder};
51
52#[cfg(feature = "sync")]
53#[cfg_attr(docsrs, doc(cfg(feature = "sync")))]
54pub(crate) mod sync {
55    pub(crate) use crossbeam_channel::{bounded, select, unbounded, Receiver, Sender};
56    pub(crate) use std::thread::{spawn, JoinHandle};
57    pub(crate) use std::time::Instant;
58
59    pub(crate) type UnboundedSender<T> = Sender<T>;
60    pub(crate) type UnboundedReceiver<T> = Receiver<T>;
61    pub(crate) type WaitGroup = wg::WaitGroup;
62
63    pub(crate) fn stop_channel() -> (Sender<()>, Receiver<()>) {
64        bounded(0)
65    }
66}
67
68#[cfg(feature = "sync")]
69#[cfg_attr(docsrs, doc(cfg(feature = "sync")))]
70pub use cache::{Cache, CacheBuilder};
71
72pub use error::CacheError;
73pub use histogram::Histogram;
74pub use metrics::{MetricType, Metrics};
75pub use utils::{ValueRef, ValueRefMut};
76
77use crate::ttl::Time;
78use seahash::SeaHasher;
79use std::fmt::{Debug, Formatter};
80use std::hash::{BuildHasher, BuildHasherDefault, Hash, Hasher};
81use std::marker::PhantomData;
82
83/// Item is the parameter when Cache reject, evict value,
84pub struct Item<V> {
85    /// the value of the entry
86    pub val: Option<V>,
87
88    /// the index of the entry(created by [`KeyBuilder`])
89    ///
90    /// [`KeyBuilder`]: struct.KeyBuilder.html
91    pub index: u64,
92
93    /// the conflict of the entry(created by [`KeyBuilder`])
94    ///
95    /// [`KeyBuilder`]: struct.KeyBuilder.html
96    pub conflict: u64,
97
98    /// the cost when store the entry in Cache.
99    pub cost: i64,
100
101    /// exp contains the ttl information.
102    pub exp: Time,
103}
104
105impl<V> Item<V> {
106    pub(crate) fn new(index: u64, conflict: u64, cost: i64, val: Option<V>, ttl: Time) -> Self {
107        Self {
108            val,
109            index,
110            conflict,
111            cost,
112            exp: ttl,
113        }
114    }
115}
116
117impl<V: Clone> Clone for Item<V> {
118    fn clone(&self) -> Self {
119        Self {
120            val: self.val.clone(),
121            index: self.index,
122            conflict: self.conflict,
123            cost: self.cost,
124            exp: self.exp,
125        }
126    }
127}
128
129impl<V: Copy> Copy for Item<V> {}
130
131impl<V: Debug> Debug for Item<V> {
132    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
133        f.debug_struct("Item")
134            .field("value", &self.val)
135            .field("cost", &self.cost)
136            .field("ttl", &self.exp)
137            .finish()
138    }
139}
140
141/// By default, the Cache will always update the value if the value already exists in the cache,
142/// this trait is for you to check if the value should be updated.
143pub trait UpdateValidator: Send + Sync + 'static {
144    /// Value
145    type Value: Send + Sync + 'static;
146
147    /// should_update is called when a value already exists in cache and is being updated.
148    fn should_update(&self, prev: &Self::Value, curr: &Self::Value) -> bool;
149}
150
151/// DefaultUpdateValidator is a noop update validator.
152#[doc(hidden)]
153pub struct DefaultUpdateValidator<V> {
154    _marker: PhantomData<fn(V)>,
155}
156
157impl<V: Send + Sync> Default for DefaultUpdateValidator<V> {
158    fn default() -> Self {
159        Self {
160            _marker: PhantomData::<fn(V)>,
161        }
162    }
163}
164
165impl<V: Send + Sync + 'static> UpdateValidator for DefaultUpdateValidator<V> {
166    type Value = V;
167
168    #[inline]
169    fn should_update(&self, _prev: &Self::Value, _curr: &Self::Value) -> bool {
170        true
171    }
172}
173
174/// CacheCallback is for customize some extra operations on values when related event happens.
175pub trait CacheCallback: Send + Sync + 'static {
176    /// Value
177    type Value: Send + Sync + 'static;
178
179    /// on_exit is called whenever a value is removed from cache. This can be
180    /// used to do manual memory deallocation. Would also be called on eviction
181    /// and rejection of the value.
182    fn on_exit(&self, val: Option<Self::Value>);
183
184    /// on_evict is called for every eviction and passes the hashed key, value,
185    /// and cost to the function.
186    fn on_evict(&self, item: Item<Self::Value>) {
187        self.on_exit(item.val)
188    }
189
190    /// on_reject is called for every rejection done via the policy.
191    fn on_reject(&self, item: Item<Self::Value>) {
192        self.on_exit(item.val)
193    }
194}
195
196/// DefaultCacheCallback is a noop CacheCallback implementation.
197#[derive(Clone, Debug)]
198#[doc(hidden)]
199pub struct DefaultCacheCallback<V> {
200    _marker: PhantomData<V>,
201}
202
203impl<V> Default for DefaultCacheCallback<V> {
204    fn default() -> Self {
205        Self {
206            _marker: Default::default(),
207        }
208    }
209}
210
211impl<V: Send + Sync + 'static> CacheCallback for DefaultCacheCallback<V> {
212    type Value = V;
213
214    fn on_exit(&self, _val: Option<Self::Value>) {}
215}
216
217/// Cost is a trait you can pass to the CacheBuilder in order to evaluate
218/// item cost at runtime, and only for the `insert` calls that aren't dropped (this is
219/// useful if calculating item cost is particularly expensive, and you don't want to
220/// waste time on items that will be dropped anyways).
221///
222/// To signal to Stretto that you'd like to use this Coster trait:
223///
224/// 1. Set the Coster field to your own Coster implementation.
225/// 2. When calling `insert` for new items or item updates, use a `cost` of 0.
226pub trait Coster: Send + Sync + 'static {
227    /// Value
228    type Value: Send + Sync + 'static;
229
230    /// cost evaluates a value and outputs a corresponding cost. This function
231    /// is ran after insert is called for a new item or an item update with a cost
232    /// param of 0.
233    fn cost(&self, val: &Self::Value) -> i64;
234}
235
236/// DefaultCoster is a noop Coster implementation.
237#[doc(hidden)]
238pub struct DefaultCoster<V> {
239    _marker: PhantomData<fn(V)>,
240}
241
242impl<V> Default for DefaultCoster<V> {
243    fn default() -> Self {
244        Self {
245            _marker: Default::default(),
246        }
247    }
248}
249
250impl<V: Send + Sync + 'static> Coster for DefaultCoster<V> {
251    type Value = V;
252
253    #[inline]
254    fn cost(&self, _val: &V) -> i64 {
255        0
256    }
257}
258
259/// [`KeyBuilder`] is the hashing algorithm used for every key. In Stretto, the Cache will never store the real key.
260/// The key will be processed by [`KeyBuilder`]. Stretto has two default built-in key builder,
261/// one is [`TransparentKeyBuilder`], the other is [`DefaultKeyBuilder`]. If your key implements [`TransparentKey`] trait,
262/// you can use [`TransparentKeyBuilder`] which is faster than [`DefaultKeyBuilder`]. Otherwise, you should use [`DefaultKeyBuilder`]
263/// You can also write your own key builder for the Cache, by implementing [`KeyBuilder`] trait.
264///
265/// Note that if you want 128bit hashes you should use the full `(u64, u64)`,
266/// otherwise just fill the `u64` at the `0` position, and it will behave like
267/// any 64bit hash.
268///
269/// [`KeyBuilder`]: trait.KeyBuilder.html
270/// [`TransparentKey`]: trait.TransparentKey.html
271/// [`TransparentKeyBuilder`]: struct.TransparentKeyBuilder.html
272/// [`DefaultKeyBuilder`]: struct.DefaultKeyBuilder.html
273pub trait KeyBuilder {
274    /// Key
275    type Key: Hash + Eq + ?Sized;
276
277    /// `hash_index` is used to hash the key to u64
278    fn hash_index<Q>(&self, key: &Q) -> u64
279    where
280        Self::Key: core::borrow::Borrow<Q>,
281        Q: core::hash::Hash + Eq + ?Sized;
282
283    /// if you want a 128bit hashes, you should implement this method,
284    /// or leave this method return 0
285    fn hash_conflict<Q>(&self, key: &Q) -> u64
286    where
287        Self::Key: core::borrow::Borrow<Q>,
288        Q: core::hash::Hash + Eq + ?Sized,
289    {
290        let _ = key;
291        0
292    }
293
294    /// build the key to 128bit hashes.
295    fn build_key<Q>(&self, k: &Q) -> (u64, u64)
296    where
297        Self::Key: core::borrow::Borrow<Q>,
298        Q: core::hash::Hash + Eq + ?Sized,
299    {
300        (self.hash_index(k), self.hash_conflict(k))
301    }
302}
303
304/// DefaultKeyBuilder is a built-in `KeyBuilder` for the Cache.
305///
306/// If the key implements [`TransparentKey`] trait, use [`TransparentKeyBuilder`].
307/// u8, u16, u32, u64, i8, i16, i32, i64, bool implement [`TransparentKey`] by default.
308///
309/// See [`KeyBuilder`] if you want to write a customized [`KeyBuilder`].
310///
311/// [`KeyBuilder`]: trait.KeyBuilder.html
312/// [`TransparentKey`]: trait.TransparentKey.html
313/// [`TransparentKeyBuilder`]: struct.TransparentKeyBuilder.html
314pub struct DefaultKeyBuilder<K> {
315    xx: xxhash_rust::xxh64::Xxh64Builder,
316    sea: BuildHasherDefault<SeaHasher>,
317    _marker: PhantomData<K>,
318}
319
320impl<K> Debug for DefaultKeyBuilder<K> {
321    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
322        f.debug_struct("DefaultKeyBuilder").finish()
323    }
324}
325
326impl<K> Default for DefaultKeyBuilder<K> {
327    fn default() -> Self {
328        use rand::{thread_rng, Rng};
329        let mut rng = thread_rng();
330        let seed = rng.gen::<u64>();
331        Self {
332            xx: xxhash_rust::xxh64::Xxh64Builder::new(seed),
333            sea: Default::default(),
334            _marker: Default::default(),
335        }
336    }
337}
338
339impl<K: Hash + Eq> KeyBuilder for DefaultKeyBuilder<K> {
340    type Key = K;
341
342    #[inline]
343    fn hash_index<Q>(&self, key: &Q) -> u64
344    where
345        Self::Key: core::borrow::Borrow<Q>,
346        Q: core::hash::Hash + Eq + ?Sized,
347    {
348        self.sea.hash_one(key)
349    }
350
351    #[inline]
352    fn hash_conflict<Q>(&self, key: &Q) -> u64
353    where
354        Self::Key: core::borrow::Borrow<Q>,
355        Q: core::hash::Hash + Eq + ?Sized,
356    {
357        self.xx.hash_one(key)
358    }
359}
360
361/// Dummy hasher will do nothing. Used by [`TransparentKeyBuilder`].
362#[derive(Default, Copy, Clone, Eq, PartialEq, Debug)]
363#[repr(transparent)]
364pub struct TransparentHasher {
365    data: u64,
366}
367
368impl Hasher for TransparentHasher {
369    #[inline]
370    fn finish(&self) -> u64 {
371        self.data
372    }
373
374    #[inline]
375    fn write(&mut self, bytes: &[u8]) {
376        let mut data = [0u8; core::mem::size_of::<u64>()];
377        if bytes.len() > core::mem::size_of::<u64>() {
378            data.copy_from_slice(&bytes[..core::mem::size_of::<u64>()]);
379        } else {
380            data[..bytes.len()].copy_from_slice(bytes);
381        }
382        self.data = u64::from_ne_bytes(data);
383    }
384
385    fn write_u8(&mut self, i: u8) {
386        self.data = i as u64;
387    }
388
389    fn write_u16(&mut self, i: u16) {
390        self.data = i as u64;
391    }
392
393    fn write_u32(&mut self, i: u32) {
394        self.data = i as u64;
395    }
396
397    fn write_u64(&mut self, i: u64) {
398        self.data = i;
399    }
400
401    fn write_u128(&mut self, i: u128) {
402        self.data = i as u64;
403    }
404
405    fn write_usize(&mut self, i: usize) {
406        self.data = i as u64;
407    }
408
409    fn write_i8(&mut self, i: i8) {
410        self.data = i as u64;
411    }
412
413    fn write_i16(&mut self, i: i16) {
414        self.data = i as u64;
415    }
416
417    fn write_i32(&mut self, i: i32) {
418        self.data = i as u64;
419    }
420
421    fn write_i64(&mut self, i: i64) {
422        self.data = i as u64;
423    }
424
425    fn write_i128(&mut self, i: i128) {
426        self.data = i as u64;
427    }
428
429    fn write_isize(&mut self, i: isize) {
430        self.data = i as u64;
431    }
432}
433
434/// Implement this trait for the key, if you want to use [`TransparentKeyBuilder`] as the [`KeyBuilder`]
435/// for the [`Cache`].
436///
437/// u8, u16, u32, u64, i8, i16, i32, i64, bool implement TransparentKey by default.
438///
439/// [`TransparentKeyBuilder`]: struct.TransparentKeyBuilder.html
440/// [`KeyBuilder`]: trait.KeyBuilder.html
441/// [`Cache`]: struct.Cache.html
442pub trait TransparentKey: Hash + Eq {
443    /// convert self to `u64`
444    fn to_u64(&self) -> u64;
445}
446
447/// TransparentKeyBuilder converts key to `u64`.
448/// If the key does not implement the trait [`TransparentKey`], please use [`DefaultKeyBuilder`]
449/// or write a custom key builder.
450///
451/// [`DefaultKeyBuilder`]: struct.DefaultKeyBuilder.html
452/// [`TransparentKey`]: trait.TransparentKey.html
453#[derive(Default, Clone, Eq, PartialEq, Debug)]
454pub struct TransparentKeyBuilder<K: TransparentKey> {
455    // hasher: TransparentHasher<K>,
456    _marker: PhantomData<K>,
457}
458
459impl<K: TransparentKey> KeyBuilder for TransparentKeyBuilder<K> {
460    type Key = K;
461
462    #[inline]
463    fn hash_index<Q>(&self, key: &Q) -> u64
464    where
465        Self::Key: core::borrow::Borrow<Q>,
466        Q: core::hash::Hash + Eq + ?Sized,
467    {
468        let mut hasher = TransparentHasher { data: 0 };
469        key.hash(&mut hasher);
470        hasher.finish()
471    }
472
473    #[inline]
474    fn hash_conflict<Q>(&self, _key: &Q) -> u64
475    where
476        Self::Key: core::borrow::Borrow<Q>,
477        Q: core::hash::Hash + Eq + ?Sized,
478    {
479        0
480    }
481}
482
483macro_rules! impl_transparent_key {
484    ($($t:ty),*) => {
485        $(
486            impl TransparentKey for $t {
487                fn to_u64(&self) -> u64 {
488                    *self as u64
489                }
490            }
491        )*
492    }
493}
494
495impl_transparent_key! {
496    bool,
497    u8,
498    u16,
499    u32,
500    u64,
501    usize,
502    i8,
503    i16,
504    i32,
505    i64,
506    isize
507}
stretto/lib.rs

stretto/
lib.rs
