04.淘汰策略

约 919 字大约 3 分钟...

过期删除策略：

场景：针对业务使用，key如果设置了有效期，过期后会进行删除

过期时间的存储结构：

typedef struct redisDb {
    dict *dict;    /* 数据库键空间，存放着所有的键值对 */
    dict *expires; /* 键的过期时间 */
    ....
} redisDb;

删除过程：
1. 查询key时，先从expires过期哈希表中查找
2. 如果过期哈希表中存在该key，则比较存储的时间和系统时间确定是否过期。
3. 如果不存在、或者key未过期，则返回key对应value
4. 如果key存在，且已过期，则返回null
图解：
一般的过期删除策略：
- 定时删除：
  - 定义：给key创建定时删除事件，时间达到则删除
  - 优点：删除更实时，内存释放更快
  - 缺点：内存不紧张时，也会耗费CPU资源
- 惰性删除：
  - 定义：不主动删除过期键，仅当key被访问时，判断是否过期，从而决定是否（同步/异步）删除。
  - 优点：占用CPU相对更少
  - 缺点：读少、写多时，内存可能得不到释放
- 定期删除：
  - 定义：每隔一段时间随机从expires哈希表取出一定数量的 key进行检查，删除其中的过期key
  - 优点：折中方案，通过检查频率，限制CPU的使用，并且能相对及时清理内存
  - 缺点：删除操作的时长和频率无法把控，频率太低或者太高都不好
Redis过期删除策略：
- 惰性删除 + 定期删除组合使用
- 同步 or 异步删除，Redis>=4.0 通过lazyfree-lazy-expire配置
- 频率：默认每秒进行10次过期检查
- 随机数量：20个
- 额外逻辑：
  - 一次检查中，如果超过25%的key过期，则再次获取20个key
  - 一次检查的最大时间限制：默认25ms。防止因为有大量key过期，一直陷在检查中，导致程序卡死。
- 疑问？：频率*最大时间限制超过了1s

内存淘汰策略：

场景：针对系统保护，如果内存使用超过设置的内存上限，就会触发淘汰
内存淘汰策略分类：
- 不淘汰：
  - noeviction：如果内存不够，触发OOM
- 淘汰：
  - 针对有过期时间的数据淘汰：
    - volatile-random：随机淘汰有过期时间的key
    - volatile-ttl：优先淘汰更早过期的key
    - volatile-lru：优先淘汰最久未使用的key；
    - ：优先淘汰最少使用的key；（4.0开始默认策略）
  - 针对全部数据淘汰：
    - allkeys-random：随机淘汰任意key;
    - allkeys-lru：优先淘汰最久未使用的key；
    - allkeys-lfu：优先淘汰最少使用的key；

Redis中的LRU(Least Recently Used)：
- 是一种近似LRU
- 在每个key对象中记录最近一次访问时间，每次触发淘汰时，随机选5个key，淘汰其中时间最早的那个。（如果是volatile，则从过期哈希表中找）
- 优点：
  - 不需要大链表，节省内存
  - 不需要频繁将被访问数据插入表头
- 缺点：
  - 缓存污染：一次取出大量数据，将热数据置换出去，导致缓存命中率下降
Redis中的LFU(Least Frequently Used)：
- 在每个key对象中记录单位时间内的访问频率，每次触发淘汰时，随机选5个key，淘汰其中频率最低的key
- 优点：同LRU，并且解决了缓存污染问题