关于redis:redis缓存回收策略

Redis 缓存应用了内存保留数据，使数据的存储和读取都失去了极大的晋升，然而因为计算机中“内存”的造价却在磁盘的数百倍之上；这也导致咱们无奈应用 Redis 缓存所有的数据；

那样也衍生出一个问题：当 Redis 中缓存的数据大小，达到下限后，redis 会作出怎么的操作？

为了解决这个问题，redis 有着本身保护的一套 缓存数据的淘汰机制；其实简略来说就是分成两步：

依据指定规定筛选出能够 ” 放弃 ” 的 key 值
开释对应 key 值的空间，用于保留新的 Key 值

Redis 中有一个 maxmemory 的概念，次要是为了将 redis 的应用内存限定在一个固定的大小，当应用内存超出限定值后，依据 maxmemory-policy 配置的策略进行内存回收；

maxmemory 的设定值有如下两种形式：

第一种：通过 congfig set 命令进行设置：

127.0.0.1:6379> config get maxmemory
1) "maxmemory"
2) "0"
127.0.0.1:6379> config set maxmemory 1024MB
OK
127.0.0.1:6379> config get maxmemory
1) "maxmemory"
2) "1073741824"

第二种：通过 redis.conf 文件批改

maxmemory 1024MB

留神： 不配置 maxmemory 的值时，将默认为 0；

64 bit 零碎：maxmemory 设置为 0 示意不限度 Redis 内存应用

32 bit 零碎：maxmemory 设置为 0 示意限度 Redis 内存不能超过 3G。

（造成这个当初的其实是系统对内存应用的限度造成的，并不是 redis 造成的，有趣味能够理解下不同 bit 系统对内存的利用）

Redis4.0 之前共实现了 6 种内存策略，之后又减少了两种内存策略；次要能够分成两类：

不进行数据淘汰的策略，只有 noeviction 这一种
会淘汰 key 值的 7 种

会进行淘汰的 7 种策略，咱们能够再进一步依据淘汰候选数据集的范畴把它们分成两类：

在设置了过期工夫的数据中进行淘汰，包含 volatile-random、volatile-ttl、volatile-lru、volatile-lfu（Redis 4.0 后新增）四种。
在所有数据范畴内进行淘汰，包含 allkeys-lru、allkeys-random、allkeys-lfu（Redis 4.0 后新增）三种。

如下图：

具体解析下：

noeviction 策略：当 Redis 缓存达到了 maxmemory 配置的值后，再有写入申请到来时，redis 将不再提供写入服务，间接响应谬误
volatile-ttl 策略：在筛选时，会针对设置了过期工夫的键值对，依据过期工夫的先后进行删除，越早过期的越先被删除
volatile-random 策略：在设置了过期工夫的键值对中，进行随机删除
volatile-lru 策略：应用 LRU 算法筛选设置了过期工夫的键值对
volatile-lfu 策略：应用 LFU 算法抉择设置了过期工夫的键值对
allkeys-random 策略，从所有键值对中随机抉择并删除数据；
allkeys-lru 策略，应用 LRU 算法在所有数据中进行筛选。
allkeys-lfu 策略，应用 LFU 算法在所有数据中进行筛选。

留神： volatile-random、volatile-ttl、volatile-lru 和 volatile-lfu 这四种淘汰策略。它们筛选的候选数据范畴，被限度在曾经设置了过期工夫的键值对上。也正因为此，即便缓存没有写满，这些数据如果过期了，也会被删除。反之：allkeys-lru、allkeys-random、allkeys-lfu 这 3 种淘汰策略。他们的筛选的候选数据范畴是全副 key，所以他们淘汰的 key 可能是没到期的。

由下面可知 volatile-lru 和 allkeys-lru 策略都是应用了 LRU 算法。

LRU(least recently used) 其实是一种缓存置换的算法，在 linux 内存治理也常有体现。即在缓存无限的状况下，如果有新的数据须要退出缓存，则咱们须要先将最不可能被拜访到的数据移除，以腾出空间缓存新数据；然而咱们无奈预知到缓存的数据哪些将不会被拜访。。。所以咱们只能基于如下的规定来实现算法：

如果一个 KEY 常常被拜访，那么这个 KEY 的 idle time（闲暇工夫）应该是最小的，而且再次拜访的概率应该是最大的；然而另外一个角度解读，这个不是必然事件，idle time 最大不能代表这个 key 就不会再被拜访。

咱们举一个例子（其中一种较为简单的形式），来看看 LRU 算法是如何做到的：

假如：咱们的内存页能存储的数据为 5 个；咱们将存储的数据结构用 双向链表 和 hashmap（这个是为了保障存储和读取都能够实现 O(1)）, 双向链表两端别离标记为 MRU 端和 LRU 端

如上图所示：

咱们数据页别离保留有 KEY1 到 KEY5 5 个数据如果 KEY4 被拜访时候，咱们遍历 Hashmap 确认了以后数据曾经存在，于是把他的 KEY4 节点挪动到 MRU 端（链表头部）；（因为是双线链表 +hashmap 机构，所以更改关系十分不便。不须要整个连进行遍历挪动）生成新的双线链表；而后，当新数据 KEY6 写入时，因为内存页曾经满了，所以咱们把 LRU 端（链表尾部）的一个元素移除，而后再在 MRU 端 插入新的元素

毛病:

下面的 LRU 算法实现形式不是很简单，然而通过双向链表和 hashmap 来治理所有的缓存数据，显然有着一些致命的缺点；这会带来大量的额定的内存空间损耗，而且咱们都晓得在 redis 中是“单线程”的。如果没次的读写都须要保护这个链表的挪动和 hashmap 关系，这会大大加大了 Redis 服务的计算时长，进而升高了 Redis 缓存的性能，这也是咱们不能承受的。

根据上述，显然 Redis 并没有应用双线链表实现 LRU 算法。

首先咱们能够看看 redisObj 构造体（其实 redis 整体上是一个大的 dict,key 是一个 string，而 value 是一个 redisObj）

/*
 * Redis 对象
 */
typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 对齐位
    unsigned notused:2;

    // 编码方式
    unsigned encoding:4;

    // LRU 工夫（绝对于 server.lruclock）unsigned lru:LRU_BITS;

    // 援用计数
    int refcount;

    // 指向对象的值
    void *ptr;

} robj;

咱们能够看到有一个 LRU 的字段，而这个字段是通过调用 lookupKey 办法来获取值的

robj *lookupKey(redisDb *db, robj *key, int flags) {
    ...
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { // 如果配置的是 lfu 形式，则更新 lfu
                updateLFU(val);
            } else {val->lru = LRU_CLOCK();// 否则按 lru 形式更新
            }
    ...
}

其实能够简略了解，redis 外部保护了一个公共的 LRU 时钟，定时刷新对应的值（就类比：咱们的时钟的秒针，始终在走）；当 Redis 的 dict 中来获取数值的时候，就会把以后 lru 时钟的值返回回去，作为以后的值返回回去。

那么咱们缓存的数据中每一个都有一个本人拜访的的工夫值，换句话说，依据这个 LRU 时钟的工夫戳，咱们能够分明的定位到每一个 key 的最初拜访工夫，咱们也能够算出他的 idle time；最初咱们只须要变量所有 Key 的 idle time 咱们就能够晓得应该淘汰哪个 Key 了。

然而淘汰时总不能挨个遍历 dict 中的所有槽，一一比拟 LRU 值大小吧，每一次都遍历，单过程的redis 读写预计会跟乌龟一样慢。

咱们下面有说过 LRU 算法实质其实也是概率性的，那么实现的时候索性就将概率性贯彻到底。。

Redis 初始的实现算法很简略，随机从 dict 中取出五个 key, 淘汰一个 lru 字段值最小的。(随机选取的 key 是个可配置的参数 maxmemory-samples, 默认值为 5).

起初在 redis3.0 中又改良了一版，引入了一个 Pool 的概念，第一次随机选取的 key 都会放入一个 pool 中,pool 中的 key 是按 lru 大小顺序排列的。接下来每次随机选取的 keylru 值必须小于 pool 中最小的 lru 才会持续放入，直到将 pool 放满。放满之后，每次如果有新的 key 须要放入，须要将 pool 中 lru 最大的一个 key 取出。

最初，淘汰的时候，间接从 pool 中退出 lru 最小的淘汰即可

有理解的应该晓得 Redis 执行命令的时候，会调用processCommand 函数（有趣味能够看下）

int processCommand(redisClient *c) {
   ....
   
    /* Handle the maxmemory directive.
     *
     * First we try to free some memory if possible (if there are volatile
     * keys in the dataset). If there are not the only thing we can do
     * is returning an error. */
    // 如果设置了最大内存，那么查看内存是否超过限度，并做相应的操作
    if (server.maxmemory) {
        // 如果内存已超过限度，那么尝试通过删除过期键来开释内存 
        int retval = freeMemoryIfNeeded();
        // 如果行将要执行的命令可能占用大量内存（REDIS_CMD_DENYOOM）// 并且后面的内存开释失败的话
        // 那么向客户端返回内存谬误
        if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {flagTransaction(c);
            addReply(c, shared.oomerr);
            return REDIS_OK;
        }
    }
    ....

}

其实下面能够看到最初开释内存是通过了 freeMemoryIfNeeded 函数来操作的

具体的剖析能够看下这个文章 Redis 源码解析(11) 内存淘汰策略

因为 LRU 算法 自身就具备概率性的，而Redis 作者在实现的形式也是基于概率的；那么在两个都是概率性的状况下，LRU 算法 在理论应用中是否会极大的偏离了咱们的料想期呢？

作者做了个试验，后果如下图：

上图分为 3 个不同的色带：

浅灰色带是被逐出的对象。
灰带是未逐出的对象。
绿带是增加的对象。

如果左上图 1，咱们定义为 LRU 算法 的最现实状况，新减少的 key 和最近被拜访的 key 都不应该被逐出；

咱们能够看到 maxmemory-samples 设置为 5 的时候 Redis 2.8 服务展示进去的后果，还是有点差强人意的，

然而当作者在 Redis 3.0 后引入了 pool 的概念后，展示进去的后果有了较大的晋升。至多新退出的 key 被回收回去的状况有了很大的晋升。

当咱们在 Redis 3.0 服务中将 maxmemory-samples 的值晋升到 10 的时候，曾经十分靠近现实值了。。

然而如果你认真浏览了上文，你会分明晓得 maxmemory-samples 越大对服务器的 cpu 都会有较大的耗费的；

所以作者在最初也给出了本人的倡议：

However you can raise the sample size to 10 at the cost of some additional CPU usage in order to closely approximate true LRU, and check if this makes a difference in your cache misses rate.

但其实如果服务器性能不是特地优良，其实应用默认值：5；就够了。。。

Redis LRU 算法的随机阐明：http://antirez.com/news/109

源码剖析查考： https://blog.csdn.net/weixin_…

Redis 用作 LRU 缓存： https://redis.io/topics/lru-c…

LRU 原理和 Redis 实现——一个今日头条的面试题：https://zhuanlan.zhihu.com/p/…

关于redis:redis缓存回收策略

redis- 缓存回收策略

如何设置 redis 的内存暂用值

Redis 缓存有哪些策略

浅谈下 LRU 算法

1. 那什么是 LRU 算法呢？

2. 那具体是如何筛选出 idle time 最大的 key 呢?

Redis 中 LRU 的实现

maxmemory-samples 该如何配置

参考：