Redis内存淘汰原因
Redis是一种内存数据库，redis的容量往往有限，无法存放所有的数据。当内存满了的时候，并且这个时候还需要往Redis中放入新的数据，就需要将Redis中的一部分数据淘汰了，把新的数据放进入。
Redis内存淘汰策略
一个Redis中存储了很多的数据，应该选取哪部分数据进行置换呢？
Redis提供了多种淘汰策略，大概分为以下五类：
1、lru
通过lru，least recently used，也就是最近最久使用算法，也就是淘汰使用时间最旧的数据。
redis中的每个数据的key和value都对应着一个redisObj对象。
typedef struct redisObject {
// 数据类型
unsigned type:4;
// 数据编码方式
unsigned encoding:4;
// 对象最后一次被访问的时间，REDIS_LRU_BITS代表着lru对应的位数
unsigned lru:REDIS_LRU_BITS;
// 引用计数
int refcount;
// 指向实际值的指针
void *ptr;
} robj;
redisObj中有一个属性 lru，lru是一个24位的数字，保存了一个时间戳，代表着一个对象最新被使用的时间。
redisServer中维护了一个lruclock属性来表示当前系统的时间戳，每隔100ms就会调用updateLRUClock()来更新server.lruclock的值。
void updateLRUClock(void) {
//server.unixtime是当前系统的时间，单位是ms
//REDIS_LRU_CLOCK_RESOLUTION是lruclock的精度，默认为1，也就说默认单位是ms，如果为10，代表为s。
//REDIS_LRU_CLOCK_MAX是时间戳的最大值，一般是1<<REDIS_LRU_BITS-1
server.lruclock = (server.unixtime / REDIS_LRU_CLOCK_RESOLUTION) &
REDIS_LRU_CLOCK_MAX;
}
当新建key或者访问key的时候，会将对应的redisObj.lru = server.lruclock。
用server.lruclock的值减去redisObj.lru的值就可以得到对应key的空闲时间了
但是当server.unixtime也就是当前系统时间大于REDIS_LRU_CLOCK_MAX的时候，会将server.lruclock从0开始计数，这就会出现redisObj.lru大于server.lruclock的情况，这种情况下如何算对应的空闲时间呢？
//这里只是粗略的估计空闲时间，因为之前算server.lruclock()和redisObj.lru的时候，已将unixtime()/REDIS_LRU_CLOCK_RESOLUTION了，对应的精度已经损失了。
unsigned long long estimateObjectIdleTime(robj *o) {
unsigned long long lruclock = LRU_CLOCK();
//正常情况，server.lruclock()还未转完一圈
if (lruclock >= o->lru) {
return (lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
} else { server.lruclock()转完一圈了，那么需要将其结果加上对应的REDIS_LRU_CLOCK_MAX的值
return (lruclock + (REDIS_LRU_CLOCK_MAX - o->lru)) *
REDIS_LRU_CLOCK_RESOLUTION;
}
}
LRU工作流程
一般的LRU的做法如下：
1、为每个节点设置一个prev前继节点指针和next后继节点指针，将所有节点通过这两个指针连接成一个链表，链表有着head和tail节点。
2、用一个哈希表将key和对应的节点存放起来，用来快速的找到key对应的节点
3、当通过key访问对应的节点的时候，通过哈希表查询key得到对应的节点。然后通过节点的的prev和next指针将节点从链表中移除，并将节点放到链表的头部中。
4、当新加入key和节点的时候，如果对应的链表已经满了，就将尾部的节点去除，然后将新节点加入到链表的头部。
从上述流程可以看出，基于链表和哈希表的LRU需要设置prev指针、next指针、以及hash表中的key和value的指针，这是一个很大的内存开销。
Redis并没有采用这样的做法，而是采用了随机抽取的做法、
Redis在每次进行内存的替换的时候，会随机抽取出若干个key，默认是5个，然后获取其对应的lru时间信息，淘汰lru最小的那个数据，也就是最久未被使用的数据。
lru升级
1、Redis3.0之后对lru算法进行了升级，Redis中会维护一个Pool，Pool中最大可以容纳16个Key，按照key的空闲时间进行排序，空闲时间就是当前时间和上一次访问时间戳之间的差值，空闲时间越大说明key越长时间没有被访问，应该被淘汰。
2、当每次要淘汰key的时候，会随机抽取若干个key，计算其空闲时间，如果Pool还没有满或者比Pool中的最小空闲时间Key大的话，就将空闲时间小的Key从Pool中移除，将Key加入到Pool中。
3、当要淘汰key的时候，将Pool中的空闲时间最大的key对应的数据移除内存。
其中根据抽取key的数据来源不同，将lru分为了两类：
1、volatile-lru
从设置了过期时间的数据中随机抽取数据淘汰，也就是从redisDb.expires中抽取key。
2、allkeys-lru
从所有数据中随机抽取数据淘汰，也就是从redisDb.dict中抽取key。
如果不知道redisDb.expires和redisDb.dict是什么意思的话，可以看一下我之前写的关于redis中存储模型的文章Redis存储模型详解
不论是3.0之前还是3.0之后，每次抽取的key次数越多，越能体现LRU的特性，但是对应耗费的CPU资源就越大，很多时候计算机系统就是这样，鱼和熊掌不能得兼。
2、ttl
ttl是time to live的简称，也就是生存时间的意思，在redis中体现的就是过期时间。
volatile-ttl
从redisDb.expires也就是拥有过期时间的数据中随机抽取出若干个key，然后找到其中存活时间最短的key，也就是最即将过期的key，将其对应的数据从内存中移除。
3、random
random就是随机的意思，分为两种：
1、volatile-random
从redisDb.expires也就是拥有过期时间的数据中随机选取一个key，将其淘汰。
2、allkeys-random
从redisDb.dict也就是所有数据中随机选取一个key，将其淘汰。
4、lfu
lfu的全称是 leastly frequently used，最近最少使用，也就是挑选出最近使用次数最少的key。
使用次数也是通过redisObject中的lru字段记录的。
我们之前说过lru有24位，其中前16位用于记录最近访问时间time，单位是分钟、后8位用于记录访问次数counter。
增长
你可能会奇怪8位最多只能记录255，这不是在开玩笑吗？其实每次访问不会一定将counter++，而是通过一定的概率来判断是否将counter++。
//counter就是当前key对应的counter
uint8_t LFULogIncr(uint8_t counter) {
if (counter == 255) return 255;
//随机生成一个数字
double r = (double)rand()/RAND_MAX;
//将当前的counter减去一个固定值
double baseval = counter - LFU_INIT_VAL;
if (baseval < 0) baseval = 0;
//server.lfu_log_factor是增长控制因子
double p = 1.0/(baseval*server.lfu_log_factor+1);
//如果随机生成的数小于p，就将counter++
if (r < p) counter++;
return counter;
}
从上述代码看出，增长概率与 server.lfu_log_factor和counter有关，server.lfu_log_factor和counter越大，增加概率越小。
但是所有的key都是共用一个server.lfu_log_factor，如果server_lfu_log_factor改变，所有key都会收到相同的影响。
而counter是每个key都对应着一个值，所以说随着key的不断访问，counter越来越大，增长速率是越来越慢的。
下图是随着factor和访问次数对counter的影响
衰减
当一个key在前一段时间被频繁访问，但是之后慢慢用不到了，对应的counter应该变小，要不然key会一直保存在内存中，无法被移除，降低内存使用率。
所以redis提供了一个衰减机制。
衰减机制 与 key的空闲时间有关， key空闲时间越长，对应的counter就减少的越多。
unsigned long LFUDecrAndReturn(robj *o) {
//将lru左移8位，得到对应的时间戳
unsigned long ldt = o->lru >> 8;
//将lru & 0000 0000 0000 0000 1111 得到对应的counter
unsigned long counter = o->lru & 255;
//算出对应的空闲周期数。
//server.lfu_decay_time是衰减因子，可以在配置文件中修改，默认是10，单位是分钟
//LFUTimeElapsed(ldt)就是算出对应的空闲时间，然后将空闲时间除去衰减因子，得到衰减周期 num_periods
unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
//将counter减去对应的衰减周期
if (num_periods)
counter = (num_periods > counter) ? 0 : counter - num_periods;
return counter;
}
从上述代码看出，如果一个Key在N分钟没有被访问，当衰减检查的时候，就会将其counter - N。
lfu工作过程：
当访问对应的key的时候，会更新其redisObj中的lru中的时间戳和counter信息。
和lru一样，lfu也会维护一个Pool，只不过Pool中的排序依据是counter，如果counter一致，就按照时间戳排序。
每次需要内存替换的时候，就随机抽取出若干个key，如果Pool不满，或者counter小于Pool中的最小值的话，就将key加入进去，然后选出Pool中counter值最小的那个Key，将其对应的数据从内存中移除。
volatile-lfu：
只从redisDb.expires中，也就是设置了过期时间的key中随机选取对应的key按照lfu规则移除
allkeys-lfu：
从redisDb.dict中，也就是全部key中随机选出对应的key按照lfu规则移除。
5、no-eviction
当内存不足的时候，不做任何操作。这种情形适用于某种特定的场景，比如redis中事先导入存放了非常热点的数据，但是系统偶尔会查询一些冷数据，这种情形就是适合用no-eviction。