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 天就会折返
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。