Redis深度历险-淘汰策略

Redis是内存型数据库，在系统中如果占用内存超过物理内存就会出现磁盘swap，这种操作就会导致性能急剧下降，所以才会出现淘汰策略

Redis配置

Redis允许用户配置使用的最大内存和超过最大内存时的处理策略

maxmemory：用于设置最大使用的内存

maxmemory-policy：超过最大内存时的处理策略

• noeviction：禁止写入操作、允许读取和删除操作，这是默认配置
• volatile-lru：淘汰设置了过期时间的key，最少使用的key会被释放掉
• volatile-lfu：淘汰设置了过期时间的key，某段时间内使用频率最少的key会被释放掉
• volatile-ttl：淘汰设置了过期时间的key，剩余寿命ttl最少的key会被释放掉
• volatile-random：淘汰设置了过期时间中的随机key
• allkeys-lru：与volatile-lru类似，只是面向所有key
• allkeys-lfu：与volatile-lfu类似，只是面向所有key
• allkeys-random：与volatile-random类似，只是面向所有的key

Redis实现

Redis对象结构体

typedef struct redisObject {
    //数据类型，redis提供的5种类型
    unsigned type:4;
    //这种类型的底层实现方式，比如有序集合底层会使用链表或者压缩列表实现
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    //元素的引用计数
    int refcount;
    //元素的数据
    void *ptr;
} robj;

这里主要需要关注的是lru字段，共24位

• 如果使用的是lru相关算法，则记录的是最后访问时间
• 如果使用的是lfu相关算法，则高16位记录的是上次访问时间（单位为分）、低8位记录的是某段时间的使用频次

lru算法

Redis实现的是一种类似LRU的算法，主要是完全按照LRU的实现需要对现有数据结构做改造同时会消耗很多内存

1. 为每个key添加一个24bit的字段，用于存储最后访问的时间戳
2. 随机采样出N个key，淘汰掉最旧的key
3. 将随机采样剩下的key放入到淘汰池中（一个数组）
4. 淘汰后内存依旧超出maxmemory，随机采样出N个key与淘汰池数据融合，淘汰掉最旧的key
5. 继续3、4步骤，直到空间小于maxmemory

Redis的淘汰过程是一个阻塞的过程，直到清理出足够的空间；如果内存达到maxmemory的限制并且客户端还在不停的写入，可能会导致反复出发清理策略，导致请求延迟
淘汰池的大小由maxmemory-samples配置来控制，设置为5-10之间即可

lfu算法

配置

• lfu-log-factor：设置计数器counter的增长速度，越小增长越快
• lfu-decay-time：设置计数器counter的减少速度，以分钟为单位，越小下降越快

lfu计数减少算法

void updateLFU(robj *val) {
    //将访问计数取出来
    unsigned long counter = LFUDecrAndReturn(val);
    //计数增长
    counter = LFULogIncr(counter);
    //将访问计数设置到redisobj中
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

unsigned long LFUDecrAndReturn(robj *o) {
    //分别取出上一次的访问时间以及访问计数
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    //每超过lfu_decay_time的时间counter计数就需要减少一
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

//以分钟为单位计算出上次访问到现在的时间
unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now-ldt;
    return 65535-ldt+now;
}
//以分钟为单位， 再对65535取模
unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;
}

随着时间的推移lfu计数应该是会降低的，但是直到下次更新lfu时才会重新计算

lfu计数增长算法

uint8_t LFULogIncr(uint8_t counter) {
    //最大的counter访问计数就是255（8）位
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

Redis内部使用了一种随机算法1.0/(baseval*server.lfu_log_factor+1)，不过大体上的规律是随着访问次数的增大增长速率降低

新生key

lfu算法会有一个问题就是新生key可能很快被淘汰掉，所以会特意设置一个访问时间

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;

    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        //新生的时候会设置一个默认值（5）
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}