Redis -LFU（Least Frequently Used，最少使用频率）缓存淘汰算法

在 Redis 的 LFU（Least Frequently Used，最少使用频率）缓存淘汰算法中，lru 字段被拆分成两部分：高 16 位存储 ldt（Last Decrement Time），低 8 位存储 logc（Logistic Counter）。这个设计使得 Redis 能够有效地结合访问频率和时间因素来管理缓存数据的淘汰策略。
在这里插入图片描述

1. `lru` 字段的拆分

高 16 位 (ldt)：
ldt 表示最后一次衰减操作的时间戳，精度为秒。这一部分用于记录 key 的最近一次访问时间，以便在下一次访问时根据时间差异计算衰减量。
低 8 位 (logc)：
logc 是逻辑计数器，用于跟踪 key 的访问频率。初始值通常为 5，但这个值并不是简单的访问次数，而是基于访问频率的一个动态值。logc 的值越小，表示该 key 的访问频率越低，因此更容易被淘汰。

2. `logc` 的衰减机制

在 Redis 的 LFU 算法中，每次访问一个 key 时，首先对 logc 进行衰减操作。衰减的目的是为了让 logc 能更准确地反映访问频率，而不仅仅是访问次数。具体来说：

衰减的计算方式：
衰减的量取决于当前时间与上次访问时间 (ldt) 的差值。如果这次访问与上次访问的时间间隔较大，那么衰减量就会更大。这样，即使一个 key 在某一时段内被频繁访问，但如果长时间没有再被访问，logc 也会逐渐减少，反映出它的使用频率在降低。
衰减的目的：
通过这种衰减机制，Redis 能够动态调整 key 的使用频率。当一个 key 长时间没有被访问时，其 logc 值会显著下降，表明它的使用频率降低，从而提高其被淘汰的概率。

3. `logc` 的增加机制

在对 logc 进行衰减操作后，Redis 会根据当前的访问情况决定是否增加 logc 的值。增加操作并不是简单地在每次访问时加 1，而是采用一种概率增加的方式。

概率增加的原因：
为了防止 logc 增长过快，Redis 引入了概率机制。logc 值越高，进一步增加的难度就越大。这样设计的目的是确保那些频繁访问的 key 才能在长期内保持较高的 logc 值，而偶尔访问的 key 即使有几次访问，也不会让 logc 增长太多。
增加的过程：
每次访问时，Redis 会基于当前的 logc 和一些内部参数来计算一个增加 logc 的概率。如果概率条件满足，则 logc 增加，否则保持不变。这种方式确保了 logc 值能准确反映长期的访问频率，而非短期内的访问突增。

4. 总结：Redis LFU 算法的工作机制

在 Redis 中，LFU 算法通过 lru 字段的 ldt 和 logc 的结合，使得缓存淘汰策略更加精确和灵活：

衰减阶段：Redis 在每次访问 key 时，根据当前时间与上次访问时间之间的差值，对 logc 进行衰减。时间差越大，衰减越多，表示该 key 的使用频率在降低。
增加阶段：衰减后，Redis 再根据概率决定是否增加 logc。logc 值越高，增加的难度越大。这种机制确保频繁访问的 key 才能在长期内保持较高的 logc 值。
淘汰策略：在需要淘汰缓存项时，Redis 会优先淘汰 logc 较低的 key，这些 key 代表的是访问频率较低或者已经很久没有被访问的缓存数据。