Redis 系列(04-2)Redis原理 - 内存回收

Redis 系列(04-2)Redis原理 - 内存回收

Redis 系列目录

相关文档推荐:

  1. Redis - LRU

Reids 所有的数据都是存储在内存中的,在某些情况下需要对占用的内存空间进行回收。内存回收主要分为两类,一类是 key 过期,一类是内存使用达到上限(max_memory)触发内存淘汰。

Redis 设置 key 的过期时间:

expire k1 1         # 设置过期时间s
expireat k1 1       # 设置过期时间,时间戳s
pexpire k1 1000     # 设置过期时间ms
pexpireat k1 1      # 设置过期时间,时间戳ms

ttl k1
persist k1          # 取消过期时间设置

1. 过期策略

要实现 key 过期,我们有几种思路。

  1. 定期过期(主动淘汰)
  2. 惰性过期(被动淘汰)
  3. 定期过期

1.1 定时过期(主动淘汰)

每个设置过期时间的 key 都需要创建一个定时器,到过期时间就会立即清除。该策略可以立即清除过期的数据,对内存很友好;但是会占用大量的 CPU 资源去处理过期的数据,从而影响缓存的响应时间和吞吐量。

1.2 惰性过期(被动淘汰)

只有当访问一个 key 时,才会判断该 key 是否已过期,过期则清除。该策略可以最大化地节省 CPU 资源,却对内存非常不友好。极端情况可能出现大量的过期 key 没有再次被访问,从而不会被清除,占用大量内存。

  1. 获取 key 时判断是否过期。调用 server.c 中 expireIfNeeded(redisDb db, robj key) 判断 key 是否过期。

  2. 写入 key 时,发现内存不够,调用 expire.c 中 activeExpireCycle 释放一部分内存。

1.3 定期过期

每隔一定的时间,会扫描一定数量的数据库的 expires 字典中一定数量的key,并清除其中已过期的 key。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时,可以在不同情况下使得 CPU 和内存资源达到最优的平衡效果。

typedef struct redisDb {
    dict *dict;                 // *redisDb中保存的数据
    dict *expires;              // *设置expire过期的key
    ...
} redisDb;

Redis 中同时使用了惰性过期和定期过期两种过期策略。

问题:如果都不过期,Redis 内存满了怎么办?

2. 淘汰策略

Redis 的内存淘汰策略,是指当内存使用达到最大内存极限时,需要使用淘汰算法来决定清理掉哪些数据,以保证新数据的存入。

2.1 最大内存设置

redis.conf 参数配置:

maxmemory <bytes>

如果不设置 maxmemory 或者设置为 0,64 位系统不限制内存,32 位系统最多使用 3GB 内存。

动态配置:

127.0.0.1:6379> config set maxmemory 2GB

2.2 淘汰策略

redis.conf 中提供了 8 种缓存淘汰策略,默认是 noeviction,即当内存到达上限时不删除 key 而直接抛出异常。

# maxmemory-policy noeviction

# volatile-lru -> Evict using approximated LRU among the keys with an expire set.
# allkeys-lru -> Evict any key using approximated LRU.
# volatile-lfu -> Evict using approximated LFU among the keys with an expire set.
# allkeys-lfu -> Evict any key using approximated LFU.
# volatile-random -> Remove a random key among the ones with an expire set.
# allkeys-random -> Remove a random key, any key.
# volatile-ttl -> Remove the key with the nearest expire time (minor TTL)
# noeviction -> Don't evict anything, just return an error on write operations.

动态配置:

127.0.0.1:6379> config set maxmemory-policy volatile-lru
表1 Redis缓存淘汰策略
淘汰策略 说明
volatile-lru 根据LRU 算法删除设置了超时属性(expire)的键,直到腾出足够内存为止。
如果没有可删除的键对象,回退到noeviction 策略。
allkeys-lru 根据LRU 算法删除键,不管数据有没有设置超时属性,直到腾出足够内存为止。
volatile-lfu 在带有过期时间的键中选择最不常用的。
allkeys-lfu 在所有的键中选择最不常用的,不管数据有没有设置超时属性。
volatile-random 在带有过期时间的键中随机选择。
allkeys-random 随机删除所有键,直到腾出足够内存为止。
volatile-ttl 根据键值对象的ttl 属性,删除最近将要过期数据。如果没有,回退到noeviction 策略。
noeviction 默认策略,不会删除任何数据,拒绝所有写入操作并返回客户端错误信息(error)OOM,
此时Redis 只响应读操作。

如果没有符合前提条件的key 被淘汰,那么 volatile-lru、volatile-random 、volatile-ttl 相当于 noeviction(不做内存回收)。建议使用 volatile-lru,在保证正常服务的情况下,优先删除最近最少使用的 key。

Redis 中内存淘汰有三种算法:

  • LRU(Least Recently Used):最近最少使用。判断最近被使用的时间,目前最远的
    数据优先被淘汰。
  • LFU(Least Frequently Used):最不常用,4.0 版本新增。
  • TTL(Time To Live):存活时间。
  • random:随机删除。

### 2.3 LRU

Redis LRU 对传统的 LRU 算法进行了改良,通过随机采样来调整算法的精度。如果淘汰策略是 LRU,则根据配置的采样值 maxmemory-samples(默认是5 个),随机从数据库中选择 m 个 key, 淘汰其中热度最低的 key 对应的缓存数据。所以采样参数 m 配置的数值越大,就越能精确的查找到待淘汰的缓存数据,但是也消耗更多的 CPU 计算,执行效率降低。

redis.conf 参数配置:

maxmemory-samples 5

问题1:如何找出热度最低的数据?

Redis 中所有对象结构都有一个 lru 字段,且使用了 unsigned 的低 24 位,这个字段用来记录对象的热度。对象被创建时会记录 lru 值。在被访问的时候也会更新 lru 的值。但是不是获取系统当前的时间戳,而是设置为全局变量server.lruclock 的值。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;  /* 记录最后一次的访问时间,与 LRU、LFU 垃圾回收算法有关
                             * LRU time (relative to global lru_clock) or
                             * LFU data (least significant 8 bits frequency
                             * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

在 server.c 中有一个定时任务 serverCron, 默认每100 毫秒调用函数 updateCachedTime 更新一次全局变量的server.lruclock 的值,它记录的是当前unix时间戳。这样 lru 获取时间时不用每次都直接调用系统函数,提高效率。

在 alibaba sentinel 限流中也需要频繁获取时间戳,因此也采取了类似的方案,在 TimeUtils 中也有一个定时任务,每 1ms 更新一次系统时间戳。

当对象里面已经有了 LRU 字段的值,就可以评估对象的热度了。函数 evict.c/estimateObjectIdleTime 评估指定对象的 lru 热度,思想就是对象的 lru 值和全局的 server.lruclock 的差值越大(越久没有得到更新),该对象热度越低。

2.4 LFU

最不常用数据淘汰策略。当采用 LFU 淘汰算法时,redisObject 对象 lru 字段存储的数据结构不同。

typedef struct redisObject {
    unsigned lru:LRU_BITS;  /* LRU time (relative to global lru_clock) or
                             * LFU data (least significant 8 bits frequency
                             * and most significant 16 bits access time). */
    ...
} robj;

当这 24 bits 用作 LFU 时,其被分为两部分:

  • 高 16 位用来记录访问时间(单位为分钟,ldt,last decrement time)

  • 低8 位用来记录访问频率,简称 counter(logc,logistic counter)

counter 是用基于概率的对数计数器实现的,8 位可以表示百万次的访问频率。对象被读写的时候,lfu 的值会被更新。

在 db.c 中调用 updateLFU 更新 lru 的值:

void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);
    counter = LFULogIncr(counter);
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

总结: 可以看到高 16 位记录访问时间 LFUGetTimeInMinutes(),低 8 位记录访问频率 counter。

在 Redis 中并不是简单的每访问一次,统计数就 +1,lfu 增加或减少都有一个影响因子。在 redis.conf 中配置如下:

# +--------+------------+------------+------------+------------+------------+
# | factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
# +--------+------------+------------+------------+------------+------------+
# | 0      | 104        | 255        | 255        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 1      | 18         | 49         | 255        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 10     | 10         | 18         | 142        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 100    | 8          | 11         | 49         | 143        | 255        |
# +--------+------------+------------+------------+------------+------------+

# lfu-log-factor 10
# lfu-decay-time 1
  • lfu-log-factor:增长因子。值越大,counter 增长的越慢。默认为 10,表示每 100 hits 次访问增加 10。
  • lfu-decay-time:减少因子(分钟)来控制。默认为 1,表示 N 分钟没有访问就要减少 N。

每天用心记录一点点。内容也许不重要,但习惯很重要!

相关文章
相关标签/搜索