1 概念与目标
缓存淘汰策略（cache eviction policy）用于在缓存达到容量上限时，按预设规则决定哪些缓存项应被移除。其核心目标通常是：在有限存储与计算资源约束下，尽量减少后续请求因缺失而引发的代价，同时保持系统可预测性与稳定性。
1.1 缓存淘汰的触发条件
常见触发情形包括：缓存容量达到上限需要插入新条目、条目到期但仍占用空间、以及由于负载变化需要回收内存或缓存页。触发时系统需要在“尽快释放空间”与“尽量不破坏已有热点”之间做选择。
1.2 评价指标与权衡
淘汰策略的效果往往不能只看单一指标。不同系统把目标权重分配给命中率、时延、资源消耗和稳定性，形成实际工程中的权衡组合。
1.2.1 命中率与误命中代价
命中率反映请求在缓存中被直接满足的比例，但“命中率高”不一定代表总体收益更优，因为不同类型的误判会带来不同代价。例如，将仍可能被频繁访问的数据误踢出缓存会导致后续大量回源或重建成本。
1.2.2 时延、抖动与吞吐
除了平均时延，还需要关注抖动（延迟波动）。某些淘汰策略在极端情况下可能触发集中回收、批量失效或更复杂的元数据维护，从而造成尾部延迟上升，降低整体吞吐表现。
1.2.3 资源开销（CPU/内存/元数据）
淘汰决策所需的元数据维护也会消耗资源。维护链表、计数器、优先级队列或分层统计，都可能增加 CPU 开销与内存占用；同时还会引入额外的并发控制成本。因而“更聪明”的策略并不总是“更划算”。
1.3 一致性与写入语义的影响
缓存淘汰不仅影响读性能，还会与写入传播方式耦合。若缓存包含可修改数据，删除时如何处理“写入尚未落盘/落后端”的状态将决定正确性与回收成本。
1.3.1 写回（write-back）与写穿（write-through）
写回模式下，缓存先接收写入，随后再在合适时机刷新到下游；淘汰时若移除的是未同步的数据，需要额外的回写或延后提交。写穿模式则通常更早完成持久化，但会降低写入聚合带来的收益，整体性能可能受影响。
1.3.2 脏页处理与回收成本
当缓存项对应的数据被修改但尚未同步时，称为“脏”的状态。回收脏页通常伴随 I/O、队列调度或一致性校验。策略设计往往会将“脏比例、回写带宽、脏页数量阈值”等因素纳入决策，以避免回收动作本身成为性能瓶颈。
2 典型淘汰策略分类
缓存淘汰策略可按信息来源与决策方式划分为多类。常见思路包括：基于时间、基于频率、基于代价与权重、以及随机化或概率选择。实际系统还会结合多策略形成分层或融合。
2.1 基于时间相关的策略
时间相关策略通常利用“近期访问”的线索。其基本假设是：越接近当前的访问越可能在未来再次发生，因此淘汰“最久未被访问”的项更符合工作负载的局部性。
2.2 基于频率相关的策略
频率相关策略使用“访问次数”或其变体作为依据。核心假设是：被访问得越多的对象在未来仍更可能被访问，因此更应保留高频条目，移除低频条目。
2.3 基于代价与权重的策略
代价与权重策略不仅考虑“是否会被再次访问”，还考虑代价大小。例如回填成本高、对象体积大或回源代价昂贵的条目，可能被赋予更高保留权重，从而减少因淘汰造成的昂贵损失。
2.4 随机化与概率策略
随机化与概率策略通过随机选择或概率估计来降低元数据开销、避免被特定访问模式“欺骗”。在某些场景中，它们能在与复杂策略接近的命中率下提供更好的实现简洁性或更稳定的运行行为。
2.5 分层缓存与组合策略
分层或组合策略将缓存空间拆为不同区域或多个队列，并针对不同对象特征采用不同规则，例如热区使用更保守策略，冷区使用更激进回收策略。
2.5.1 本地/远端协同
分层不仅体现在同一节点内，也体现在与远端存储或上游缓存的配合上。淘汰决定常常需要考虑“从本地失效后去哪里拿”（上游命中率、回源延迟、带宽等），从而形成更符合业务的整体优化。
2.5.2 多队列与多策略融合
多队列可按访问频度、对象大小或是否脏数据分组，再配合迁移规则实现自适应。融合策略则可能在不同阶段切换（例如从随机到频率驱动），或对不同对象子集分别决策。
3 基于 LRU 系思想的策略
LRU 系思想强调“最近性”，认为近期被访问的数据更可能在不久后再次被访问。相较纯随机，它通常能更好捕捉局部性；但在特定访问模式下也可能出现系统性误判。
3.1 LRU（最近最少使用）
LRU（Least Recently Used，最近最少使用）淘汰策略选择“距离当前最久未被访问”的条目移除。其直观对应是：保留最新活动范围内的对象，丢弃长期沉寂的数据。
3.1.1 维护方式：链表与哈希
常见实现使用哈希表提供定位，用链表维持访问顺序：每次访问把对应节点移动到链表头部；需要淘汰时移除链表尾部节点。这样可以将查找和更新做到常数时间，但链表操作带来一定的指针与并发管理开销。
3.1.2 典型问题：顺序扫描“误伤”
LRU 在面对顺序扫描式访问（例如一次性遍历大量不同对象）时，可能迅速把原本应保留的热点“挤出”。原因在于近期访问记录会被扫描阶段主导，导致热点在淘汰队列中被错误标记为“较冷”。
3.2 近似 LRU：CLOCK / 二次机会
近似 LRU 以更低的维护成本替代严格的访问顺序记录。CLOCK（时钟）或二次机会（second chance）类策略常用“引用位”来近似判断近期性。
3.2.1 引用位与扫描机制
在访问时将某条目标记“引用位=1”。淘汰时从“指针位置”开始顺序扫描：若遇到引用位为 1 的项，将其清零并跳过；若引用位为 0，则选择它进行淘汰。该过程以循环扫描方式减少维护链表的需求。
3.2.2 实现复杂度与效果
CLOCK 的元数据维护通常更简单，且在工程上更易扩展到大规模缓存。但由于它只保留二值“近期是否被引用”的信息，精度可能低于严格 LRU，命中率在某些工作负载下会出现差距。
3.3 分段与改进：MRU-LRU 等
分段或改进版 LRU 试图缓解顺序扫描等问题，或针对不同对象阶段采取更合适的保留方式。MRU-LRU 等命名通常表示对“最近访问”与“最久未访问”策略进行变体组合或区域化处理。
3.3.1 对热点抖动的应对
当热点频繁切换时，严格 LRU 可能不断误判热点冷却。通过分段管理或引入“保护区”，系统可以给新热点更快的提升机会，避免被短暂的访问波动过度驱逐。
3.3.2 适用场景与参数敏感性
这类策略往往需要参数（例如分段大小、迁移阈值）来定义保护力度与扫描节奏。参数不匹配可能导致：要么保护过度降低整体命中，要么保护不足仍然被扫描或抖动击穿。
4 基于 LFU 系思想的策略
LFU 系思想根据“访问频率”判断价值。它适合那些呈现长期稳定热度的工作负载；但对频率统计的维护、并发更新以及“频率失真”问题需要额外处理。
4.1 LFU（最不常用）
LFU（Least Frequently Used，最不常用）通常淘汰访问次数最低的条目。其直观假设是：高频对象更可能持续被请求，因此应优先保留。
4.1.1 频次计数与更新策略
基础实现需要为每个缓存项维护计数器。访问时递增计数；淘汰时移除计数最小的项。实际实现可能用桶（bucket）或优先级结构来降低选择复杂度，但更新和维护成本仍较可观。
4.1.2 并发更新与一致性
在并发环境中，计数器的更新容易成为热点争用点。系统可能采用分片计数、近似计数或延迟合并，以降低锁竞争；同时要确保最终统计不会导致明显偏差。
4.2 近似 LFU：分桶与采样
近似 LFU 通过降低计数精度或减少跟踪范围来降低开销。例如用分桶表示频率等级，或通过采样估计频率分布。
4.2.1 计数衰减（老化机制）
为了避免“长期但已不再热门”的对象长期占据高频档位，引入衰减或老化机制会让旧访问逐渐失去权重。常见做法是随时间降低计数或按窗口重新统计。
4.2.2 限制元数据开销
分桶与采样能减少精确计数带来的空间与计算压力，但会牺牲一定的分辨能力。工程上通常通过桶数、采样率等参数在精度与成本之间折中。
4.3 处理“频率失真”的变体
频率失真指的是计数并不等价于未来收益。比如某对象在短期内被大量请求（造成高频），但随后完全不再访问，这会让 LFU 错误保留。
4.3.1 冷启动与长尾访问
新对象缺少历史数据，会在纯 LFU 下长期处于劣势。长尾访问模式则可能让大量低频对象长期存在，挤占空间并影响整体效率。为此需要冷启动策略或更合理的统计衰减。
4.3.2 防止早期高频“霸占”
早期高频霸占可通过衰减、窗口化统计或对高频增长速度设置上限来缓解。目标是让“持续热度”比“瞬时热度”更受重视。
5 衰减与动态权重策略
衰减与动态权重策略把“频率”与“代价”与时间因素结合，使得淘汰判断更贴近真实收益。它们常用于工作负载随时间演化明显的环境。
5.1 时间衰减的频率模型
时间衰减让统计值对时间更敏感，能在热点发生迁移时更快反映变化。
5.1.1 指数衰减（aging）
指数衰减通过随时间衰减历史贡献，使得最近访问拥有更大权重。这样既能保留一定频率信息，也能避免旧热对象“永远不出局”。
5.1.2 窗口化计数（time window）
窗口化计数只统计最近一段时间内的访问。窗口长度决定了系统对变化的敏感度：窗口太长反应迟钝，窗口太短又容易受噪声影响。
5.2 代价感知淘汰
代价感知淘汰把“失去该条目”带来的代价纳入评分。代价来源可能是回源延迟、重新计算成本、带宽消耗或写回回收成本。
5.2.1 回填成本与重新计算成本
当条目缺失需要从远端获取或执行昂贵计算时，应提高保留优先级。反之，如果回填成本低，淘汰该条目损失较小，策略可更激进。
5.2.2 大对象与小对象权重
缓存容量以“空间”衡量时，大对象可能显著影响可用空间。为平衡空间效率，系统可能对对象体积引入归一化权重，例如用单位大小的热度或单位成本的收益来决策。
5.3 热度/代价综合评分
综合评分将热度与失效风险、以及代价函数统一到一个可比较的分数中，减少单一指标导致的偏差。
5.3.1 命中收益与失效风险
热度可由衰减频率估计；失效风险可由对象大小、访问间隔波动或一致性开销推断。评分倾向于选择“即使失去也损失较低、但未来命中收益较低”的条目先淘汰。
5.3.2 与业务指标联动
在一些系统中，热度评分会和业务指标联动，例如按用户群、接口重要性或服务等级分层，确保对关键业务路径更友好的淘汰顺序。
6 随机与概率策略
随机策略不依赖完整历史信息，常用于降低元数据维护成本、避免被特定模式“投机”，或作为策略组件的兜底方案。
6.1 纯随机淘汰
6.1.1 基本原理与适用性
纯随机淘汰在缓存满时从现有项中等概率选择一个移除。它实现极简，不需要维护复杂的访问历史，因此在资源紧张或对实现确定性要求较低的场景中有一定价值。
6.1.2 与其他策略对比
与 LRU、LFU 相比，纯随机通常命中率较低，但代价是实现简单、行为不易被工作负载“定向击穿”。在某些高度噪声化的访问环境下，随机反而可能具有更平稳的表现。
6.2 随机采样淘汰（Random Sampling）
随机采样并非在全体项上随机，而是先从若干候选中挑选再做比较，从而在保持低成本的同时提升决策质量。
6.2.1 从若干候选中选择
典型流程是：从缓存中随机抽取 k 个候选，然后按某个简单准则（如最久未用、最低频次、最低评分）选择其中一个淘汰。k 的大小决定了近似精度与额外成本。
6.2.2 采样规模与效果关系
k 越大，选择越接近理想策略，但需要更多元数据读取与候选比较。工程上常用经验或基准测试来确定一个“足够好”的采样规模。
7 组合策略与自适应
实际系统往往难以找到单一最优策略，因此组合与自适应成为常见方向。它们通过分区决策、动态切换和在线反馈来适应不断变化的工作负载。
7.1 多队列策略（例如分层冷热）
多队列策略把缓存划分为多个队列，各队列采用不同淘汰规则。常见形式是冷热分离：热区保留更稳健，冷区回收更主动。
7.1.1 热区/冷区划分
热区的判定可以基于访问频率或最近访问；冷区则为尚未被证实的对象或历史访问较少的条目。分区的核心目的是减少“新对象用满缓存热度空间”的风险，同时防止冷对象长期占用宝贵容量。
7.1.2 队列间迁移规则
条目在队列间移动时，需要定义晋升与降级规则，例如达到访问阈值进入热区，长期未命中则降级。迁移规则既影响命中率，也影响抖动与元数据成本。
7.2 自适应选择策略（策略切换）
自适应策略会根据在线观测动态调整淘汰逻辑。例如当扫描行为增多时，从基于近期的策略切换到更稳健的方案。
7.2.1 负载识别与在线调整
负载识别可能基于命中率趋势、访问方差、队列长度、脏页比例或尾部延迟变化。然后触发策略切换或参数调整，例如改变衰减速度、分段比例或采样规模。
7.2.2 监控指标与回滚机制
切换带来的风险在于短期观测误差。为此系统常引入回滚机制：当新策略导致指标恶化超阈值，则回到先前配置，避免策略“越切越糟”。
7.3 轻量级在线学习思路
轻量级在线学习强调在低成本下逐步改进决策，而不是引入重型模型推断。
7.3.1 反馈回路与收敛
反馈回路通常以“淘汰导致的后续命中变化”为信号，逐步调整评分权重或队列阈值。收敛依赖于访问稳定性与反馈延迟，过于频繁的更新可能引入额外波动。
7.3.2 安全边界与异常保护
在线方法需要安全边界，例如限制权重变化幅度、设定最低命中保障或保底策略兜底。这样即便出现异常数据或瞬时尖峰，也能维持可接受的系统行为。
8 实现要点与工程细节
实现层面决定了策略是否可用。即便理论性能很好，如果元数据维护复杂、并发冲突严重或计数精度不足，也可能导致实际收益下降。
8.1 数据结构与复杂度分析
不同策略的复杂度不仅体现在时间复杂度，还体现在常数因子与内存局部性上。
8.1.1 维护开销的来源
开销来源包括：更新访问顺序、维护计数或桶、选择候选项、以及清理过期或迁移队列条目。对于大规模缓存，内存布局与指针追踪会进一步放大成本。
8.1.2 O(1) 目标与近似策略
很多工程实现会追求常数时间更新与淘汰，但当元数据太复杂时会转向近似策略，例如近似计数、抽样比较或简化队列结构，以换取可控的延迟。
8.2 并发与一致性
并发环境下，淘汰决策需要面对同时访问、同时插入与同时回收带来的竞争问题。
8.2.1 锁与无锁实现取舍
锁能保证一致性，但可能阻塞访问路径；无锁或低锁实现减少等待但增加实现复杂度。选择取决于平台特性、访问并发度和性能目标。
8.2.2 多核下的竞争问题
在多核上，热点对象的元数据更新可能成为瓶颈。常用缓解方式包括分片缓存、分区统计、批量更新与减少跨核共享。
8.3 统计计数的精度
计数精度影响策略判断的可靠性。近似计数能降低开销，但也会引入误差与偏差。
8.3.1 近似计数与误差控制
例如分桶计数或衰减计数会造成离散化误差。系统需控制误差范围，避免低频对象被误当成高频，从而持续占用缓存空间。
8.3.2 采样偏差与校准
随机采样可能产生偏差，特别是在小样本 k 较小的情况下。校准可以通过调参或周期性重估来缓解，保证整体判断不过度偏向局部噪声。
8.4 过期（TTL）与淘汰的关系
TTL 使缓存项按时间失效，形成“到期即清理”的机制；淘汰则是“容量满了就清理”。两者常需要协同，否则可能出现重复清理或资源争用。
8.4.1 主动过期与被动淘汰
主动过期由定时器或批处理触发清理，到期条目不必占用缓存太久；被动淘汰则在需要插入时才移除。二者组合决定了空间回收速度与元数据复杂度。
8.4.2 清理节奏与批处理
频繁清理可能造成额外开销，因此常用批处理或分片清理节奏控制清理成本。选择合适的节奏可减少尾延迟并保持吞吐。
9 应用场景
缓存淘汰策略在不同系统中面临不同约束：数据回填成本、并发访问模式、以及一致性需求均不同，因此策略的选择与参数也会随场景变化。
9.1 Web 缓存与反向代理
反向代理缓存对象可能是静态内容或计算结果片段。热点 URL 的稳定性、访问模式的突发性都会影响淘汰策略的有效性。
9.1.1 对“热点URL”的影响
当访问呈现集中化热点时，基于近期或基于频率的策略通常能保住热点，从而提升命中率；但若热点短期漂移，LRU 可能受到扫描或抖动影响，需要结合衰减或分层策略缓解。
9.1.2 请求模式导致的失效
例如爬虫或顺序遍历会制造扫描式访问，使近期驱动策略误保留大量“短暂活跃”的对象。此时引入随机采样、分段保护或基于代价的决策可能更合适。
9.2 数据库缓冲池
数据库缓冲池通常管理页或块，并且淘汰与 I/O 成本高度相关。对象被踢出后往往需要磁盘读取或执行复杂重建。
9.2.1 页/块淘汰与 I/O 成本
若淘汰导致频繁磁盘读取，会显著增加延迟。策略往往需要考虑读 I/O 与写回 I/O 的代价差异，并与脏页回收机制联动。
9.2.2 与预取（prefetch）的配合
预取会提前加载可能被访问的数据。淘汰策略若与预取不匹配，可能出现“预取冲掉有效缓存”或“淘汰了预取目标导致浪费”。因此需在淘汰与预取之间做节奏协调。
9.3 操作系统页缓存
操作系统页缓存承受的挑战是内存压力与回写机制的复杂耦合。淘汰决策与页面回写、脏页回收和系统调度有关。
9.3.1 内存压力下的回收
当内存紧张时，系统需要快速回收页面并控制抖动。淘汰策略通常会区分可丢弃页面与必须回写页面，避免回收动作引发过高的 I/O 延迟。
9.3.2 与页面回写机制的协同
回写机制会影响“脏页清理”的成本曲线。策略设计因此常需平衡：一方面回收尽快释放内存，另一方面避免集中回写导致系统卡顿。
9.4 CDN 与边缘缓存
边缘缓存面对跨区域一致性现实限制与热点迁移问题。淘汰策略不仅影响本地命中率，也影响整体带宽与上游压力。
9.4.1 分布式一致性的现实限制
在分布式环境中，强一致往往代价高。缓存项可能基于过期策略或校验机制更新，因此淘汰应配合一致性语义，减少无效请求或不必要的回源。
9.4.2 热点迁移与再平衡
热点在地理和时间上都会迁移。良好的淘汰策略能让边缘节点更快适应新热点，同时避免旧热点长期占用容量，降低再平衡时的流量波动。
10 评估方法与基准
评估淘汰策略需要将工作负载、缓存容量、访问模式与指标采集方式统一起来，避免只在单一数据集上得出结论。
10.1 工作负载建模
工作负载建模用于生成或选择具有代表性的访问序列，以检验策略在不同访问特征下的表现。
10.1.1 Zipf 分布与访问特征
很多缓存分析会用 Zipf 分布描述访问的长尾特性。通过改变参数可观察策略对“集中化程度”的敏感性，从而判断其适用范围。
10.1.2 顺序扫描与循环访问
顺序扫描用于模拟一次性遍历；循环访问用于模拟周期性热点。对比不同模式能揭示 LRU 或 LFU 在扫描与抖动场景下的差异。
10.2 实验设置与可重复性
实验需要保证可重复与可解释，尤其是涉及并发与在线自适应时。
10.2.1 缓存容量、对象分布
容量大小会显著改变淘汰行为；对象大小分布则影响空间占用与回填代价。基准应明确这些设置，以便复现与对比。
10.2.2 指标采集与置信区间
应采集命中率、平均/尾部时延、吞吐、以及元数据开销等指标。使用置信区间或重复试验有助于确认差异是否来自噪声而非策略本身。
10.3 故障与极端条件测试
极端情况会放大策略差异，因此需要测试抖动、尖峰与冷启动等条件。
10.3.1 抖动、尖峰与冷启动
冷启动时缺少历史统计，衰减与频率类策略可能不稳定；尖峰时访问模式突变，会触发队列竞争或集中回收，从而影响系统尾延迟。
10.3.2 元数据耗尽与保护策略
当元数据结构接近资源上限时，策略可能退化甚至失败。测试应包含元数据耗尽情况，并验证保护策略是否能维持可用性与基本性能。
11 常见误区与“梗式”吐槽
缓存淘汰策略的选择常被简化为单点比较。工程经验表明，真正决定效果的往往是业务特征与代价结构，而不是某个名字本身“听起来就很厉害”。
11.1 只看命中率的陷阱
命中率忽视了回填代价、抖动和系统开销，可能导致策略在平均指标上看似不错，却在尾部延迟或 CPU/I/O 成本上造成灾难。
11.2 LRU 并非“永远正确”
LRU 依赖近期性假设，而顺序扫描或热点抖动会削弱该假设。将 LRU 当作通用答案容易踩坑。
11.3 LFU 也会“被频率骗到”
瞬时高频、频率失真与冷启动问题可能让 LFU 错把“短暂热闹”当成“长期价值”。加入衰减与窗口化通常更稳。
11.4 选择策略就像选爱情：合适比流行更重要
不同系统的“合适”来自代价结构与访问模式，而不是某个策略在论文或面板上更常见。
11.4.1 业务特征才是最终裁判
访问分布、对象大小、回源路径、写一致性与一致性开销都会影响最优策略。理解业务链路比套用算法更关键。
11.4.2 别把默认当答案
默认参数或默认策略可能只对典型场景有效。调参、分层与自适应往往能显著提升鲁棒性，而不是盲信“开箱即用”。