缓存过期策略算法

FIFO:First In First Out,先进先出

LRU:Least Recently Used,最近最少使用

LFU:Least Frequently Used,最不经常使用

 

1、FIFO(First In,First Out,先进先出)

FIFO的原理淘汰数据,正好符合队列的特性,先进队列先退出去的策略,数据结构上使用队列Queue来实现。

fifo-lru-lfu-huan-cun-tao-tai-suan-fa-de-yuan-li-01

1. 新访问的数据插入FIFO队列尾部,数据在FIFO队列中顺序移动;

2. 淘汰FIFO队列头部的数据;

 

2、LRU(Least recently used,最近最少使用)

算法根据数据的历史访问记录来进行淘汰数据

其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:

fifo-lru-lfu-huan-cun-tao-tai-suan-fa-de-yuan-li-02

1. 新数据插入到链表头部;

2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;

3. 当链表满的时候,将链表尾部的数据丢弃。

 

3、LFU(Least Frequently Used,最不经常使用)

算法根据数据的历史访问频率来淘汰数据,

其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。

LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。

具体实现如下:

fifo-lru-lfu-huan-cun-tao-tai-suan-fa-de-yuan-li-03

1. 新加入数据插入到队列尾部(因为引用计数为1);

2. 队列中的数据被访问后,引用计数增加,队列重新排序;

3. 当需要淘汰数据时,将已经排序的列表最后的数据块删除。