Redis数据缓存淘汰策略详解：FIFO、LFU、LRU与2Q算法

Redis数据缓存淘汰策略详解：FIFO、LFU、LRU与2Q算法

引用

CSDN

1.

https://blog.csdn.net/2401_83384536/article/details/138311686

Redis作为一款高性能的键值存储系统，其数据缓存淘汰策略对于系统的性能和效率有着至关重要的影响。本文将详细介绍几种常见的缓存淘汰算法，包括FIFO、LFU、LRU以及2Q算法。

FIFO：先进先出算法

FIFO（First in First out）算法的核心原则是：如果一个数据最先进入缓存中，则应该最早被淘汰掉。

1. 利用一个双向链表保存数据
2. 当来了新的数据之后便添加到链表末尾
3. 如果Cache存满数据，则把链表头部数据删除
4. 然后把新的数据添加到链表末尾
5. 在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值
6. 否则返回-1。如果想提高访问效率，可以利用hashmap来保存每个key在链表中对应的位置

LFU：最近最少使用算法

LFU（Least Frequently Used）算法淘汰一定时期内被访问次数最少的数据，以次数作为参考。

1. 新加入数据插入到队列尾部（因为引用计数为1）
2. 队列中的数据被访问后，引用计数增加，队列重新排序
3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除

LRU：最近最少使用算法

1. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
2. 当链表满的时候，将链表尾部的数据丢弃

Two queues(2Q)：2Q算法

2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。

1. 新访问的数据插入到FIFO队列
2. 如果数据在FIFO队列中一直没有被再次访问，则最终按照FIFO规则淘汰
3. 如果数据在FIFO队列中被再次访问，则将数据移到LRU队列头部
4. 如果数据在LRU队列再次被访问，则将数据移到LRU队列头部
5. LRU队列淘汰末尾的数据

这种情况适用于以下场景：

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。周期性的批量操作，会立即淘汰LRU队列中的大量数据，导致缓存命中率大幅度下降。而APP常规操作中，有大量偶发批量操作，比如：进入页面后立即返回，就是很典型的一种。