PS：创作不易，感谢阅读，希望对读者有所帮助，喜欢的话可以点赞、收藏、关注，作者会持续更新 Java 生态圈常见知识。黑色加粗为重点关注内容！
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 天就会折返
