Redis数据缓存淘汰策略【FIFO 、LRU、LFU】
2024-08-26 19:10:02
FIFO、LFU、LRU
FIFO:先进先出算法
FIFO(First in First out),先进先出。在FIFO Cache设计中,核心原则就是:如果一个数据最先进入缓存中,则应该最早淘汰掉。
1、利用一个双向链表保存数据,
2、当来了新的数据之后便添加到链表末尾,
3、如果Cache存满数据,则把链表头部数据删除,
4、然后把新的数据添加到链表末尾。
5、在访问数据的时候,如果在Cache中存在该数据的话,则返回对应的value值;
6、否则返回-1。如果想提高访问效率,可以利用hashmap来保存每个key在链表中对应的位置。
LFU淘汰一定时期内被访问次数最少的数据,以次数作为参考
image.png
1、新加入数据插入到队列尾部(因为引用计数为1);
2、 队列中的数据被访问后,引用计数增加,队列重新排序;
3、当需要淘汰数据时,将已经排序的列表最后的数据块删除。
LRU:
1、新数据插入到链表头部;
2、每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
3、当链表满的时候,将链表尾部的数据丢弃。
Two queues(2Q):2Q算法有两个缓存队列,一个是FIFO队列,一个是LRU队列。
2Q算法将数据缓存在FIFO队列里面,当数据第二次被访问时,则将数据从FIFO队列移到LRU队列里面,两个队列各自按照自己的方法淘汰数据。详细实现如下:
image.png
- 新访问的数据插入到FIFO队列;
- 如果数据在FIFO队列中一直没有被再次访问,则最终按照FIFO规则淘汰;
- 如果数据在FIFO队列中被再次访问,则将数据移到LRU队列头部;
- 如果数据在LRU队列再次被访问,则将数据移到LRU队列头部;
- LRU队列淘汰末尾的数据。
这种情况适用与以下场景
当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。
周期性的批量操作,会立即淘汰LRU队列中的大量数据,导致缓存命中率大幅度下降。而APP常规操作中,有大量偶发批量操作,比如:进入页面后立即返回,就是很典型的一种。
作者:conowen
链接:https://www.jianshu.com/p/4cd5509eec3d
来源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
链接:https://www.jianshu.com/p/4cd5509eec3d
来源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
最新文章
- mysql5.6 主从同步
- Highcharts使用教程(2):设置选项
- Hibernate5.2之QBC查询
- NGUI 灰化按钮或图标
- [转载]JavaEE学习篇之——JQuery技术详解
- Python学习总结11:获取当前运行类名和函数名
- android 6.0权限处理
- linux下的加减运算
- 利用ExcelDataReader封装类 导入表格数据
- 李洪强iOS开发之-PCH文件的配置
- java.lang.NoSuchMethodError: com.google.common.collect.Maps.newConcurrentMap()Ljava/util/concurrent/Concurren​tMap;
- SSE再学习:灵活运用SIMD指令6倍提升Sobel边缘检测的速度(4000*3000的24位图像时间由180ms降低到30ms)。
- 栈和队列数据结构的相互实现[LeetCode]
- Qt中实现将float类型转换为QString类型
- (转)InFluxDB数据库使用手册
- 【Solution】MySQL 5.8 this is incompatible with sql_mode=only_full_group_by
- linux修改主机名+免密认证+关闭防火墙
- Gitlab安装以及汉化
- keepalived实现haproxy负载均衡器的高可用
- ubuntu上解压目录里的文件到指定文件夹