Redis 系列内存淘汰

当 Redis 内存超出物理内存限制时，内存的数据会开始和磁盘产生频繁的交换 (swap)。交换会让 Redis 的性能急剧下降。

内存淘汰策略:

noeviction：当内存使用超过配置的时候会返回错误，不会驱逐任何键。
allkeys-lru：首先通过 LRU 算法驱逐最久没有使用的键。
volatile-lru：首先从设置了过期时间的键集合中驱逐最久没有使用的键。
allkeys-random：从所有 key 随机删除。
volatile-random：从过期键的集合中随机驱逐。
volatile-ttl：从配置了过期时间的键中驱逐马上就要过期的键。
volatile-lfu：从所有配置了过期时间的键中驱逐使用频率最少的键。
allkeys-lfu：从所有键中驱逐使用频率最少的键。

LRU 算法

标准 LRU 算法除了需要 key/value 字典外，还需要附加一个链表，链表中的元素按照一定的顺序进行排列。当空间满的时候，会踢掉链表尾部的元素。当字典的某个元素被访问时，它在链表中的位置会被移动到表头。所以链表的元素排列顺序就是元素最近被访问的时间顺序。

位于链表尾部的元素就是不被重用的元素，所以会被踢掉。位于表头的元素就是最近刚刚被人用过的元素，所以暂时不会被踢。

OrderedDict(双向链表+字典) 可实现一个简单的 LRU 算法

近似 LRU 算法

Redis 使用的是一种近似 LRU 算法，它跟 LRU 算法还不太一样。之所以不使用 LRU 算法，是因为需要消耗大量的额外的内存，需要对现有的数据结构进行较大的改造。近似 LRU 算法则很简单，在现有数据结构的基础上使用随机采样法来淘汰元素，能达到和 LRU 算法非常近似的效果。

Redis 为实现近似 LRU 算法，它给每个 key 增加了一个额外的小字段，这个字段的长度是 24 位，也就是最后一次被访问的时间戳。Redis维护了一个 24 位时钟，可以简单理解为当前系统的时间戳，每隔一定时间会更新这个时钟。比如现在要进行 LRU，那么首先拿到当前的全局时钟，然后再找到 key 内部时钟与全局时钟距离时间最久的（差最大）进行淘汰，这里值得注意的是全局时钟只有 24 位，按秒为单位来表示才能存储 194 天，所以可能会出现 key 的时钟大于全局时钟的情况，如果这种情况出现那么就两个相加而不是相减来求最久的 key。

LRU 的处理方式只有懒惰处理。当 Redis 执行写操作时，发现内存超出 maxmemory，就会执行一次 LRU 淘汰算法。LRU 并不维护队列，只是根据配置的策略要么从所有的 key 中随机选择 N 个（N 可以配置）要么从所有的设置了过期时间的 key 中选出 N 个键，然后再从这 N 个键中选出最久没有使用的一个 key 进行淘汰。

为什么要使用近似 LRU？

性能问题，由于近似 LRU 算法只是最多随机采样 N 个 key 并对其进行排序，如果精准需要对所有 key 进行排序，这样近似 LRU 性能更高。
内存占用问题，redis 对内存要求很高，会尽量降低内存使用率，如果是抽样排序可以有效降低内存的占用。
实际效果基本相等，如果请求符合长尾法则，那么真实LRU与Redis LRU之间表现基本无差异。
在近似情况下提供可自配置的取样率来提升精准度，例如通过 CONFIG SET maxmemory-samples <count> 指令可以设置取样数，取样数越高越精准，如果你的CPU和内存有足够，可以提高取样数看命中率来探测最佳的采样比例。

LFU 算法

LFU 是在 Redis4.0 后出现的，LRU 的最近最少使用实际上并不精确，考虑下面的情况，如果某个 key 距离最近一次更新的时间最久，但实际上使用频率更频繁，所以合理的淘汰策略应该是此 key 不应该被优先淘汰。LFU 就是为应对这种情况而生的。

LFU 把原来的 key 对象的内部时钟的 24 位分成两部分，前 16 位还代表时钟，后 8 位代表一个计数器。16 位的情况下如果还按照秒为单位就会导致不够用，所以一般这里以分钟为单位。而后8位表示当前key对象的访问频率，8位只能代表255，但是redis并没有采用线性上升的方式，而是通过一个复杂的公式，通过配置如下两个参数来调整数据的递增速度。

lfu-log-factor 可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。
lfu-decay-time 是一个以分钟为单位的数值，可以调整counter的减少速度。

降低LFUDecrAndReturn：

先从高16位获取最近的变更时间 ldt 以及低 8 位的计数器 counter 值
计算当前时间 now 与 ldt 的差值（now-ldt），当 ldt 大于 now 时，那说明是过了一个周期，按照65535-ldt+now计算（16位一个周期最大65535）
使用第2步计算的差值除以lfu_decay_time，即 LFUTimeElapsed(ldt) / server.lfu_decay_time，已过去 n 个 lfu_decay_time，则将counter 减少 n。

增长LFULogIncr：

获取0-1的随机数r
计算0-1之间的控制因子p，它的计算逻辑如下:

//LFU_INIT_VAL默认为5
baseval = counter - LFU_INIT_VAL;
//计算控制因子
p = 1.0/(baseval*lfu_log_factor+1);

如果r小于p，counter增长1

p 取决于当前 counter 值与 lfu_log_factor 因子，counter值与lfu_log_factor因子越大，p越小，r小于p的概率也越小，counter增长的概率也就越小。

新生KEY策略: 另外一个问题是，当创建新对象的时候，对象的counter如果为0，很容易就会被淘汰掉，还需要为新生key设置一个初始counter。counter会被初始化为LFU_INIT_VAL，默认5。

参考文档

彻底弄懂Redis的内存淘汰策略

开启 redis 探索新篇章

LRU 算法

近似 LRU 算法

LFU 算法

参考文档

CATALOG

FEATURED TAGS

FRIENDS