常见缓存策略FIFO,LRU,LFU,TimeOut
FIFO(First In First Out)
先进先出,使用队列保存顺序。
LRU(Least Recently Used)
最近最少使用,根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”
通常使用链表保存数据节点,具体算法如下:
- 新数据插入到链表头部;
- 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
- 当链表满的时候,将链表尾部的数据丢弃。
LFU(Least Frequently Used)
使用次数最少,根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。
- 新加入数据插入到队列尾部(因为引用计数为1);
- 队列中的数据被访问后,引用计数增加,队列重新排序;
- 当需要淘汰数据时,将已经排序的列表最后的数据块删除。
TimeOut
超时自动失效,如果数据可以容忍在一段时间内不一致,那么可以对一个数据设置一定时间的过期时间,在数据过期后,再从真实数据源获取数据,重新放到缓存中,继续设置过期时间。
几种策略的比较
策略 | 缓存一致性 | 维护成本 |
---|---|---|
FIFO,LRU,LFU | 差 | 低 |
超时(TimeOut)失效 | 较差 | 低 |
前三种策略都是为移除缓存指定大概方向,并不明确是否能够正确保证数据正确,所以一致性较超时删除较差。