Redis LRU算法详述(Least Recently Used - 最近最少使用)

一、简介

Redis是基于内存存储的 key-value 数据库。我们都知道，内存虽然快但空间大小有限，当物理内存达到上限时，系统就会跑的很慢，这是因为 swap 机制会将部分内存的数据转移到swap分区中，通过与swap的交换保证系统继续运行；但是swap属于硬盘存储，速度远远比不上内存，尤其是对于Redis这种QPS非常高的服务，发生这种情况是无法接受的。（注意如果swap分区内存也满了，系统就会发生错误！）

因此如何防止Redis发生这种情况非常重要（面试官问到Redis几乎没有不问这个知识点的）。

swap 空间对于操作系统来说比较重要，当我们使用操作系统的时候，如果系统内存不足，常常会将一部分内存数据页进行swap操作，以解决临时的内存困境。swap空间由磁盘提供，对于高并发场景下，swap空间的使用会严重降低系统性能，因为它引入了磁盘IO操作。

在Linux中，提供了 free 命令来查询操作系统的内存使用情况，free 命令的结果中也包含了swap相关的情况，例如下面的结果中：

[root@TR ~]# free -ht
                     total        used        free      shared     buff/cache   available
Mem:          3.6Gi       233Mi       2.1Gi       1.0Mi       1.3Gi          3.2Gi
Swap:            0B          0B             0B
Total:           3.6Gi       233Mi       2.1Gi

二、maxmemory配置

Redis 针对上述问题提供了 maxmemory 配置，maxmemory指令用于将可用内存限制成一个固定大小，还包括了Redis使用的LRU算法，这个实际上只是近似的LRU。 (从 Redis 4.0 版开始，引入了新的 LFU（最不常用）驱逐策略)。默认情况 maxmemory 配置项并未启用，Redis官方介绍64位操作系统默认无内存限制，32位操作系统默认3GB隐式内存配置，如果maxmemory 为0，代表内存不受限。因此我们在做缓存架构时，要根据硬件资源+业务需求做合适的maxmemory配置。

三、内存达到maxmemory怎么办？

当maxmemory达到了最大上限之后，Redis 很可能“罢工”了，那么Redis是怎么来处理这个问题的呢？这就是本文的重点，Redis 提供了 maxmemory-policy 淘汰策略（本文只讲述LRU不涉及LFU，LFU在下一篇文章讲述），对满足条件的key进行删除操作。

maxmemory-policy淘汰策略：

• noeviction：当达到内存限制并且客户端尝试执行可能导致使用更多内存的命令时返回错误，简单来说读操作仍然允许，但是不准写入新的数据，del（删除）请求可以。
• allkeys-lru：从全部的key中，通过lru（Least Recently Used - 最近最少使用）算法进行淘汰，使得新添加的数据有空间存放。
• allkeys-random：从全部的key中，随机进行淘汰，使得新添加的数据有空间存放。
• volatile-lru：从设置了过期时间的全部key中，通过lru（Least Recently Used - 最近最少使用）算法进行淘汰，这样可以保证未设置过期时间需要被持久化的数据，不会被选中淘汰
• volatile-random：从设置了过期时间的全部key中，随机进行淘汰
• volatile-ttl：从设置了过期时间的全部key中，通过比较key的剩余过期时间TTL的值，TTL越小越先被淘汰

四、近似LRU算法

Redis的 LRU 算法并非完整的实现。这意味着Redis并不是完全准确的淘汰掉最近最不经常使用的key。相反它会尝试运行一个近似LRU的算法，通过对少量keys进行取样，然后回收其中一个最早的key（被访问时间较早的）。不过从Redis 3.0算法已经改进为回收键的候选池子。这改善了算法的性能，使得更加近似真是的LRU算法的行为。

Redis LRU有个很重要的点，你通过调整每次回收时检查的采样数量，以实现调整算法的精度。这个参数可以通过以下的配置指令调整:

maxmemory-samples 5

针对上述的随机LRU算法，Redis官方给出了一张测试准确性的数据图：

• 最上层浅灰色表示被淘汰的key，图一是标准的LRU算法淘汰的示意图
• 中间深灰色层表示未被淘汰的旧key
• 最下层浅绿色表示最近被访问的key

在Redis 3.0 maxmemory_samples 设置为10的时候，Redis的近似LRU算法已经非常的接近真实LRU算法了，但是显然maxmemory_samples设置为10比maxmemory_samples 设置为5要更加消耗CPU计算时间，因为每次采样的样本数据增大，计算时间也会增加。

Redis3.0的LRU比Redis2.8的LRU算法更加准确，是因为Redis3.0增加了一个与maxmemory_samples相同大小的淘汰池，每次淘汰key的时候，先与淘汰池中等待被淘汰的key进行比较，最后淘汰掉最老旧的key，其实就是被选中淘汰的key放到一起再比较一下，淘汰其中最旧的。

五、LRU算法存在的问题

LRU算法看似比较好用，但是也存在不合理的地方。

例如：有A、B两个key，在发生淘汰的前一个小时同时添加到Redis中，A在前49分钟被访问了10000次，但是后11分钟没有被访问；B在这一个小时内仅仅第59分钟被访问了1次；此时如果使用LRU算法，那么A、B均会被Redis采样选中，而结果是A被淘汰，B没有被淘汰。结果很显然是不合理的。针对这种情况Redis 4.0添加了LFU算法，(Least frequently used) 最不经常使用，这种算法比LRU更加合理。下一篇文章将会详细讲解 LFU 算法。