社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
LRU （Least recently used，最近最少使用）
最常的实现就是使用一个链表来保存缓存数据，最常用在例如：
最近阅读：。。。。
。。。。
。。。。
经常访问的网站 。。。。
。。。。
。。。。
等等等！
其核心的思想就是“如果数据最近被访问过，那么将来被访问的几率也会更高！”
上张图来看下其保存数据的是想！
 |
|
2 每当缓存数据被访问时（缓存命中），则将数据移动到链表的头部
3 当链表装满的时候，将尾部的数据丢弃！
当数据存在热点时（也就是有几条数据频繁被访问）LRU的效率很好！但是在偶发性的，周期性的批量操作会导致LRU的命中率急速
下降，缓存污染的情况比较严重！
LRU-K
lru-k中的k代表最近使用的次数！lru-k主要是为了解决lru的污染缓存问题！其核心思想就是讲最近使用过1次的数据扩展到最近使
用过K次的数据！
相比之下，LRU-K比LRU多维护一个队列，用于记录缓存数据被访问历史！只有当缓存数据达到K次的时候才将数据放入到缓存
当中。需要淘汰时，LRU-K会淘汰掉第K次访问时间距离当前时间最长的数据。
 |
|
| 1.数据第一次被访问，加入到访问历史列表 2 如果数据在访问历史列表里面没有达到K次访问次数，则按照FIFO进行淘汰 3 当访问历史队列中的数据访问次数达到K此以后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序。 4 缓存队列中的数据被再次访问后，重新排序 5 需要淘汰数据时，淘汰掉缓存队列中排在末尾的数据，既：淘汰掉缓存中访问时间里现在最久的数据。LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-K时综合各种因素后的最优选择，LRU-3或许有更大的K中命中率，但适应性差，需要大量的数据访问才能将历史访问记录清楚掉！ |
|
| 分析：LRU-K 命中率：LRU-K降低了“缓存污染”带来的问题，命中率比LRU要高 复杂度：LRU-K队列是一个优先级队列，算法复杂度和代价比较高 代价：由于LRU-K还需要记录哪些被访问过，但是还没有放入缓存的对象，因此内存消耗会比LRU更多！当数据访问量很大的时候，内存消耗会比较可观！ LRU-K需要基于时间进行排序（可以需要淘汰时在排序，也可以及时排序）CPU消耗比LRU更高！ |
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
