释义：Least recently used，最近最少使用
用途：常用于 redis 的数据淘汰策略，Linux读文件、msyql查询
传统LRU算法的缺陷
1、预读失效导致缓存命中率下降
2、缓存污染导致缓存命中率下降
什么是预读
就是多读取数据，目的为了减少了 磁盘 I/O 次数，提高系统磁盘 I/O 吞吐
Linux 操作系统为基于 Page Cache 的读缓存机制提供预读机制，举个例子：
- 应用程序只想读取磁盘上文件 A 的 offset 为 0-3KB 范围内的数据，由于磁盘的基本读写单位为 block（4KB），于是操作系统至少会读 0-4KB 的内容，这恰好可以在一个 page 中装下。
- 但是操作系统出于空间局部性原理（靠近当前被访问数据的数据，在未来很大概率会被访问到），会选择将磁盘块 offset[4KB,8KB]、[8KB,12KB] 以及 [12KB,16KB] 都加载到内存，于是额外在内存中申请了 3 个 page；
预读失效
基于预读，多读取的数据没被使用，即为预读失效
如何避免预读失效（即解决缺陷1）
参考 Linux 和 mysql 的做法，这两个的方案，那肯定是当下最牛逼的
Linux 实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list），预读的都放在非活跃 LRU 链表，被使用在加载到 活跃链表的头部
mysql 在 LRU 链表上划分来 2 个区域，young 区域 和 old 区域，预读的页只需要加入到 old 区域的头部，当页被真正访问的时候，才将页插入 young 区域的头部
缓存污染
批量读取数据的时候，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」里，然后之前缓存在活跃 LRU 链表（或者 young 区域）里的热点数据全部都被淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区域）就被污染了。
人话：常用的数据都不在缓存里了，缓存里现在全是垃圾，基本不会再次被访问
如何避免缓存污染（即解决缺陷2）
提高数据进入活跃 LRU 链表（或者 young 区域）的条件
这个我认为就是 LFU 的原理
还是参考 Linux 和 mysql 的做法
Linux：内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。
mysql：内存页被访问第二次的时候，不会马上将该页从 old 区域升级到 young 区域，还要对停留在 old 区域的时间判断：
- 如果第二次的访问时间与第一次访问的时间在 1 秒内（默认值），那么该页就不会被从 old 区域升级到 young 区域；
- 如果第二次的访问时间与第一次访问的时间超过 1 秒，那么该页就会从 old 区域升级到 young 区域；