缓存淘汰算法

FIFO 先进先出

  • 思想：最先进来的数据，被认为在未来被访问的概率也是最低的，因此，当规定空间用尽且需要放入新数据的时候，会优先淘汰最早进来的数据

  • 优点：公平，逻辑简单，容易实现

  • 缺点：命中率极低

20250809181008

LRU

  • 思想：如果一个数据最近很少被访问到，那么被认为在未来被访问的概率也是最低的，当规定空间用尽且需要放入新数据的时候，会优先淘汰最久未被访问的数据

  • 优点：LRU 可以有效的对访问比较频繁的数据进行保护，也就是针对热点数据的命中率提高有明显的效果。

  • 缺点：对于周期性、偶发性的访问数据，有大概率可能造成缓存污染，也就是置换出去了热点数据，把这些偶发性数据留下了，从而导致 LRU 的数据命中率急剧下降。
    20250809181206

LFU

  • 思想：如果一个数据在一定时间内被访问的次数很低，那么被认为在未来被访问的概率也是最低的，当规定空间用尽且需要放入新数据的时候，会优先淘汰时间段内访问次数最低的数据
  • 优点：LFU 也可以有效的保护缓存，相对场景来讲，比 LRU 有更好的缓存命中率。
  • 缺点：因为 LFU 需要记录数据的访问频率，因此需要额外的空间；当访问模式改变的时候，算法命中率会急剧下降，这也是他最大弊端。
    20250809181427

W-TinyLFU

  • 思想：当一个数据进来的时候，会进行筛选比较，进入 W-LRU 窗口队列，以此应对流量突增，经过淘汰后进入过滤器，通过访问访问频率判决是否进入缓存。如果一个数据最近被访问的次数很低，那么被认为在未来被访问的概率也是最低的，当规定空间用尽的时候，会优先淘汰最近访问次数很低的数据；
  • 优点：使用 Count-Min Sketch 算法存储访问频率，极大的节省空间；定期衰减操作，应对访问模式变化；并且使用 window-lru 机制能够尽可能避免缓存污染的发生，在过滤器内部会进行筛选处理，避免低频数据置换高频数据。
  • 缺点：应用少
    20250809181611