HashiCorp-LRU

[

][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.md) | 简体中文

## Introduction 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. ## 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](benches), I am also looking forward to anyone's help for writing more reasonable test cases for benchmark). ## Usages - [**`RawLRU`** and **`LRUCache`**](#rawlru-and-lrucache) - [Default](#default-no-op-callback) - [Custom OnEvictCallback](#custom-callback) - [**`AdaptiveCache`**](#adaptivecache-adaptive-replacement-cache) - [**`TwoQueueCache`**](#twoqueuecache) ### 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`, so it does not support custom the `on_evict` callback. More methods and examples, please see [documents]. #### Default No-op Callback Use `RawLRU` with default noop callback. ```rust 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. ```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) -> Self { Self { ctr, } } } impl OnEvictCallback for EvictedCounter { fn on_evict(&self, _: &K, _: &V) { self.ctr.fetch_add(1, Ordering::SeqCst); } } fn main() { let counter = Arc::new(AtomicU64::new(0)); let mut cache: RawLRU = 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 [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) } ``` ### TwoQueueCache 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::::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::::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](https://github.com/jeromefroe/lru-rs) and [`std::collections`] library of Rust. - Thanks for [HashiCorp's golang-lru](https://github.com/hashicorp/golang-lru) providing the amazing Go implementation. #### License ^{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.} [`Rc`]: https://doc.rust-lang.org/std/rc/struct.Rc.html [`Box`]: https://doc.rust-lang.org/std/boxed/struct.Box.html [`mem::swap`]: https://doc.rust-lang.org/stable/std/mem/fn.swap.html [`std::collections`]: https://doc.rust-lang.org/stable/std/collections/ [Github-url]: https://github.com/al8n/hashicorp-lru/ [CI-url]: https://github.com/al8n/hashicorp-lru/actions/workflows/ci.yml [codecov-url]: https://codecov.io/gh/al8n/hashicorp-lru [license-apache-url]: https://opensource.org/licenses/Apache-2.0 [license-mit-url]: https://opensource.org/licenses/Apache-2.0 [crates-url]: https://crates.io/crates/hashicorp-lru [doc-url]: https://docs.rs/hashicorp-lru [documents]: https://docs.rs/hashicorp-lru