缓存淘汰算法-LRU

绝地灬酷狼 2024-03-08 02:03 83阅读 0赞

##  ##

**目录**

前言

一、LRU 算法

二、LRU 算法图解

三、LRU 算法实现

四、LRU 算法分析

五、LRU 算法改进方案

--------------------

## 前言 ##

我们常用缓存来提升数据查询速度，由于缓存容量有限，当缓存容量到达上限，就需要删除部分数据挪出空间，这样新数据才可以添加进来。缓存数据不能随机删除，一般情况下我们需要根据某种算法删除缓存数据。常用淘汰算法有 LRU,LFU,FIFO,这篇文章我们聊聊 LRU 算法。

--------------------

## 一、LRU 算法 ##

LRU（Least recently used，最近最少使用）[算法][Link 1]根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：

1. 新数据插入到链表头部；

2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；

3. 当链表满的时候，将链表尾部的数据丢弃。

## 二、LRU 算法图解 ##

1.初始化一个大小为 n 的列表

![56e1b292fc224285932b75111d1229f3.png][]

2.访问一个数据且该数据存在于缓存空间中，返回该数据对应值并将该节点移动到列表头节点， 其余节点位置不变。比如访问 key=C

![893b8354cd8b48ca877f60e3492a1252.png][]

3.插入一个 key=G 节点，直接将数据添加到头结点

![a1c4141d2f3b4ed18376d09ca88c36ef.png][]

4. 假设列表已满，这时再插入一个 key=H 节点，则先删除F节点，在将H节点添加到头结点

![96ddd39ecf7d48228e4c2648d3024773.png][]

![830bf29a6b894e1282ad1dbf18d6d0cd.png][]

这里总结一下 LRU 算法的具体步骤：

*  新数据直接插入到列表头部
 *  缓存数据被命中，将数据移动到列表头部
 *  缓存已满的时候，移除列表尾部数据。

## 三、LRU 算法实现 ##

上面例子中可以看到，LRU 算法需要添加头节点，删除尾结点。而链表添加节点/删除节点时间复杂度 O(1)，非常适合当做存储缓存数据容器。但是不能使用普通的单向链表，单向链表有几点劣势:

1.  每次获取任意节点数据，都需要从头节点遍历下去，这就导致获取节点复杂度为 O(N)。
2.  移动中间节点到头结点，我们需要知道中间节点前一个节点的信息，单向链表就不得不再次遍历获取信息。

针对以上问题，可以结合其他数据结构解决。

使用散列表存储节点，获取节点的复杂度将会降低为 O(1)。节点移动问题可以在节点中再增加前驱指针，记录上一个节点信息，这样链表就从单向链表变成了双向链表。

综上使用双向链表加散列表结合体，数据结构如图所示:

![145ddee7bfaf43ecb7201d380f4a24dd.png][]

> 在双向链表中特意增加两个『哨兵』节点，不用来存储任何数据。使用哨兵节点，增加/删除节点的时候就可以不用考虑边界节点不存在的情况，简化编程难度，降低代码复杂度。

###  ###

## 四、LRU 算法分析 ##

缓存命中率是缓存系统的非常重要指标，如果缓存系统的缓存命中率过低，将会导致查询回流到数据库，导致数据库的压力升高。

结合以上分析 LRU 算法优缺点。

LRU 算法优势在于算法实现难度不大，对于热点数据， LRU 效率会很好。

LRU 算法劣势在于对于偶发的批量操作，比如说批量查询历史数据，就有可能使缓存中热门数据被这些历史数据替换，造成缓存污染，导致缓存命中率下降，减慢了正常数据查询。

## 五、LRU 算法改进方案 ##

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

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

![227816a01d744606b036dc5dd89e1dbf.png][]

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

1.  访问数据如果位于热数据区，与之前 LRU 算法一样，移动到热数据区的头结点。
2.  插入数据时，若缓存已满，淘汰尾结点的数据。然后将数据**插入冷数据区**的头结点。
3.  处于冷数据区的数据每次被访问需要做如下判断：
4.  若该数据已在缓存中超过指定时间，比如说 1 s，则移动到热数据区的头结点。
5.  若该数据存在在时间小于指定的时间，则位置保持不变。

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

##  ##

## 六、Redis LRU 算法 ##

redis中每一个value都可以理解为是一个RedisObject，结构体RedisObject定义了5个属性：type、enconding、lru、refcount和\*prt，如下图

![6a0d3658078f4144b8e067eef41f87db.png][]

Redis对每个KV对中的V，会使用个redisObject结构体保存指向V的指针。那redisObject除记录值的指针，还会使用24 bits保存LRU时钟信息，对应的是lru成员变量。这样，每个KV对都会把它最近一次被访问的时间戳，记录在lru变量。

Redis 在每个数据对象 RedisObject 中存放 lru 字段，表示该数据最近一次访问的时间戳，以后做数据淘汰时用该字段作为比较依据。

当执行数据淘汰时， 首次 执行将按以下步骤选择数据：

1、随机 选出 N （maxmemory-samples）个数据，把它们作为一个候选集合；

2、比较这 N 个数据的 lru 字段，把 lru 字段值最小的数据淘汰出去；

以后 再次 进行数据淘汰时，将以 第一次淘汰时创建的候选集合中最小的 lru 值 minLruInSet 为基准，挑选 lru 字段值 小于 minLruInSet 的数据并放入到集合中，当候选数据集中的数据个数再次达到 maxmemory-samples 时，Redis 就把候选集合中 lru 字段值最小的数据淘汰出去。

通过维护这个 lru 小值集合可以减小发生数据淘汰时对 redis 产生的性能影响，因为它不需要使用链表来保存所有的数据，也不存在数据的移动。

官网 表明在样本数 maxmemory-samples = 10 的情况下，Redis3.0 很接近真正的 LRU 实现。

[Link 1]: http://lib.csdn.net/base/datastructure
[56e1b292fc224285932b75111d1229f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/3a98aa63c7a04bd7ad124a0cfb502b1c.png
[893b8354cd8b48ca877f60e3492a1252.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/65ec032d58804a6da4da1460ea6822c4.png
[a1c4141d2f3b4ed18376d09ca88c36ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/647999542fcb4157833da58eabb92c19.png
[96ddd39ecf7d48228e4c2648d3024773.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/67e4744c6df94803965937b32a4ac216.png
[830bf29a6b894e1282ad1dbf18d6d0cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/e76a526695c446de8c590dea1c0e9c6e.png
[145ddee7bfaf43ecb7201d380f4a24dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/75e8d952b6654eb8b1a133ece54570d2.png
[227816a01d744606b036dc5dd89e1dbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/50fbb1bbb91845b5999cd67737393374.png
[6a0d3658078f4144b8e067eef41f87db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/e6f3cdbe89cb4460af9932ea7ea3d4f1.png