Lfu 缓存在 Rust 中的实现及源码解析

2024-06-28
福建
本文字数：6298 字
阅读完需：约 21 分钟

一个 lfu(least frequently used/最不经常使用页置换算法 ) 缓存的实现，其核心思想是淘汰一段时间内被访问次数最少的数据项。与 LRU（最近最少使用）算法不同，LFU 更侧重于数据的访问频率而非访问的新鲜度。

LFU 的原理与实现机制

普通队列：LFU 算法通过记录数据项的访问频次来工作。当缓存容量达到上限时，系统将会淘汰访问频次最低的数据项。这种方法基于一个假设，即在一段时间内被访问频次较少的数据，未来被访问的几率同样较小。

数据结构选择：为实现 O(1)的时间复杂度，这里 LFU 通常使用哈希表（存储 key 与节点数据）和双向链表（存储次数与 key 结构关系）结合的方式来实现。哈希表用于快速查找节点是否存在，而双向链表则用于根据访问频次组织数据项。此处双向链表用一个无限长度的LruCache代替。在remove或者改变频次的时候可以用 O(1)的复杂度进行操作。一开始用HashSet<Key>来设计，因为在 Rust 中 HashSet 并不存在pop函数，在数据大量触发替代的时候随机选择一个元素效率太低。

节点管理：每个节点除了存储键值之外，还需附带访问频次信息。每次数据项被访问时，其对应的节点频次会增加；当需要淘汰时，寻找频次最低的节点进行移除或替换。

LFU 与 LRU 的对比及使用场景

算法侧重点差异：LRU 侧重于数据的访问新鲜度，即最近未被访问的数据更容易被淘汰；而 LFU 更关注数据项的总访问频次，不频繁访问的数据被认为是低优先级的。
适用场景的不同：LRU 适合应对具有时间局部性的数据访问模式，例如某些顺序读取的场景；LFU 则更适合数据访问模式较为平稳，且各个数据项访问频率差异明显的环境。
实现复杂性对比：LRU 的实现相对简单，通常只需要维护一个按照时间顺序排列的链表即可；而 LFU 需要同时考虑访问频次和时间两个维度，因此实现上更为复杂。

LFU 算法的实际案例

缓存系统中的应用：许多现代缓存系统中，如 Redis，都实现了 LFU 作为缓存逐出策略之一，允许用户根据具体需求选择合适的淘汰算法。在数据负载高的时候可以允许配置maxmemory-policy为volatile-lru|allkeys-lru|volatile-random|allkeys-random|volatile-ttl|volatile-lfu|allkeys-lfu|noeviction
负载均衡算法：在分布式系统中，LFU 也可以作为一种简单的负载均衡策略，将请求分散到不同的服务器上，避免单点过载。
数据库查询优化：数据库管理系统中，LFU 可以用来优化查询计划的缓存，减少磁盘 I/O 次数，提高重复查询的性能。

结构设计

与 Lru 的结构类似，K 与 V 均用指针方式保存，避免在使用过程中出现 Copy 或者 Clone 的可能，提高性能。注:该方法用了指针会相应的出现许多unsafe的代码，因为在 Rsut 中，访问指针都被认为是unsafe。我们也可以使用数组坐标模拟指针的方式来模拟。

节点设计

相对普通的 Lru 节点，我们需要额外存储次数数据。

/// Lfu节点数据pub(crate) struct LfuEntry<K, V> {    pub key: mem::MaybeUninit<K>,    pub val: mem::MaybeUninit<V>,    /// 访问总频次    pub counter: usize,    /// 带ttl的过期时间，单位秒    /// 如果为u64::MAX，则表示不过期    #[cfg(feature = "ttl")]    pub expire: u64,}

复制代码

类设计

Lfu 相对复杂度会比较高，这里维护了最大及最小的访问频次，方便遍历的时候高效

pub struct LfuCache<K, V, S> {    map: HashMap<KeyRef<K>, NonNull<LfuEntry<K, V>>, S>,    /// 因为HashSet的pop耗时太长, 所以取LfuCache暂时做为平替    times_map: HashMap<u8, LruCache<KeyRef<K>, (), DefaultHasher>>,    cap: usize,    /// 最大的访问频次     max_freq: u8,    /// 最小的访问频次    min_freq: u8,    /// 总的访问次数    visit_count: usize,    /// 初始的访问次数    default_count: usize,    /// 每多少次访问进行一次衰减    reduce_count: usize,     /// 下一次检查的时间点，如果大于该时间点则全部检查是否过期    #[cfg(feature = "ttl")]    check_next: u64,    /// 每次大检查点的时间间隔，如果不想启用该特性，可以将该值设成u64::MAX    #[cfg(feature = "ttl")]    check_step: u64,    /// 所有节点中是否存在带ttl的结点，如果均为普通的元素，则过期的将不进行检查    #[cfg(feature = "ttl")]    has_ttl: bool,}

复制代码

频次的设计

这此处频次我们设计成了一个 u8 类型，但是实际上我们访问次数肯定远远超过u8::MAX即 255 的数值。因为此处将访问总次数与频次做了一个映射，防止数据碎片太高及变动频次太频繁。比如初始操作比较频繁的0-10分别映射成0-6如 2 或者 3 均映射到 2，10-40 映射到7-10。其本质的原理就是越高的访问频次越不容易被淘汰，相对来说 4 次或者 5 次很明显，但是 100 次和 101 次其实没多少差别。这样子我们就可以将很高的梯度映射成一颗比较小的树，减少碎片化的操作。

/// 避免hash表爆炸, 次数与频次映射fn get_freq_by_times(times: usize) -> u8 {    lazy_static! {        static ref CACHE_ARR: Vec<u8> = {            let vec = vec![                (0, 0, 0u8),                (1, 1, 1u8),                (2, 3, 2u8),                (4, 4, 3u8),                (5, 5, 4u8),                (6, 7, 5u8),                (8, 9, 6u8),                (10, 12, 7u8),                (13, 16, 8u8),                (16, 21, 9u8),                (22, 40, 10u8),                (41, 79, 11u8),                (80, 159, 12u8),                (160, 499, 13u8),                (500, 999, 14u8),                (999, 1999, 15u8),            ];            let mut cache = vec![0;2000];            for v in vec {                for i in v.0..=v.1 {                    cache[i] = v.2;                }            }            cache        };        static ref CACHE_LEN: usize = CACHE_ARR.len();    };    if times < *CACHE_LEN {        return CACHE_ARR[times];    }    if times < 10000 {        return 16;    } else if times < 100000 {        return 17;    } else if times < 1000000 {        return 18;    } else {        return 19;    }}

复制代码

这里用懒初始化，只有该函数第一次被调用的时候才会初始化这 static 代码，且只会初始化一次，增加访问的速度。

`reduce_count`的设计

假设一段时间内某个元素访问特别多，如algorithm-rs访问了 100000 次，接下来很长的一段时间内他都没有出现过，如果普通的 Lfu 的淘汰规则，那么他将永远的保持在访问频次 100000 次，基本上属于很难淘汰。那么他将长久的占用了我们的数据空间。针对这种情况此处设计了降权的模式，假设reduce_count=100000，那么就每 10w 次访问，将对历史的存量数据访问次数进行降权即新次数=原次数/2，那么在第一次降权后，algorithm-rs将变成了50000，其的权重将被削减。在一定访问的之后如果都没有该元素的访问最后他将会被淘汰。visit_count将当前访问的次数进行记录，一旦大于reduce_count将进行一轮降权并重新计算。

`default_count`的设计

由于存在降权的，那么历史的数据次数可能会更低的次数。那么我们将插入的每个元素赋予初始次数，以防止数据在刚插入的时候就被淘汰。此处默认的访问次数为 5。如果历史经历了降权，那么将会有可能存在数据比 5 小的数据，将优先被淘汰。

初始化

首先初始化对象，初始化 map 及空的双向链表：

impl<K, V, S> LfuCache<K, V, S> {    /// 提供hash函数    pub fn with_hasher(cap: usize, hash_builder: S) -> LfuCache<K, V, S> {        let cap = cap.max(1);        let map = HashMap::with_capacity_and_hasher(cap, hash_builder);        Self {            map,            times_map: HashMap::new(),            visit_count: 0,            max_freq: 0,            min_freq: u8::MAX,            reduce_count: cap.saturating_mul(100),            default_count: 4,            cap,            #[cfg(feature = "ttl")]            check_step: DEFAULT_CHECK_STEP,            #[cfg(feature = "ttl")]            check_next: get_milltimestamp()+DEFAULT_CHECK_STEP * 1000,            #[cfg(feature = "ttl")]            has_ttl: false,        }    }}

复制代码

此处min_freq > max_freq在循环的时候将不会进行任何循环，表示没有任何元素。

元素插入及删除

插入对象，分已在缓存内和不在缓存内与 Lru 的类似，此处主要存在可能操作的列表变化问题

fn try_fix_entry(&mut self, entry: *mut LfuEntry<K, V>) {    unsafe {        if get_freq_by_times((*entry).counter) == get_freq_by_times((*entry).counter + 1) {            self.visit_count += 1;            (*entry).counter += 1;        } else {            self.detach(entry);            self.attach(entry);        }    }}

复制代码

假如访问次数从 10 次->变成 11 次，但是他的映射频次并没有发生变化，此处我们仅仅需要将元素的次数+1 即可，不用移动元素的位置。

attach 其中附到节点上：

fn attach(&mut self, entry: *mut LfuEntry<K, V>) {    unsafe {        self.visit_count += 1;        (*entry).counter += 1;        let freq = get_freq_by_times((*entry).counter);        self.max_freq = self.max_freq.max(freq);        self.min_freq = self.min_freq.min(freq);        self.times_map            .entry(freq)            .or_default()            .reserve(1)            .insert((*entry).key_ref(), ());         self.check_reduce();    }}

复制代码

附到节点时我们将会改变min_freq,max_freq,并将该元素放入到对应的频次里预留足够的空间reserve(1)。并在最后检测是否降权self.check_reduce()

detach 从队列中节点剥离

/// 从队列中节点剥离fn detach(&mut self, entry: *mut LfuEntry<K, V>) {    unsafe {        let freq = get_freq_by_times((*entry).counter);        self.times_map.entry(freq).and_modify(|v| {            v.remove(&(*entry).key_ref());        });    }}

复制代码

此处我们仅仅移除节点 key 信息，这里使用的是 LruCache，移除也是 O(1)的时间复杂度。但是此处我们不维护min_freq及max_freq因为不确定是否当前是否维一，此处维护带来的收益较低，故不做维护。

check_reduce 降权

/// 从队列中节点剥离fn check_reduce(&mut self) {    if self.visit_count >= self.reduce_count {        let mut max = 0;        let mut min = u8::MAX;        for (k, v) in self.map.iter() {            unsafe {                let node = v.as_ptr();                let freq = get_freq_by_times((*node).counter);                (*node).counter /= 2;                let next = get_freq_by_times((*node).counter);                max = max.max(next);                min = min.min(next);                if freq != next {                    self.times_map.entry(freq).and_modify(|v| {                        v.remove(k);                    });                    self.times_map                        .entry(next)                        .or_default()                        .reserve(1)                        .insert((*node).key_ref(), ());                }            }        }        self.max_freq = max;        self.min_freq = min;        self.visit_count = 0;    }}

复制代码

当前降权后将重新初始化min_freq及max_freq，将当前的所有的频次/2，此算法的复杂度为 O(n)。

replace_or_create_node 替换节点

fn replace_or_create_node(&mut self, k: K, v: V) -> (Option<(K, V)>, NonNull<LfuEntry<K, V>>) {    if self.len() == self.cap {        for i in self.min_freq..=self.max_freq {            if let Some(val) = self.times_map.get_mut(&i) {                if val.is_empty() {                    continue;                }                let key = val.pop_unusual().unwrap().0;                let old_node = self.map.remove(&key).unwrap();                let node_ptr: *mut LfuEntry<K, V> = old_node.as_ptr();                 let replaced = unsafe {                    (                        mem::replace(&mut (*node_ptr).key, mem::MaybeUninit::new(k))                            .assume_init(),                        mem::replace(&mut (*node_ptr).val, mem::MaybeUninit::new(v))                            .assume_init(),                    )                };                unsafe {                    (*node_ptr).counter = self.default_count;                }                return (Some(replaced), old_node);            }        }        unreachable!()    } else {        (None, unsafe {            NonNull::new_unchecked(Box::into_raw(Box::new(LfuEntry::new_counter(                k,                v,                self.default_count,            ))))        })    }}

复制代码

当元素数据满时，我们将做淘汰算法，此处我们将从min_req到max_req做遍历，并将最小的频次的 pop 掉最后一个元素。此处如果我们不需护min_req与max_req那么将会最坏的情况为 0-255，即 256 次循环。

其它操作

pop移除栈顶上的数据，最近使用的
pop_last移除栈尾上的数据，最久未被使用的
contains_key判断是否包含 key 值
raw_get直接获取 key 的值，不会触发双向链表的维护
get获取 key 的值，并维护双向链表
get_mut获取 key 的值，并可以根据需要改变 val 的值
retain 根据函数保留符合条件的元素
get_or_insert_default 获取或者插入默认参数
get_or_insert_mut 获取或者插入对象，可变数据
set_ttl 设置元素的生存时间
del_ttl 删除元素的生存时间，表示永不过期
get_ttl 获取元素的生存时间
set_check_step 设置当前检查 lru 的间隔

如何使用

在 cargo.toml 中添加

[dependencies]algorithm = "0.1"

复制代码

示例

 use algorithm::LfuCache;fn main() {    let mut lru = LfuCache::new(3);    lru.insert("hello", "algorithm");    lru.insert("this", "lru");    lru.set_reduce_count(100);    assert!(lru.get_visit(&"hello") == Some(5));    assert!(lru.get_visit(&"this") == Some(5));    for _ in 0..98 {        let _ = lru.get("this");    }    lru.insert("hello", "new");    assert!(lru.get_visit(&"this") == Some(51));    assert!(lru.get_visit(&"hello") == Some(3));    let mut keys = lru.keys();    assert!(keys.next()==Some(&"this"));    assert!(keys.next()==Some(&"hello"));    assert!(keys.next() == None);}

复制代码

结语

综上所述，LFU 算法通过跟踪数据项的访问频次来决定淘汰对象，适用于数据访问频率差异较大的场景。与 LRU 相比，LFU 更能抵御偶发性的大量访问请求对缓存的冲击。然而，LFU 的实现较为复杂，需要综合考虑效率和公平性。在实际应用中，应当根据具体的数据访问模式和系统需求，灵活选择和调整缓存算法，以达到最优的性能表现。

文章转载自：问蒙服务框架
原文链接：https://www.cnblogs.com/wmproxy/p/18270304
体验地址：http://www.jnpfsoft.com/?from=infoq

发布于: 刚刚阅读数: 4

快乐非自愿限量之名

关注

还未添加个人签名 2023-06-19 加入

还未添加个人简介

发布

暂无评论

创作场景

Lfu 缓存在 Rust 中的实现及源码解析

LFU 的原理与实现机制

LFU 与 LRU 的对比及使用场景

LFU 算法的实际案例

结构设计

节点设计

类设计

reduce_count的设计

default_count的设计

初始化

元素插入及删除

attach 其中附到节点上：

detach 从队列中节点剥离

check_reduce 降权

replace_or_create_node 替换节点

其它操作

如何使用

结语

快乐非自愿限量之名

评论

`reduce_count`的设计

`default_count`的设计