LRU算法

• 根据最近访问时间，离当前时间最远的数据优点被淘汰
• 实现 LRU 算法除了需要 key/value 字典外，还需要附加一个链表，链表中的元素按照一定的顺序进行排列。
• 当空间满的时候，会踢掉链表尾部的元素。当字典的某个元素被访问时，它在链表中的位置会被移动到表头。
  • 链表的元素排列顺序就是元素最近被访问的时间顺序。

近似 LRU 算法

• redis 使用的不是完全 LRU 算法
  • 不使用 LRU 算法，为了节省内存，采用随机 LRU 算法
  • Redis 为每一个 key 增加了一个 24bit 的字段，用来记录这个 ke y 最后一次被访问的时间戳
• Redis 3.0 对 LRU 进行了优化
  • 它会维护一个大小 16 的候选池，其数据根据【访问时间】进行排序
  • 第一次随机选取的 5 个 key 都会放入池中
  • 后续每次随机选取的 key，只有【访问时间】小于候选池中【最小时间】的 key 才会放入池中，直到候选池被放满。
    • 也就是比候选池更老的数据才会放入
  • 当放满后，如果有新的 key 放入，则移除候选池中【访问时间】最小的 key
  • 当需要淘汰时，则直接淘汰候选池中【访问时间】最小的 key
• 如何采样就是看 maxmemory-policy 的配置
  • 如果是 allkeys 就是从所有的 key 字典中随机
  • 如果是 volatile 就从带过期时间的 key 字典中随机。
• 每次采样多少个 key 看的是 maxmemory_samples 的配置，默认为 5

LFU

• Redis 4.0 里引入了一个新的淘汰策略 —— LFU（Least Frequently Used） ，作者认为它比 LRU 更加优秀。
• LFU 表示按照最近【访问频率】进行淘汰，它比 LRU 更加精准地表示了一个 key 被访问的热度。
  • 如果一个 key 长时间不被访问，只是刚刚偶然被用户访问了一下，那么在使用 LRU 算法下它是不容易被淘汰的，因为 LRU 算法认为当前这个 key 是很热的。
  • 而 LFU 是需要追踪最近一段时间的访问频率，如果某个 key 只是偶然被访问一次是不足以变得很热的，它需要在近期一段时间内被访问很多次才有机会被认为很热。

Redis 对象热度的数据结构

Redis 的所有对象头中都有一个字段，用来记录对象的热度， 大小为 24bit。

// redis 的对象头
typedef struct redisObject {
    unsigned type:4; // 对象类型如 zset/set/hash 等等
    unsigned encoding:4; // 对象编码如 ziplist/intset/skiplist 等等
    unsigned lru:24; // lfu：热度/ lru：时间戳
    int refcount; // 引用计数
    void *ptr; // 对象的 body
} robj;

LRU 模式

• 在 LRU 模式下，lru 字段存储的是 Redis 时钟 server.lruclock
• 它是一个 24bit 的时间戳
  • 默认是 Unix 时间戳对 2^24 取模的结果，大约 97 天清零一次。
• 当某个 key 被访问一次，它的对象头的 lru 字段值就会被更新为 server.lruclock。

LFU 模式

• 在 LFU 模式下，lru 字段 24 个 bit 用来存储两个值，它分别是访问频次（logc，logistic counter）和上一次访问的更新时间（ldt，last decrement time）
• 访问频次
  • logc 是 8 个 bit，用来存储访问频次
  • 因为 8 个 bit 能表示的最大整数值为 255，存储频次肯定远远不够，所以这 8 个 bit 存储的是频次的对数值，并且这个值还会随时间衰减。
  • 如果它的值比较小，那么就很容易被回收。为了确保新创建的对象不被回收，新对象的这 8 个 bit 会初始化为一个大于零的值，默认是 LFU_INIT_VAL=5。
• 上一次访问频次的更新时间
  • ldt 是 16 个位，用来存储上一次 logc 的更新时间
  • 因为只有 16 位，所以精度不可能很高。
  • 它取的是分钟时间戳对 2^16 进行取模，大约每隔 45 天就会折返