LRU算法及其变种算法原理分析_lru-2

这一篇主要介绍缓存替换算法LRU及其变种算法的实现原理。

LRU（Least Recently Used）算法

最近最少使用算法，核心思想是：最近使用的数据很大概率将会再次被使用。而最近一段时间都没有使用的数据，很大概率不会再使用。做法：把最长时间未被访问的数据置换出去。这种算法是完全从最近使用的时间角度去考虑的。

执行过程理解:

1. 在缓存中查找客户端需要访问的数据 如果缓存命中，则将访问的数据中队列中取出，重新加入到缓存队列的头部。
2. 如果没有命中，表示缓存穿透，将需要访问的数据从磁盘中取出，加入到缓存队列的尾部；
3. 如果此时缓存满了，则需要先置换出去一个数据，淘汰队列尾部的数据，然后再在队列头部加入新数据。

存在的问题：

缓存污染：如果某个客户端访问大量历史数据时，可能使缓存中的数据被这些历史数据替换，其他客户端访问数据的命中率大大降低。

 
 

LRU变种算法

LRU-K算法

LRU-K算法相对于LRU算法来说多维护了一个队列用来存放访问历史数据，所有新加入缓存的数据都会加入到历史访问队列中，当历史访问队列中数据的访问次数达到K，才会将数据放置到LRU缓存队列中。
LRU算法可以理解为K为1的LRU-K算法，这个算法主要是解决缓存污染的问题，将数据访问一次就进入缓存队列的条件提高到访问K次才能进入缓存队列。

执行过程理解:

1. 在LRU缓存队列中查找客户端需要访问的数据。 如果缓存命中，则将访问的数据中队列中取出，重新加入到缓存队列的头部。
2. 如果没有命中，