常见缓存策略

常见缓存策略FIFO,LRU,LFU,TimeOut

FIFO(First In First Out)

先进先出,使用队列保存顺序。

LRU(Least Recently Used)

最近最少使用,根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高

通常使用链表保存数据节点,具体算法如下:

  1. 新数据插入到链表头部;
  2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
  3. 当链表满的时候,将链表尾部的数据丢弃。

LFU(Least Frequently Used)

使用次数最少,根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。

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

TimeOut

超时自动失效,如果数据可以容忍在一段时间内不一致,那么可以对一个数据设置一定时间的过期时间,在数据过期后,再从真实数据源获取数据,重新放到缓存中,继续设置过期时间。


几种策略的比较

策略 缓存一致性 维护成本
FIFO,LRU,LFU
超时(TimeOut)失效 较差

前三种策略都是为移除缓存指定大概方向,并不明确是否能够正确保证数据正确,所以一致性较超时删除较差。