My-Notes

Search

SearchSearch

025.内存淘汰策略

Sep 04, 2024, 11 min read

前面说的过期删除策略，是删除已过期的 key；而当 Redis 的运行内存超过 Redis 设置的最大内存后，则会使用内存淘汰策略删除符合条件的 key，以此来保障 Redis 高效运行

设置 Redis 最大运行内存

在配置文件 redis.conf 中，可以通过参数 maxmemory <bytes> 来设定最大运行内存，不同位数的操作系统，默认值不同：

  • 64 位操作系统：默认值是 0，表示没有内存大小限制。即：不管用户存放多少数据，Redis 也不会对可用内存进行检查，直到 Redis 实例因内存不足而崩溃也无作为
  • 32 位操作系统：默认值是 3G。因为 32 位的机器最大只支持 4GB 的内存，而系统本身就需要一定的内存资源，所以限制最大 3 GB 非常合理，可以避免因为内存不足而导致 Redis 实例崩溃

Redis 内存淘汰策略有哪些？

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

不进行数据淘汰的策略

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

进行数据淘汰的策略

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

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

  • volatile-random：随机淘汰设置了过期时间的任意键值
  • volatile-ttl：优先淘汰更早过期的键值
  • volatile-lru（Redis3.0 之前的默认值）：淘汰设置了过期时间的键值中，最久未使用的键值
  • volatile-lfu（Redis4.0 新增）：淘汰设置了过期时间的键值中，访问频率最低的键值

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

  • allkeys-random：随机淘汰任意键值
  • allkeys-lru：淘汰整个键值中最久未使用的键值
  • allkeys-lfu（Redis4.0 新增）：淘汰整个键值中访问频率最低的键值

查看和设置 Redis 内存淘汰策略

查看当前 Redis 使用的内存淘汰策略：

> config get maxmemory-policy
1) "maxmemory-policy"
2) "noeviction"

设置内存淘汰策略：

  • 临时设置：通过 config set maxmemory-policy <策略> 命令设置
    • 设置之后立即生效，不需要重启 Redis 服务
    • 重启 Redis 之后，设置就会失效
  • 永久设置：修改 Redis 配置文件 redis.conf 的 maxmemory-policy <策略> 配置项
    • 设置之后必须重启 Redis 服务，才能生效
    • 重启 Redis 服务后配置不会丢失

LRU 算法

LRU（Least Recently Used，最近最少使用）会优先淘汰最久未使用的数据

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

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

  • 需要用链表管理所有数据，这会带来额外的空间开销
  • 当有数据被访问时，需要移动到链表头端，比较耗时

Redis 实现的是一种近似 LRU 算法，目的是为了更好的节约内存

具体实现方式是：

  • ==在 Redis 的对象结构体中添加一个额外的字段，用于记录此数据的最后一次访问时间==
  • 当进行内存淘汰时，会使用随机采样的方式来淘汰数据，淘汰 EvictionPoolLRU 数组中最久没有使用的那个 ^nctt
    • 随机取 n 个值（maxmemory-samples 配置，默认为 5）
    • 尝试把采样的每一个键值对插入 EvictionPoolLRU 数组，这主要取决于：
        1. 能在数组中找到一个尚未插入键值对的空位
        1. 能在数组中找到一个空闲时间小于采样键值对空闲时间的键值对
      • 这两个条件有一个成立，就插入 EvictionPoolLRU 数组
    • 遍历 EvictionPoolLRU 数组（按空闲时间从小到大排序好了），从数组的最后一个 key 开始选择，如果选到的 key 不是空值，就把它作为最终淘汰的 key
    • 选到了被淘汰的 key，就会根据 Redis server 的惰性删除配置，来执行同步删除或异步删除

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

因此，在 Redis 4.0 之后引入了 LFU 算法来解决这个问题

LFU 算法

LFU（Least Frequently Used，最近最不常用）会优先淘汰访问频率最低的数据，它的核心思想是：如果数据过去被访问很少次，那么将来被访问的频率也很低

Redis 是如何实现 LFU 算法的？

Redis 的对象结构体中添加一个额外的字段，用于记录此数据的数据的访问频次。Redis 对象的结构如下：

typedef struct redisObject {
    ...
    
    unsigned lru:24; // 24 bits，用于记录对象的访问信息
    ...
} robj;

LRU 算法和 LFU 算法共用 lru 字段，其含义不同：

  • LRU 算法：用来记录 key 的访问时间戳
  • LFU 算法：24 bits 被分成两段，高 16bit 存储 ldt，低 8bit 存储 logc
    • ldt（Last Decrement Time）：记录 key 的访问时间戳
      • 因为只有 16 位，所以精确到分钟，最多能表示 65535 分钟（约 45 天）
    • logc（Logistic Counter）：计数器，表示 key 的访问频次
      • 只有 8 位，取值范围 0～255
      • logc 并不是单纯的访问次数，而是访问频次（访问频率），代表数据的热度
      • 每个新加入 key 的 logc 初始值为 5

每次 key 被访问时：

  • 先对 logc 做一个衰减操作，衰减值与距上次访问时间有关，差距越大衰减越大（代表访问频率、数据热度越低），最多衰减至 0
    • 衰减值 = 距上次访问时间（单位分钟）/ lfu_decay_time（默认为 1）
  • 之后对 logc 进行增加操作，不是单纯的 +1，而是通过一套递增规则得出增加值，原则就是计数器越大，递增的难度也越高
    • 因为计数器只有 8 bit，最多也只能表示 255，如果每次访问 Key 都直接递增计数器，很容易打满，当所有 Key 的计数器都打满，计数器就没有意义了
    • 递增规则：计算计数器与初始值的差值 baseval，用这个差值乘以 lfu_log_factor 后加一，再取倒数记为阈值 p，取一个随机数，只有当随机数小于阈值 p 才会递增计数器
// 衰减，返回计数器
unsigned long LFUDecrAndReturn(robj *o) {
    // ldt 时间戳（精确到分钟）
    unsigned long ldt = o->lru >> 8;
    // logc 计数器
    unsigned long counter = o->lru & 255;
    // 计算衰减值：衰减值 = 距上次访问时间（单位分钟）/ lfu_decay_time（默认为 1）
    // server.lfu_decay_time：配置文件的配置项，表示 n 分钟计数器--，默认为 1 分钟
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    // 最多衰减至 0
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}
// 增加，返回计数器
uint8_t LFULogIncr(uint8_t counter) {
    // logc 计数器已最大，返回
    if (counter == 255) return 255;
    // 获取随机数
    double r = (double)rand()/RAND_MAX;
    // 当前计数器与初始值的差值
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    // 计算阈值：差值 * lfu_log_factor + 1 的倒数
    // 1. counter 越大，计数器增加的概率就越低
    // 2. lfu_log_factor 越大，计数器增加的概率就越低（配置文件的配置项）
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    // 当随机数小于阈值 p，递增计数器
    if (r < p) counter++;
    return counter;
}

redis.conf 提供两个配置项，用于调整 logc 的增长和衰减：

  • lfu-decay-time：用于调整 logc 的衰减速度，表示每 n 分钟衰减一，值越大，衰减越慢。默认值为 1
  • lfu-log-factor：用于调整 logc 的增长速度，值越大，增长越慢。默认是 10，大约命中 100 次，计数器加 10；命中 1000 次，计数器加 18

当进行内存淘汰时，会使用随机采样的方式来淘汰数据，淘汰 EvictionPoolLRU 数组中访问频率最低的那个（具体流程）

Graph View

Backlinks