这里主要是针对LRU算法的几种拓展优化思路记录，学习。
LRU算法，最近最少使用页面置换算法：
如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。
这里提供四种LRU拓展算法。
- LRU-Middle，指的是MySQL数据库用到的中点插入策略。
- LRU+FIFO，当数据第一次访问时进入FIFO队列，二次命中再放入LRU链表中。
- LRU-K，这里K代表最近使用过的次数。
- Multi-Queue，根据访问频率将数据划分为多个队列，不同的队列具有不同的访问优先级
LRU-Middle
这个算法的思想来自于《深入浅出MySQL》，里面提到了InnoDB和MyISAM引擎的中点插入策略。
这里以InnoDB引擎为例，简单理解算法思想。
InnoDB也实现了自己的缓存，称为Buffer Pool，我们将它分为 sublist_of_new_block（young区域）和sublist_of_old_block（old区域）
当然了这两个区域其实还是在LRU List里面，只是young在表头，old在表尾。
插入的时候，插入到old的头部（相当于表的中间位置），删除则从old表尾删除。
二次访问，则会将old区域的数据提升到young区域中。
最简单的一句话就是：插入在表中，二次访问提升，删除从表尾。
解决的问题就是，当数据访问次数极少时，插入到表中会比在表头更快淘汰。
LRU+FIFO
这个方案解决的想法跟LRU-Middle类似，它有两个缓存队列，一个是FIFO队列，一个是LRU队列。
当数据第一次访问时，放入到FIFO队列中，当二次命中则移到LRU队列中。
两个队列按照自己的逻辑运行即可。
新的数据插入在FIFO，如果没有二次访问，则最终会被淘汰。
如果被二次访问，则移动到LRU头部，淘汰LRU末尾的数据。
LRU-K
这里K代表最近使用次数，所以LRU可以被理解为LRU-1，表示最近使用过1次，就放入缓存。
而LRU-K则是将最近使用过一次的标准提升为最近使用过K次。
这个算法可以解决LRU缓存污染的问题。
缓存污染是指操作系统将不常用的数据从内存移到缓存，降低了缓存效率的现象。
LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史(后面称为历史访问列表)。
当数据第一次访问时，加入到历史访问列表中，如果它没有达到K次访问，则按照FIFO、LRU之类的规则淘汰。
只有当数据的访问次数达到K次的时候，才将它从历史访问列表中移到缓存队列中，并缓存数据（注意在历史访问列表中的数据是不被缓存的）。
当需要淘汰数据时，我思考了两种淘汰方案：
- 淘汰倒数第K次访问时间点距离当前时间最大的数据。
- 淘汰上次访问时间点距离当前时间最大的数据。
从淘汰上讲，方案1符合了LFU算法思想，一段时间内命中次数多。
从实现上讲，方案2更符合LRU设计思想，删除最近没有访问的数据。
从编码上讲，方案2更省内存，毕竟我不想去存储最近K次的访问时间，更想只存储一个时间点。
举个例子，A和B的访问时间是：
- A：1-3-5-7-9
- B：0-2-4-8-10
如果按照倒数K次的话，假设这里K = 3，那么应该淘汰B，因为B倒数第3次访问时间点4比A在时间点5要早，A在更短的时间内命中了K次。
如果按照上次访问时间，那么应该淘汰A，因为B的最后一次访问时间点比A更晚，更符合最近访问过的数据。
根据LRU算法设计，就应该选用方案2。
提一句LFU算法：最近最不常用页面置换算法，也就是淘汰一定时期内被访问次数最少的页，符合方案1。
关于K的取值，在实际应用中，LRU-2是综合最优的选择。
Multi-Queue（MQ）
MQ算法将数据划分为多个队列，不同队列具有不同的访问优先级。
其核心思想：优先缓存访问次数多的数据。
举个例子?：
如果在低优先级队列中一个数据访问达到一定次数，需要提升优先级，将数据从当前优先级队列移动到上一级优先级队列中。
如果在高优先级队列中一个数据长时间没有被访问，当新数据进来，那么长时间未被访问的数据就移到低一级优先级的队列中。
需要淘汰数据时，从最低一级的队列按照LRU规则淘汰。
当数据被淘汰时，将数据从缓存中删除，将数据的索引放入历史访问队列中，如果重新访问数据，则再次计算优先级，移到目标队列头部。
MQ算法需要维护多个队列以及多个页面的数据，成本较大，复杂度也比LRU高。
LFU算法思想
我们先看一个数据访问例子：横轴是时间点，纵轴是不同的数据访问ABCD。
如果采用LRU算法，缓存大小是2，那么我们依据时间线会发现缓存内容如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
~~A~~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~| B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~| ~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~| ~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D| 0----5----X--------------------------------->时间t t0 -> B ~ 缓存B未命中 t1 -> A B 无数据访问 t2 -> A B 缓存A未命中 t3 -> D B 缓存B命中，缓存D未命中 t4 -> D B 无数据访问 t5 -> D B 无数据访问 t6 -> B D 缓存B命中 t7 -> B D 无数据访问 t8 -> C B 缓存未命中 t9 -> B A 缓存A未命中，缓存B未命中 tX -> B A 无数据访问 ... ... last D B 缓存D未命中 |
我们可以看到开头的10个时间点，有6次未命中记录。
我们回顾淘汰的本质，就是想保留最可能再次访问的数据。
LRU是认为，最近被访问的数据，将来最有可能被访问。
LFU的思想则是：最频繁被访问的数据，将来最有可能被访问。
那么根据LFU算法，我们得出的时间点是这样：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
LFU算法 t0 -> B ~ 缓存B未命中；缓存缺失1次，B访问1次 t1 -> A B 无数据访问 t2 -> A B 缓存A未命中；缓存缺失2次，A访问1次, B访问1次, t3 -> B D 缓存B命中, 缓存D未命中； 缓存缺失3次，A访问1次, B访问2次, D访问1次 t4 -> B D 无数据访问 t5 -> B D 无数据访问 t6 -> B D 缓存B命中；A访问1次, B访问3次, D访问1次 t7 -> B D 无数据访问 t8 -> B C 缓存C未命中；缓存缺失4次， A访问1次, B访问3次, C访问1次, D访问1次 t9 -> B A 缓存A未命中, 缓存B命中；缓存缺失5次，A访问2次, B访问4次, C访问1次, D访问1次 tX -> B A 无数据访问 ... ... 总计10个时间点，5次未命中。 |
这里缓存淘汰优先按次数排序，次数一致则按最后一次访问时间决定。
LFU算法存在的问题：
- LFU算法要求严格按照计数器进行排序，新增节点或者更新节点时效率是O(N)。
- 简单计数并不完美，访问模式可能频繁变化。一段时间内频繁访问的数据，可能之后很少用到。
问题的解决思路：
- 第一个问题可以维护待淘汰的pool，这样相对整体来说更新的效率会变高。
- 记录最后访问的时间，随着时间推移，降低计数器，这样就减小它的优先级。