过期删除策略有哪些？

Redis 是可以对 key 设置过期时间的，因此需要有相应的机制将已过期的键值对删除，而做这个工作的就是过期键值删除策略。

在说 Redis 过期删除策略之前，先介绍下，常见的三种过期删除策略：

• 定时删除（在设置 key 的过期时间时，同时创建一个定时事件，当时间到达时，由事件处理器自动执行 key 的删除操作）；
  • 优点：
    • 可以保证过期 key 会被尽快删除，也就是内存可以被尽快地释放。因此，定时删除对内存是最友好的
  • 缺点：
    • 在过期 key 比较多的情况下，删除过期 key 可能会占用相当一部分 CPU 时间，在内存不紧张但 CPU 时间紧张的情况下，将 CPU 时间用于删除和当前任务无关的过期键上，无疑会对服务器的响应时间和吞吐量造成影响。所以，定时删除策略对 CPU 不友好
• 惰性删除（不主动删除过期键，每次从数据库访问 key 时，都检测 key 是否过期，如果过期则删除该 key）；
  • 优点：
    • 因为每次访问时，才会检查 key 是否过期，所以此策略只会使用很少的系统资源，因此，惰性删除策略对 CPU 时间最友好
  • 缺点：
    • 如果一个 key 已经过期，而这个 key 又仍然保留在数据库中，那么只要这个过期 key 一直没有被访问，它所占用的内存就不会释放，造成了一定的内存空间浪费。所以，惰性删除策略对内存不友好
• 定期删除（每隔一段时间「随机」从数据库中取出一定数量的 key 进行检查，并删除其中的过期key）。
  • 优点：
    • 通过限制删除操作执行的时长和频率，来减少删除操作对 CPU 的影响，同时也能删除一部分过期的数据减少了过期键对空间的无效占用
  • 缺点：
    • 内存清理方面没有定时删除效果好，同时没有惰性删除使用的系统资源少
    • 难以确定删除操作执行的时长和频率。如果执行的太频繁，定期删除策略变得和定时删除策略一样，对CPU不友好；如果执行的太少，那又和惰性删除一样了，过期 key 占用的内存不会及时得到释放

Redis过期删除策略

Redis 选择「惰性删除+定期删除」这两种策略配和使用，以求在合理使用 CPU 时间和避免内存浪费之间取得平衡

如何判定 key 已过期了？

每当我们对一个 key 设置了过期时间时，Redis 会把该 key 带上过期时间存储到一个过期字典（expires dict）中，也就是说「过期字典」保存了数据库中所有 key 的过期时间。

过期字典存储在 redisDb 结构中，如下：

Redis 的惰性删除策略

Redis 在访问或者修改 key 之前，都会调用 expireIfNeeded 函数对其进行检查，检查 key 是否过期：

• 如果过期，则删除该 key；
• 如果没有过期，不做任何处理，然后返回正常的键值对给客户端。

Redis 的定期删除策略

1. 默认每秒进行 10 次过期检查，从过期字典中随机抽取 20 个 key（默认值）；
2. 检查这 20 个 key 是否过期，并删除已过期的 key；
3. 如果本轮检查的已过期的 key 比例大于 25%，则继续重复步骤 1；如果已过期的 key 比例小于 25%，则停止继续删除过期 key，然后等待下一轮再检查。

Redis内存淘汰策略

Redis 内存淘汰策略有哪些？

Redis 内存淘汰策略共有八种，这八种策略大体分为「不进行数据淘汰」和「进行数据淘汰」两类策略。

1、不进行数据淘汰的策略

noeviction（Redis3.0之后，默认的内存淘汰策略） ：它表示当运行内存超过最大设置内存时，不淘汰任何数据，这时如果有新的数据写入，会报错通知禁止写入，不淘汰任何数据，但是如果没用数据写入的话，只是单纯的查询或者删除操作的话，还是可以正常工作。

2、进行数据淘汰的策略

针对「进行数据淘汰」这一类策略，又可以细分为「在设置了过期时间的数据中进行淘汰」和「在所有数据范围内进行淘汰」这两类策略。

在设置了过期时间的数据中进行淘汰：

• volatile-ttl：优先淘汰更早过期的键值。
• volatile-random：随机淘汰设置了过期时间的任意键值；
• volatile-lru（Redis3.0 之前，默认的内存淘汰策略）：淘汰所有设置了过期时间的键值中，最久未使用的键值；
• volatile-lfu（Redis 4.0 后新增的内存淘汰策略）：淘汰所有设置了过期时间的键值中，最少使用的键值；

在所有数据范围内进行淘汰：

• allkeys-random：随机淘汰任意键值;
• allkeys-lru：淘汰整个键值中最久未使用的键值；
• allkeys-lfu（Redis 4.0 后新增的内存淘汰策略）：淘汰整个键值中最少使用的键值。

一种是不开启淘汰策略，此时如果内存满了，写入操作失败，但是不会淘汰已有数据。

另一种是开启淘汰策略，这时候有两个大的分支，一个是基于有过期时间的数据淘汰，一个是基于所有数据，他们都支持LRU、LFU、RANDOM算法，过期时间还支持按ttl大小淘汰。

LRU算法

LRU 全称是 Least Recently Used 翻译为最近最少使用，会选择淘汰最近最少使用的数据。

传统 LRU 算法：

• 基于「链表」结构，链表中的元素按照操作顺序从前往后排列，最新操作的键会被移动到表头，当需要内存淘汰时，只需要删除链表尾部的元素即可，因为链表尾部的元素就代表最久未被使用的元素。

• 两个问题：

  • 需要用链表管理所有的缓存数据，这会带来额外的空间开销；

  • 当有数据被访问时，需要在链表上把该数据移动到头端，如果有大量数据被访问，就会带来很多链表移动操作，会很耗时，进而会降低 Redis 缓存性能。

Redis 实现的 LRU 算法：

• Redis 实现的是一种近似 LRU 算法，目的是为了更好的节约内存，它的实现方式是在 Redis 的对象结构体中添加一个额外的字段，用于记录此数据的最后一次访问时间。当 Redis 进行内存淘汰时，会使用随机采样的方式来淘汰数据，它是随机取 5 个值（此值可配置），然后淘汰最久没有使用的那个。

• 优点：

  • 不用为所有的数据维护一个大链表，节省了空间占用；
  • 不用在每次数据访问时都移动链表项，提升了缓存的性能；

• 问题：

  • 无法解决缓存污染问题，比如应用一次读取了大量的数据，而这些数据只会被读取这一次，那么这些数据会留存在 Redis 缓存中很长一段时间，造成缓存污染。

LFU算法

LFU 全称是 Least Frequently Used 翻译为最近最不常用，LFU 算法是根据数据访问次数来淘汰数据的，它的核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。

Redis 实现的 LRU 算法：

• LFU 算法相比于 LRU 算法的实现，多记录了「数据的访问频次」的信息；

  • 在 LRU 算法中，Redis 对象头的 24 bits 的 lru 字段是用来记录 key 的访问时间戳

  • 在 LFU 算法中，Redis对象头的 24 bits 的 lru 字段被分成两段来存储，高 16bit 存储 ldt( key 的访问时间戳)，低 8bit 存储 logc(key 的访问频次)

• logc 并不是单纯的访问次数，而是访问频次（访问频率），因为 logc 会随时间推移而衰减的

  • redis 在访问 key 时，对于 logc 是这样变化的：

    1. 先按照上次访问距离当前的时长，来对 logc 进行衰减

    2. 然后，再按照一定概率增加 logc 的值（ logc 越大越难再增加）

内存回收什么时候发起的

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

参考：

小林coding (xiaolincoding.com)