前言

缓存淘汰算法是指：在无限容量的 list 中，空间被占满后要存入新的 item 时，决定出那个数据应该被剔除剔除的一类算法。
其外围是为了计算出哪个 item 应该被剔除，也就是淘汰机制。

介绍

LRU (Least Recently Used / 最近起码应用)

淘汰最久没有用过的元素。

根本思维

如果数据过来被拜访屡次，那么未来被拜访的频率也更高。

存在的问题

偶发性的、周期性的批量查问操作（蕴含冷数据）会淘汰掉大量的热点数据，导致 LRU 命中率急剧下降，缓存净化状况比较严重。

LFU (Least Frequently Used / 最不常常应用)

淘汰拜访频率最低的元素。

留神 LFU 和 LRU 的区别，LRU 的淘汰规定是基于拜访工夫，而 LFU 是基于拜访次数。

根本思维

如果数据最近被拜访过，那么未来被拜访的几率也更高。

存在的问题：

1. 最近退出的数据总是易于被剔除（缓存末端抖动），因为他起始的频率很低。它无奈对一个领有最后高访问率之后长时间没有被拜访的条目缓存负责。
2. 为了防止晚期的热点数据始终占据缓存，即 LFU 算法也需有一些拜访工夫模式的个性。
   然而，如果频率的工夫度量是 1 小时（数据依据最近一小时内的拜访次数排序），则均匀每小时拜访 1000 次的数据可能会比前一个小时内拜访次数为 1001 的数据更优先剔除掉。

个别状况下，LFU 效率要优于 LRU，且可能防止周期性或者偶发性的操作导致缓存命中率降落的问题，但 LFU 须要记录数据的历史拜访记录，一旦数据拜访模式扭转，LFU 须要更长时间来实用新的拜访模式，即 LFU 存在历史数据影响未来数据的 缓存净化 问题。
LFU 应用计数器来记录条目被拜访的频率，通过应用 LFU 缓存算法，最低拜访次数的条目首先被移除，此办法并不常常应用，因为它无奈对一个领有最后高访问率之后长时间没有被拜访的条目缓存负责。

总结

因为两种算法的各自特点及毛病，所以在行业生产线上通常会联结两者应用。
咱们能够在 LRU 的实现根底上稍作衍生，能够采纳队列分级的思维。
例如 Oracle 利用两个队列保护拜访的数据元素，按被拜访的频率的维度把元素别离搁在热端与冷端队列；而在同一个队列内，最初拜访工夫越久的元素会越被排在队列尾，实现细节参考 详解 Oracle 数据库 LRU 算法：LRU 链、脏块与脏 LRU 链。

参考

1. https://www.cnblogs.com/gisor…
2. https://melonshell.github.io/…
3. https://database.51cto.com/ar…