> LRU（Least Recently Used）是最经典的缓存淘汰算法：当缓存满时，驱逐最长时间未被访问的条目。本文从数据结构设计出发，推导出 O(1) 的实现，并深入分析 LRU 在工程中的边界情况与局限性。 相关文章：LFU（最少使用频率） · ARC（自适应替换缓存） · W-TinyLFU 与 Caffei…
2026-06-02
> LFU（Least Frequently Used）淘汰访问频率最低的缓存条目（频率相同时淘汰最久未用的）。相比 LRU 的"时间局部性"，LFU 利用"频率局部性"——高频访问的数据更值得保留。本文推导出 O(1) 实现，并深入分析 LFU 的老化问题与修复方案。 相关文章：LRU（最近最少使用） · ARC（自…
2026-06-02
> Clock 算法是操作系统页面置换的经典算法，用一个循环缓冲区和"引用位"近似实现 LRU，避免了 LRU 精确实现的大量链表操作开销。CLOCK-Pro 在此基础上引入冷热页分类，接近最优置换。本文深入伪代码级别，追踪指针运动轨迹。 相关文章：LRU（最近最少使用） · LFU（最少使用频率） · ARC（自适应…
2026-06-02
> ARC（Adaptive Replacement Cache）由 IBM 于 2003 年提出，通过同时维护"最近使用一次"和"最近使用多次"两条 LRU 链，并根据实际命中情况自动调整两者的比例，无需人工调参即可适配不同工作负载。ZFS、Oracle Database 均采用 ARC。 相关文章：LRU（最近最少…
2026-06-02
> W-TinyLFU 是 Caffeine（Java 高性能本地缓存库）的核心算法，接近最优缓存命中率，同时规避了 ARC 的专利问题。它用 Count-Min Sketch 解决 LFU 的频率老化问题，用 Window 区解决新晋热点难以进入缓存的问题。本文深入三个核心组件的算法细节。 相关文章：LRU（最近最少…
2026-06-02
> MySQL InnoDB Buffer Pool 是数据库最重要的内存结构，所有读写都必须经过它。InnoDB 在标准 LRU 基础上做了"midpoint insertion"改造，通过将新页插入链表中间位置，防止全表扫描污染热点数据页。本文深入 Buffer Pool 的页管理、LRU 变体、刷脏策略和并发控制…
2026-06-02
> Redis 没有使用精确 LRU（双向链表），而是通过随机采样实现近似 LRU，同时在 4.0 版本引入了近似 LFU（基于 Morris 计数器）。本文深入两种算法的实现细节、误差分析，以及 8 种淘汰策略的适用场景。 相关文章：LRU（最近最少使用） · LFU（最少使用频率） · W-TinyLFU 与 Ca…
2026-06-02