缓存的⼏种淘汰策略
缓存的⼏种淘汰策略：
1.LRU（Least Recently Used） “最近最少使⽤”淘汰策略。如果数据最近被访问过，那么它将来也最有可能被访问。其原理是
a、新访问的数据放在链表的头部，因为这个数据被访问，那么他将来最有可能被访问，适⽤于缓存热点数据，访问⽐较频繁，命中率⾼。
b、每当缓存数据命中之后，就将数据移到链表头部。
c、当链表满了之后，链表尾部的被淘汰。
算法结实模型如下：链表⼀开始是缓存如下数据
dog
cat
monkey
bull
，这时访问缓存数据monkey，就把monkey放在链表顶端，排序如下，
monkey
dog
cat
bull
，接着如果访问新的数据tiger，把tiger放在链表顶端，链表满了，淘汰缓存数据bull。
tiger
monkeyaccess被淘汰了吗
dog
cat
。
从其实现原理来看，适合热点数据缓存。但缺点也相应的容易造成缓存污染，因为新访问的数据，不管访问次数，都会往链表顶部塞。⽐如，新的数据tiger1，tiger2，tiger3.。。这些数据进来，⽽之后这些tigern之后可能并不会访问到，链表⾥⾯会被这些⽆效缓存充斥，造成缓存污染。
为了解决LRU这个问题，可以引⼊LRU-K，即访问次数达到K次，才移到链表头部，避免了缓存污染问题，实际情况中⼀般LRU-2⼀般是最优选择。这种算法
LRU-K淘汰策略原理：
LRU-K算法分为两张表，历史队列和缓存队列。
a、新访问的数据放在历史队列中，然后通过（FIFO、LFU）淘汰尾部访问没有达到K次的数据
b、如果数据访问次数达到K次，把数据放到缓存队列⾥⾯，放在链表头部。
c、淘汰尾部数据。
2、LFU（Least Frequently Used），“最不经常使⽤”淘汰策略。如果数据过去被访问的次数越多，那么它将来也最有可能被访问。其原理是：
a、新加⼊的数据加⼊到队列尾部，计数引⽤为1。
b、数据再次被访问时，计数引⽤加1，队列重新排序。
c、淘汰数据时讲队列尾部的数据淘汰。
这种策略相⽐LRU内存消耗⼤。
简单模型：初始情况
dog10
cat8
monkey7
bull2
当访问monkey 2次后，重新排序 如下
dog10
monkey9
cat8
bull2
当访问tiger时，淘汰bull，tiger计数1次，如下
dog10
monkey9
cat8
tiger1
3、FIFO，“先进先出”策略。访问的数据依次往队列尾部添加 ，淘汰头部的缓存数据。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。