LRU

算法介绍：一个双向链表，一个map记录链表中的节点，访问一个节点，如果在链表里面，就把这个节点从原来的地方删除并且插入到链表头部。

优点：考虑了时间的因素

缺点：没有考虑频率的原因，容易因为扫库把热点数据扫出去

LFU

算法介绍： 在最前面的是访问频率最多的数据，访问一次就把这个数据的访问次数加一并且排序把序列有序，如果满了就把频率最低的节点淘汰

可以使用最小堆或者优先队列实现，时间复杂度O（logn）

优点：考虑了频率的因素

缺点：没有考虑时间的原因，容易收到历史数据的影响。

冷热LRU（mysql的缓存池做法）

把一个LRU链表中的5/8作为热点数据链表，3/8作为冷LRU链表

插入：节点不在链表时就先插入到冷链表，第二次在遇到这个节点就插入到热链表中，也像lru链表一样，每次遇到就会插入到前面，热链表再次遇到就插入到最前面，冷链表中再次遇到就插入到热链表的最前面，

淘汰：每次都淘汰冷链表中最后几个数据页。

优点：防止扫库把热点数据淘汰了，既考虑了时间，也考虑了频率。

什么时候将LRU链表中的冷热数据中的缓存页刷盘

定时刷盘，MySQL会起一个后台线程，运行定时任务，每隔一定的时间就将LRU链表的冷数据区域尾部的一些缓存页刷盘，然后清空这些缓存页，并放入free链表，从LRU链表删除，从Flush链表删除

LRU-K

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

常用实现如下

数据第一次被访问，加入到访问历史列表；如果数据在访问历史列表里后没有达到K次访问，则按照LRU淘汰；当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；缓存数据队列中被再次访问后，重新排序；需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即淘汰”倒数第K次访问离现在最久”的数据。

命中率分析

LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。LRU-K降低了”缓存污染”带来的问题，命中率比LRU要高。

2Q与LRU-2类似，不同点在于将LRU-2算法中的访问历史队列改成了一个FIFO队列