Redis 的内存淘汰算法和原理

Redis 内存的使用率到达了 maxmemory 的时候的一种内存释放行为

算法

Redis 主要提供了 4 种内存淘汰算法：

• Random 算法

  随机移除某个 key

• TTL 算法

  在设置了过期时间的 key 里面找到更早过期时间的 key，进行优先移除

• LRU 算法

  Least Recently Used，移除最近最少使用的 key

  Redis 中会维护一个大小为 16 的候选池，候选池中的数据会根据时间进行排序，每一次会随机抽取 5 个 key 放到这个候选池中，当候选池已满，访问的时间间隔最大 key 会从候选池中取出进行淘汰

  LRU 算法存在一些问题，例如某个 key 很长时间没有被访问，最近一次偶然被访问，LRU 会认为这是一个热点 key，不需要淘汰此 key，此时使用 LRU 算法进行淘汰会出现偏差

• LFU 算法

  Least Frequently Used，移除最不经常使用的 key

  LFU 相比 LRU 增加了访问频率的维度来统计数据的热点情况，LFU 主要使用了两个双向链表，一个用来保存访问频率，另一个用来保存访问频率相同的所有的 key，当添加 key 的时候，访问频次默认为 1，此时会找到频次为 1 的节点，添加到相同频次节点对应的双向列表的头部，当 key 被访问的时候，会增加对应 key 的访问频率，并且把当前访问的节点移动到下一个频次的节点

  LFU 通过使用频率和上次访问时间标记数据的热度：如果某个数据有读和写，则会增加访问的频率；如果一段时间内没有读和写，会减少访问频率

  通过 LFU 算法可以真正达到非热点数据的淘汰，但 LFU 也有缺点，相对 LRU 增加了访问频次的维护，实现的复杂度也要高于 LRU

  

设置

可以通过设置maxmemory-policy进行切换，可选项有：

• no-envicition

  该策略对于写请求不再提供服务，会直接返回错误（排除 get、del 等），redis默认是 no-envicition 策略

• allkeys-random

  随机选取 key 进行淘汰

• allkeys-lru

  使用 LRU 算法进行淘汰

• volatile-random

  设置过过期时间的 key，进行随机淘汰

• volatile-ttl

  选取即将过期的 key，进行淘汰

• volatile-lru

  使用 LRU 算法，从设置过过期时间的 key 中进行淘汰

• volatile-lfu

  使用 LFU 算法，从设置了过期时间的键中选择某段时间之内使用频次最小的键值对清除掉

• allkeys-lfu

  使用 LFU 算法，从所有的键中选择某段时间之内使用频次最少的键值对清除