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