The project is renamed to Caches, please see crate caches
][Github-url]
[
][CI-url]
[
][codecov-url]
[
][doc-url]
[
][crates-url]
[
][license-apache-url]
[
][license-mit-url]
This is a Rust implementation for [HashiCorp's golang-lru](https://github.com/hashicorp/golang-lru).
This crate contains three LRU based cache, `LRUCache`, `TwoQueueCache` and `AdaptiveCache`.
See [Introduction](#introduction), [Trade-Off](#trade-off) and [Usages](#usages) for more details.
English | [简体中文](README-zh_CN.md)
The MSRV for this crate is 1.55.0.
LRU based caches are O(1) for read, write and delete.
LRUCache or RawLRU is a fixed size LRU cache.
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.
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).
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.
More methods and examples, please see [documents].
Use RawLRU with default noop callback.
```rust use hashicorp_lru::{RawLRU, PutResult};
fn main() { let mut cache = RawLRU::new(2).unwrap(); // fill the cache asserteq!(cache.put(1, 1), PutResult::Put); asserteq!(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});
} ```
Use RawLRU with a custom callback.
```rust 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
impl EvictedCounter {
pub fn new(ctr: Arc
impl OnEvictCallback for EvictedCounter {
fn onevict
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), 2);
} ```
More methods and examples, please see [documents].
```rust 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)
} ```
More methods and examples, please see [documents].
```rust 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);
} ```
The implementation of RawLRU is highly inspired by Jerome Froelich's LRU implementation and [std::collections] library of Rust.
Thanks for HashiCorp's golang-lru providing the amazing Go implementation.
Licensed under either of Apache License, Version 2.0 or MIT license at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.