Redis-内存淘汰算法

Redis可以存多少数据

32位的操作系统默认3G

谁现在用32位啊?我们说64位的 一般来讲是不设上限的

但是我们也可以主动配置maxmemory, maxmemory支持各单位:
maxmemory 1024 (默认字节)
maxmemory 1024KB
maxmemory 1024MB
maxmemory 1204GB
当Redis存储超过这个配置值，则触发Redis内存淘汰。

实际上，每次进行读写的时候，都会去检查是否需要释放内存，如果需要则会触发。
 

那怎么淘汰呢

分两大类

第一类

noeviction,默认就是这种策略，此时如果内存达到maxmemory, 则写入操作会失败，但
不会淘汰已有数据。

第二类

多种淘汰策略，主要支持LRU, LFU, RANDOM, TTL这几个方式:
lru:根据LRU (Least recently used， 最近最少使用)算法尝试回收最长时间未使用的。              

Ifu:根据LFU (Least Frequently Use) 驱逐最不常用的键，Ifu是在4.0引入的

random: 回收随机的键使得新添加的数据有空间存放。

ttl:回收在过期集合的键，并且优先回收存活时间(TTL) 较短的键，使得新添加的数据有空间存放。

这四种策略，可以选择时volatile, 也就是设置了过期时间的Key,或者是alkeys,即全部的Key,所以一共有8种淘汰方式。

LRU算法

最近最久未使用，即记录每个Key的最近访问时间，维护一一个访问时间的数据

如果为所有数据维护一个顺序列表，实际就是做一个双向链表，但是如果Redis数据稍微多些，这个链表就是巨大的成本，对于Redis而言，内存是最宝贵的，所以Redis选择了近似LRU算法。

近似的LRU算法

在LRU模式，redisObject对象 中Iru字段存储的是key被访问时Redis的时钟server.lruclock,当key被访问的时候,
Redis会更新这个key的redisObject的Iru字段。注意，Redis为了保证核心单线程服务性能，缓存了Unix操作系统时钟，默认每100毫秒更新一次，缓存的值是Unix时间戳取模2^24
近似LRU算法在现有数据结构的基础上采用随机采样的方式来淘汰元素，当内存不足时，就执行一次近似LRU算法。
具体步骤是随机采样n个key,这个采样个数默认为5,然后根据时间戳淘汰掉最旧的那个key,如果淘汰后内存还是不足，就继续随机采样来淘汰。

采样范围

采样范围是什么呢? Redis可以选择范围策略，有两种: 1.alkeys, 所有key中随机采样。2.volatile从有过期时间的key随机采样。分别对应alkeys-lru, volatitle-lru。

优化-淘汰池

Redis3.0对近似LRU算法进行了一些优化。
新算法会维护一个大小为16的候选池，池中的数据根据访问时间进行排序。第-次随机选取的key都会放入池中,
然后淘汰掉最久未访问的，比如第一次选了5个，淘汰了1个，剩下4个继续留在池子里。
随后每次随机选取的key只有活性比池子里活性最小的key还小时才会放入池中，当池子装满了，如果有新的key需要放入，则将池中活性最大的key移除。
 

有一个活性堆 最上面永远是活性最小的 如果比它还小才能加入堆 但是如果堆已经满了 那就要把最大的活性的弹出(既然我们要让结果贴合 淘汰最旧的 那就不会弹出活性最大的拉) 合理 里面只存最小活性的 然后每次要淘汰就淘汰活性最小的

原本的近似LRU算法 全局采样 然后从里面拿出一个活性最低的 来近似作为淘汰了全局活性最低的 这到底哪合理了

现在的算法比之前的贴近反正

LFU算法

LFU淘汰算法，即Least Frequently Used,最不频繁(断句)淘汰算法，顾名思义，优先淘汰活跃最低，使用频率最低的。
 

LRU是淘汰最久没使用的 我个人觉得LFU更合理 我肯定要淘汰最不常用的反正

如果使用LRU，那么redisObject中lru字段， 就是用来存储最近访问时间的，这个字段长度是LRU_ _BITS, 这个值一直都是24位。
如果是LFU,因为LRU、LFU是不会同时开启的，所以两者可以说是互斥，基于这个情况，加上节约内存的考虑,Redis在LFU策略下复用Iru字段,还是用它来表示LFU的信息，不过将24拆解，高16bit存储ldt(L ast DecrementTime),低8bit存储logc(Logistic Counter)
 

高的16位保存了.上次访问时间戳，因为少了8位，所以LFU下时间精度是1分钟，不然用秒的话2^16次方只能表示65536秒(因为这次的时间只是辅助作用喵)，后8位存储的是一个访问计数。
一个Key是否活跃，就是这两个字段综合决定的。
如果上一次访问时间很久，那么访问计数就会衰减，当然，最后起作用的就是访问计数。

当某个KEY被访问到的时候
 

第一步,计算次数衰减
因为无论是多快，相对于上次访问，-定有时间间隔，根据间隔，来计算你应该减少的次数。使用的函数就是LFUDecrAndReturn。
 

第二步，一定概率增加访问计数
次数不足5次，那一定会增加，如果大于5次小于255次，会一定概率加1，原来的次数越大，越困难。除了原来的次数影响之外，还有一个Ifu-log-factor参数可以被设置的。也就是说，可以通过lfu-log-factor参 数来调节难度，这个越大，难度也越大，如果为0，那么每次必然+1,很快就能255， 255就是最大值,默认是10，需要1M流量才能达到最大值。

第三步,更新
当前时间更新到高16位，次数更新到低8位。