LRU 是使用在图像加载库中常用的缓存算法。
简单的描述 LRU 算法:
- 新的资源放在队列头部
- 当资源被使用,就把资源移动到队列头部
- 当队列满的时候,首先从队列尾部淘汰
看起来没有什么问题,不常用的资源会被先淘汰。
但是当遇到突发的资源缓存,就有可能发生缓存污染,导致热点资源也会被淘汰:
刷微博的时候,主页中的「关注」tab 里的图像应该是热点数据,因为它们稳定存在并且变化的概率很小。 但是访问到「发现」里的微博时,里面的数据是随机推荐的,数据经常变化。 如果发现页面刷的越久,缓存队列中真正的热点资源就会被淘汰掉,从而造成缓存污染。
为了解决这个问题,就要多加一层缓存队列,把 LRU 队列中的数据保护起来。
在 LRU 的外部增加一个先入先出(FIFO)队列,资源进来的时候,先进入 FIFO 队列。 如果 FIFO 中的资源再次被访问,则将其移出并加入 LRU 队列头部。
使用 FIFO 作为保护队列,先假设资源都是临时缓存,除非被重复使用才认定为热点资源。 临时缓存使用 FIFO 的规则进行淘汰,这样就保证了面对突发的资源缓存时保证 LRU 队列的清洁。