缓存算法详解
缓存算法用于在缓存容量不足时决定哪些数据应被淘汰，以最大化缓存命中率。以下是常见算法的深入解析、实现细节及优化策略。
一、常见缓存算法概览
算法名称
核心思想
适用场景
复杂度
优缺点
FIFO
淘汰最早进入缓存的数据
顺序访问模式
O(1)
实现简单，但对热点数据不敏感。
LRU
淘汰最久未被访问的数据
突发访问、短期热点数据
O(1)
高效，但对周期性访问模式不友好（如全表扫描）。
LFU
淘汰访问频率最低的数据
长期热点数据（如热门商品）
O(1)*
精准统计访问频率，但需维护复杂结构，对突发流量不敏感。
MRU
淘汰最近被访问的数据
逆序访问模式（如数据库回滚）
O(1)
适用于特定场景，如避免淘汰即将再次访问的大数据。
ARC
结合LRU与LFU，动态调整淘汰策略
混合访问模式
O(1)
自适应强，但实现复杂，内存占用高。
2Q
用两个队列（FIFO和LRU）管理冷热数据
冷热数据分离场景
O(1)
比LRU内存效率高，但对高频访问数据可能不够敏感。
注：LFU的标准实现为O(1)，但部分优化可能引入近似计算。
二、LRU（最近最少使用算法）
1. 核心原理
淘汰策略：优先移除最久未被访问的数据。
数据结构 ：双向链表（维护访问顺序） + 哈希表（快速定位节点）。
链表：头部为最近访问的节点，尾部为待淘汰节点。
哈希表 ：键到链表节点的映射（key → Node）。
2. 操作流程
访问数据 ：
若存在，将节点移动到链表头部。
若不存在，返回未命中。
插入数据 ：
若缓存未满，直接插入链表头部。
若缓存已满，淘汰链表尾部节点，插入新节点到头部。
三、LFU（最不经常使用算法）
1. 核心原理
淘汰策略：移除访问次数最少的数据；若次数相同，则按LRU淘汰最久未访问的。
数据结构 ：
键值映射 ：key → (value, freq)。
频率映射 ：freq → LinkedHashSet
最小频率变量：快速定位待淘汰数据。
2. 操作流程
访问数据 ：
增加该键的频率，将其从原频率集合移除，加入新频率集合。
若原频率为minFreq且其集合为空，则minFreq++。
插入数据 ：
若缓存已满，移除minFreq对应的集合中的首个键（LRU）。
新键频率初始化为1，更新minFreq=1。
3. Java实现优化点
频率更新 ：使用LinkedHashSet维护同一频率的LRU顺序。
时间复杂度：通过哈希表与双向链表的组合，确保所有操作O(1)。
四、Redis中的LRU与LFU优化
1. Redis的近似LRU
问题：精确LRU需要维护链表，内存开销大。
优化策略 ：
随机采样：默认随机选取5个键，淘汰其中最久未访问的。
时间戳精度：记录键的最后访问时间（精度毫秒），但采样范围有限。
配置参数 ：
maxmemory-samples：调整采样数量（增大提高精度，但增加CPU开销）。
volatile-lru：仅淘汰有过期时间的键。
2. Redis的近似LFU
问题：精确LFU需维护全局频率计数器，内存占用高。
优化策略 ：
概率计数器：使用8位存储频率（最大值255），通过概率递增减少写入。
衰减机制 ：定期降低计数器值，防止旧数据长期占据缓存。
衰减公式：counter = counter * lfu_decay_time + 1。
配置参数 ：
lfu-log-factor：控制计数器增长速率（值越大，低频访问增长越慢）。
lfu-decay-time：衰减时间窗口（单位分钟）。
五、算法对比与选型建议
场景
推荐算法
原因
短期突发流量
LRU
对最近访问敏感，快速响应热点变化。
长期稳定热点（如电商）
LFU
精准统计访问频率，避免高频数据被淘汰。
内存敏感型系统
Redis近似LRU/LFU
平衡内存与性能，通过采样和衰减减少开销。
复杂访问模式
ARC/2Q
自适应调整策略，兼顾LRU和LFU优势。
六、总结
LRU：简单高效，适合短期热点，但对周期性扫描不友好。
LFU：精准维护长期热点，实现复杂，需权衡计数器开销。
Redis优化：通过近似算法和衰减机制，以极小精度损失换取内存与性能的平衡。
选型关键：根据业务场景的数据访问模式、内存约束及性能要求综合选择。
LRU（最近最少使用算法）和LFU（最不经常使用算法）详解
LRU（Least Recently Used）
核心思想：淘汰最久未被访问的数据。
工作原理：
维护一个双向链表，节点按访问时间排序，最近访问的节点移到链表头部。
当缓存满时，淘汰链表尾部的节点。
使用哈希表（key → 链表节点）实现快速查找。
时间复杂度：访问、插入、删除操作均为O(1)。
LFU（Least Frequently Used）
核心思想：淘汰访问次数最少的数据，若次数相同则淘汰最久未访问的。
工作原理：
使用两个哈希表：
keyMap：记录键到值和频率的映射（key → {value, freq}）。
freqMap：记录频率到键的集合（freq → LinkedHashSet），维护同一频率下的LRU顺序。
维护最小频率值minFreq，淘汰时从minFreq对应的集合中移除最旧的键。
时间复杂度：访问、插入、删除操作均为O(1)。
总结
LRU：简单高效，适合突发访问模式，但对长期热点数据可能不够敏感。
LFU：适合长期热点数据，但实现复杂，需维护频率信息。
Redis优化：通过近似算法和衰减机制，在性能和准确性间取得平衡。
Redis中的LRU和LFU优化
Redis的LRU优化
近似LRU：通过随机采样减少内存开销。
每次淘汰时随机选取5个键（默认配置），淘汰其中最近最久未访问的。
每个键记录最近访问时间戳（精度为毫秒），比较样本中的时间戳。
配置参数：maxmemory-policy allkeys-lru 或 volatile-lru。
Redis的LFU优化
近似LFU + 衰减机制：
访问计数器（8位，最大值255）随时间衰减，防止旧数据长期占据缓存。
衰减公式：counter = counter * decay + access_time_diff，其中decay是衰减因子（默认0.5）。
访问计数更新概率性增加，避免频繁更新。
配置参数：maxmemory-policy allkeys-lfu 或 volatile-lfu。
调整参数：lfu-log-factor（控制计数器增长速度）和lfu-decay-time（衰减时间窗口）。