Redis-内存淘汰算法

淡淡的烟草味﹌ 2023-10-14 18:56 29阅读 0赞

## 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位。