数据结构与算法 / LRU 缓存淘汰算法

一、诞生原因

缓存是一种提供数据读取性能的技术，在硬件设计、软件开发中有广泛的应用，比如常见的 CPU 缓存，DB 缓存和浏览器缓存等。但是缓存的大小是有限的，需要一定的机制判断哪些数据需要淘汰，即：移出缓存，从而保证缓存中的数据始终是常用的。常用的机制里面包括 LRU 缓存淘汰算法。

二、设计原则

全称：Least Recently Used

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。所以淘汰的数据应该是许久没有访问到的数据。

三、所用的数据结构

1. 双向链表：用于串联缓存数据。
2. 红黑树（散列表）：用于索引缓存数据。

四、执行过程

假设 data 中包含 key 和 value。

节点为 node（指针）。

1、增加缓存数据时，

若缓存已满，double list 尾部数据 delete 掉，将新 data 压入双向链表头部；

将新 data 压入到红黑树中，key 值为 data 中的 key，value 为 node。

2、获取缓存数据时，

先从红黑树中根据 key 找到 node，将 node 放到双向链表的头部，最后返回 node 中 data。

五、代码栗子

github

六、优化

节选：https://www.cnblogs.com/goodAndyxublog/p/11757134.html

以下方案来源与 MySQL InnoDB LRU 改进算法

将链表拆分成两部分，分为热数据区，与冷数据区，如图所示。

改进之后算法流程将会变成下面一样:

1. 访问数据如果位于热数据区，与之前 LRU 算法一样，移动到热数据区的头结点。
2. 插入数据时，若缓存已满，淘汰尾结点的数据。然后将数据插入冷数据区的头结点。
3. 处于冷数据区的数据每次被访问需要做如下判断：

• 若该数据已在缓存中超过指定时间，比如说 1 s，则移动到热数据区的头结点。
• 若该数据存在在时间小于指定的时间，则位置保持不变。

对于偶发的批量查询，数据仅仅只会落入冷数据区，然后很快就会被淘汰出去。热门数据区的数据将不会受到影响，这样就解决了 LRU 算法缓存命中率下降的问题。

参考：极客时间《数据结构与算法之美》王争

这门课真心推荐，内容很经典、栗子很形象，里面还包含了很多面试题目。真是居家旅行必备良药。

（SAW：Game Over！）