数据结构与算法 / LRU 缓存淘汰算法
一、诞生原因
缓存是一种提供数据读取性能的技术，在硬件设计、软件开发中有广泛的应用，比如常见的 CPU 缓存，DB 缓存和浏览器缓存等。但是缓存的大小是有限的，需要一定的机制判断哪些数据需要淘汰，即：移出缓存，从而保证缓存中的数据始终是常用的。常用的机制里面包括 LRU 缓存淘汰算法。
二、设计原则
全称：Least Recently Used
如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。所以淘汰的数据应该是许久没有访问到的数据。
三、所用的数据结构
- 双向链表：用于串联缓存数据。
- 红黑树（散列表）：用于索引缓存数据。
四、执行过程
假设 data 中包含 key 和 value。
节点为 node（指针）。
1、增加缓存数据时，
若缓存已满，double list 尾部数据 delete 掉，将新 data 压入双向链表头部；
将新 data 压入到红黑树中，key 值为 data 中的 key，value 为 node。
2、获取缓存数据时，
先从红黑树中根据 key 找到 node，将 node 放到双向链表的头部，最后返回 node 中 data。
五、代码栗子
六、优化
以下方案来源与 MySQL InnoDB LRU 改进算法
将链表拆分成两部分，分为热数据区，与冷数据区，如图所示。
改进之后算法流程将会变成下面一样:
- 访问数据如果位于热数据区，与之前 LRU 算法一样，移动到热数据区的头结点。
- 插入数据时，若缓存已满，淘汰尾结点的数据。然后将数据插入冷数据区的头结点。
- 处于冷数据区的数据每次被访问需要做如下判断：
- 若该数据已在缓存中超过指定时间，比如说 1 s，则移动到热数据区的头结点。
- 若该数据存在在时间小于指定的时间，则位置保持不变。
对于偶发的批量查询，数据仅仅只会落入冷数据区，然后很快就会被淘汰出去。热门数据区的数据将不会受到影响，这样就解决了 LRU 算法缓存命中率下降的问题。
（SAW：Game Over！）