沧州网站制作网站,网站seo,朱能源做网站,网站建设实训报告的内容怎么写一个 lfu(least frequently used/最不经常使用页置换算法 ) 缓存的实现#xff0c;其核心思想是淘汰一段时间内被访问次数最少的数据项。与LRU#xff08;最近最少使用#xff09;算法不同#xff0c;LFU更侧重于数据的访问频率而非访问的新鲜度。 LFU的原理与实现机制 普通…一个 lfu(least frequently used/最不经常使用页置换算法 ) 缓存的实现其核心思想是淘汰一段时间内被访问次数最少的数据项。与LRU最近最少使用算法不同LFU更侧重于数据的访问频率而非访问的新鲜度。 LFU的原理与实现机制 普通队列LFU算法通过记录数据项的访问频次来工作。当缓存容量达到上限时系统将会淘汰访问频次最低的数据项。这种方法基于一个假设即在一段时间内被访问频次较少的数据未来被访问的几率同样较小。 数据结构选择为实现O(1)的时间复杂度这里LFU通常使用哈希表存储key与节点数据和双向链表存储次数与key结构关系结合的方式来实现。哈希表用于快速查找节点是否存在而双向链表则用于根据访问频次组织数据项。此处双向链表用一个无限长度的LruCache代替。在remove或者改变频次的时候可以用O(1)的复杂度进行操作。一开始用HashSetKey来设计因为在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 LfuEntryK, V {pub key: mem::MaybeUninitK,pub val: mem::MaybeUninitV,/// 访问总频次pub counter: usize,/// 带ttl的过期时间单位秒/// 如果为u64::MAX则表示不过期#[cfg(feature ttl)]pub expire: u64,
} 类设计 Lfu相对复杂度会比较高这里维护了最大及最小的访问频次方便遍历的时候高效
pub struct LfuCacheK, V, S {map: HashMapKeyRefK, NonNullLfuEntryK, V, S,/// 因为HashSet的pop耗时太长, 所以取LfuCache暂时做为平替times_map: HashMapu8, LruCacheKeyRefK, (), 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均映射到210-40映射到7-10。其本质的原理就是越高的访问频次越不容易被淘汰相对来说4次或者5次很明显但是100次和101次其实没多少差别。这样子我们就可以将很高的梯度映射成一颗比较小的树减少碎片化的操作。
/// 避免hash表爆炸, 次数与频次映射
fn get_freq_by_times(times: usize) - u8 {lazy_static! {static ref CACHE_ARR: Vecu8 {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_count100000那么就每10w次访问将对历史的存量数据访问次数进行降权即新次数原次数/2那么在第一次降权后algorithm-rs将变成了50000其的权重将被削减。在一定访问的之后如果都没有该元素的访问最后他将会被淘汰。visit_count将当前访问的次数进行记录一旦大于reduce_count将进行一轮降权并重新计算。 default_count的设计 由于存在降权的那么历史的数据次数可能会更低的次数。那么我们将插入的每个元素赋予初始次数以防止数据在刚插入的时候就被淘汰。此处默认的访问次数为5。如果历史经历了降权那么将会有可能存在数据比5小的数据将优先被淘汰。 初始化 首先初始化对象初始化map及空的双向链表
implK, V, S LfuCacheK, V, S {/// 提供hash函数pub fn with_hasher(cap: usize, hash_builder: S) - LfuCacheK, 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 LfuEntryK, 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 LfuEntryK, 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 LfuEntryK, 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), NonNullLfuEntryK, 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 LfuEntryK, 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 体验地址引迈 - JNPF快速开发平台_低代码开发平台_零代码开发平台_流程设计器_表单引擎_工作流引擎_软件架构
