LRU算法

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

缺陷：大量的顺序读加入新的数据将缓存都淘汰，但是新加入的缓存不是那些真正被经常使用的数据。

核心逻辑：

• 新数据插入到链表头部
• 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
• 当链表满的时候，将链表尾部的数据丢弃
• 当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重
• 命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。LinkedHashMap就是一个LRU的实现，命中数据块的时间复杂度为O(1)。

LRU-K算法中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

• 相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。
• 数据第一次被访问，加入到访问历史列表（内存消耗更多）；
• 如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；
• 当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序（CPU消耗更高）；
• LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。