java基础|Redis-LFU与LRU内部实现原理源码分析

1、LRU模式有效控制内存的大小,将冷数据从内存中淘汰出去,在Redis里引入一个新的淘汰形式LFU1)LFU全称是Least Frequently Used 表示按最近的访问频率进行淘汰,更加准确的判断一个key别访问的热度
【java基础|Redis-LFU与LRU内部实现原理源码分析】2、Redis对象的热度
Redis中所有对象结构头中都有一个24bit字段,这个字段用来记录对象的热度

// redis 的对象头
typedef struct redisObject {
unsigned type:4; // 对象类型如 zset/set/hash 等等
unsigned encoding:4; // 对象编码如 ziplist/intset/skiplist 等等
unsigned lru:24; // 对象的「热度」
int refcount; // 引用计数
void *ptr; // 对象的 body
} robj;

3、LRU模式
1)lru字段存储的是Redis时钟server.lruclock,默认是Unix时间窜对2^24取模的结果,当某个 key 被访问一次,它的对象头的 lru 字段值就会被更新为server.lruclock。
2)Redis的时钟值是每毫米奥更新一次,可以在定时任务serverCron里设置
3)如果server.lruclock没有折返 (对 2^24 取模),它就是一直递增的,这意味着对象的 LRU 字段不会超过server.lruclock的值。如果超过了,说明server.lruclock折返了。通过这个逻辑就可以精准计算出对象多长时间没有被访问——对象的空闲时间。
4)计算对象空闲时间
unsigned long long estimateObjectIdleTime(robj *o) {
unsigned long long lruclock = LRU_CLOCK(); // 获取 redis 时钟,也就是 server.lruclock 的值
if (lruclock >= o->lru) {
// 正常递增
return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION; // LRU_CLOCK_RESOLUTION 默认是 1000
} else {
// 折返了
return (lruclock + (LRU_CLOCK_MAX - o->lru)) * // LRU_CLOCK_MAX 是 2^24-1
LRU_CLOCK_RESOLUTION;
}
}



4、LFU模式
1)在该模式下,lru字段用来存储来个值即16个bit的ldt(last decrement time)和8bit的logc(logistic counter)。logc用来存储访问频次,最大能整数值为255,存储频次肯定不够,所有这8个bit只是用来存储频次的对数值,而且该值还随时间在衰减,如果该值比较小,那么很容易被回收。为了确保新创建的对象不被回收,新对象的8个bit会初始化为一个大雨零的值,默认是5
2)ldt用来存储上一次logc的更新时间,它取得是分钟时间戳对2^16进行取模,
// nowInMinutes
// server.unixtime 为 redis 缓存的系统时间戳
unsigned long LFUGetTimeInMinutes(void) {
return (server.unixtime/60) & 65535;
}
// idle_in_minutes
unsigned long LFUTimeElapsed(unsigned long ldt) {
unsigned long now = LFUGetTimeInMinutes();
if (now >= ldt) return now-ldt; // 正常比较
return 65535-ldt+now; // 折返比较
}

3)ldt的值和LRU模式的lru字段值不同的是ldt不是在对象被访问时更新,他在Redis的淘汰逻辑进行时进行更新,淘汰逻辑只会是在内存达到maxmemory设置时才促发。没次淘汰的策略是采用随机策略,挑选若干个key,更新这个key的热度,淘汰掉热度最低的key。
ldt更新的同时会衰减logc的值,衰减的算法是将现有的logc值减去对象的空闲时间厨艺一个衰减系数,默认的衰减西戎lfu_decay_time是1,如果这个值大于1,就会衰减比较慢,等于0就是不衰减。
// 衰减 logc
unsigned long LFUDecrAndReturn(robj *o) {
unsigned long ldt = o->lru >> 8; // 前 16bit
unsigned long counter = o->lru & 255; // 后 8bit 为 logc
// num_periods 为即将衰减的数量
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;
}、

4)logc的更新和LRU模式的lru字段一样,都会在key没次被访问的时候更新,只不过他的更新不是简单的+1,而是采用概率发进行递增,因为logc存储的是访问计数的对数值,不能直接+1
/* Logarithmically increment a counter. The greater is the current counter value
* the less likely is that it gets really implemented. Saturate it at 255. */
// 对数递增计数值
uint8_t LFULogIncr(uint8_t counter) {
if (counter == 255) return 255; // 到最大值了,不能在增加了
double baseval = counter - LFU_INIT_VAL; // 减去新对象初始化的基数值 (LFU_INIT_VAL 默认是 5)
// baseval 如果小于零,说明这个对象快不行了,不过本次 incr 将会延长它的寿命
if (baseval < 0) baseval = 0;
// 当前计数越大,想要 +1 就越困难
// lfu_log_factor 为困难系数,默认是 10
// 当 baseval 特别大时,最大是 (255-5),p 值会非常小,很难会走到 counter++ 这一步
// p 就是 counter 通往 [+1] 权力的门缝,baseval 越大,这个门缝越窄,通过就越艰难
double p = 1.0/(baseval*server.lfu_log_factor+1);
// 开始随机看看能不能从门缝挤进去
double r = (double)rand()/RAND_MAX; // 0 < r < 1
if (r < p) counter++;
return counter;
}

5、Redis缓冲时间戳
Redis不能没次需要系统时间时,都调用一次系统获取时间,因为这样的调用对于单线程的Redis来讲,是比较费时间的,Redis是承受不起,所有它需要对时间进行缓冲,获取时间就直接从缓冲中拿
6、Redis使用原子操作获取lruclock原因
unsigned int LRU_CLOCK(void) {
unsigned int lruclock;
if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
// 这里原子操作,通常会走这里,我们只需要注意这里
atomicGet(server.lruclock,lruclock);
} else {
// 直接通过系统调用获取时间戳,hz 配置的太低 (一般不会这么干),lruclock 更新不及时,需要实时获取系统时间戳
lruclock = getLRUClock();
}
return lruclock;
}
因为 Redis 实际上并不是单线程,它背后还有几个异步线程也在默默工作。这几个线程也要访问 Redis 时钟,所以 lruclock 字段是需要支持多线程读写的。使用 atomic 读写能保证多线程 lruclock 数据的一致性。
7、打开LFU模式
1)Redis4.0对淘汰策略配置参数maxmemory-policy增加了2个选项,分别是volatile-lfu和allkeys-lfu,根据字面含义都可以看出,前者是对带过期时间key进行lfu淘汰,后者的参数对所有的key进行lfu淘汰算法
> config set maxmemory-policy allkeys-lfu
OK
> set codehole yeahyeahyeah
OK
// 获取计数值,初始化为 LFU_INIT_VAL=5
> object freq codehole
(integer) 5
> get codehole// 访问一次
"yeahyeahyeah"
// 计数值增加了
> object freq codehole//get lfu计数值
(integer) 6

    推荐阅读