Crate hashicorp_lru[−][src]
Expand description
HashiCorp-LRU
This is a Rust implementation for HashiCorp’s golang-lru.
This crate contains three LRU based cache, LRUCache
, TwoQueueCache
and AdaptiveCache
.
See Introduction, Trade-Off and Usages for more details.
Introduction
The MSRV for this crate is 1.55.0.
LRU based caches are O(1)
for read, write and delete.
-
AdaptiveCache
is a fixed size Adaptive Replacement Cache (ARC). ARC is an enhancement over the standard LRU cache in that tracks both frequency and recency of use. This avoids a burst in access to new entries from evicting the frequently used older entries. -
TwoQueueCache
is a fixed size 2Q cache. 2Q is an enhancement over the standard LRU cache in that it tracks both frequently and recently used entries separately.
Trade-Off
In theory, AdaptiveCache
and TwoQueueCache
add some additional
tracking overhead to a LRUCache
cache, computationally it is roughly 2x the cost,
and the extra memory overhead is linear with the size of the cache.
AdaptiveCache
and TwoQueueCache
have similar computationally cost,
which has been patented by IBM, but the TwoQueueCache
(2Q) need to set reasonable parameters.
However, the implementation for the RawLRU
uses Box
and a
raw pointer for each entry to break the limitation of the
Rust language (It does not use Rc
, because Rc
is slower).
Thus, in practice, TwoQueueCache
is 2.5x computationally
slower than LRUCache
and AdaptiveCache
is 3x computationally slower than LRUCache
,
because TwoQueueCache
and AdaptiveCache
has to do more box and re-box
than LRUCache
, even though I try my best to avoid boxing and re-boxing and
use mem::swap
to avoid memory allocating and deallocating.
Hence, it is better to understand what is the situation is (your project wants a cache with a higher hit ratio or faster computationally performance), and then choose the reasonable Cache in your project.
(For more performance details, you can clone the project and
run cargo bench
. The source code for benchmark is in the
benches,
I am also looking forward to anyone’s help for writing more
reasonable test cases for benchmark).
Usages
RawLRU and LRUCache
RawLRU
is the basic data structure over the crate, it has a generic type E: OnEvictCallback
, which support users to write and apply their own callback policy.
LRUCache
is a type alias for RawLRU<K, V, DefaultOnEvictCallback, S>
, so it does not support custom the on_evict
callback.
Default No-op Callback
Use RawLRU
with default noop callback.
use hashicorp_lru::{RawLRU, PutResult};
fn main() {
let mut cache = RawLRU::new(2).unwrap();
// fill the cache
assert_eq!(cache.put(1, 1), PutResult::Put);
assert_eq!(cache.put(2, 2), PutResult::Put);
// put 3, should evict the entry (1, 1)
assert_eq!(cache.put(3, 3), PutResult::Evicted {key: 1,value: 1});
// put 4, should evict the entry (2, 2)
assert_eq!(cache.put(4, 4), PutResult::Evicted {key: 2,value: 2});
// get 3, should update the recent-ness
assert_eq!(cache.get(&3), Some(&3));
// put 5, should evict the entry (4, 4)
assert_eq!(cache.put(5, 5), PutResult::Evicted {key: 4,value: 4});
}
Custom Callback
Use RawLRU
with a custom callback.
use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
use hashicorp_lru::{OnEvictCallback, RawLRU, PutResult};
// EvictedCounter is a callback which is used to record the number of evicted entries.
struct EvictedCounter {
ctr: Arc<AtomicU64>,
}
impl EvictedCounter {
pub fn new(ctr: Arc<AtomicU64>) -> Self {
Self {
ctr,
}
}
}
impl OnEvictCallback for EvictedCounter {
fn on_evict<K, V>(&self, _: &K, _: &V) {
self.ctr.fetch_add(1, Ordering::SeqCst);
}
}
fn main() {
let counter = Arc::new(AtomicU64::new(0));
let mut cache: RawLRU<u64, u64, EvictedCounter> = RawLRU::with_on_evict_cb(2, EvictedCounter::new(counter.clone())).unwrap();
// fill the cache
assert_eq!(cache.put(1, 1), PutResult::Put);
assert_eq!(cache.put(2, 2), PutResult::Put);
// put 3, should evict the entry (1, 1)
assert_eq!(cache.put(3, 3), PutResult::Evicted {key: 1,value: 1});
// put 4, should evict the entry (2, 2)
assert_eq!(cache.put(4, 4), PutResult::Evicted {key: 2,value: 2});
// get 3, should update the recent-ness
assert_eq!(cache.get(&3), Some(&3));
// put 5, should evict the entry (4, 4)
assert_eq!(cache.put(5, 5), PutResult::Evicted {key: 4,value: 4});
assert_eq!(counter.load(Ordering::SeqCst), 3);
}
AdaptiveCache
(Adaptive Replacement Cache)
More methods and examples, please see AdaptiveCache
.
use hashicorp_lru::AdaptiveCache;
fn main() {
let mut cache = AdaptiveCache::new(4).unwrap();
// fill recent
(0..4).for_each(|i| cache.put(i, i));
// move to frequent
cache.get(&0);
cache.get(&1);
assert_eq!(cache.frequent_len(), 2);
// evict from recent
cache.put(4, 4);
assert_eq!(cache.recent_evict_len(), 1);
// current state
// recent: (MRU) [4, 3] (LRU)
// frequent: (MRU) [1, 0] (LRU)
// recent evict: (MRU) [2] (LRU)
// frequent evict: (MRU) [] (LRU)
// Add 2, should cause hit on recent_evict
cache.put(2, 2);
assert_eq!(cache.recent_evict_len(), 1);
assert_eq!(cache.partition(), 1);
assert_eq!(cache.frequent_len(), 3);
// Current state
// recent LRU: (MRU) [4] (LRU)
// frequent LRU: (MRU) [2, 1, 0] (LRU)
// recent evict: (MRU) [3] (LRU)
// frequent evict: (MRU) [] (LRU)
// Add 4, should migrate to frequent
cache.put(4, 4);
assert_eq!(cache.recent_len(), 0);
assert_eq!(cache.frequent_len(), 4);
// Current state
// recent LRU: (MRU) [] (LRU)
// frequent LRU: (MRU) [4, 2, 1, 0] (LRU)
// recent evict: (MRU) [3] (LRU)
// frequent evict: (MRU) [] (LRU)
// Add 5, should evict to b2
cache.put(5, 5);
assert_eq!(cache.recent_len(), 1);
assert_eq!(cache.frequent_len(), 3);
assert_eq!(cache.frequent_evict_len(), 1);
// Current state
// recent: (MRU) [5] (LRU)
// frequent: (MRU) [4, 2, 1] (LRU)
// recent evict: (MRU) [3] (LRU)
// frequent evict: (MRU) [0] (LRU)
// Add 0, should decrease p
cache.put(0, 0);
assert_eq!(cache.recent_len(), 0);
assert_eq!(cache.frequent_len(), 4);
assert_eq!(cache.recent_evict_len(), 2);
assert_eq!(cache.frequent_evict_len(), 0);
assert_eq!(cache.partition(), 0);
// Current state
// recent: (MRU) [] (LRU)
// frequent: (MRU) [0, 4, 2, 1] (LRU)
// recent evict: (MRU) [5, 3] (LRU)
// frequent evict: (MRU) [0] (LRU)
}
TwoQueueCache
More methods and examples, please see TwoQueueCache
.
use hashicorp_lru::{TwoQueueCache, PutResult};
fn main() {
let mut cache = TwoQueueCache::new(4).unwrap();
// Add 1,2,3,4,
(1..=4).for_each(|i| { assert_eq!(cache.put(i, i), PutResult::Put);});
// Add 5 -> Evict 1 to ghost LRU
assert_eq!(cache.put(5, 5), PutResult::Put);
// Pull in the recently evicted
assert_eq!(cache.put(1, 1), PutResult::Update(1));
// Add 6, should cause another recent evict
assert_eq!(cache.put(6, 6), PutResult::<i32, i32>::Put);
// Add 7, should evict an entry from ghost LRU.
assert_eq!(cache.put(7, 7), PutResult::Evicted { key: 2, value: 2 });
// Add 2, should evict an entry from ghost LRU
assert_eq!(cache.put(2, 11), PutResult::Evicted { key: 3, value: 3 });
// Add 4, should put the entry from ghost LRU to freq LRU
assert_eq!(cache.put(4, 11), PutResult::Update(4));
// move all entry in recent to freq.
assert_eq!(cache.put(2, 22), PutResult::Update(11));
assert_eq!(cache.put(7, 77), PutResult::<i32, i32>::Update(7));
// Add 6, should put the entry from ghost LRU to freq LRU, and evicted one
// entry
assert_eq!(cache.put(6, 66), PutResult::EvictedAndUpdate { evicted: (5, 5), update: 6});
assert_eq!(cache.recent_len(), 0);
assert_eq!(cache.ghost_len(), 1);
assert_eq!(cache.frequent_len(), 4);
}
Acknowledgments
-
The implementation of
RawLRU
is highly inspired by Jerome Froelich’s LRU implementation andstd::collections
library of Rust. -
Thanks for HashiCorp’s golang-lru providing the amazing Go implementation.
Structs
AdaptiveCache
is a fixed size Adaptive Replacement Cache (ARC).
ARC is an enhancement over the standard LRU cache in that tracks both
frequency and recency of use. This avoids a burst in access to new
entries from evicting the frequently used older entries. It adds some
additional tracking overhead to a RawLRU
cache with default evict callback policy, computationally
it is roughly 2x the cost, and the extra memory overhead is linear
with the size of the cache. ARC has been patented by IBM, but is
similar to the TwoQueueCache
(2Q) which requires setting parameters.
AdaptiveCacheBuilder
is used to help build a AdaptiveCache
with custom configuration.
DefaultEvictCallback
is a noop evict callback.
An iterator over entries, from less recent used to most recent used.
An iterator over entries, from most recent used to less recent used.
An iterator over the entries from less recent used to most recent used.
An iterator over mutable entries, from less recent used to most recent used.
An iterator over the entries, from most recent used to less recent used.
An iterator over mutable entries, from most recent used to less recent used.
A fixed size RawLRU Cache
TwoQueueCache
is a fixed size 2Q cache.
2Q is an enhancement over the standard LRU cache
in that it tracks both frequently and recently used
entries separately. This avoids a burst in access to new
entries from evicting frequently used entries. It adds some
additional tracking overhead to the RawLRU
cache, and is
computationally about 2x the cost, and adds some metadata over
head. The AdaptiveCache
is similar to the TwoQueueCache, but does not require setting any
parameters.
TwoQueueCacheBuilder
is used to help build a TwoQueueCache
with custom configuration.
An iterator over entries, from less recent used to most recent used.
An iterator over mutable entries, from less recent used to most recent used.
An iterator over entries, from most recent used to less recent used.
An iterator over mutable entries, from most recent used to less recent used.
Enums
CacheError
is the errors of this crate.
PutResult
is returned when try to put a entry in cache.
Constants
DEFAULT_2Q_GHOST_ENTRIES
is the default ratio of ghost
entries kept to track entries recently evicted for TwoQueueCache
.
DEFAULT_2Q_RECENT_RATIO
is the ratio of the TwoQueueCache
dedicated
to recently added entries that have only been accessed once.
Traits
OnEvictCallback
is used to apply a callback for evicted entry.