标签 lru 下的文章

Redis 的优胜劣汰 LRU 算法

本章主要介绍:

  1. redis 内存满了以后会怎样 ?
  2. redis 的近似 LRU 算法和严格 LRU 算法有什么区别 ?

Redis 的五种最大内存时的释放策略

场景

  • 当 redis 内存超出物理内存限制时, 会频繁和硬盘交换(swap), 极大影响性能
  • redis 可配置 maxmemory 参数来限制内存超出期望大小
  • 当实际内存超出 maxmemory 时, redis 提供了五种策略来让用户自己觉得如何腾出新空间提供读写服务

五种策略

  • noeviction: 默认策略. 不提供除 del 之外的写请求, 读请求可以继续进行. 保证不会丢失数据
  • volatile-lru: 尝试淘汰设置了过期时间且最少使用的 key.
  • volatile-ttl: 尝试淘汰设置了过期时间且 ttl 小的 key.
  • volatile-random: 尝试随机淘汰设置了过期时间的 key.
  • allkeys-lru: 在全体 key 中淘汰最少使用的.
  • allkeys-random: 在全体 key 中随机淘汰

严格 LRU 算法

  • 维护一个链表, 将所有设置了过期时间的 key 放在这个链表中
  • 当字典中某个元素被访问时, 它在链表中的位置会被移动到链表头部
  • 当空间满时, 就从链表尾部开始移除元素

近似 LRU 算法

为了不维护严格算法的链表, 节省内存

  • 给每个 key 增加一个额外 24bit 长度的小字段, 存储该 key 的最后一次访问时间戳
  • 当空间满时, 随机采样取出 5 个 key (数量可配置), 按时间戳淘汰掉最旧的 key
  • 循环第二步, 直到内存低于 maxmemory 值
  • 随机采样的范围取决于配置的策略是 volatile 还是 allkeys

Redis 3.0 开始, 增加了 淘汰池 进一步提升了近似 LRU 的效果:
上一次随机采样后未淘汰的 key, 会放入 淘汰池 留待下一次循环,
下一次随机采样的 key 会先和 淘汰池 中的 key 合并后, 再计算淘汰最旧的 key