Lib.rs

› 数据结构
#lru-cache #cache #lru #fixed-size #2q #arc-cache

已删除 hashicorp-lru

项目已移动到caches，请参阅crate caches

由 Al Liu 和 5位贡献者

0.1.6 2021年9月20日
0.1.5 2021年9月19日

#55 in #lru

MIT/Apache

240KB
3K SLoC

项目已重命名为Caches，请参阅crate caches

HashiCorp-LRU

github Build codecov

docs.rs crates.io license-apache license-mit

这是HashiCorp的golang-lru的Rust实现。

该crate包含三个基于LRU的缓存，LRUCache、TwoQueueCache 和 AdaptiveCache。

请参阅简介、权衡 和 用法 获取更多详细信息。

英文 | 简体中文

简介

该crate的MSRV是1.55.0。

基于LRU的缓存在读取、写入和删除时都是O(1)。

  • LRUCache 或 RawLRU 是一个固定大小的LRU缓存。

  • AdaptiveCache 是一个固定大小的自适应替换缓存（ARC）。ARC是对标准LRU缓存的改进，它跟踪使用频率和最近使用情况。这避免了频繁使用的老旧条目被驱逐时对新增条目访问的突发。

  • TwoQueueCache 是一个固定大小的2Q缓存。2Q是对标准LRU缓存的改进，它分别跟踪频繁和最近使用的条目。

权衡

从理论上讲，AdaptiveCache 和 TwoQueueCache 在LRUCache缓存上添加了一些额外的跟踪开销，计算上大约是成本的两倍，额外的内存开销与缓存的大小成线性关系。AdaptiveCache 和 TwoQueueCache 的计算成本相似，已被IBM专利，但TwoQueueCache（2Q）需要设置合理的参数。

然而，对于RawLRU的实现使用了Box和每个条目的原始指针，以突破Rust语言（它不使用Rc，因为Rc较慢）。因此，在实践中，TwoQueueCache的计算速度比LRUCache慢2.5倍，而AdaptiveCache的计算速度比LRUCache慢3倍，因为TwoQueueCache和AdaptiveCache需要进行更多的装箱和反装箱操作，尽管我尽力避免装箱和反装箱操作，并使用mem::swap来避免内存分配和释放。

因此，了解具体情况（您的项目需要一个具有更高命中率的缓存或更快的计算性能）后，再选择项目中合理的缓存。

（有关更多性能细节，您可以克隆项目并运行cargo bench。基准测试的源代码在benches中，我也期待任何人为基准测试编写更合理的测试用例。）

用法

RawLRU和LRUCache

RawLRU是该crate的基本数据结构，它具有泛型类型E: OnEvictCallback，支持用户编写和应用自己的回调策略。

LRUCache是RawLRU<K, V, DefaultOnEvictCallback, S>的类型别名，因此不支持自定义on_evict回调。

更多方法和示例，请参阅文档。

默认No-op回调

使用带有默认No-op回调的RawLRU。

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});
}

自定义回调

使用带有自定义回调的RawLRU。

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), 2); 
}

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

更多方法和示例，请参阅文档。

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);
}

致谢

许可

根据您选择，许可协议为Apache License, Version 2.0或MIT许可。
除非您明确声明，否则根据Apache-2.0许可定义，您有意提交的任何贡献，都应如上所述双重许可，不得附加任何额外条款或条件。

依赖项

~1MB
~16K SLoC