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的实现需要对现有数据结构做改造同时会消耗很多内存
- 为每个
key添加一个24bit的字段，用于存储最后访问的时间戳 - 随机采样出N个
key，淘汰掉最旧的key - 将随机采样剩下的
key放入到淘汰池中（一个数组） - 淘汰后内存依旧超出
maxmemory，随机采样出N个key与淘汰池数据融合，淘汰掉最旧的key - 继续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;
}
