Redis内存回收

1. 过期策略

1.1 立即过期(主动淘汰)

每个设置过期时间的key都需要创建一个定时器，到过期时间就会立即清除。该策略可以立即清除过期的数据，对内存很友好，但是会占用大量CPU资源去处理过期的数据，从而影响缓存的响应时间和吞吐量。

1.2 惰性过期(被动淘汰)

只有当访问一个key时，才会判断该key是否已经过期，过期则清除。该策略可以最大化的节省CPU资源，却对内存非常不友好。极端情况下可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存。

第一种情况，所有的查询都会调用expireIfNeeded判断是否过期：

expireIfNeeded(redisDb *db, robj *key)

第二种情况，每次写入key时，发现内存不够，吊桶activeExpireCycle释放一部分内存。

activeExpireCycle(int type)

1.3 定期过期

每隔一定的时间，会扫描一定数量的数据库的expire字典中一定数量的key，并清除其中已经过期的key。该策略是前两者的一个折中方案，通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以再不同情况下使得Cpu和内存资源达到最优的平衡效果。

typedef struct redisDb{
    dict *dict;
    dict *expires;
    dict *blocking_keys;
    dict *ready_keys;
    dict *watched_keys;
    int id;
    long long avg_ttl;
    unsigned long expires_cursor;
    list *defrag_later;
} redisDb;

总结: Redis中同时使用了惰性过期和定期过期两种过期策略，并不是实时的清除过期的key。

2. 淘汰策略

Redis的内存淘汰策略，是指当内存使用达到最大内存极限时，需要使用淘汰算法来决定清理掉哪些数据，以保证新数据的存入。

2.1 最大内存设置

Redis.conf参数配置 #maxmemory

如果不设置maxmemory或者设置为0，32位系统最多使用3GB内存，64位系统不限制内存。

动态修改（先get一下）：

redis> config set maxmemory 2GB

2.2 淘汰策略

https://redis.io/docs/reference/eviction/

redis.conf #maxmemory-policy noeviction

# volatile-lru -> Evict using approximated LRU, only keys with an expire set
# allkeys-lru  -> Evict any key using approximated LRU
# vloatile-lfu -> Evict using approximated LFU, only keys with an expire set
# allkeys-lfu  -> Evict any key using approximated LFU
# volatile-random -> Remove a random key having an expire set
# allkeys-random  -> Remove a random key, any key
# volatile-ttl -> Remove the key with the nearest expire time(minor TTL)

（1）先从后缀的算法名来看：

LRU，Least Recently Used：最近最少使用。判断最近被使用的时间，目前最远的数据有限被淘汰。

LFU，Least Frequently Used：最不常用，按照使用频率删除，4.0版本新增。

Random 随机删除。

（2）从前缀针对的对象来分：volatile是针对设置了ttl的key，allkeys是针对所有key

策略	含义
volatile-lru	根据LRU算法删除设置了超时属性(expire)的键，直到腾出足够内存为止。如果没有可删除的对象，回退到noeviction策略
allkeys-lru	根据LRU算法删除键，不管数据有没有设置超时属性，知道腾出足够的内存为止
volatile-lfu	在带有过期时间的键中选择最不常用的
allkeys-lfu	在所有键中选择最不常用的，不管数据有没有设置超时属性
volatile-random	在带有过期时间的键中随机选择
allkeys-random	随机删除所有键，知道腾出足够内存为止
volatile-ttl	根据键值对象的ttl属性，删除最近将要过期数据。如果没有，回退到noevitcion策略
noeviction	默认策略，不会删除任何数据，拒绝所有写入操作并返回客户端错误信息(error)OOM command not allowed when used memory, 此时Redis只响应读操作

如果没有设置ttl或者没有符合前提条件的key被淘汰，那么volatile-lru，volatile-random，volatile-ttl相当于noeviction（不做内存回收）。动态修改淘汰策略（先get一下）

redis> config set maxmemory-policy volatile-lru

建议使用volatile-lru，在保证正常服务的情况下，有限删除最近最少使用的key。

2.3 LRU淘汰原理

LRU是一个很常见的算法，比如InnoDB的Buffer Pool也用到了LRU。传统LRU：通过链表+HashMap实现，设置链表长度，如果新增或者被访问，就移动到头节点，超过链表长度，末尾的节点被删除。

如果基于传统LRU算法实现redis LRU的话，需要额外的数据结构存储，消耗内存。所以Redis LRU对传统的LRU算法进行了改良，通过随机采样来调整算法的精度。如果淘汰策略是LRU，则根据篇日志的采样值maxmemory_samples（默认是5个），随机从数据库中选择m个key，淘汰其中热度最低的key对应的缓存数据。所以采样参数m配置的数值越大，就越能精确的查找到待淘汰的缓存数据，但是也消耗更多的CPU计算，执行效率降低。

Redis中所有对象结构都有一个lru字段，且使用了unsigned的低24位，这个字段用来记录对象的热度。对象被创建时会记录lru值。在被访问的时候也会更新lru的值。但并不是获取系统当前的时间戳，而是设置位全局变量server.lruclock的值。

typedef struct redisObject{
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

Redis中有个定时处理的函数serverCron，默认每100毫秒调用函数updateCachedTime更新一次全局变量的server.lruclock的值，它记录的是当前unix时间戳。

void updateCachedTime(int update_daylight_info){
    server.ustime = ustime();
    server.mstime = server.ustime / 1000;
    server.unixtime = server.mstime / 1000;
    if(update_daylight_info){
        struct tm tm;
        time_t ut = server.unixtime;
        localtime_r(&ut,&tm);
        server.daylight_active = tm.tm_isdst;
    }
}

问题：为什么不获取精确的时间而是放在全局变量中？不会有延迟的问题吗？

这样函数查询key调用lookupKey中更新数据的lru热度值时，就不用换每次调用系统函数time，可以提高执行效率。

当对象里面已经有了LRU字段的值，就可以评估对象的热度了。

unsigned long long estimeteObjectIdleTime(robj *o){
    unsigned long long lrulock = LRU_CLOCK();
    if(lruclock >= o->lru){
        return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
    } else {
        return (lruclock + (LRU_CLOCK_MAX - o->lru)) * LRU_CLOCK_RESOLUTION;
    }
}

函数estimateObjectIdleTime评估指定对象的lru热度，方法就是对象的lru值和全局的server.lruclock的差值越大（越久没有得到更新）,该对象热度越低。server.lruclock 只有24位，按秒位单位来标识才能存储194天。但超过24bit能表示的最大时间的时候，他会从头开始计算。在这种情况下，可能会出现对象的lru大于server.lruclocl的情况，如果这种情况出现那么就两个相加而不是相减来求最久的key。

Redis LRU算法在sample为10的情况下，已经能接近传统LRU算法了。

2.4 LFU

typedef struct redisObject{
    unsigned type:4;
    unsigned enncoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

当这24bits 用作LFU时，其被分为两部分：高16位用来记录访问时间（单位为分钟，Idt-last decrement time）低8位用来记录访问频率，简称counter（logc-logistic counter）

counter是用基于概率的对数计数器来实现的，8位可以标识百万次的访问频率。对象被读写的时候，lfu的值会被更新。

void updateLFU(robj *val){
    unsigned long counter = LFUDecrAndReturn(val);
    counter = LFULogIncr(counter);
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

当然这里并不是访问一次，技术就加1。增长的速率由一个参数决定，lfu-log-factor越大，counter增长的越慢，redis.conf配置文件：

# lfu-log-factor 10

如果一段时间热点高，就一直保持这个热度，肯定也是不行的，体现不了整体频率。所以，没有被访问的时候，计数器还要递减。减少的值由衰减因子lfu-decay-time(分钟)来控制，如果值是1的话，N分钟没有访问，计数器就要减少N。lfu-decay-time越大，衰减越慢。Redis.conf配置文件

# lfu-decay-time 1