当 Redis 内存超出物理内存限制时,为了保持高效的可用性,Redis 需要对内存中部分数据进行淘汰。Redis 早起版本使用的数据淘汰策略是 LRU (Least Recently Used,最近最少使用) 策略,LRU 策略是基于最近访问时间进行排序、淘汰的。后来加入了 LFU (Least Frequency Used,最近最低频率) 策略。
Redis 主要使用的还是 LRU 策略。
Redis 的数据都是由 key-value 形式构成的,在实现 LRU 的内存淘汰机制时,除了 key-value,LRU 还需要维护一个列表,链表尾部的数据是最少被访问的数据。列表按照最近访问时间进行排序。当内存达到物理内存限制触发 LRU 回收时,对链表尾部的 k-v 进行回收。
但 Redis 的 LRU 并不是这样执行的,Redis 使用了一种近似 LRU 算法。对于所有 Redis 对象,对象头中包含一个 24bit 的信息,作为对象热度的标志。在 LRU 淘汰算法中,该标志是一个时间戳,记录了最近一次访问该标志位的时间。
在触发了 LRU 淘汰时,Redis 会随机抽取若干个(默认是 5 个)key,然后删掉最旧的 key。如果这时候内存依旧超出限制,则再次抽选、删除最旧的 Key 值,直到内存低于最大内存限制为止。
Redis Object 的对象头如下所示:
typedef struct redisObject {
// 对象类型,如 zset, set, hash 等
unsigned type: 4;
// 对象编码如 ziplist, inset, skiplist 等
unsigned encoding: 4;
// 对象的热度
unsigned lru: 24;
// 引用计数
int refcount;
// 对象的 body
void *ptr;
}
其中,lru 值即为表示热度的值。在 LRU 模式下,该字段存储的时间戳是 Redis 服务器的时钟信息 server.lruclock,单位为毫秒。server.lruclock 持续更新,某对象被访问时,对象头中的 LRU 值被更新为当前 server.lruclock 的值,最后当触发 LRU 内存淘汰时,该对象的 LRU 值会与当前 server.lruclock 进行取模等一系列运算,即可得到 LRU 值。
LFU 策略与 LRU 的计算方式大致相同,都是根据 Redis 对象头的 LRU 值与 server.lruclock 值进行计算的。但是 LFU 策略下,24bit 的 lru 值被分为 16+8 两部分。
当前对数值 - 基值 (5)
;p = 1 / 差值
;