TinyLFU 缓存的实现

TinyLFU 建议使用基于频率的缓存准入策略来提高受倾斜访问分布影响的缓存的效率。给定一个新访问的项目和缓存中的驱逐候选者，TinyLFU 方案根据最近的访问历史决定是否值得以驱逐候选者的代价将新项目纳入缓存。TinyLFU 维护了一个大样本最近访问项目访问频率的近似表示。TinyLFU 非常紧凑和轻量，因为它建立在布隆过滤器理论之上。

此存储库通过 probabilistic_collections 库实现了 TinyLFU。

缓存提供： insert、insert_with_ttl、get、get_mut、remove、contains、is_empty 操作。

示例

extern crate cascara;

use cascara::{Cache, OnEvict};
use std::time::Duration;

#[derive(Default, Debug)]
struct Evict {}

impl OnEvict<usize, usize> for Evict {
    fn evict(&self, k: &usize, v: &usize) {
        println!("Evict item.  k={}, v={}", k, v);
    }
}

fn main() {
    //create cache with activated metrics collecting(mis, hit, insert, update, evict)
    let mut cache = Cache::with_on_evict(10, 20, Evict::default())
        .with_metrics();
    assert!(cache.is_empty());
    assert_eq!(cache.get(&1), None);
    cache.insert(1, 1).expect("Item is not inserted");
    assert_eq!(cache.get(&1), Some(&1));
    let previous = cache.insert(1, 2).expect("Item is not updated");
    assert_eq!(previous, Some(1));
    assert_eq!(cache.get(&1), Some(&2));
    cache
        .insert_with_ttl(2, 2, Duration::from_secs(1))
        .expect("Item is not inserted");
    assert!(cache.contains(&2));
    std::thread::sleep(Duration::from_secs(2));
    assert!(!cache.contains(&2));
    {
        let v = cache.get_mut(&1).unwrap();
        *v = 3;
    }
    assert_eq!(cache.get(&1), Some(&3));
    for i in 0..25 {
        match cache.insert(i, i) {
            Ok(_) => println!("Item is inserted. i: {}", i),
            Err(_) => println!("Item is rejected. i: {}", i),
        }
    }
    for (k, v) in cache.iter() {
        println!("Item: k: {}, v: {}", k, v);
    }
    println!(
        "\nCache metrics. {:?}",
        cache.metrics().expect("Cache should have metrics")
    )
}