每次看到redis的内存淘汰策略的时候，都只会想到8种配置参数：noenviction、allkeys-lru、volatile-lru、allkeys-random、volatile-random、volatile-ttl、volatile-lfu、allkeys-lfu。
Redis的LRU算法不是一个严格的LRU实现，这意味着Redis不能选择最久未被访问的那些键。Redis会尝试执行一个近似LRU的算法，通过采样一小部分键，然后再采样键中回收最适合的那个。
从Redis3.0开始，算法被改进为维护一个回收候选键池。这改善了算法的性能，使得更接近于真实的LRU算法的行为。Redis的LRU算法有一点很重要，你可以调整算法的精度，通过改变每次回收时检查的采样数量。maxmemory-samples 5
Redis没有使用真实的LRU实现的原因，是因为这会消耗更多的内存。然而，近似值对使用Redis的应用来说基本上也是等价的。下面的图形对比，为Redis使用的LRU近似值和真实LRU之间的比较。
第1个theoretical 是理论上的LRU，最上层的浅灰色是被回收的对象，灰色带是没有被回收的对象，绿色带是被添加的对象。Approx 代表近似LRU，从图2可以看出Redis3.0版本 10个采样随机大小已经非常接近理论LRU了。图3与图4相比，同样在5个采样随机大小的不同版本中Redis LRU的表现是不一样的。图2与图4得知在采样个数越多得到的效果也就越佳，不过会消耗额外的CPU。
redis实现LRU的算法
redis没有像mysql一样使用双向链表实现一个LRU算法。Redis整体上是一个大的dict，如果实现一个双向链表需要额外的存储存放 next 和 prev 指针，需要16个字节，并且额外需要一个list结构体去存储该双向链表的头尾节点信息。基于内存考虑，没有选择双向链表。redis实现LRU是采用一个全局时钟，这个时钟供每个object更新自己object的时间。其中存储了服务器自启动之后的lru时钟。
#define LRU_BITS 24
typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; //24bit int refcount; void *ptr; } robj;
这个lru:LRU_BITS 用来保存最后一次被访问的时间戳（server.lruclock）。最大可以表示的数字为2^24-1 毫秒。当一个key被访问的时候这个lru就会更新，移动到lru的头部，避免从lur中淘汰。
redis定时器
Redis 中有一个全局的定时器函数 serverCron，用于刷新服务器的 LRU 时钟
int serverCron(...) {
...
server.lruclock = getLRUClock();
...
}
其中，server.lruclock 代表服务器的 LRU 时钟，这个时钟的刷新频率由 server.hz 决定，即每秒钟会调用 server.hz （默认值为 10）次 serverCron 函数。那么，服务器每 1 / server.hz （100ms）秒就会调用一次定时器函数 serverCron。redis LRU的时钟
Redis 对象的 LRU 时钟
#define LRU_CLOCK_RESOLUTION 1000
每个 Redis 对象的 LRU 时钟的计算方式由宏 LRU_CLOCK 给出，实现如下：
#define LRU_CLOCK() ((1000/server.hz <= LRU_CLOCK_RESOLUTION) ? server.lruclock : getLRUClock())
为了避免重复计算，减少调用系统函数gettimeofday()的时间，可以用最近一次计算得到的LRU时钟作为近似值，即server.lruclock。
Redis 对象的LRU时钟更新有2个地方
1 对象创建的时候
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;
o->lru = LRU_CLOCK();
return o;
}
2 对象被使用的时候。
robj *lookupKey(redisDb *db, robj *key, int flags) {
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
...
val->lru = LRU_CLOCK(); //这里
...
return val;
} else {
return NULL;
}
}
空闲时间的计算
unsigned long long estimateObjectIdleTime(robj *o) {
unsigned long long lruclock = LRU_CLOCK();
if (lruclock >= o->lru) {
return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;//当前时间-减去最后一次访问时间的时间戳 就是空闲时间
} else {
return (lruclock + (LRU_CLOCK_MAX - o->lru)) * LRU_CLOCK_RESOLUTION;
}
}
LRU 算法的核心，首先从目标字典中随机采样出 server.maxmemory_samples 个键，缓存在 samples 数组中，然后一个一个取出来，并且和回收池中的已有的键对比空闲时间，从而更新回收池。更新的过程首先，利用遍历找到每个键的实际插入位置 k ，然后，总共涉及四种情况如下：
a) 回收池已满，且当前插入的元素的空闲时间最小，则不作任何操作；
b) 回收池未满，且将要插入的位置 k 原本没有键，则可直接执行插入操作；
c) 回收池未满，且将要插入的位置 k 原本已经有键，则将当前第 k 个以后的元素往后挪一个位置，然后执行插入操作；
d) 回收池已满，则将当前第 k 个以前的元素往前挪一个位置，然后执行插入操作；
redis的LRU内存回收影响的参数
- maxmemory 20GB
- maxmemory-policy allkeys-lru/volatile-lru
- maxmemory-samples 5
Redis的LFU算法
全称是 Least Frequently Used，表示按最近的访问频率进行淘汰，它比 LRU 更加精准地表示了一个 key 被访问的热度。
在 LFU 模式下，lru 字段 24 个 bit 用来存储两个值，分别是 ldt(last decrement time) 和 logc(logistic counter)
logc 是 8bit 大小，用来存储访问频次，因为 8bit 能表示的最大整数值为 255，存储频次肯定远远不够，所以这 8bit 存储的是频次的对数值，并且这个值还会随时间衰减。如果它的值比较小，那么就很容易被回收。为了确保新创建的对象不被回收，新对象的这 8bit 会初始化为一个大于零的值，默认是 LFU_INIT_VAL=5。
ldt 是 16bit 大小，用来存储上一次 logc 的更新时间，取的是分钟时间戳对 2^16 进行取模，大约每隔 45 天就会折返。同 LRU 模式一样，我们也可以使用这个逻辑计算出对象的空闲时间，只不过精度是分钟级别的。
ldt 的值和 LRU 模式的 lru 字段不一样的是， ldt 不是在对象被访问时更新的。它在 Redis 的淘汰逻辑进行时进行更新，淘汰逻辑只会在内存达到 maxmemory 的设置时才会触发，在每一个指令的执行之前都会触发。
每次淘汰都是采用随机策略，随机挑选若干个 key，更新这个 key 的「热度」，淘汰掉「热度」最低的。
LFU的配置参数
lfu-log-factor 10 counter的缩减因子 lfu-decay-time 1 计数器应该被衰减的分钟数
总结：LRU最近最少使用算法，redis使用lru记录一个时间戳，每次创建和访问的时候都会更新这个时间戳，当随机采样的key被采样到长度为16的evictionPool（回收池）里，会按空闲时间排序。
LFU使用频率最少的算法，lfu使用lru的高16位存储上一次logc的更新时间，取的是分钟时间戳。后8位用来存储访问的频次的对数值（a的x次方是N，x为对数）。每过一些时间key的计数器将会缩减。
附：查看热点key的方法
1 object freq key
2 redis-cli --hotkeys