缓存淘汰算法W-TinyLFU

W-TinyLFU算法是一种**融合LFU与LRU双重特性的混合淘汰算法**，其本质是通过分层机制将短期突发流量与长期热点数据分离处理。 --- ### 一、缓存结构设定（以总容量100为例） 1. **窗口缓存（Window Cache）** • **容量**：总容量的1%（即1个槽位） • **淘汰策略**：LRU（应对突发流量） *示例*：新访问的数据A、B、C会先进入此区域，若已满则淘汰最早进入的数据。 2. **主缓存（Main Cache）** • **容量**：总容量的99%（99个槽位） • **细分结构**： ◦ **保护区（Protected，80%）**：长期高频数据 ◦ **考察区（Probation，20%）**：待晋升候选数据 • **淘汰策略**：SLRU（分段LRU）结合频率统计 --- ### 二、算法流程示例 **场景**：缓存已满（1窗口+99主缓存），新数据D进入 **步骤说明**： 1. **窗口缓存阶段** • D进入窗口缓存（LRU结构），若窗口已满则触发淘汰： *示例*：窗口中原有数据C被淘汰，D占据窗口唯一槽位。 2. **主缓存准入竞争** • **频率对比**：D需与主缓存考察区的数据E（访问频率最低者）比较 • **频率统计工具**： ◦ 使用**Count-Min Sketch**，通过4个哈希函数定位计数器组，取最小值作为近似频率 ◦ 若D的预估频率＞E的频率：D进入主缓存考察区，E被淘汰 *示例*：D的预估频率为5次，E为3次 → D胜出进入主缓存。 3. **主缓存内部晋升** • **考察区→保护区**：若数据在考察区再次被访问，则晋升至保护区 • **保护区淘汰**：保护区满时，淘汰最久未访问的高频数据 *示例*：假设D在考察区被访问2次后晋升保护区，长期保留。 --- ### 三、算法本质剖析 #### 1. **LFU特性** • **频率统计核心**：基于Count-Min Sketch的近似LFU • **保鲜机制**：定期对所有计数器衰减（如除2操作），防止旧热点数据长期霸占缓存 #### 2. **LRU特性** • **窗口缓存**：纯LRU结构应对突发访问 • **主缓存淘汰**：SLRU在局部使用LRU策略 #### 3. **混合优势** | 场景 | W-TinyLFU处理逻辑 | 传统算法缺陷 | |---------------------|--------------------------------|--------------------------| | **突发新闻访问潮** | 数据暂存窗口缓存，避免被立即淘汰 | LFU会因低频统计被淘汰 | | **长期热门商品缓存** | 高频数据晋升保护区长期保留 | LRU会被新数据冲刷淘汰 | --- ### 四、技术突破点 1. **空间优化** • Count-Min Sketch仅需传统LFU 10%的内存 *示例*：统计100万数据的频率仅需4MB内存（传统LFU需40MB） 2. **动态比例调整** • 根据命中率动态调整窗口/主缓存容量比例 *示例*：突发流量激增时，自动扩大窗口缓存比例至5% --- ### 五、总结归类 W-TinyLFU是**以LFU为基底、LRU为补充的增强型算法**： • **LFU基因**：通过概率数据结构实现轻量级频率统计 • **LRU外延**：窗口缓存吸收突发流量，SLRU优化局部淘汰 这种混合设计使其在Twitter等实测场景中，命中率比纯LRU提升20%以上。