Redis 的过期删除策略与内存淘汰策略
2024-03-28 10:32:53 # Technical # Redis #Redis

Redis 的「内存淘汰策略」和「过期删除策略」，很容易混淆，这两个机制虽然都是做删除的操作，但是触发的条件和使用的策略都是不同的

过期删除策略

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

设置过期时间

设置 key 过期时间的命令一共有 4 个：

1
2
3
4
5
6
7
8
# key 在 100 秒后过期
expire key 100
# key 在 1000 毫秒后过期
pexpire key 1000
# key 在时间戳 1702986550（精确到秒）后过期
expireat key 1702986550
# key 在时间戳 1702986563737（精确到毫秒）后过期
pexireat key 1702986563737

也可在设置键值对时同时设置过期时间：

1
2
3
4
5
6
# 设置 k1 v1 并在 10 秒后过期
set k1 v1 ex 10
# 设置 k2 v2 并在 1000 毫秒后过期
set k2 v2 px 1000
# 设置 k3 v3 并在 100 秒后过期
setex k3 100 v3

可以通过 TTL <key> 查看 key 剩余的存活时间

1
2
3
# 查看 k3 过期时间剩余多少
ttl k3
(integer) 88

如果想取消 key 的过期时间，可以使用 PERSIST <key>

1
2
3
4
5
persist k3
(integer) 1

ttl k3
(integer) -1

如何判断 key 是否过期

Redis 中有一个过期字典（expires dict）存放着所以 key 的过期时间

「过期字典」实际是个哈希表，它的 key 指向某个键对象，value 是一个 long long 类型的整数，保存着这个 key 的过期时间

过期字典的数据结构

当我们查询一个 key 时，Redis 首先检查这个 key 是否存在「过期字典」中：

  • 如果不在，正常读取
  • 如果存在，会获取该 key 的过期时间，与当前的系统时间对比，如果比系统时间大，则没有过期，否则已过期
graph TB
A(客户端) --> |请求| B{是否在过期字典中?}
B{是否在过期字典中?} --> |否| C(正常读取)
B{是否在过期字典中?} --> |是| D{过期时间是否大于系统时间?}
D{过期时间是否大于系统时间?} --> |是| C(正常读取)
D{过期时间是否大于系统时间?} --> |否| E(key过期)
C(正常读取) --> F(结束)
E(key过期) --> F(结束)

过期删除的相关策略

常见有三种过期删除策略：

  • 定时删除
  • 惰性删除
  • 定期删除

定时删除

定时删除的做法是，在设置 key 的过期时间的同时，创建一个定时事件，当到时间时，由事件处理器自动执行 key 的删除操作

优点：

  • 可以保证过期 key 的即时清理
  • 内存的尽快释放

缺点：

  • 过期 key 较多的情况下，会造成 CPU 的负担影响响应时间与吞吐量

惰性删除

惰性删除的做法是，不主动删除，每次查询 key 时，检查是否过期，过期则删除

优点：

  • 没有定时事件，对 CPU 友好

缺点：

  • 过期的 key 依然保留在数据库中，如果一直不访问，则这个 key 占用的内存将一直得不到释放

定期删除

定期删除的做法是：每隔一段时间 随机 从数据库中取出一定数量的 key 进行检查，并删除其中过期的 key

优点：

  • 定时定量检查并删除过期 key，对 CPU 和内存都较为友好

缺点：

  • 内存清理的效果没有定时删除好，同时占用的资源没有惰性删除少
  • 如果定期删除频率过高，对 CPU 不友好，如果频率太低，对内存不友好，频率的设置很关键

Redis 采用的过期策略

Redis 采用了 「惰性删除+定期删除」 的组合，以追求合理的资源占用

惰性删除的实现

Redis 的惰性删除由 db.c 文件中的 expireIfNeeded 函数实现：

1
2
3
4
5
6
7
8
9
10
int expireIfNeeded(redisDb *db, robj *key) {
    // 判断 key 是否过期
    if (!keyIsExpired(db,key)) return 0;
    ....
    /* 删除过期键 */
    ....
    // 如果 server.lazyfree_lazy_expire 为 1 表示异步删除，反之同步删除；
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}

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

  • 如果过期，删除该 key，至于同步删除还是异步删除，根据 lazyfree_lazy_expire 参数决定
  • 如果没有过期，正常返回
graph TB
A(客户端) --> |请求| B{key是否过期?}
B{key是否过期?} --> |否| C(正常返回数据)
C(正常返回数据) --> D(结束)
B{key是否过期?} --> |是| E{同步?异步?删除}
E{同步?异步?删除} --> |同步| G(删除过期key)
E{同步?异步?删除} --> |异步| F(返回null)
G(删除过期key) --> F(返回null)
F(返回null) --> D(结束)

定期删除的实现

  1. 检查频率

    Redis 中，默认每秒 10 次的频率进行检查数据库

    可通过 hz <1-500> 配置频率

    Redis 调用一个内部函数来执行许多后台任务，比如关闭超时的客户端连接、清理从未被请求的过期键等

    并非所有任务都以相同的频率执行，但 Redis 根据指定的「hz」值检查要执行的任务

    默认情况下，「hz」设置为 10。提高这个值会在 Redis 空闲时使用更多的 CPU，但同时在有许多键同时过期时，使 Redis 更具响应性，超时可能会更精确地处理。

    取值范围在 1 到 500 之间，但通常不建议将值设置为超过 100。大多数用户应该使用默认值 10，并仅在需要非常低延迟的环境中将其提高到 100

  2. 随机抽查的数量

    定期删除的实现在 expire.c 文件下的 activeExpireCycle 函数中，其中随机抽查的数量由 ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP 定义，并且写死在代码中为：20

定期删除流程：

  1. 从「过期字典」中随机抽取 20 个 key
  2. 检查这个 20 个 key 是否过期，过期则删除
  3. 如果本次检查的已过期 key 的数量超过 5 个（已过期 / 20 > 25%），则继续重复步骤 1，否则结束本次抽查
graph TB
A(开始) --> B(从过期字段中随机抽取20个key)
B(从过期字段中随机抽取20个key) --> C(删除过期的key)
C(删除过期的key) --> E{用时是否超过25ms}
E{用时是否超过25ms} --> |否| D{过期的key是否超过25%}
E{用时是否超过25ms} --> |是| F(结束)
D{过期的key是否超过25%} --> |否| F(结束)
D{过期的key是否超过25%} --> |是| B(从过期字段中随机抽取20个key)

Redis 为了保证不会出现一直循环抽查（每次都超过 25%）的情况，为此增加了定期删除的时间上限，默认不会超过 25 ms

内存淘汰策略

上面说的过期策略是针对过期 key 的删除与清理，而 Redis 的运行内存超过其设置的最大内存后，Redis 会使用内存淘汰策略删除符合条件的 key，以此保障 Redis 的高效运行

设置最大内存

可以通过 maxmemory <bytes> 来设定最大运行内存

不同位数的操作系统中，maxmemory 的默认值不同：

  • 64 位的系统中，maxmemory 默认为 0，表示没有内存限制，即使崩溃也不会进行任何操作
  • 32 位的系统中，maxmemory 默认位 3G，因为 32 位的机器最大只支持 4GB 的内存

淘汰策略

Redis 内存淘汰的策略共 8 种，8 种大致分为「非数据淘汰」与「数据淘汰」两种策略

  • 非数据淘汰型

    noeviction：redis 3.0 后默认的淘汰策略，不会淘汰任何数据，只保证单纯的查询与删除操作，如果新数据写入，会报错通知禁止写入

  • 数据淘汰型

    数据淘汰型又可以分为「期限数据淘汰」与「任意数据淘汰」

    • 期限数据淘汰型

      volatile-random：随机淘汰设置了过期时间的数据

      volatile-ttl：优先淘汰更快过期的数据

      volatile-lru：淘汰有期限数据中，最久未使用（Least Recently Used）的数据

      volatile-lfu：淘汰有限数据中，最少使用（Least Frequently Used）的数据

    • 任意数据淘汰型

      allkeys-random：随机淘汰任意数据

      allkeys-lru：淘汰最久未使用的数据

      allkeys-lfu：淘汰最少使用的数据

查看内存淘汰策略

1
2
3
config get maxmemory-policy
"maxmemory-policy"
"noeviction"

修改内存淘汰策略

  • 通过命令 config set maxmemory-policy <policy> 配置，可以立即生效，但重启后失效
  • 修改配置文件中的 maxmemory-policy <policy> 配置，重启后生效

LRU与LFU

LFU 内存淘汰算法是 Redis 4.0 后新增的内存淘汰策略

什么是 LRU

LRU（Least Recently Used）最近最少使用，淘汰上次使用距离现在最久的数据

传统的 LRU 算法基于「链表」结构，链表中的元素按照操作顺序从前往后排列，最新操作的元素会被移动到表头，当需要淘汰时，只需要移除链表尾部的元素即可

Redis 并没有使用这样的方式，这种传统的 LRU 算法实现方式存在两个问题：

  • 需要用链表单独管理使用数据，照成额外的空间开销
  • 当有数据访问时，需要将该元素移动到链表头部，当访问量过大时，很影响性能

Redis 实现 LRU

Redis 在对象的结构体中加了一个额外的字段，用于记录此数据最后的操作时间

当 Redis 进行内存淘汰时，会随机挑选 5 个数据，然后淘汰最久没用的那个

优点：

  • 不用单独维护一个大链表，节省了内存空间
  • 不用每次数据访问时都移动节点，提高性能

缺点：

  • 如果一次读取了大量数据，那么这批数据会在 Redis 中存留很长一段时间（需要靠 LFU 解决）

什么是 LFU

LFU（Least Frequently Used）最不频繁使用，淘汰使用次数最少的数据

LFU 算法会记录每个数据的访问次数，当一个数据被访问时，就会增加这个数据被访问次数

Redis 实现 LFU

Redis 对象头的 24 bits 的 LRU 字段被分为两段来存储，高 16bit 存储 LDT（Last Decrement Time），低 8bit 存储 LogC（Logistic Counter）

  • LDT：用来记录 key 访问的时间戳
  • LogC：用来记录 key 的访问频次，值越小代表使用频次越小，越容易被淘汰

每次 key 被访问时，Redis 会对 LogC 进行一个衰减操作，衰减的值跟前后访问的时间差距有关，如果上次访问距离本次访问时间很大，衰减的值也会很大

对 LogC 做完 衰减操作后，就开始对 LogC 进行增加操作，但并不是单纯的 +1，而是根据当前 LogC 的值增加，如果 LogC 越大，增加得越少

Redis 提供了两个相关配置项，用于调整 LFU 算法中 LogC 的衰减与增长

  • lfu-decay-time： 衰减时间，用于调整 LogC 的衰减速度，以分钟为单位，默认为 1，值越大衰减越慢，0 代表不衰减
  • lfu-log-factor：用于调整 LogC 的增长速度，值越大，LogC 增长越慢

LRU（Least Recently Used，最近最少使用）、LFU（Least Frequently Used，最不经常使用）和最小TTL（Time-To-Live，最小生存时间）算法不是精确的算法，而是近似算法（为了节省内存），因此您可以根据速度或准确性进行调整。默认情况下，Redis 会检查 5 个键并选择最近最少使用的键，可以通过配置 maxmemory-samples 参数改变样本大小

默认值 5 可以产生足够好的结果。10 非常接近真正的 LRU，但成本更高。3 更快但不太准确

Thanks

小林coding——Redis 过期删除策略和内存淘汰策略有什么区别？

Prev
2024-03-28 10:32:53 # Technical # Redis #Redis
Next