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

LFU的原理与实现机制

  1. 普通队列
    :LFU算法通过记录数据项的访问频次来工作。当缓存容量达到上限时,系统将会淘汰访问频次最低的数据项。这种方法基于一个假设,即在一段时间内被访问频次较少的数据,未来被访问的几率同样较小。
  2. 数据结构选择
    :为实现O(1)的时间复杂度,这里LFU通常使用哈希表(存储key与节点数据)和双向链表(存储次数与key结构关系)结合的方式来实现。哈希表用于快速查找节点是否存在,而双向链表则用于根据访问频次组织数据项。此处双向链表用一个无限长度的
    LruCache
    代替。在
    remove
    或者改变频次的时候可以用O(1)的复杂度进行操作。一开始用
    HashSet<Key>
    来设计,因为在Rust中HashSet并不存在
    pop
    函数,在数据大量触发替代的时候随机选择一个元素效率太低。
  3. 节点管理
    :每个节点除了存储键值之外,还需附带访问频次信息。每次数据项被访问时,其对应的节点频次会增加;当需要淘汰时,寻找频次最低的节点进行移除或替换。

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

完整项目地址

https://github.com/tickbh/algorithm-rs

结语

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

标签: none

添加新评论