pub struct Cache<K, V, S = RandomState> { /* private fields */ }
sync
only.Expand description
A thread-safe concurrent in-memory cache built upon dashmap::DashMap
.
The Cache
uses DashMap
as the central key-value storage. It performs a
best-effort bounding of the map using an entry replacement algorithm to determine
which entries to evict when the capacity is exceeded.
To use this cache, enable a crate feature called “dash” in your Cargo.toml.
Please note that the API of dash
cache will be changed very often in next few
releases as this is yet an experimental component.
Examples
Cache entries are manually added using insert
method, and are
stored in the cache until either evicted or manually invalidated.
Here’s an example of reading and updating a cache by using multiple threads:
use mini_moka::sync::Cache;
use std::thread;
fn value(n: usize) -> String {
format!("value {}", n)
}
const NUM_THREADS: usize = 16;
const NUM_KEYS_PER_THREAD: usize = 64;
// Create a cache that can store up to 10,000 entries.
let cache = Cache::new(10_000);
// Spawn threads and read and update the cache simultaneously.
let threads: Vec<_> = (0..NUM_THREADS)
.map(|i| {
// To share the same cache across the threads, clone it.
// This is a cheap operation.
let my_cache = cache.clone();
let start = i * NUM_KEYS_PER_THREAD;
let end = (i + 1) * NUM_KEYS_PER_THREAD;
thread::spawn(move || {
// Insert 64 entries. (NUM_KEYS_PER_THREAD = 64)
for key in start..end {
my_cache.insert(key, value(key));
// get() returns Option<String>, a clone of the stored value.
assert_eq!(my_cache.get(&key), Some(value(key)));
}
// Invalidate every 4 element of the inserted entries.
for key in (start..end).step_by(4) {
my_cache.invalidate(&key);
}
})
})
.collect();
// Wait for all threads to complete.
threads.into_iter().for_each(|t| t.join().expect("Failed"));
// Verify the result.
for key in 0..(NUM_THREADS * NUM_KEYS_PER_THREAD) {
if key % 4 == 0 {
assert_eq!(cache.get(&key), None);
} else {
assert_eq!(cache.get(&key), Some(value(key)));
}
}
Avoiding to clone the value at get
The return type of get
method is Option<V>
instead of Option<&V>
. Every
time get
is called for an existing key, it creates a clone of the stored value
V
and returns it. This is because the Cache
allows concurrent updates from
threads so a value stored in the cache can be dropped or replaced at any time by
any other thread. get
cannot return a reference &V
as it is impossible to
guarantee the value outlives the reference.
If you want to store values that will be expensive to clone, wrap them by
std::sync::Arc
before storing in a cache. Arc
is a
thread-safe reference-counted pointer and its clone()
method is cheap.
Size-based Eviction
use std::convert::TryInto;
use mini_moka::sync::Cache;
// Evict based on the number of entries in the cache.
let cache = Cache::builder()
// Up to 10,000 entries.
.max_capacity(10_000)
// Create the cache.
.build();
cache.insert(1, "one".to_string());
// Evict based on the byte length of strings in the cache.
let cache = Cache::builder()
// A weigher closure takes &K and &V and returns a u32
// representing the relative size of the entry.
.weigher(|_key, value: &String| -> u32 {
value.len().try_into().unwrap_or(u32::MAX)
})
// This cache will hold up to 32MiB of values.
.max_capacity(32 * 1024 * 1024)
.build();
cache.insert(2, "two".to_string());
If your cache should not grow beyond a certain size, use the max_capacity
method of the CacheBuilder
to set the upper bound. The cache
will try to evict entries that have not been used recently or very often.
At the cache creation time, a weigher closure can be set by the weigher
method
of the CacheBuilder
. A weigher closure takes &K
and &V
as the arguments and
returns a u32
representing the relative size of the entry:
- If the
weigher
is not set, the cache will treat each entry has the same size of1
. This means the cache will be bounded by the number of entries. - If the
weigher
is set, the cache will call the weigher to calculate the weighted size (relative size) on an entry. This means the cache will be bounded by the total weighted size of entries.
Note that weighted sizes are not used when making eviction selections.
Time-based Expirations
Cache
supports the following expiration policies:
- Time to live: A cached entry will be expired after the specified duration
past from
insert
. - Time to idle: A cached entry will be expired after the specified duration
past from
get
orinsert
.
use mini_moka::sync::Cache;
use std::time::Duration;
let cache = Cache::builder()
// Time to live (TTL): 30 minutes
.time_to_live(Duration::from_secs(30 * 60))
// Time to idle (TTI): 5 minutes
.time_to_idle(Duration::from_secs( 5 * 60))
// Create the cache.
.build();
// This entry will expire after 5 minutes (TTI) if there is no get().
cache.insert(0, "zero");
// This get() will extend the entry life for another 5 minutes.
cache.get(&0);
// Even though we keep calling get(), the entry will expire
// after 30 minutes (TTL) from the insert().
Thread Safety
All methods provided by the Cache
are considered thread-safe, and can be safely
accessed by multiple concurrent threads.
Cache<K, V, S>
requires trait boundsSend
,Sync
and'static
forK
(key),V
(value) andS
(hasher state).Cache<K, V, S>
will implementSend
andSync
.
Sharing a cache across threads
To share a cache across threads, do one of the followings:
- Create a clone of the cache by calling its
clone
method and pass it to other thread. - Wrap the cache by a
sync::OnceCell
orsync::Lazy
from once_cell create, and set it to astatic
variable.
Cloning is a cheap operation for Cache
as it only creates thread-safe
reference-counted pointers to the internal data structures.
Hashing Algorithm
By default, Cache
uses a hashing algorithm selected to provide resistance
against HashDoS attacks. It will be the same one used by
std::collections::HashMap
, which is currently SipHash 1-3.
While SipHash’s performance is very competitive for medium sized keys, other hashing algorithms will outperform it for small keys such as integers as well as large keys such as long strings. However those algorithms will typically not protect against attacks such as HashDoS.
The hashing algorithm can be replaced on a per-Cache
basis using the
build_with_hasher
method of the
CacheBuilder
. Many alternative algorithms are available on crates.io, such
as the aHash crate.
Implementations§
source§impl<K, V> Cache<K, V, RandomState>
impl<K, V> Cache<K, V, RandomState>
sourcepub fn new(max_capacity: u64) -> Self
pub fn new(max_capacity: u64) -> Self
Constructs a new Cache<K, V>
that will store up to the max_capacity
.
To adjust various configuration knobs such as initial_capacity
or
time_to_live
, use the CacheBuilder
.
sourcepub fn builder() -> CacheBuilder<K, V, Cache<K, V, RandomState>>
pub fn builder() -> CacheBuilder<K, V, Cache<K, V, RandomState>>
Returns a CacheBuilder
, which can builds a Cache
with
various configuration knobs.
source§impl<K, V, S> Cache<K, V, S>
impl<K, V, S> Cache<K, V, S>
sourcepub fn policy(&self) -> Policy
pub fn policy(&self) -> Policy
Returns a read-only cache policy of this cache.
At this time, cache policy cannot be modified after cache creation. A future version may support to modify it.
sourcepub fn entry_count(&self) -> u64
pub fn entry_count(&self) -> u64
Returns an approximate number of entries in this cache.
The value returned is an estimate; the actual count may differ if there are
concurrent insertions or removals, or if some entries are pending removal due
to expiration. This inaccuracy can be mitigated by performing a sync()
first.
Example
use mini_moka::sync::Cache;
let cache = Cache::new(10);
cache.insert('n', "Netherland Dwarf");
cache.insert('l', "Lop Eared");
cache.insert('d', "Dutch");
// Ensure an entry exists.
assert!(cache.contains_key(&'n'));
// However, followings may print stale number zeros instead of threes.
println!("{}", cache.entry_count()); // -> 0
println!("{}", cache.weighted_size()); // -> 0
// To mitigate the inaccuracy, bring `ConcurrentCacheExt` trait to
// the scope so we can use `sync` method.
use mini_moka::sync::ConcurrentCacheExt;
// Call `sync` to run pending internal tasks.
cache.sync();
// Followings will print the actual numbers.
println!("{}", cache.entry_count()); // -> 3
println!("{}", cache.weighted_size()); // -> 3
sourcepub fn weighted_size(&self) -> u64
pub fn weighted_size(&self) -> u64
Returns an approximate total weighted size of entries in this cache.
The value returned is an estimate; the actual size may differ if there are
concurrent insertions or removals, or if some entries are pending removal due
to expiration. This inaccuracy can be mitigated by performing a sync()
first. See entry_count
for a sample code.
source§impl<K, V, S> Cache<K, V, S>
impl<K, V, S> Cache<K, V, S>
sourcepub fn contains_key<Q>(&self, key: &Q) -> bool
pub fn contains_key<Q>(&self, key: &Q) -> bool
Returns true
if the cache contains a value for the key.
Unlike the get
method, this method is not considered a cache read operation,
so it does not update the historic popularity estimator or reset the idle
timer for the key.
The key may be any borrowed form of the cache’s key type, but Hash
and Eq
on the borrowed form must match those for the key type.
sourcepub fn get<Q>(&self, key: &Q) -> Option<V>
pub fn get<Q>(&self, key: &Q) -> Option<V>
Returns a clone of the value corresponding to the key.
If you want to store values that will be expensive to clone, wrap them by
std::sync::Arc
before storing in a cache. Arc
is a
thread-safe reference-counted pointer and its clone()
method is cheap.
The key may be any borrowed form of the cache’s key type, but Hash
and Eq
on the borrowed form must match those for the key type.
sourcepub fn insert(&self, key: K, value: V)
pub fn insert(&self, key: K, value: V)
Inserts a key-value pair into the cache.
If the cache has this key present, the value is updated.
sourcepub fn invalidate<Q>(&self, key: &Q)
pub fn invalidate<Q>(&self, key: &Q)
Discards any cached value for the key.
The key may be any borrowed form of the cache’s key type, but Hash
and Eq
on the borrowed form must match those for the key type.
sourcepub fn invalidate_all(&self)
pub fn invalidate_all(&self)
Discards all cached values.
This method returns immediately and a background thread will evict all the
cached values inserted before the time when this method was called. It is
guaranteed that the get
method must not return these invalidated values
even if they have not been evicted.
Like the invalidate
method, this method does not clear the historic
popularity estimator of keys so that it retains the client activities of
trying to retrieve an item.
source§impl<'a, K, V, S> Cache<K, V, S>
impl<'a, K, V, S> Cache<K, V, S>
sourcepub fn iter(&self) -> Iter<'_, K, V, S> ⓘ
pub fn iter(&self) -> Iter<'_, K, V, S> ⓘ
Creates an iterator visiting all key-value pairs in arbitrary order. The
iterator element type is EntryRef<'a, K, V, S>
.
Unlike the get
method, visiting entries via an iterator do not update the
historic popularity estimator or reset idle timers for keys.
Locking behavior
This iterator relies on the iterator of dashmap::DashMap
,
which employs read-write locks. May deadlock if the thread holding an
iterator attempts to update the cache.
Examples
use mini_moka::sync::Cache;
let cache = Cache::new(100);
cache.insert("Julia", 14);
let mut iter = cache.iter();
let entry_ref = iter.next().unwrap();
assert_eq!(entry_ref.pair(), (&"Julia", &14));
assert_eq!(entry_ref.key(), &"Julia");
assert_eq!(entry_ref.value(), &14);
assert_eq!(*entry_ref, 14);
assert!(iter.next().is_none());