当前位置： 首页 > news >正文

详解缓存淘汰策略：LFU

news 2025/7/15 11:15:57

文章目录

  • 前言
  • LFU
    • 数据结构
    • 读写流程
    • 优缺点
  • 源码走读
    • 数据结构
    • Get
    • Set

前言

前面两篇文章介绍了缓存淘汰策略中的LRU，2q
详解缓存淘汰策略：LRU
详解缓存淘汰策略：2q

2q解决了LRU的突发访问污染问题：如果短时间内有大量新数据涌入（例如全表扫描，批量查询），LRU 会快速淘汰旧的热点数据，导致缓存命中率骤降

但这两者都没考虑缓存的访问频率。例如LRU，仅考虑数据的最近访问时间，淘汰最久未被访问的数据。这可能导致某些 高频访问但近期未被使用的数据被错误淘汰


LFU

本文介绍第三种缓存淘汰策略：LFU

LFU（Least Frequently Used）是一种基于 访问频率 的缓存淘汰策略，其核心思想是：

  • 优先淘汰访问次数最少的数据
  • 若频率相同
    • 可以随机淘汰一个（本文介绍这种方式）
    • 也可以淘汰最久未使用的数据，也就是按LRU淘汰

数据结构

LFU由以下核心结构组成：

  • 哈希表items：从 key 到缓存项的映射
  • 双向链表freqList：每个节点freqEntry表示一个访问频率等级（如 freq=1、freq=2 等等），链表按频率递增排序。每个节点结构如下：
    • 频率freq：当前频率值
    • 哈希表items：存储属于该频率的所有缓存项
  • 每个缓存项item：存储key，value，所属的freqEntry

在这里插入图片描述


读写流程

写：
在这里插入图片描述

  1. 如果 key在哈希表items中已存在，则直接更新对应的 value 值 (O(1))
  2. 否则就需要插入新缓存项：
    1. 如果缓存未满，直接插入到 哈希表items中，并将其加入 freqList 中频率最低（即 freq=0）的 freqEntry.items中(O(1))
    2. 如果缓存已满，调用 evict 方法淘汰随机淘汰频率最低的一个缓存项，然后插入新缓存项
      1. 具体做法：取出freqList的头节点，从其items中随机选择一个item删除 (O(1))

时间复杂度：在哈希表和双向链表的配合下，插入和更新的时间复杂度为O(1)


读：
在这里插入图片描述

  1. 通过哈希表items快速查找 key 对应的缓存项 (O(1))
  2. 如果找到且未过期，则调用 increment 方法增加该项的访问频率，并返回值

频率更新逻辑：

  1. 将缓存项从当前频率等级中移除，并添加到下一个频率等级中 (O(1))
    1. 如果移除后当前频率等级为空，则将其从 freqList 中删除，节约内存 (O(1))
    2. 如果下一个频率等级freqEntry不存在，或者freqEntry.freq不是当前freq+1，那就新建一个freqEntry，然后往里面插入当前缓存项item (O(1))

时间复杂度：查找和频率更新的时间复杂度均为 O(1)，非常高效


优缺点

  • 优点：
    • 稳定性：对于过往高频，近期低频的数据，LFU能在缓存中很好地保留下来。避免因为短期波动，导致
    • 比 LRU 更能抵抗突发流量污染：因为突发访问大概率就访问一次，往往频率增加不多，很快会被真正高频的项挤掉
  • 局限性：
    • 历史频率权重问题: 稳定性同时也是一把双刃剑：一个过去访问频率很高但最近不再访问的项，其频率计数会一直很高，长期占据缓存无法被淘汰，即使它已经不再有用。同时短期内的热点也无法在缓存中长留，导致缓存命中率不高
    • 冷启动问题：新加入的数据初始访问频率低，即使未来会成为热点，也可能被快速淘汰

源码走读

下面将针对开源库https://github.com/bluele/gcache的LFU实现进行源码走读，版本：v0.0.2
这个库目前2.7k star，算是能找到的LFU实现里还不错的：


在这里插入图片描述


数据结构

type LFUCache struct {baseCache// key到lfuItem的映射items map[interface{}]*lfuItem// 每个 freqEntry 表示一个访问频率等级（如 freq=1, freq=2...）。 // items map[*lfuItem]struct{} 存储属于该频率的所有缓存项/**LFUCache├── baseCache            // 公共配置与方法├── items                // key -> *lfuItem└── freqList             // list<*freqEntry>└── freqEntry     // freq=1└── items     // map[*lfuItem]struct{}└── freqEntry     // freq=2└── items...*/freqList *list.List  // list for freqEntry
}

其中lfuItem定义如下：

type lfuItem struct {// ...key         interface{}value       interface{}// 属于哪个freqEntry ，用于直接定位到freqEntryfreqElement *list.Element// ...
}

初始化：

func (c *LFUCache) init() {c.freqList = list.New()c.items = make(map[interface{}]*lfuItem, c.size)// 初始化生成一个freq=0的freqEntry，该freqEntry会一直存在c.freqList.PushFront(&freqEntry{freq:  0,items: make(map[*lfuItem]struct{}),})
}

Get

func (c *LFUCache) getValue(key interface{}, onLoad bool) (interface{}, error) {c.mu.Lock()item, ok := c.items[key]// 存在if ok {// 没有过期if !item.IsExpired(nil) {// 调用 c.increment(item) 增加该项的访问频率c.increment(item)v := item.valuec.mu.Unlock()if !onLoad {c.stats.IncrHitCount()}return v, nil}c.removeItem(item)}c.mu.Unlock()if !onLoad {c.stats.IncrMissCount()}return nil, KeyNotFoundError
}

其中核心方法increment流程如下：

func (c *LFUCache) increment(item *lfuItem) {// 拿到当前的freqEntrycurrentFreqElement := item.freqElementcurrentFreqEntry := currentFreqElement.Value.(*freqEntry)// 计算下一个频率值nextFreq := currentFreqEntry.freq + 1//  从当前频率条目中移除缓存项delete(currentFreqEntry.items, item)// 是否可删除currentFreqEntry？currentFreqEntry.items为空时可以删除removable := isRemovableFreqEntry(currentFreqEntry)// insert item into a valid entrynextFreqElement := currentFreqElement.Next()switch {// 需要创建新的FreqElement: 没有nextFreq的频率map时case nextFreqElement == nil || nextFreqElement.Value.(*freqEntry).freq > nextFreq:if removable {// 复用之前的FreqElementcurrentFreqEntry.freq = nextFreqnextFreqElement = currentFreqElement} else {// 添加一个新的FreqElementnextFreqElement = c.freqList.InsertAfter(&freqEntry{freq:  nextFreq,items: make(map[*lfuItem]struct{}),}, currentFreqElement)}// 不需要创建新的case nextFreqElement.Value.(*freqEntry).freq == nextFreq:if removable {c.freqList.Remove(currentFreqElement)}default:panic("unreachable")}nextFreqElement.Value.(*freqEntry).items[item] = struct{}{}item.freqElement = nextFreqElement
}

Set

func (c *LFUCache) set(key, value interface{}) (interface{}, error) {var err errorif c.serializeFunc != nil {value, err = c.serializeFunc(key, value)if err != nil {return nil, err}}// 检查是否已存在相同的 keyitem, ok := c.items[key]if ok {// 如果存在，直接更新valueitem.value = value} else {// 不存在相同key，那就要创建个新的// 如果容量满了，随机淘汰一个频率最低的if len(c.items) >= c.size {c.evict(1)}item = &lfuItem{clock:       c.clock,key:         key,value:       value,freqElement: nil,}el := c.freqList.Front()fe := el.Value.(*freqEntry)// 把当前item添加到频率为0的freqEntry中fe.items[item] = struct{}{}item.freqElement = elc.items[key] = item}if c.expiration != nil {t := c.clock.Now().Add(*c.expiration)item.expiration = &t}if c.addedFunc != nil {c.addedFunc(key, value)}return item, nil
}

删除一个频率最低的缓存项：

func (c *LFUCache) evict(count int) {// 从最低频率的map中，随机挑选一个淘汰entry := c.freqList.Front()for i := 0; i < count; {if entry == nil {return} else {for item := range entry.Value.(*freqEntry).items {if i >= count {return}c.removeItem(item)i++}entry = entry.Next()}}
}
http://www.lryc.cn/news/587142.html

相关文章：

  • 初级网安作业笔记1
  • 3. 【Blazor全栈开发实战指南】--Blazor是什么？为什么选择Blazor？
  • [特殊字符]使用 Nginx 将 HTTP 重定向到 HTTPS
  • Spring-----MVC配置和基本原理
  • CD49.【C++ Dev】容器适配器模式
  • 一个链表节点构造函数的定义及使用
  • 如何将FPGA设计的验证效率提升1000倍以上(4)
  • Datawhale AI 夏令营【更新中】
  • 动态规划题解_零钱兑换【LeetCode】
  • 数学与应用数学核心课程有哪些？全文解析！
  • Cursor精准上下文指定
  • [Python 基础课程]字典
  • Spring AI 项目实战（十七）：Spring Boot + AI + 通义千问星辰航空智能机票预订系统（附完整源码）
  • 12.3 安全内存区域划分
  • Kubernetes集群安装
  • Word中的批注显示与修订显示
  • 无需付费即可利用AI消除音频噪声和生成字幕
  • 云服务器的基础使用
  • 代码部落 20250713 CSP-J复赛 模拟赛
  • Java#为什么使用ThreadLocal传参而不是直接传参
  • 每天一个前端小知识 Day 30 - 前端文件处理与浏览器存储机制实践
  • 5.适配器模式
  • ClickHouse 分区机制详解：规则、合并与实践指南
  • LeetCode 1156.单字符重复子串的最大长度
  • 力扣 hot100 Day43
  • OSPF与BGP的联动特性
  • 【设计模式】备忘录模式（标记(Token)模式）
  • 面向对象设计模式详解
  • Flink学习笔记：整体架构
  • NO.4数据结构数组和矩阵|一维数组|二维数组|对称矩阵|三角矩阵|三对角矩阵|稀疏矩阵