从访问历史选择淘汰对象
最不经常使用策略通常简称LFU,英文为Least Frequently Used,是在缓存空间不足时,优先淘汰访问频率较低对象的一类替换策略。它可以用于讨论虚拟内存中的页面,也可以用于应用程序中的缓存条目;页面回收只是应用场景之一,而不是LFU的全部定义。
一个简化模型为每个驻留对象保存计数,新对象进入后从约定初值开始,每次访问增加计数,需要腾出位置时选取计数最小者。这里必须说明统计范围:只统计对象本次驻留期间的访问,与保存所有曾见对象的完整历史不是同一种实现。对象离开缓存后是否丢弃计数,会改变它再次进入时的待遇。
热点变化与历史负担
以容量为两个对象的缓存为例:A曾连续被访问一百次,B刚开始被频繁访问,随后请求又在B、C之间交替。如果A的旧计数永远保留,而新对象每次进入都从低计数开始,B、C可能不断互相淘汰,已经不再被请求的A却长期占据位置。这是说明历史累积影响的示例,不代表所有LFU实现都会采用这样的计数规则。
老化机制让较早的访问逐渐失去权重,或只统计一定窗口内的请求,使策略能跟随热点迁移。衰减过慢会保留过时热点,过快则可能把短暂中断误判为长期冷却。计数相同也不能仅靠“最不经常”决定淘汰谁;实现可再按最近访问时间、进入次序或其他规则打破平局,因此比较结果时必须交代这些细节。
精确计数与近似实现
频率判断并非没有成本。精确记录需要额外元数据,也要在访问或替换时维护候选对象。若连已淘汰对象的历史也保存下来,统计空间还可能远大于实际缓存。LRU关注的是最近一次访问的先后,而LFU关注一段历史中的访问次数;前者通常较快反映最近活动,但精确LRU也需要维护次序,不能简单认定它没有管理开销。
Redis自4.0提供近似LFU模式。官方文档说明,它使用概率计数器估算热度,结合时间衰减,并通过抽样选取淘汰候选,而不是每次扫描全部键求出精确最小值。其计数增长因子和衰减时间可以调整:有限计数空间、估计误差和运行开销之间需要折中。这些参数属于Redis的实现,不能当成所有LFU策略的固定组成。
替换、准入与适用条件
频率统计还可以用于决定新对象是否值得进入缓存。TinyLFU论文提出的重点是准入判断:比较新对象与替换候选的近期估计频率,再决定是否接受这次交换。它可以与其他替换策略组合,因此不等于把整个缓存简单改成精确LFU。
选择策略应依据实际访问轨迹、缓存容量、未命中代价和管理开销。稳定且集中的热点有利于频率信息发挥作用,热点快速变换则要求适当遗忘历史。无论LFU还是LRU,都只是利用过去推测未来,不能保证保留下一个必将访问的对象,也不能凭某一组实验宣称对所有工作负载最优。