Redis内存淘汰原因

Redis是一种内存数据库，redis的容量往往有限，无法存放所有的数据。当内存满了的时候，并且这个时候还需要往Redis中放入新的数据，就需要将Redis中的一部分数据淘汰了，把新的数据放进入。

Redis内存淘汰策略

一个Redis中存储了很多的数据，应该选取哪部分数据进行置换呢？

Redis提供了多种淘汰策略，大概分为以下五类：

1、lru

通过lru，least recently used，也就是最近最久使用算法，也就是淘汰使用时间最旧的数据。

redis中的每个数据的key和value都对应着一个redisObj对象。

typedef struct redisObject {

    // 数据类型
    unsigned type:4;

    // 数据编码方式
    unsigned encoding:4;

    // 对象最后一次被访问的时间，REDIS_LRU_BITS代表着lru对应的位数
    unsigned lru:REDIS_LRU_BITS; 

    // 引用计数
    int refcount;

    // 指向实际值的指针
    void *ptr;

} robj;

redisObj中有一个属性 lru，lru是一个24位的数字，保存了一个时间戳，代表着一个对象最新被使用的时间。

redisServer中维护了一个lruclock属性来表示当前系统的时间戳，每隔100ms就会调用updateLRUClock()来更新server.lruclock的值。

void updateLRUClock(void) {
    //server.unixtime是当前系统的时间，单位是ms
    //REDIS_LRU_CLOCK_RESOLUTION是lruclock的精度，默认为1，也就说默认单位是ms，如果为10，代表为s。
    //REDIS_LRU_CLOCK_MAX是时间戳的最大值，一般是1<<REDIS_LRU_BITS-1
    server.lruclock = (server.unixtime / REDIS_LRU_CLOCK_RESOLUTION) &
                                                REDIS_LRU_CLOCK_MAX;
}

当新建key或者访问key的时候，会将对应的redisObj.lru = server.lruclock。

用server.lruclock的值减去redisObj.lru的值就可以得到对应key的空闲时间了

但是当server.unixtime也就是当前系统时间大于REDIS_LRU_CLOCK_MAX的时候，会将server.lruclock从0开始计数，这就会出现redisObj.lru大于server.lruclock的情况，这种情况下如何算对应的空闲时间呢？

//这里只是粗略的估计空闲时间，因为之前算server.lruclock()和redisObj.lru的时候，已将unixtime()/REDIS_LRU_CLOCK_RESOLUTION了，对应的精度已经损失了。
unsigned  long  long  estimateObjectIdleTime(robj *o) {
     unsigned  long  long  lruclock = LRU_CLOCK();
     //正常情况，server.lruclock()还未转完一圈
     if  (lruclock >= o->lru) {
         return  (lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
     }  else  { server.lruclock()转完一圈了，那么需要将其结果加上对应的REDIS_LRU_CLOCK_MAX的值
         return  (lruclock + (REDIS_LRU_CLOCK_MAX - o->lru)) *
                     REDIS_LRU_CLOCK_RESOLUTION;
     }
}

LRU工作流程

一般的LRU的做法如下：
1、为每个节点设置一个prev前继节点指针和next后继节点指针，将所有节点通过这两个指针连接成一个链表，链表有着head和tail节点。
2、用一个哈希表将key和对应的节点存放起来，用来快速的找到key对应的节点
3、当通过key访问对应的节点的时候，通过哈希表查询key得到对应的节点。然后通过节点的的prev和next指针将节点从链表中移除，并将节点放到链表的头部中。
4、当新加入key和节点的时候，如果对应的链表已经满了，就将尾部的节点去除，然后将新节点加入到链表的头部。

从上述流程可以看出，基于链表和哈希表的LRU需要设置prev指针、next指针、以及hash表中的key和value的指针，这是一个很大的内存开销。

Redis并没有采用这样的做法，而是采用了随机抽取的做法、

Redis在每次进行内存的替换的时候，会随机抽取出若干个key，默认是5个，然后获取其对应的lru时间信息，淘汰lru最小的那个数据，也就是最久未被使用的数据。

lru升级
1、Redis3.0之后对lru算法进行了升级，Redis中会维护一个Pool，Pool中最大可以容纳16个Key，按照key的空闲时间进行排序，空闲时间就是当前时间和上一次访问时间戳之间的差值，空闲时间越大说明key越长时间没有被访问，应该被淘汰。

2、当每次要淘汰key的时候，会随机抽取若干个key，计算其空闲时间，如果Pool还没有满或者比Pool中的最小空闲时间Key大的话，就将空闲时间小的Key从Pool中移除，将Key加入到Pool中。

3、当要淘汰key的时候，将Pool中的空闲时间最大的key对应的数据移除内存。

其中根据抽取key的数据来源不同，将lru分为了两类：
1、volatile-lru
从设置了过期时间的数据中随机抽取数据淘汰，也就是从redisDb.expires中抽取key。
2、allkeys-lru
从所有数据中随机抽取数据淘汰，也就是从redisDb.dict中抽取key。

如果不知道redisDb.expires和redisDb.dict是什么意思的话，可以看一下我之前写的关于redis中存储模型的文章Redis存储模型详解

不论是3.0之前还是3.0之后，每次抽取的key次数越多，越能体现LRU的特性，但是对应耗费的CPU资源就越大，很多时候计算机系统就是这样，鱼和熊掌不能得兼。

2、ttl

ttl是time to live的简称，也就是生存时间的意思，在redis中体现的就是过期时间。

volatile-ttl
从redisDb.expires也就是拥有过期时间的数据中随机抽取出若干个key，然后找到其中存活时间最短的key，也就是最即将过期的key，将其对应的数据从内存中移除。

3、random

random就是随机的意思，分为两种：
1、volatile-random
从redisDb.expires也就是拥有过期时间的数据中随机选取一个key，将其淘汰。

2、allkeys-random
从redisDb.dict也就是所有数据中随机选取一个key，将其淘汰。

4、lfu

lfu的全称是 leastly frequently used，最近最少使用，也就是挑选出最近使用次数最少的key。

使用次数也是通过redisObject中的lru字段记录的。

我们之前说过lru有24位，其中前16位用于记录最近访问时间time，单位是分钟、后8位用于记录访问次数counter。

增长

你可能会奇怪8位最多只能记录255，这不是在开玩笑吗？其实每次访问不会一定将counter++，而是通过一定的概率来判断是否将counter++。

//counter就是当前key对应的counter
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    //随机生成一个数字
    double r = (double)rand()/RAND_MAX;
    //将当前的counter减去一个固定值
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    //server.lfu_log_factor是增长控制因子
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    //如果随机生成的数小于p，就将counter++
    if (r < p) counter++;
    return counter;
}

从上述代码看出，增长概率与 server.lfu_log_factor和counter有关，server.lfu_log_factor和counter越大，增加概率越小。

但是所有的key都是共用一个server.lfu_log_factor，如果server_lfu_log_factor改变，所有key都会收到相同的影响。

而counter是每个key都对应着一个值，所以说随着key的不断访问，counter越来越大，增长速率是越来越慢的。

下图是随着factor和访问次数对counter的影响

衰减
当一个key在前一段时间被频繁访问，但是之后慢慢用不到了，对应的counter应该变小，要不然key会一直保存在内存中，无法被移除，降低内存使用率。

所以redis提供了一个衰减机制。

衰减机制与 key的空闲时间有关， key空闲时间越长，对应的counter就减少的越多。

unsigned long LFUDecrAndReturn(robj *o) {
    //将lru左移8位，得到对应的时间戳
    unsigned long ldt = o->lru >> 8;
    //将lru & 0000 0000 0000 0000 1111 得到对应的counter
    unsigned long counter = o->lru & 255;
    //算出对应的空闲周期数。
    //server.lfu_decay_time是衰减因子，可以在配置文件中修改，默认是10，单位是分钟
    //LFUTimeElapsed(ldt)就是算出对应的空闲时间，然后将空闲时间除去衰减因子，得到衰减周期 num_periods
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    //将counter减去对应的衰减周期
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

从上述代码看出，如果一个Key在N分钟没有被访问，当衰减检查的时候，就会将其counter - N。

lfu工作过程：

当访问对应的key的时候，会更新其redisObj中的lru中的时间戳和counter信息。

和lru一样，lfu也会维护一个Pool，只不过Pool中的排序依据是counter，如果counter一致，就按照时间戳排序。

每次需要内存替换的时候，就随机抽取出若干个key，如果Pool不满，或者counter小于Pool中的最小值的话，就将key加入进去，然后选出Pool中counter值最小的那个Key，将其对应的数据从内存中移除。

volatile-lfu：
只从redisDb.expires中，也就是设置了过期时间的key中随机选取对应的key按照lfu规则移除

allkeys-lfu：
从redisDb.dict中，也就是全部key中随机选出对应的key按照lfu规则移除。

5、no-eviction

当内存不足的时候，不做任何操作。这种情形适用于某种特定的场景，比如redis中事先导入存放了非常热点的数据，但是系统偶尔会查询一些冷数据，这种情形就是适合用no-eviction。

Redis内存淘汰策略LRU、LFU详解

Redis内存淘汰原因